linux 进程调度器（下） -- 调度器演进

1. 引言

通过此前的两篇文章，我们系统介绍了 linux 操作系统中的调度算法与其演进：

linux 操作系统的进程调度（上） -- 进程调度的基本概念

linux 操作系统的进程调度（中） -- 进程调度算法的演进

本文，我们就来介绍 Linux 操作系统实际使用的进程调度器以及它们的演进。

2. O(n) 调度器

在早期的 linux 操作系统中，2.4 版本到 2.6 版本之间，linux 采用了实现起来十分简单的 O(n) 调度器。

O(n) 调度器只有一个全局的任务队列，即使有多个 CPU，它们也同样共享这个全局的队列。每当有进程就绪，就会被添加到队列，一旦进程运行结束，操作系统就会从队列中删除它。

由于每个进程都拥有自己的优先级，所以每当一个 CPU 执行完一个时间片或空闲时，它只需要遍历整个任务队列，找到优先级最高的一个并执行即可，由于这一遍历过程的时间复杂度为 O(n)，所以这个算法实现的调度器就被命名为 O(n) 调度器。

O(n) 调度器将进程标记为两种基本的类型：

1. 实时进程；
2. 非实时进程。

2.1 实时进程的调度

对于实时进程来说，进程必须以高于实时进程的优先级被调用，并且用户不能用 nice 值对这一优先级进行修改。

为了保证实时进程能够得到最高的优先级，操作系统的实现中固定地使用 1000 + 进程的实际优先级来实现对优先级数值的提升，这是一个简单有效的方案。

2.2 非实时进程的调度

对于绝大多数用户进程来说，它们都是非实时进程，因此，非实时进程的调度是操作系统中最为普遍的。

正如上一篇文章中介绍的，调度器会按照进程的类型，即它是 CPU 密集型还是 IO 密集型来为进程分配优先级，同时，为了应对进程类型的动态变化以及防止进程为了提升优先级而进行的作弊，操作系统会周期性地重置所有任务的优先级到最高，然后再进行动态调整。

在此基础上，用户还可以为进程分配 nice 值来对优先级进行一定程度上的调整。

这里提到了“周期”，那么这个周期以及动态调整的优先级是怎么实现的呢？它们的答案是同一个东西 -- 时间片。每当一个尚未分配时间片的进程出现在队列中时，调度器都会为这个进程分配固定数量的时间片。而在执行过程中，剩余时间片越多，说明进程 IO 越多，也就说明这个进程是一个 IO 密集型进程，它的调度优先级也就相应的越高。当进程的时间片使用完毕，重复这一过程，意即开启下一周期即可。

而实际上，非实时进程的调度优先级为：

时间片剩余数量 + 20 - nice

2.3 O(n) 调度器的缺点

显而易见，上述调度算法存在以下问题：

1. 随着时间片的切换，进程会在不同的 CPU 上执行，因此对 CPU 的缓存利用率很低；
2. 由于多个 CPU 共享全局队列，因此，当队列中的进程进行增、删、更新时，需要加锁，这显然会对整体运行效率造成较大的影响；
3. 在队列中，进程无序存放，即使是实时进程也同样混合其中，因此每次寻找下一个执行的进程都需要遍历整个队列，性能较低。

3. O(1) 调度器

在 linux 内核采用 O(n) 调度器的 4 年后，Linux2.6.0 采纳了 Rad Hat 公司设计的 O(1) 调度算法，这是一个基于上一篇文章中介绍的多级反馈队列算法的调度器实现。

3.1 O(1) 调度器的实现

首先，O(1) 调度器最明显的改进是为每个 CPU 都实现了一套队列，并且实现了一套负载均衡算法，每当新的任务到来时，这个负载均衡器会动态决定将进程分配到哪个 CPU 的队列中。

针对每个 CPU，都有两组链表组成两个 hash 表，分别是 active RunQueue 和 expire RunQueue。而每个哈希表中，都通过拉链法维护了 140 个链表，每个槽代表一个优先级，每个链表中的所有任务优先级都相同，因此，调度器可以以 O(1) 时间时间复杂度获取到优先级最高的进程，而为了进一步提升这一过程的执行效率，调度器还通过一个 bitmap 来存储 active 队列各个优先级是否存在任务。

为什么哈希表要拥有 140 个槽呢？因为他们对应了 0~139 这 140 个进程优先级。在 O(1) 调度器中，进程优先级数字越低，实际优先级越高，而 0~99 为实时进程优先级，100~139 为非实时进程优先级。

3.2 O(1) 调度器的执行

当 active 队列中某一个进程完成执行，它就会被移动到队列尾部；当队列全部任务都执行过指定时间片以后，bitmap 该优先级对应的位就会被置为 0，当整个 bitmap 全部被置 0 后，调度器指向 active 队列和 expired 队列的指针就会交换，并且重新对已执行过的进程进行优先级重估，并且添加到全新的 active 队列中，开启新的一轮执行。

3.3 O(1) 执行器的缺点

当然了，O(1) 执行器也存在一些缺点：

1. IO 密集型任务的识别准确率欠佳，尤其是与 O(n) 简单粗暴的实现方式相比，并且随着时间的推移，这类问题暴露的也越来越多，直到到了积重难返的地步；
2. avtive 队列和 expire 队列交换的过程虽然简单快捷，但重新评估优先级仍然存在一定的耗时。

4. CFS 调度器

由于 O(1) 调度器的上述问题，很快在 Linux 2.6.23 版本，就有一款新的调度器 -- CFS 被内核采用，它是由匈牙利程序员 Ingo Molnar 在澳大利亚外科医生 Con Kolivas 提出的楼梯调度算法基础上改进实现的。

这其中还有一个有趣的轶事，作为外科医生的 Con Kolivas 在完成他的楼梯调度算法的设计后，开发实现了一款名为 RSDL 的调度器，意即公平策略调度器（The Rotating Staircase Deadline Schedule），然而，这个调度器被 Linus 无情地拒绝了，这让 Con Kolivas 十分不满，他愤而退出了 Linux 内核开发社区，并且在此后开发了 BFS，意即“脑残调度器”（Brain Fuck Scheduler）来发泄自己的不满。

4.1 调度器分层思想

而事实证明，在公平策略调度器基础上改进设计的 CFS 确实是一款优秀的调度器，它的思想是将调度器进行模块化，从而让操作系统中可以有多种调度器以不同的策略和优先级来执行。

这样一来，CFS 再也不用去关心实时进程了，它只需要专注于普通进程即可，这也就是“让最适合的调度器，去做最适合的事”。

操作系统中，调度器由此分为四层：

1. DL 调度器：采用 sched_deadline 策略；
2. RT 调度器：采用 sched_rr 和 sched_fifo 策略；
3. CFS 调度器：采用 sched_normal 和 sched_batch 策略；
4. IDEL 调度器：采用 sched_idle 策略。

4.2 CFS 调度器的实现

CFS 调度器的思想是“完全公平”，可是显然，不同优先级的进程实际执行的物理时间是不同的，那么，怎么算是公平的呢？

CFS 调度器提出了“虚拟运行时间”的概念：

虚拟运行时间 = 物理运行时间 * nice 值对应的权重 / 优先级对应的权重

这里有一个“权重”的概念，在 CFS 调度器中，维护了一个与普通进程优先级 100~139 一一对应的 40 个权重组成的列表：

const int sched_prio_to_weight[40] = {
	88761,     71755,     56483,     46273,     36291,
	29154,     23254,     18705,     14949,     11916,
	 9548,      7620,      6100,      4904,      3906,
	 3121,      2501,      1991,      1586,      1277,
	 1024,       820,       655,       526,       423,
	  335,       272,       215,       172,       137,
	  110,        87,        70,        56,        45,
	   36,        29,        23,        18,        15,
};

在保证公平，即所有进程虚拟运行时间相同的前提下，通过上述计算，优先级对应的权重值越大，实际的物理运行时间也就越长。

这个算法让物理运行时间在不同优先级的进程中发生不同程度的膨胀，从而实现了虚拟运行时间上的完全公平，这样一来，在系统负载高时，任务可以仍然在保证公平的前提下对其物理执行时间进行伸缩，这是 O(1) 调度器和 O(n) 调度器这类通过分配固定时间片的调度器所不能实现的。

4.3 CFS 调度器的 pick-next 算法

CFS 调度器的执行过程与其选取下一个将要执行的任务的 pick-next 算法所依赖的数据结构息息相关，那就是 -- 红黑树。

红黑树拥有很强的自适应性，我们知道，有序的二叉树都有一个致命的弱点，那就是增、删、更新操作时，需要进行 rebalance，这是一个十分耗时的操作，例如在 AVL 树中，删除节点时，整个树结构的旋转次数都是 O(logN) 量级的，而红黑树则在最坏情况下只需要进行三次旋转，而增加节点时，红黑树则只需要至多进行两次旋转。

同时，红黑树虽然并不保证平衡，但它保证了有序，在 CFS 调度器中，pick-next 的红黑树中，key 是任务已经执行过的虚拟运行时间，这样一来，在公平原则的前提下，调度器只需要每次都选取最左子树的左叶子结点进行执行，也就是每次都去执行已经运行虚拟运行时间最少的进程，这当然就是最公平的。

5. 后记

本文介绍了 linux 操作系统中的调度器和调度算法的演进，这当然是非常大略的介绍，有兴趣还是建议去阅读相关的内核源码，这里包括对操作系统调度器实际使用的辅助性的数据结构的缺省，都是为了提高文章可读性的需要，实际上，在操作系统中仍然有大量的细节，和许多调度器实际遇到的问题的解决值得我们深入地进一步研究