Linux 2.6 Completely Fair Scheduler 内幕
Linux 调度器是一个颇有压力但很有趣的课题。一方面它涉及应用 Linux 的使用模型。尽管 Linux 最初开发为桌面操作系统环境，但现在在服务器、微型嵌入式设备、主机和超级计算机中都能发现它。 无疑，这些领域的调度负载有很大差异。另一方面，它要考虑平台方面的技术进步，包括架构（多处理、对称多线程、非一致内存访问 [NUMA] 和虚拟化）。 另外，这里还要考虑交互性（用户响应能力）和整体公平性之间的平衡。从这些方面很容易看出解决 Linux 中的调度问题有多难。
Linux 调度器简史
早期的 Linux 调度器使用了最低的设计，它显然不关注具有很多处理器的大型架构，更不用说是超线程了。1.2 Linux 调度器使用了环形队列用于可运行的任务管理，使用循环调度策略。 此调度器添加和删除进程效率很高（具有保护结构的锁）。简而言之，该调度器并不复杂但是简单快捷。
Linux 版本 2.2 引入了调度类的概念，允许针对实时任务、非抢占式任务、非实时任务的调度策略。 2.2 调度器还包括对称多处理 (SMP) 支持。
2.4 内核包含了相对简单的调度器，按 O(N) 的时间间隔运行（在调度事件期间它会迭代每个任务）。2.4 调度器将时间分割成 epoch，每个 epoch 中，每个任务允许执行到其时间切片用完。如果某个任务没有使用其所有的时间切片，那么 剩余时间切片的一半将被添加到新时间切片使其在下个 epoch 中可以执行更长时间。 调度器只是迭代任务，应用 goodness 函数（指标）决定下面执行哪个任务。尽管这种方法比较简单，但是却比较低效、缺乏可扩展性而且不适合用在实时系统中。它还缺少利用新硬件架构（比如多核处理器）的能力。
早期的 2.6 调度器，叫做 O(1) 调度器，它旨在解决 2.4 调度器存在的问题 — 该调度器不需要迭代整个任务列表来确定要调度的下一个任务（因此得名 O(1)，这意味着它效率更高，扩展性更好）。O(1) 调度器跟踪运行队列中可运行的任务（实际上，每个优先级水平有两个运行队列 — 一个用于活动任务，一个用于过期任务）， 这意味着要确定接下来执行的任务，调度器只需按优先级将下一个任务从特定活动的运行队列中取出即可）。 O(1) 调度器扩展性更好而且包含交互性，提供了大量启示用于确定任务是受 I/O 限制还是受处理器限制。 但是 O(1) 调度器在内核中很笨拙。需要大量代码计算启示，难以管理并且对于纯粹主义者而言未能体现算法的本质。
 |
|
为了解决 O(1) 调度器面临的问题以及应对其他外部压力， 需要改变某些东西。这种改变来自 Con Kolivas 的内核补丁，其中包括他的 Rotating Staircase Deadline Scheduler (RSDL)， 这包含了他在 staircase 调度器方面的早期工作。这些工作的成果就是一个设计简单的调度器，包含了公平性和界限内延迟。 Kolivas 的调度器吸引了很多人（并且很多人呼吁将其包含在目前的 2.6.21 主流内核中），很显然调度器的变革即将发生。 Ingo Molnar，O(1) 调度器的创造者，然后围绕 Kolivas 的一些思想开发了基于 CFS 的调度器。我们来剖析一下 CFS，从较高的层次上看看它是如何运行的。