Linux 2.6 完全公平调度算法CFS（Completely Fair Scheduler） 分析

转会http://www.ibm.com/developerworks/cn/linux/l-completely-fair-scheduler/index.html?

ca=drs-cn-0125

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。从较高的层次上看看它是怎样执行的。

------------------------------------------------------------------------------------------------------------------------------

CFS 概述

CFS 背后的主要想法是维护为任务提供处理器时间方面的平衡（公平性）。这意味着应给进程分配相当数量的处理器。

分给某个任务的时间失去平衡时（意味着一个或多个任务相对于其它任务而言未被给予相当数量的时间）。应给失去平衡的任务分配时间，让其运行。

要实现平衡，CFS 在叫做虚拟执行时 的地方维持提供给某个任务的时间量。任务的虚拟执行时越小。 意味着任务被同意訪问server的时间越短 — 其对处理器的需求越高。

CFS 还包括睡眠公平概念以便确保那些眼下没有执行的 任务（比如。等待 I/O）在其终于须要时获得相当份额的处理器。

可是与之前的 Linux 调度器不同，它没有将任务维护在执行队列中，CFS 维护了一个以时间为顺序的红黑树（參见图 1）。

 红黑树 是一个树，具有非常多有趣、实用的属性。首先，它是自平衡的，这意味着树上没有路径比不论什么其它路径长两倍以上。

第二，树上的执行按 O(log n) 时间发生（当中 n 是树中节点的数量）。这意味着您能够高速高效地插入或删除任务。

图 1. 红黑树演示样例

任务存储在以时间为顺序的红黑树中（由 sched_entity 对象表示），对处理器需求最多的任务 （最低虚拟执行时）存储在树的左側，处理器需求最少的任务（最高虚拟执行时）存储在树的右側。 为了公平。调度器然后选取红黑树最左端的节点调度为下一个以便保持公平性。

任务通过将其执行时间加入到虚拟执行时， 说明其占用 CPU 的时间，然后假设可执行。再插回到树中。这样，树左側的任务就被给予时间执行了，树的内容从右側迁移到左側以保持公平。

因此，每一个可执行的任务都会追赶其它任务以维持整个可执行任务集合的执行平衡。

------------------------------------------------------------------------------------------------------------------------------

CFS 内部原理

Linux 内的全部任务都由称为 task_struct 的任务结构表示。该结构（以及其它相关内容）完整地描写叙述了任务并包含了任务的当前状态、其堆栈、进程标识、优先级（静态和动态）等等。

您能够在 ./linux/include/linux/sched.h 中找到这些内容以及相关结构。 可是由于不是全部任务都是可执行的。您在 task_struct 中不会发现不论什么与 CFS 相关的字段。 相反，会创建一个名为 sched_entity 的新结构来跟踪调度信息（參见图 2）。

图 2. 任务和红黑树的结构层次

各种结构的关系如 图 2 所看到的。

树的根通过 rb_root 元素通过 cfs_rq 结构（在 ./kernel/sched.c 中）引用。红黑树的叶子不包括信息。可是内部节点代表一个或多个可执行的任务。

红黑树的每一个节点都由 rb_node 表示，它仅仅包括子引用和父对象的颜色。

 rb_node 包括在sched_entity 结构中，该结构包括 rb_node 引用、负载权重以及各种统计数据。最重要的是， sched_entity 包括 vruntime（64 位字段），它表示任务执行的时间量，并作为红黑树的索引。 最后，task_struct 位于顶端，它完整地描写叙述任务并包括 sched_entity 结构。

就 CFS 部分而言，调度函数很easy。 在 ./kernel/sched.c 中。您会看到通用 schedule() 函数，它会先抢占当前执行任务（除非它通过yield() 代码先抢占自己）。注意 CFS 没有真正的时间切片概念用于抢占，由于抢占时间是可变的。

当前执行任务（如今被抢占的任务）通过对 put_prev_task 调用（通过调度类）返回到红黑树。 当 schedule 函数開始确定下一个要调度的任务时，它会调用 pick_next_task函数。此函数也是通用的（在 ./kernel/sched.c 中）。但它会通过调度器类调用 CFS 调度器。 CFS 中的 pick_next_task 函数能够在 ./kernel/sched_fair.c（称为 pick_next_task_fair()）中找到。 此函数仅仅是从红黑树中获取最左端的任务并返回相关 sched_entity。通过此引用，一个简单的 task_of() 调用确定返回的 task_struct 引用。通用调度器最后为此任务提供处理器。

------------------------------------------------------------------------------------------------------------------------------

优先级和 CFS

CFS 不直接使用优先级而是将其用作同意任务运行的时间的衰减系数。

低优先级任务具有更高的衰减系数。而高优先级任务具有较低的衰减系数。

这意味着与高优先级任务相比，低优先级任务同意任务运行的时间消耗得更快。 这是一个绝妙的解决方式，能够避免维护按优先级调度的运行队列。

CFS 组调度

CFS 还有一个有趣的地方是组调度 概念（在 2.6.24 内核中引入）。组调度是还有一种为调度带来公平性的方式，尤其是在处理产生非常多其它任务的任务时。 如果一个产生了非常多任务的server要并行化进入的连接（HTTP server的典型架构）。不是全部任务都会被统一公平对待， CFS 引入了组来处理这样的行为。产生任务的server进程在整个组中（在一个层次结构中）共享它们的虚拟执行时，而单个任务维持其自己独立的虚拟执行时。这样单个任务会收到与组大致同样的调度时间。

您会发现 /proc 接口用于管理进程层次结构，让您对组的形成方式有全然的控制。使用此配置。您能够跨用户、跨进程或其变体分配公平性。

调度类和域

与 CFS 一起引入的是调度类概念（能够回想 图 2）。每一个任务都属于一个调度类，这决定了任务将怎样调度。 调度类定义一个通用函数集（通过 sched_class），函数集定义调度器的行为。

比如，每一个调度器提供一种方式， 增加要调度的任务、调出要执行的下一个任务、提供给调度器等等。

每一个调度器类都在一对一连接的列表中彼此相连，使类能够迭代（比如。 要启用给定处理器的禁用）。一般结构如图 3 所看到的。注意，将任务函数增加队列或脱离队列仅仅需从特定调度结构中增加或移除任务。 函数 pick_next_task 选择要执行的下一个任务（取决于调度类的详细策略）。

图 3. 调度类图形视图

可是不要忘了调度类是任务结构本身的一部分（參见 图 2）。这一点简化了任务的操作，不管其调度类怎样。比如， 下面函数用 ./kernel/sched.c 中的新任务抢占当前执行任务（当中 curr 定义了当前执行任务。 rq 代表 CFS 红黑树而 p 是下一个要调度的任务）：

static inline void check_preempt( struct rq *rq, struct task_struct *p )
{
  rq->curr->sched_class->check_preempt_curr( rq, p );
}

假设此任务正使用公平调度类，则 check_preempt_curr() 将解析为 check_preempt_wakeup()。

您能够在 ./kernel/sched_rt.c, ./kernel/sched_fair.c 和 ./kernel/sched_idle.c 中查看这些关系。

调度类是调度发生变化的还有一个有趣的地方，可是随着调度域的添加。功能也在添加。 这些域同意您出于负载平衡和隔离的目的将一个或多个处理器按层次关系分组。 一个或多个处理器可以共享调度策略（并在其之间保持负载平衡）或实现独立的调度策略从而有益隔离任务。

其它调度器

继续研究调度，您将发现正在开发中的调度器将会突破性能和扩展性的界限。Con Kolivas 没有被他的 Linux 经验羁绊。他开发出了还有一个 Linux 调度器。其缩写为：BFS。

该调度器据说在 NUMA 系统以及移动设备上具有更好的性能。 而且被引入了 Android 操作系统的一款衍生产品中。