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 调度器简史

为了解决 O(1) 调度器面临的问题以及应对其他外部压力， 需要改变某些东西。这种改变来自 Con Kolivas 的内核补丁，其中包括他的 Rotating Staircase Deadline Scheduler (RSDL)， 这包含了他在 staircase 调度器方面的早期工作。这些工作的成果就是一个设计简单的调度器，包含了公平性和界限内延迟。 Kolivas 的调度器吸引了很多人（并且很多人呼吁将其包含在目前的 2.6.21 主流内核中），很显然调度器的变革即将发生。 Ingo Molnar，O(1) 调度器的创造者，然后围绕 Kolivas 的一些思想开发了基于 CFS 的调度器。我们来剖析一下 CFS，从较高的层次上看看它是如何运行的。

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

CFS 概述

CFS 背后的主要想法是维护为任务提供处理器时间方面的平衡（公平性）。这意味着应给进程分配相当数量的处理器。分给某个任务的时间失去平衡时（意味着一个或多个任务相对于其他任务而言未被给予相当数量的时间），应给失去平衡的任务分配时间，让其执行。

要实现平衡，CFS 在叫做虚拟运行时 的地方维持提供给某个任务的时间量。任务的虚拟运行时越小， 意味着任务被允许访问服务器的时间越短 — 其对处理器的需求越高。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 部分而言，调度函数非常简单。 在 ./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 内核中引入）。组调度是另一种为调度带来公平性的方式，尤其是在处理产生很多其他任务的任务时。 假设一个产生了很多任务的服务器要并行化进入的连接（HTTP 服务器的典型架构）。不是所有任务都会被统一公平对待， CFS 引入了组来处理这种行为。产生任务的服务器进程在整个组中（在一个层次结构中）共享它们的虚拟运行时，而单个任务维持其自己独立的虚拟运行时。这样单个任务会收到与组大致相同的调度时间。您会发现 /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 操作系统的一款衍生产品中。