进程调度器--UNIX还是是老大

linux调度器从2.4以前的O(n)发展到2.6.0到2.6.23之前的O(1)，意义是什么，其实就是增加了每cpu运行队列的支持，另外就是优化了pick_next算法，不管哪个调度器，都是基于优先级的分时调度，优先级到底起到了什么作用，难道是确保高优先级的进程首先被选中吗？不，优先级影响的是进程时间片的分配，如果从一个长久的时间段考虑的话，谁先运行谁后运行是无所谓的，不考虑交互判断的话，每个进程从高优先级到低优先级轮流使用cpu，然后最低优先级的最后一个进程使用完cpu后再从新开始，这个意义上，每个进程都是在所有进程的时间片之和的时间片后再次得到调度运行，结果就是不分谁先谁后，于是O(1)的意义中时间复杂度为O(1)对于效率的提高已经意义不大，它对效率的优化仅仅体现在每cpu运行队列的支持上和动态优先级计算以及交互进程判断上，不管哪一种调度器，理论上每个进程都是在所有进程的时间片之和的时间后得到再次调度的机会，于是进程数量越多，进程的响应性越差，其实很简单，不管哪个调度器在效率优先的前提下，必须保证一定的公平，于是必然要有一个系统调度周期的概念，就是调度完所有进程的时间，在O(n)或者O(1)中，这个调度周期就是所有进程的时间片之和，每个进程的时间片长度和其优先级成比例，而且对于一定的优先级其时间片是固定的，结果就是同样都是三个进程分时，如果三个进程的优先级都比较高，那么系统的响应性就会低，反之，如果优先级都比较低，那么响应性就会变高，这是按照理论推理出来的，但是符合事实吗？我们需要的是按比例分时而不是绝对的分配时间片，所谓按照比例分时就是按照进程们的相对的优先级分配时间片而不是绝对优先级分配。在进入UNIX之前先看看linux的调度器发展，其实windows调度器直接受到了unix的影响，就不再多说了，linux调度器显然对于unix来说是个另类，它竟然将pick_next作为一个衡量标准，从而将精力集中到了pick_next算法上，殊不知这个因素是个并无所谓的因素，更多的努力应该放到效率和公平这两件重要的事上而不是冰山的狭小一角，比如pick_next上，从此一来，必须需要复杂的额外机制来支持交互进程，既然给了交互进程特权，那么为了公平同样需要复杂的机制避免饥饿，一切开始变得混乱。如果说linux调度器一开始就走进了死胡同，那么自从cfs调度器成为主调度器以来，linux才开始进入正轨。在cfs之前曾经有两次试验性的调度器，一个是SD楼梯算法，一个是RSDL调度器，都是在O(1)的基础上进行修改的，SD调度器的描述大致如下(摘自《Linux调度器发展简述》)：

楼梯算法(SD)在思路上和O(1)算法有很大不同，它抛弃了动态优先级的概念。而采用了一种完全公平的思路。前任算法的主要复杂性来自动态优先级的计算，调度器根据平均睡眠时间和一些很难理解的经验公式来修正进程的优先级以及区分交互式进程。这样的代码很难阅读和维护。楼梯算法思路简单，但是实验证明它对应交互式进程的响应比其前任更好，而且极大地简化了代码。和O(1)算法一样，楼梯算法也同样为每一个优先级维护一个进程列表，并将这些列表组织在active数组中。当选取下一个被调度进程时，SD算法也同样从active数组中直接读取。与 O(1)算法不同在于，当进程用完了自己的时间片后，并不是被移到expire数组中。而是被加入active数组的低一优先级列表中，即将其降低一个级别。不过请注意这里只是将该任务插入低一级优先级任务列表中，任务本身的优先级并没有改变。当时间片再次用完，任务被再次放入更低一级优先级任务队列中。就象一部楼梯，任务每次用完了自己的时间片之后就下一级楼梯。任务下到最低一级楼梯时，如果时间片再次用完，它会回到初始优先级的下一级任务队列中。比如某进程的优先级为1，当它到达最后一级台阶140后，再次用完时间片时将回到优先级为2的任务队列中，即第二级台阶。不过此时分配给该任务的time_slice将变成原来的2倍。比如原来该任务的时间片time_slice为10ms，则现在变成了20ms。基本的原则是，当任务下到楼梯底部时，再次用完时间片就回到上次下楼梯的起点的下一级台阶。并给予该任务相同于其最初分配的时间片。总结如下：

设任务本身优先级为P，当它从第N级台阶开始下楼梯并到达底部后，将回到第N+1级台阶。并且赋予该任务N+1倍的时间片。

以上描述的是普通进程的调度算法，实时进程还是采用原来的调度策略，即FIFO或者Round Robin。楼梯算法能避免进程饥饿现象，高优先级的进程会最终和低优先级的进程竞争，使得低优先级进程最终获得执行机会。对于交互式应用，当进入睡眠状态时，与它同等优先级的其他进程将一步一步地走下楼梯，进入低优先级进程队列。当该交互式进程再次唤醒后，它还留在高处的楼梯台阶上，从而能更快地被调度器选中，加速了响应时间。

在SD之后出现了RSDL调度器，简述如下（摘自《Linux调度器发展简述》）：

RSDL也是由Con Kolivas开发的，它是对SD算法的改进。核心的思想还是“完全公平”。没有复杂的动态优先级调整策略。RSDL重新引入了expire数组。它为每一个优先级都分配了一个 “组时间配额”， 我们将组时间配额标记为Tg；同一优先级的每个进程都拥有同样的"优先级时间配额"本文中用Tp表示，以便于后续描述。当进程用完了自身的Tp时，就下降到下一优先级进程组中。这个过程和SD相同，在RSDL中这个过程叫做minor rotation。请注意Tp不等于进程的时间片，而是小于进程的时间片。在SD算法中，处于楼梯底部的低优先级进程必须等待所有的高优先级进程执行完才能获得CPU。因此低优先级进程的等待时间无法确定。RSDL中，当高优先级进程组用完了它们的Tg(即组时间配额)时，无论该组中是否还有进程Tp尚未用完，所有属于该组的进程都被强制降低到下一优先级进程组中。这样低优先级任务就可以在一个可以预计的未来得到调度。从而改善了调度的公平性。这就是RSDL中Deadline代表的含义。进程用完了自己的时间片time_slice时（下图中T2），将放入expire数组中它初始的优先级队列中(priority 1)。

最终cfs吸取了SD和RSDL的思想，并且勇敢的抛弃了O(1)中的一切，而不是像SD和RSDL一样在其基础上修改，关于cfs调度器的点点滴滴我就不多说了，以前不敢写cfs的文章，后来胆子大了，写了很多，实在太多了，不敢再写了。问题是如果linux一开始就吸取unix的经验的话，可能O(n)和O(1)就不会出现了，很早以前写过一篇《从古老的System V进程调度器说开去》，可以看出，unix调度器中就有了朴素的完全公平的思想，本质上unix中也是选取优先级最高的进程，而每个进程的优先级在1秒的间隔中都会得到调整，unix的调度器保证正在运行的进程的优先级持续增加，而没有运行的等待进程慢速增加，最终挑选优先级数值最小的进程，这其实就是cfs中的vruntime的概念了，只不过unix中没有如此抽象的虚拟时钟的概念，而只是将一切归到优先级这个古来而又朴素的概念上，然后以固定的期限比如1秒来定时权衡调度，也就是每隔一秒进行一次调度，挑选优先级最高的进程：

0.cpu = cpu +1;

1.cpu = cpu/2;

2.priority = (cpu/2) + base level priority;

这以上三个公式解决了一切问题，每次时钟滴答，都会执行公式0，然后每隔1秒都会执行公式1和公式2，执行公式2之后再在全局范围内选择一个优先级数值最小的进程运行。这个调度策略很简单，很容易的可以实现基于组的调度，很灵活，仔细想一下，这难道不是cfs最原始的版本吗？只不过将一个时钟滴答变成了1秒，在最原始的cfs版本中，每个时钟滴答，当前进程都要和整个所有的其它进程比较其虚拟运行时间，然后调度器选择最小的，在system v的调度器中，每隔1秒一次的权衡比较和cfs的2.6.23的原始版本很相似。到了2.6.25的cfs调度器，看起来不再是固定时间的权衡比较了，而是让当前进程运行完它应该运行的时间后，知道产生不公平之后再权衡比较，2.6.28之后将这种思想发挥到了极致，2.6.25之后就引入了固定的调度周期的概念(sysctl_sched_latency_ns)，这样可以从根本上消除进程饥饿，但是可能带来频繁调度，关键看你怎么选取这个调度周期了，如果你的系统的进程数量很多而且交互性不强，那么尽量将调度周期选择大一些，反之，如果你运行桌面系统，那么就将调度周期选择小一些，一切成了可配置的了，追其根本，2.6.25之后的cfs版本是unix固定权衡期限和O(n)以及O(1)的固定运行期限的折中，我们假设2.6.23的cfs版本和unix的调度器策略是一致的。我们既不能让系统死定的每隔一秒权衡比较一次也不能放任不管任凭系统的调度周期为所有进程的时间片之和，咋办呢？那就是配置一个调度周期，保证在此周期内运行为所有的进程，将这一段时间按比例分配给所有的进程。UNIX调度器的思想其实很伟大，它根本上就实现了完全公平的思想，不区分什么交互进程等等复杂的策略，它只是设定了几个与睡眠原因绑定在一起的内核优先级，一旦进程睡眠了，那么它被唤醒时的优先级就根据睡眠原因被提升到相应的级别上了，unix的调度器可能和cfs相比显得不是那么灵活，但是对于服务器来说，不需要那么多复杂的策略，没那么多事儿，性能就会很棒了，服务器如果频繁调度的话，没有人会在乎其响应性提高，但是会有人在乎性能的下降，毕竟切换进程不是免费的午餐。

所以，unix的调度器永远都是最猛的，windiws nt的调度器由于吸取了unix的优良基因，也很不错，至于linux，还在不断地探索中，cfs虽然已经步入了正轨，但还是有很多有待该进。

 本文转自 dog250 51CTO博客，原文链接:http://blog.51cto.com/dog250/1274131