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 另一个有趣的地方是组调度 概念(在 2.6.24 内核中引入)。组调度是另一种为调度带来公平性的方式,尤其是在处理产生很多其他任务的任务时。 假设一个产生了很多任务的服务器要并行化进入的连接(HTTP 服务器的典型架构)。不是所有任务都会被统一公平对待, CFS 引入了组来处理这种行为。产生任务的服务器进程在整个组中(在一个层次结构中)共享它们的虚拟运行时,而单个任务维持其自己独立的虚拟运行时。这样单个任务会收到与组大致相同的调度时间。您会发现 /proc 接口用于管理进程层次结构,让您对组的形成方式有完全的控制。使用此配置,您可以跨用户、跨进程或其变体分配公平性。