一、前言

1.1 叙叙旧

这篇博客是自己在学习高级操作系统时，老师让我们选择一个感兴趣的题目，写一篇技术报告。自己和小组的同学商量了一下，决定选择Linux调度算法的演进。由于整个技术报告有30页，这里选择其中的核心部分进行表述，希望能够让大家了解Linux调度算法有一定的帮助。

1.2 文章摘要

调度算法是操作系统高效公平运行的核心，如何实现高效公平的调度对Linux操作系统至关重要。本文从Linux0.11内核到Linux5.0内核分析调度算法的演进，在演进过程中主要出现了经典的O(n)调度算法、高效复杂的O(1)调度算法、起到重要意义的SD调度算法、高效简单的RSDL调度算法以及沿用至今的CFS调度算法。本文介绍这些调度算法的基本思想，分析其优点与缺点以及在Linux内核中的源码，旨在让读者能够更快的理解Linux调度算法的基本思想和演进过程。

二、Linux调度算法演进史

2.1 调度器的基本介绍

进程是操作系统虚拟出来的概念，用来组织和执行计算机中的任务。但随着进程被赋予越来越多的任务，进程好像有了真实的生命，它从诞生就随着CPU时间执行，直到最终消失。如何在进程间分配有限的计算资源，最终让用户获得最佳的使用体验。内核中安排进程执行顺序的模块称为调度器。

2.2 调度器的复杂度演进

Linux内核最开始的调度算法时间复杂度为O(n),也称O(n)调度算法，系统中运行的的进程越多，花费的时间越大。在最开始的Linux版本中只支持64个进程同时运行，因此时间开销并不高，随着计算机硬件的快速发展，Linux操作系统能够同时运行越来越多的进程，因此时间复杂度成为O(n)调度算法的瓶颈。在2.6.0版本，开源社区提出了时间复杂度为O(1)的调度算法，为了进一步解决调度公平性问题提出了时间复杂度仍然为O(1)的SD调度算法和RSDL调度算法。在SD调度算法和RSDL调度算法的影响下，最终提出了时间复杂度为O(log(n))的CFS调度算法，并不断发展和完善，一直沿用至今。

2.3 调度器的核心开发者

在调度器的不断演进过程中，大量拥有开源精神的程序员参与到Linux调度器的开发中。Linus Torvalds是Linux内核的首要架构师与项目协调者，也是O(n)调度算法的主要开发者，同时也是Git开源项目的主要开发者。Ingo Molnar是匈牙利程序员，在Linux2.6.0引入了O(1)调度器，受雇于Red Hat。Con Kolivas是一名澳洲的职业麻醉师，在闲暇时间自学编程，参与到Linux调度器的开发中，提出了时间复杂度均为O(1)的SD调度算法和RSDL调度算法。Ingo Molnar借鉴SD调度算法和RSDL调度算法的完全公平思想，开发出了沿用至今的CFS调度算法。由于Con Kolivas的调度算法被替换未CFS，让他觉得自己并不被认可，曾一度在Linux开发社区发言说从此不再参与Linux kernel的开发。但是最后被Ingo Molnar邀请加入Linux开源的大家庭，一起完善Linux调度算法。

三、O(n)调度算法

3.1 O(n)调度算法基本思想

全局维护一个runqueue队列，基于runqueue队列中进程的优先级进行调度。在调度的时候，对runqueue队列中所有进程的优先级依次进行比较，选择最高优先级的进程作为下一个被调度的进程。在SMP环境下，没有采用复杂的负载均衡策略，而是依次分配给CPU，O(n)调度算法如下图所示。

每个进程被创建的时候都赋予了一个时间片。时钟中断递减当前运行进程的时间片，当进程的时间片被用完以后，需要等待CPU重新赋予时间片才有机会继续运行。其分配机制是：当所有的RUNNING进程时间片都被用完以后，才对所有进程重新分配时间片。其分配机制既保证了处于阻塞状态的进程时间片不会显著增加，也保证了高优先级的进程时间片不会显著减少。通过这种设计，在一个epoch后可以保证每个进程都有机会得到执行。

实时进程的优先级是静态设定的，而且始终大于普通进程的优先级。因此只有当runqueue队列中没有实时进程的情况下，普通进程才有机会执行。实时进程的调度采用FIFO和RR调度策略，先进先出的调度确保先进入的进程总是可以优先获得调度，轮转调度策略使得相同优先级的实时进程能够轮流获得调度。

普通进程的优先级主要由task_struct结构体中的counter字段决定，counter字段表示该进程当前还可以运行多久，值越大，表示运行的时间越短，则优先级越高。另外进程在创建子进程的时候，子进程的counter值为父进程的counter值一半，保证进程不能通过不断的创建子进程而获得更多的执行机会。

3.2 Linux0.11调度算法源码分析

Linux0.11调度算法的思想非常简单，同时也非常实用。通过简单的遍历所有进程，根据每个进程的counter值来确定下一个应该执行的进程。如果所有进程的counter值都为0，则为所有进程重新分配counter值。在重新分配的时候不考虑进程当前的状态，将已有的counter值除以2再加上其优先级作为新的counter值。这样的分配方式可以保证处于阻塞状态的进程的counter值不会一直增大，导致一旦进入就绪队列就执行它。在Linux0.11版本中并没有实现实时进程和普通进程的区别调度，所有进程都采用相同的调度算法，Linux0.11调度算法核心代码如下图所示。

3.3 O(n)调度算法总结

O(n)调度算法由于其简单有效的核心思想，在Linux最开始的十几年一直使用该调度算法。但是随着硬件技术的不断突破和迭代，该算法的弊端日益突出。

（1）时间复杂度太高
每次调度的时候都需要遍历runqueue队列，随着runqueue队列中的进程数量越来越多，效率也越来越低。

（2）缓存效率低下
在SMP环境下仍然全局维持一个runqueue队列，在调度的时候，进程需要在多个CPU之间来回切换，如果两次分配不在同一个CPU，那么之前的缓存就没有任何作用，降低系统的性能。

（3）自旋锁的瓶颈
多个CPU共享同一个runqueue队列，使得每个CPU在对队列操作的时候都需要对队列进行加锁，这时其他队列需要访问运行队列就需要等待，浪费CPU资源。

（4）负载均衡策略简单
在调度的时候那个CPU空闲就把就绪的进程分配给那个CPU，这样简单的负载均衡策略会导致进程迁移比较频繁，从而多次出现（2）的情况。

（5）不支持内核抢占
内核不能及时响应实时任务，无法满足实时系统的实时性要求，导致应用范围有限。

（6）调度的不公平性
在重新分配时间片的时候，除了参考进程的nice值，进程的剩余时间成为最大的影响因素，因此调度算法更倾向于执行I/O型的进程。

四、O(1)调度算法分析

4.1 O(1)调度算法基本思想

O(1)调度算法为了解决SMP环境下共用一个runqueue中的问题，提出了per-CPU runqueue的思想，每一个CPU维持一个runqueue队列。每个运行队列中拥有active队列和expired队列，active队列中保存时间片未用完的进程，expired队列中保存时间片已经用完的进程。每个active队列和expired队列中又有多个不同优先级的队列。

进程的时间片用完以后，为该进程重新分配时间片后，就从active队列移到expired队列。所有进程的时间片都用完以后，就直接通过指针交换active队列和expired队列即可。

为了实现时间复杂度为O(1)的调度算法，引入了位图的方式进行快速查找。如果该优先级上有进程，则用1表示，如果该优先级上没有进程则用0表示。每次调度的时候，只需要找位图上第一个为1的的bit位置。比如位图上第5位为1，则表示当前runqueue中没有优先级为0，1，2，3，4的进程。这样每次在调度的时候只和优先级的数量有关，和进程的个数没有关系。而在位图上查找第一个为1的位置，通过一条CPU指令就可以完成，O(1)调度算法如下图所示。

在O(1)调度算法中共有140个不同优先级的进程，其中优先级从0到99是实时进程，优先级从100到139是非实时进程。在调度的时候依次从优先级0的队列检查到优先级为139的队列，如果队列上有进程（bit位为1），则执行该优先级上的第一个进程。

4.2 Linux2.6.0调度算法源码分析

Linux2.6.0调度算法中每个CPU都有一个runqueue队列。对于每个runqueue队列的操作仍然采用自旋锁机制来解决互斥使用的问题，runqueue结构体如下图所示。

每个活动队列和过期队列由prio_array结构体数组表示，prio_array结构体数组中包含每个优先级的进程队列，即活动队列和过期队列中各自维持着140个不同优先级的队列，prio_array结构体如下图所示。

在调度过程中，如果发现active中没有进程，则需要交换active队列和expired队列。Linux2.6.0交换active队列和expired队列如下图所示。

在实现调度的时候，首先查找当前CPU对应的runqueue，然后在active队列中的位图中找到第一位不为0的位置，计算得到下一个应该调度的进程描述符，Linux2.6.0调度算法核心代码如下图所示。

4.3 O(1)调度算法总结

O(1)调度算法解决了很多O(n)调度算法中的问题，极大的提高了CPU的利用效率。首先是时间复杂度的问题，通过引入位图和active队列的方式，每次调度的是否不需要遍历整个runqueue，使时间复杂度降低到了O(1)。其次是per-CPU的思想，解决了O(n)调度算法中缓存利用率低的问题，同时将大锁变成小锁，减少了CPU等待时间，进一步提高了CPU的利用效率。另外也支持了内核抢占，使得实时进程可以更有效的执行。

虽然O(1)调度算法解决了很多问题，但是在Linux内核中使用的时间并不长，很快就被其他算法所取代。主要原因如下：

（1）复杂的代码
在Linux2.6.0中，引入了大量的复杂代码，特别是在负载均衡这一块算法非常复杂，导致后来的开发者参与到调度器的开发中非常困难。

（2）调度的公平性
通过O(1)的调度算法，我们可以知道低优先级的进程迟迟无法得到执行。调度器更加偏向于高优先级的进程。

（3）调度器性能
O(1)调度器区分交互式进程和批处理进程的算法与以前虽大有改进，但仍然在很多情况下会失效。有一些著名的程序总能让该调度器性能下降，导致交互式进程反应缓慢。

五、SD调度算法分析

5.1 SD调度算法基本思想

SD调度算法也称楼梯调度算法，其时间复杂度也为O(1)。SD调度算法和O(1)调度算法的思想有很大的不同，它抛弃了动态优先级的概念。而是采用了一种完全公平的思路。O(1)调度算法的主要复杂性来自动态优先级的计算，调度算法根据平均睡眠时间和一些很难理解的经验公式来修正进程的优先级来区分交互式进程，因此引入了大量难以维护的代码。

SD调度算法思路简单，但是实验证明它对应交互式进程的响应比O(1)调度算法更好，而且极大的简化了代码。和O(1)算法一样，楼梯算法也同样为每一个优先级维护一个进程列表，并将这些列表组织在active数组中。当选取下一个被调度进程时，SD算法也同样从active数组中直接读取。与O(1)算法不同在于，当进程用完了自己的时间片后，并不是被移到expire数组中。而是被加入active数组的低一优先级列表中，即将其降低一个级别。不过请注意这里只是将该任务插入低一级优先级任务列表中，任务本身的优先级并没有改变。当时间片再次用完，任务被再次放入更低一级优先级任务队列中。就象一部楼梯，任务每次用完了自己的时间片之后就下一级楼梯。

任务下到最低一级楼梯时，如果时间片再次用完，它会回到初始优先级的下一级任务队列中。比如某进程的优先级为1，当它到达最后一级台阶140后，再次用完时间片时将回到优先级为2的任务队列中，即第二级台阶。不过此时分配给该任务的time_slice将变成原来的2倍。比如原来该任务的时间片time_slice为10ms，则现在变成了20ms。基本的原则是，当任务下到楼梯底部时，再次用完时间片就回到上次下楼梯的起点的下一级台阶。并给予该任务相同于其最初分配的时间片。SD调度算法基本思想如下图所示。

以上描述的是普通进程的调度算法，实时进程还是采用原来的调度策略，即FIFO或者Round Robin。另外SD调度算法能避免进程饥饿现象，高优先级的进程会最终和低优先级的进程竞争，使得低优先级进程最终获得执行机会。

对于交互式应用，当进入睡眠状态时，与它同等优先级的其他进程将一步一步地走下楼梯，进入低优先级进程队列。当该交互式进程再次唤醒后，它还留在高处的楼梯台阶上，从而能更快地被调度器选中，加速了响应时间。

从实现角度看，SD调度算法基本上沿用了O(1)的整体框架，只是删除了O(1)调度器中动态修改优先级的复杂代码；还淘汰了expire数组，从而简化了代码。它最重要的意义在于证明了完全公平这个思想的可行性。

5.2 SD调度算法总结

SD调度算法在历史的长河中存在的时间很短，很多人甚至称呼其为O(1)调度算法的补丁。但是该调度算法在Linux调度算法的演进中却存在至关重要的意义，因为该调度算法证明了完全公平的可行性。其主要特定如下：

（1）数据结构跟O(1)调度差不多，不过少了expired队列。

（2）两种时间片：粗粒度、细粒度。粗粒度由多个细粒度组成，当一个粗粒度时间片被用完，进程就开始降级，一个细粒度用完就进行轮回。这样CPU消耗型的进程在每个优先级上停留的时间都是一样的。而I/O消耗型的进程会在优先级最高的队列上停留比较长的时间，而且不一定会滑落到很低的优先级队列上去。

（3）不会饥饿，代码比O(1)调度简单，最重要的意义在于证明了完全公平的思想的可行性。

（4）相对与O(1)调度的算法框架还是没有多大的变化，每一次调整优先级的过程都是一次进程的切换过程，细粒度的时间片通常比O(1)调度的时间片短很多。这样不可避免地带来了较大的额外开销，使吞吐量下降的问题。这是SD算法不被采用的主要原因。

六、RSDL调度算法分析

6.1 RSDL调度算法基本思想

RSDL调度算法也称为旋转楼梯最终时限调度算法。RSDL调度算法重新引入了expire数组，它为每一个优先级都分配了一个“组时间配额”，我们将组时间配额标记为Tg；同一优先级的每个进程都拥有同样的“优先级时间配额”本文中用Tp表示，以便于后续描述。

当进程用完了自身的Tp时，就下降到下一优先级进程组中。这个过程和SD相同，在RSDL中这个过程叫做minor rotation。请注意Tp不等于进程的时间片，而是小于进程的时间片。进程从priority1的队列中一步一步下到priority140之后回到priority2的队列中，这个过程如下图左边所示，然后从priority 2开始再次一步一步下楼，到底后再次反弹到priority3队列中

在SD算法中，处于楼梯底部的低优先级进程必须等待所有的高优先级进程执行完才能获得CPU。因此低优先级进程的等待时间无法确定。RSDL中，当高优先级进程组用完了它们的Tg(即组时间配额)时，无论该组中是否还有进程Tp尚未用完，所有属于该组的进程都被强制降低到下一优先级进程组中。这样低优先级任务就可以在一个可以预计的未来得到调度，从而改善了调度的公平性。

进程用完了自己的时间片time_slice时，将放入expire数组中它初始的优先级队列中。当active数组为空，或者所有的进程都降低到最低优先级时就会触发major rotation：。Major rotation交换active数组和expire数组，所有进程都恢复到初始状态，再一次从新开始minor rotation的过程。

和SD同样的道理，交互式进程在睡眠时间时，它所有的竞争者都因为minor rotation而降到了低优先级进程队列中。当它重新进入RUNNING状态时，就获得了相对较高的优先级，从而能被迅速响应。

七、CFS调度算法分析

7.1 CFS调度算法基本思想

CFS调度算法中的核心是红黑树，红黑树是一种平衡二叉树。主要具有以下性质。节点是红色或者黑色；根是黑色；所有叶子都是黑色；每个红色节点必须有两个黑色的子节点；从任一节点到其叶子结点的所有简单路径都包含相同数目的黑色结点。红黑树的图例如下图所示。

红黑树在Linux内核中，除了调度算法中使用，也在虚拟内存中使用。在Linux2.6.23中定义的红黑树数据结构如下图所示。

对于红黑树的操作，Linux内核中定义了rb_erase 删除结点、rb_insert_color插入结点、rb_first 寻找中序遍历的第一个结点，即最左边的结点、rb_last 寻找中序遍历的下一个结点、rb_prev寻找中序遍历的上一个结点、rb_next_postorder 寻找后续遍历的下一个结点、rb_first_postorder 寻找后续遍历的第一个结点、rbtree_postorder_for_each_entry_safe 后续遍历红黑树等接口。

在CFS调度算法中，每个进程都有一个虚拟时钟。得到执行的时候虚拟时钟的值就增加，没有得到执行的时候虚拟时钟的值就保持不变。每次调度的时候都选择虚拟时钟值最小的进程执行，因为虚拟时钟值最小，表示获得执行的时间就越短，也就越不公平，在红黑树中通过调用rb_first就可以获得虚拟时钟值最小的结点。CFS调度算法的核心就是通过CPU的调度使得每个进程的虚拟时钟值相互追赶，当实现了所有进程的虚拟时钟值都相等的时候，就实现了完全公平。因此CFS调度算法也称为完全公平调度算法。

接下来通过公式来证明每个进程虚拟时钟的值和进程本身无关。① 进程运行时间 = 调度周期 * 进程权重 / 所有进程的权重之和，其中调度周期表示调度一遍运行队列中国的所有进程所需时间，进程权重表示系统维护一张nice值对应的权重表；② 虚拟时钟的值 = 进程运行时间 * NICE_0_LOAD / 进程权重，其中NICE_0_LOAD 是nice值为0的进程权重，在Linux2.6.23中该值是1024。由①和②可以得出：③ 虚拟时钟的值 = 调度周期 * NICE_0_LOAD / 所有进程的权重之和，其中调度周期的值是固定的，NICE_0_LOAD 是恒定不变的，所有进程的值也是固定的。所有最后的结论是虚拟时钟的值和进程本身无关。CFS调度算法中的进程权重表如下图所示。

7.2 CFS调度算法源码分析

CFS调度算法在开始调度的时候，首先需要禁止内核抢占，然后依次获取当前CPU的编号、当前CPU对应的运行队列runqueue、当前进程的切换次数switch_count以及当前进程的描述符prev。调度算法开始前的参数初始化如下图所示。

通过put_prev_task()将prev进程重新插入到就绪队列合适的位置中。再通过pick_next_task()在当前的就绪队列中挑选下一个应该被执行的进程next。有时候，调度器所选的下一个被执行的进程恰好就是当前进程，那么调度器就不必耗费精力去执行上下文切换，但这种情况不是经常发生的。如果prev和next不是同一个进程，那么先通过sched_info_switch()更新两个进程描述符的相关字段，并且更新可运行队列的相关字段。Linux2.6.23调度算法的核心代码如下图所示。