sched-design-CFS

• 概述

CFS代表Completely Fair Scheduler，是新的桌面设备调度器，由Ingo Molnar实现并在2.6.23版本合入。80%的CFS设计可以概括为一句话：CFS建立一个理想、精确的多任务CPU模型。
理想多任务CPU是指，CPU能够以100%的物理性能精确等速的运行每个任务，任务是并行的，每个任务的运行速度等于1/nr_running。例如，有两个任务，并行情况下每个任务都以50%物理性能运行。
在真实的硬件上，一次只能运行一个任务。所以我们必须介绍“虚拟运行时”的概念。任务的虚拟运行时间指其下一个时间片何时开始。在实践中，任务的虚拟运行时间是将其运行时间根据任务个数进行归一化。

• CFS理念

CFS中的virtual runtime通过per-task的p->se.vruntime(单位ns)来跟踪和表示的。这样，就有可能准确地时间戳，并测量任务应该得到的“预期CPU时间”。在“理想”硬件上，任何时候所有任务的p->se.vruntime值都是一样的。
CFS选择下一个执行任务的逻辑是基于p->se.vruntime值，它总是选择p->se.vruntime值最小的任务。CFS总是试图把CPU时间平均分配给可运行的任务之间。
CFS剩余的设计都来自于这个非常简单的概念，再添加一些附加的功能，如nice levels、多处理器和各种识别睡眠的变种算法。

• 红黑树

CFS的设计非常激进：它没有使用旧的数据结构用于runqueues，但是它使用一个时间顺序的rbtree来构建未来任务执行的“时间线”。
CFS还维护rq->cfs.min_vruntime值，这是一个单调递增值，跟踪runqueue中所有任务中最小的vruntime。使用min_vruntime跟踪系统完成的总工作量；该值用于尽可能地将新激活的实体放在树的左侧。runqueue中正在运行的任务总数通过rq->cfs.load值来计算，rq->cfs.load值是runqueue中排队的任务的权重之和。
CFS维护一个时间顺序的rbtree，其中所有可运行的任务都按p->se.vruntime排序。CFS从这个树中选择“最左边”的任务开始执行。随着系统向前推进，执行的任务越来越多地被放到右边的树中--缓慢但肯定地使每个任务都有机会成为“最左边的任务”，从而在一定时间内获得CPU。
总结起来，CFS是这样工作的：它运行一个任务，当任务调度（或调度器滴答发生）时，任务的CPU占用率就被“记入”了：它刚刚在物理CPU上花费的时间被加到p->se.vruntime。一旦p->se.vruntime足够高，另一个任务就成为rbtree的“最左边的任务”，则选取最左边的新任务，并抢占当前任务。

• CFS的特点

CFS统计单位是ns，不依赖于任何jiffies或者HZ。因此CFS调度器没有时间片的概念，也没有启发式帽子。只有一个*调节器（需要打开CONFIG_SCHED_DEBUG）。
/proc/sys/kernel/sched_min_granularity_ns
CFS调度程序对nice level和SCHED_BATCH的处理比以前的常规调度程序要强得多：这两种工作负载的隔离要严格得多。
SMP负载均衡已经改写/清理：现在负载均衡代码中不再使用runqueue-walking假设，使用调度模块的迭代器。结果，平衡代码变得简单多了。

• CFS策略

CFS实现三种调度策略：
　　SCHED_NORMAL：（传统称为SCHED_OTHER）：常规任务的调度策略。
　　SCHED_BATCH：不像常规任务那样频繁抢占，从而允许任务运行更长的时间，更好地利用缓存，但以交互性为代价。这非常适合批处理作业。
　　SCHED_IDLE：这甚至比nice 19弱，但它不是真正的idle计时器调度程序，为避免陷入优先级倒置问题。

SCHED_FIFO/_RR：在sched/rt.c中实现，由POSIX指定。

• 调度分类Scheduling classes

CFS引入了调度类的概念，这是调度的扩展功能，调度类是通过sched_class结构实现，该结构包含函数的钩子，当事件发生时必须调用这些函数。如下为部分回调函数：
　　enqueue_task(...)：当任务进入运行状态时，它把调度实体加入红黑树中，同时递增nr_running变量。
　　dequeue_task(...)：当任务不再可以运行时，调用此函数使相应调度实体退出红黑树，同时递减nr_running变量。
　　check_preempt_curr（...）：该函数检查进入可运行状态的任务是否应抢占当前正在运行的任务。
　　pick_next_task(...)：此函数选择最适合下次运行的任务。
　　set_curr_task（...）：当任务更改其调度类或更改其任务组时，将调用此函数。
　　任务_tick(...)：这个函数通常从时间标记函数调用，它可能导致进程切换。这会驱动运行抢占。

• 调度器分组

通常，调度器努力为每个任务提供公平的CPU时间。有时，可能需要对任务进行分组，并为每个此类任务组提供公平的CPU时间。例如，可能希望首先向系统上的每个用户提供公平的CPU时间，然后向属于用户的每个任务提供公平的CPU时间。
CONFIG_CGROUP_SCHED致力于实现这一点。它允许将任务分组，并在这些组之间公平地分配CPU时间。
CONFIG_RT_GROUP_SCHED允许对实时任务（即SCHED_FIFO和SCHED_RR）进行分组。
CONFIG_FAIR_GROUP_SCHED允许对CFS（即SCHED_NORMAL和SCHED_BATCH）任务进行分组。
这些选项需要定义CONFIG_CGROUPS，并让管理员使用“cgroup”伪文件系统创建任意任务组。有关此文件系统的详细信息，请参见Documentation/cgroup-v1/cgroups.txt。
当定义CONFIG_FAIR_GROUP_SCHED时，将为使用伪文件系统创建的每个组创建一个“cpu.shares”文件。

参考文档

Linux文档：Documentation/scheduler/