朴素的UNIX之-调度器细节_unix调度算法

0.多进程调度的本质

我们都知道UNIX上有一个著名的nice调用，何谓nice，当然是“好”了，常规的想法是nice值越大越好，实际上，nice值越好，自己的优先级越低，那么为何不用badness呢？

       事实上，如果我们理解了操作系统多进程调度系统是一个“利他”系统，这个问题就不是个问题了。nice当然还是好，不是对自己好，而是对别人好。利他系统是一个人人为我我为人人的系统，类似还有TCP流量控制和拥塞控制，人类的宗教社会组织等等，利他系统都有一个负反馈机制，让波动保持在一个同样的范围内，你少了，大家每人给你捐一点点，积少成多，没人可以一次性帮到你，因为没人可以大量结余。反之，“因为凡是有的，还要给他，他就充足有余；凡是没有的，就连他有什么也要拿去。”则是一个自私的系统了，比如UDP或者实时进程，或者没有信仰的某国人...

1.UNIXv6的利他性体现

在UNIX中，进程的用户态优先级由一个公式表述(数值越小，优先级越高)：

prio = USER + p_cpu/4 + 2*nice

解释一下其中的字段：

USER：是用户态的基准优先级，这是为了保证但凡生活在用户态的进程的优先级都高于USER，因为处在内核态的优先级都要小于USER，保证机要机构快速出入。

p_cpu：进程的CPU占用时间。 值得注意的是，在4.3BSD以后的BSD中，这个字段并不是线性增加的，即不是每来一个时钟中断就会递增1，而是按照“越接近现在越重要，历史越久远越不重要”的原则衰减的，衰减因子为：
(2*load)/(2*load+1).可见，越是离现在久远的CPU占用，越对总的CPU占用时间具有小的影响。为什么要强调p_cpu呢？因为在利他系统中，你占用CPU的时间越久，就越不符合利他行为的特征，随着p_cpu的积累，prio会逐渐增加，造成优先级降低，进而让出CPU，最终的行为还是利他的。那么为何要有一个衰减指数呢？在利他系统中，长期占用CPU是一个“错误”的行为，但是如果知错能改，也可以既往不咎，很久以前的CPU占用仅仅起到参考作用即可，没有决定性作用。利他系统中，目的不在惩罚。

       在p_cpu的衰减因子中，有一个load，它指的是系统的总负载，也就是总进程数，你会发现，负载越大，因子越小，由于因子小于1，所以因子越小，p_cpu增加的速度越快，进程优先级的降低越快，每个进程的调度周期越短，保证所有进程的调度周期保持在一个大致相同的范围内，每一个进程都不会过度饥饿。

nice：利他行为的直接体现，nice越大优先级越低。

我们总体看一下这个prio的计算公式。如果nice是负值，说明这个进程不是那么“利他”，因为它的nice值并不是那么的NICE！那么此时p_cpu就起到牵制它的作用了，如果nice的值是一个正值，并且很大，则说明它在利他系统中非常NICE！此时p_cpu的意义就不大了，因此p_cpu的作用要除以4来造成“忽略最小项”的效果，我们再看nice是负值的情况p_cpu除以4的意义，在那种情况下，nice的值造成进程持续占据CPU，即便p_cpu的值除以4，它也是一个不小的值。最后，注意，即便在利他系统中，也不是人人平等的，这就是nice值限制在一个范围内而不是一个固定值的原因，有些进程比较重要，它的nice值理所当然的低，没说的。举个例子，即便在宗教系统，也分教皇，主教...

       理解了朴素的UNIX调度机制后，我们会发现它是如何得朴素和优美，每一个进程的优先级上下波动，随时抢占(包括时钟中断发现了更高优先级的进程以及唤醒后的低内核优先级抢占，注意后者本文没有介绍，请参考UNIXv6或者《Windows Internals》)，p_cpu衰减因子的计算保证即便系统负载很大，进程也不会过度饥饿，负载的增加对进程造成的影响仅仅是每个进程每次运行的时间减少了，因为切换密集了，这个策略十分适用于桌面交互式应用。

       我给出一幅图，整体描述一下UNIXv6的调度：

2.调度算法问题

注意，在以上的描述中，我并没有描述系统怎么检索出优先级最高的进程，以及如何来维护所有的进程，是保存在数组，还是链表，或者其它数据结构，比如AVL树，红黑树...这是实现问题，并不是本质问题，第一个版本的实现一般都是数组或者链表实现的，为的是简单，尽快出一个可以运行的版本，再往后会迁移到更加高效的数据结构上，比如红黑树，这是优化问题。

       如果你读过Linux的0.11版本内核代码一直到2.4内核的代码，你会发现系统在检索优先级最高的进程时使用的都是链表遍历，这被称为O(n)算法，旨在表达这种算法的时间复杂度和系统负载成正比，人们一般仅仅关注算法实现问题，网上遍布着大量的O(n)，O(1)算法的文章，但是几乎没有描述优先级计算的文章，而后者要比前者更重要。我们知道，Linux 2.6.0到2.6.23以及Windows NT的调度器实现都是O(1)的，可以说是几乎一样，它们都为每一个优先级维护了一个链表，每个CPU有一个位图，指示哪个优先级有进程/线程就绪，所不同的是Windows NT依赖动态优先级提升以及基本优先级回落而仅仅维护一个链表组，而Linux的O(1)则是维护了两个链表组，因为在Linux中优先级提升只是一个辅助的优化。这又有什么意义呢？

       我想说一句，在2008年，我实现了一个调度器，当时是在2.6.18内核上，当时还没有CFS(也许有了，但是我没有查到什么资料)。我们当时的需求是实时音视频传输，但允许丢帧，并且系统行为不随着系统负载的变化而变化。我当时的设计是将进程执行的平均时间片设置成一个常量T，然后计算：

Tt = nr_task * T

将Tt划分为nf_task个片段，每一个片段长度为：

Ttn = Tt*(Wn/Wt)

其中，Wn为进程n的权重，而Wt为总权重，关于权重，我只是简单按照nice进行归一化，保证总的所有的nice'即weight值的和为1。以上就是一个简单的设计，你是不是觉得和CFS狠像呢？我也觉得！但是在实现上，我却使用了链表而不是红黑树，因为链表简单。后来想用堆实现，也作罢了。链表遍历不是啥大不了的事儿！后来我看CFS，发现其中的以下代码来表示所有进程调度一遍的周期：

if (unlikely(nr_running > 5)) {
        period = sysctl_sched_min_granularity;
        period *= nr_running;
}

觉得CFS和我2008年的那个调度器实现犯了同一个错误，那就是如果nr_running非常之大，就会导致调度一遍的时间非常长久，按照BSD4.3 UNIX的思想，应该阻止增加全部进程调度一遍的时间才对！好吧，那我能限制period的最大值吗？可以！但是如果优先级公式本身保证了这一点，岂不是更加完美吗？

3.时间片调度

多数现代操作系统的调度都是基于时间片的，所不同的是时间片和进程优先级的关系。对于Linux的O(n)以及O(1)调度器来讲，时间片都是优先级的函数，时间片的另一个计算因子就是进程执行的特性，总体加起来计算一个动态优先级。对于Windows NT而言，所有线程的时间片是固定的，优先级包括线程的基本优先级数值以及动态调整的数值，不同优先级线程的每次执行时间都是一致的，所不同的是高优先级线程总是可以抢占低优先级线程从而先执行。这是和UNIXv6进程调度的本质区别，再次重申，UNIXv6的调度不是基于时间片的，进程根本就没有时间片。

       时间片调度的好处在于时间片是预先分配的，减少了每次计算全部进程的动态优先级的开销，增加了系统吞吐能力，但是传统的时间片计算方式有一个缺点，那就是容易造成进程/线程饥饿，虽然WIndows NT采用了固定时间片来避免某优先级线程时间片过长，但是它不得不靠外部的平衡器来适时地发现饥饿线程并动态调整其到高优先级队列。UNIXv6的进程调度(其实说的是后来的BSD4.3+)完全没有这个问题：

a.依靠一个单一的公式来适应系统的负载，动态平滑调整优先级；

b.分离内核态运行优先级，提高I/O完成后的响应速度。

3.1.可变时间片调度

Linux 2.6.23之前采用的是可变时间片调度。它将时间片描述为一个静态优先级的函数，对于固定的nice值，其时间片是固定的，即每一个nice值对应一个时间片，然后依照先运行高优先级进程的策略来调度运行队列的进程，这会带来两个问题：

1.如果大量进程处在相同的高优先级，将会造成它们之间轮转运行，造成低于它们的所有优先级的进程持续饥饿；

2.I/O后的快速响应问题。

我们看一下Linux 2.6.23之前是怎么解决这些问题的。这可以分类两种方案，对于O(n)算法而言，系统严格执行完预分配给进程的时间片并且只执行1次，然后将其时间片设置为0，接下来当所有的进程时间片均为0的时候，一次性重新设置所有进程的时间片，由于每个进程只运行1次自己的时间片，那么即便它拥有再高的优先级，也总有用完的那一刻，这就避免了进程永远饥饿，对于I/O完成的快速响应问题，O(n)并没有很好的解决！注意，O(n)调度器是不可抢占的，即进程在时间片用完之前，不可抢占。

       对于O(1)算法，类似的也是进程运行完分配给自己的时间片并且只运行1次，然后重置其时间片并将其放在一个过期队列中，等所有的进程都在过期数组中了，切换过期数组而活动数组。我们可以看见，实际上O(1)调度器和O(n)调度器在本质上都是一致的，没有什么除了实现方式之外的其它区别。唯一的区别在于O(1)实现了抢占，复杂到死人的动态优先级的调整，“时间片再分片”以及饥饿避免机制：

内核抢占：刑可上大夫。只要没有占用机要机构，不管是内核态还是用户态的进程，也不管时间片有没有用尽，均可以被抢占。这实际上是减小了内核保护的粒度。

动态优先级调整：根据进程的睡眠时间和实际占用CPU时间的比率来调整优先级，原则在于，睡眠越久的进程给与的补偿越高，这也是一个利他性补偿；

时间片再分片：在特殊的交互环境下，将一个超级长的计算型进程的时间片再次分片，分成很小的slice，为其它进程提供执行机会；

饥饿避免：由于引入了上述的机制，难免由于优先级提升导致的高优先级进程们持续占有CPU，因此引入了饥饿避免机制。这实际上类似Windows NT的平衡器。但是不同的是，WIndows NT中，优先级调整和抢占是主线，而在Linux中，它们则是辅助功能。

附：比较Linux的O(n)调度器和O(1)调度器

不管是哪一个，都有2个效果，那就是，其一，高优先级的进程首先运行，其二，高优先级进程每次执行的时间片长。这就造成了高优先级进程在系统中占有绝对的优势，调度行为严格依照调度器而不是别的额外机制。

       有没有想过，O(1)的效果并没有想象的那么比O(n)好！O(1)仅仅对于交互式应用更加合理，对于吞吐优先的服务器而言，甚至不如O(n)，特别是内核抢占功能，在编译内核的时候，你会看到，如果你编译的是服务器而不是桌面版本，建议是关闭内核抢占。因为总时间是一定的，切换时间占用多了，执行任务时间就少了，另外，对于服务器而言，一般都倾向于一次性完成任务，最大化缓存的利用率，切换会导致缓存刷新，TLB刷新。

       个人感觉，O(1)并没有较O(n)提高多少性能，可能沾光的仅仅是Ubuntu，Suse之类的桌面系统吧。

3.2.固定时间片调度

Windows NT采用的是固定时间片调度，不管是高优先级还是低优先级线程，每次均运行一个固定的时间片，每次调度器选择最高优先级队列的第一个线程来运行，其思想非常简单。但是如果仅仅如此，饥饿是不可避免的，因为它不像Linux的O(n)那样限制每一轮每个进程只运行1次，也不像Linux的O(1)那样维护一个过期队列。那么Windows NT是怎么解决这类问题的呢？首先看一个图吧：



Windows NT调度器的关键在于动态优先级的调整，因此整体上看，你会看到任何线程都是在不同时刻在不同的优先级队列里面蹦来跳去的，对于睡眠的线程，Windows NT几乎完全继承了UNIXv6的睡眠唤醒优先级的思想。

       由于WinNT的调度器并没有规定“调度一轮”的概念，因此也就没有规定每个线程运行几个时间片，所以它的时间片是固定的，毕竟一个高优先级的线程可能会连续运行好几个时间片，只要期间没有更高优先级的线程就绪。可以抢占高优先级线程的办法就是依赖系统将一个低优先级线程提升到一个高优先级队列，提升优先级的原因有好多：调度器事件提升，睡眠唤醒后提升；等锁控锁后提升，I/O完成提升(延续自UNIXv6)，等待执行体资源后提升，交互式前台窗口线程提升，长期饥饿提升。以上每一种优先级提升机制都有复杂的实现，且优先级的提升数值也不同，这说明，WinNT的调度器主线就是优先级调整，每一个线程都有一个固定的基本优先级，它的作用在于线程优先级的回归。

WinNT的O(1)调度器评价

个人认为这个调度器在现代操作系统的观点看来是比较优秀的，但是还是不如Linux的CFS调度器。WInNT调度器的精巧在于其依赖的外部因素特别少，非常类似UNIXv6，美中不足就是平衡器。对于服务器版本和家庭版本，WInNT定义的时间片是不同的，服务器追求高吞吐，要避免频繁切换，因此时间片就会更长，而家用版本追求高响应性，因此时间片就会更短，这也符合UNIXv6的调度器设计思想。

       WinNT调度器并没有体现利他系统应有的行为，而是完全依赖外部诸如优先级提升原因以及平衡器的操作，这就意味着它不是一个自洽的调度系统，只有在WinNT这个环境下才能发挥其作用。

       我在2008年设计自己(其实是为公司)的08调度器(姑且这个命名)的初衷在于O(1)调度器无法满足实时性需求，特别是在负载很大的时候。时间片是固定的，进程数量越多，调度完一轮的时间就越久，这是Linux的“按轮”调度思想最大弊端，WinNT调度器就没有这样的问题，因为随便一个线程的优先级在任意时刻都可以由于任意原因而得到任意的提升，最后收摊的就是平衡器，它能保证线程不会持续4秒以上的饥饿。但是Linux的“按轮调度”完全做不到这一点，因此我实现了自己的08调度器。

4.CFS调度

但是我自己的08调度器也没有解决所有问题，原因在于我中了毒，什么毒？“按轮”调度的毒！我思想里面总是有一个Linux的传统观念，那就是所有的进程必须一轮一轮地被调度，每一轮中一个进程只能被调度一次！事实上，这种思想没有什么不好，相反它是避免混乱迎战复杂的最佳方式，关键是你怎么理解它，怎么实现它。

       Linux在2.6.23以后，采用了CFS调度算法。先说一句，它也是“按轮”调度器的实现。

4.1.总览

CFS？怎么说呢？完全公平！怎么体现啊？先看一张图：



我们应该转换一种思维，将思路切换到虚拟时钟上，对于虚拟时钟而言，每一个进程每次运行相等的时间片，系统总是选择虚拟时钟最小的进程运行，效果就是所有进程的虚拟时钟以相同的步进速度你追我赶，这就是平等的体现！每一轮的调度周期中，每一个进程都能得到运行机会，运行多久呢？统一都运行N个虚拟时钟周期！但是怎么对应到真实的时钟呢？答案是按权重来解释这N个虚拟时钟周期！每一个虚拟时钟周期的真实时钟周期是：

Tr = T*(Wn/Wbase)

其中，T为时钟嘀嗒间隔，Wn为当前进程的权重，Wbase为参照权重，即nice为0的进程的权重，可以看出，进程权重越大，对应的真实时间越久。那么在任意一个周期T内，一个进程应该运行多少时间呢？很简单，答案是
T*(Wn/Wt)其中Wt为队列的所有进程的权重总和。

       这十分类似我的08调度器！但是比我的精致。难道原因在于它使用了红黑树？...

       在Linux 2.6.23到2.6.25之间，Linux CFS的实现比较朴素，它为每一个队列维护了一个fair_clock变量跟踪虚拟时钟的步进，每一个task都有一个key，其值为该task当前的虚拟时钟的值，为了保证公平，调度器总是选择虚拟时钟最小的task运行。这些task存储在红黑树中，当然也能存在堆中，甚至链表中。到了2.6.25内核，CFS实现更直接了，抛弃了队列虚拟时钟的跟踪，而是直接应用T*(Wn/Wt)时间来决定进程n是否在本轮调度已经到期。

       不管怎样，这个CFS调度器还是有一些问题，那就是总的一轮所有进程调度的时间没有被限制，还是会造成饥饿，但是红黑树的插入算法会导致task总是会从右到左移动，虽然会等很久，但饥饿问题并不是持续的(即使用链表也是这样，这是虚拟时钟随风奔跑决定的，不是算法决定的！)，这也是按轮调度的优势吧！

       Linux CFS调度器在UNIXv6的平滑调度的基础上实现了“按轮”调度，实则一朵奇葩。

4.2.睡眠/唤醒

以上描述的CFS调度器是朴素的，没有涉及优先级的提升问题。比如大家都在用的I/O完成后的优先级提升等。实际上CFS并不关注这些，它只要保证睡眠唤醒后的进程得到比较小的虚拟时钟即可。它并不动态改变进程的权重，而是根据其权重计算其虚拟时钟减少多少，CFS总是选择虚拟时钟最小的进程投入运行，如此一来，睡眠唤醒的进程就会率先得到执行机会，得到多少额外的机会就看它的权重了。

       我已经无力关注CFS的细节，细节都是实现问题，如果你理解了原理，细节难道不可以自己实现吗？

5.朴素的UNIX调度器

UNIXv6的调度器是朴素的，超级朴素。可以看到，不管是Linux还是WinNT，都无法超越UNIXv6(事实上是BSD4.3+)调度器，它们均采用了各种小技巧，小手段以及额外的诸如平衡器之类的东西。

       最后我想说一下内核抢占。起初的UNIX系统为了保护内核数据而不允许内核抢占，鉴于这只是一种类似锁一样的保护策略，它并不是长久的，最终的内核抢占被几乎所有的现代操作系统实现了，不管是WinNT还是Linux还是现代的UNIX变种。起初，UNIX在实现内核抢占的时候，只是定义了一些内核可抢占的点，即那些没有占有任何可能导致互斥问题的机要机构的点。但是有一种反其道而行之的思想，即，与其说在不可抢占的内核中定义一些可以抢占的点，不如说在可抢占内核中定义一些不可抢占的点，且后者实现起来更容易。不管是WinNT还是Linux，还是Solaris，都是这么实现的。

       觉得UNIXv6过时的XX们，你们懂CFS吗？你们受过排队之苦吗？朴素的东西永远都不过时，只是你不懂而已...