CFS 调度器¶
1. 概述¶
CFS 代表 “完全公平调度器”，是由 Ingo Molnar 实现并在 Linux 2.6.23 中合并的 “桌面” 进程调度器。最初合并时，它是先前 vanilla 调度器的 SCHED_OTHER 交互代码的替代品。如今，CFS 正在为 EEVDF 让路，相关文档可以在 EEVDF 调度器 中找到。
CFS 80% 的设计可以用一句话概括：CFS 基本上在真实的硬件上模拟了一个“理想的、精确的多任务 CPU”。
“理想的多任务 CPU” 是一个（不存在的 :-）CPU，它拥有 100% 的物理能力，并且可以以精确相等的速度并行运行每个任务，每个任务的速度为 1/nr_running。例如：如果有 2 个任务正在运行，那么它将以 50% 的物理能力运行每个任务，即实际上是并行运行。
在真实的硬件上，我们一次只能运行一个任务，因此我们必须引入 “虚拟运行时” 的概念。任务的虚拟运行时指定了它在上述理想多任务 CPU 上下一次时间片开始执行的时间。实际上，任务的虚拟运行时是其相对于正在运行的任务总数而标准化的实际运行时。
2. 一些实现细节¶
在 CFS 中，虚拟运行时通过每个任务的 p->se.vruntime (纳秒单位) 值来表达和跟踪。这样，就可以精确地为任务打上时间戳并测量任务应该获得的 “预期 CPU 时间”。
一个小细节：在 “理想” 硬件上，任何时候所有任务都具有相同的 p->se.vruntime 值，即任务将同时执行，并且没有任务会从 “理想” 的 CPU 时间份额中 “失衡”。
CFS 的任务选择逻辑基于此 p->se.vruntime 值，因此非常简单：它总是尝试运行具有最小 p->se.vruntime 值的任务（即，到目前为止执行最少的任务）。CFS 总是尝试在可运行的任务之间尽可能接近 “理想的多任务硬件” 地分配 CPU 时间。
CFS 的其余大部分设计都源于这个非常简单的概念，以及一些额外的修饰，如 nice 级别、多处理以及各种用于识别睡眠者的算法变体。
3. RBTREE¶
CFS 的设计非常激进：它不使用旧的运行队列数据结构，而是使用时间排序的 rbtree 来构建未来任务执行的 “时间线”，因此没有 “数组切换” 的伪像（之前的 vanilla 调度器和 RSDL/SD 都受其影响）。
CFS 还维护 rq->cfs.min_vruntime 值，这是一个单调递增的值，用于跟踪运行队列中所有任务中的最小 vruntime。系统完成的总工作量使用 min_vruntime 进行跟踪；该值用于尽可能将新激活的实体放置在树的左侧。
运行队列中正在运行的任务总数通过 rq->cfs.load 值来计算，该值是运行队列中排队的任务的权重之和。
CFS 维护一个时间排序的 rbtree，其中所有可运行的任务都按照 p->se.vruntime 键进行排序。CFS 从这棵树中选择 “最左边” 的任务并坚持执行它。随着系统的推进，执行的任务被越来越多地放到树的右侧，慢慢地但肯定地给每个任务一个成为 “最左边任务” 的机会，从而在确定的时间内获得 CPU。
总而言之，CFS 的工作方式如下：它运行一个任务一段时间，当任务调度（或发生调度器滴答）时，任务的 CPU 使用情况会被 “考虑在内”：它刚刚使用物理 CPU 所花费的（少量）时间会添加到 p->se.vruntime 中。一旦 p->se.vruntime 足够高，以至于另一个任务成为其维护的时间排序 rbtree 的 “最左边任务”（加上相对于最左边任务的一小段 “粒度” 距离，以便我们不会过度调度任务并破坏缓存），那么新的最左边任务会被选中，并且当前任务会被抢占。
4. CFS 的一些特性¶
CFS 使用纳秒级粒度的计算，不依赖任何节拍或其他的 HZ 细节。因此，CFS 调度器没有像之前的调度器那样的 “时间片” 概念，并且没有任何启发式算法。只有一个中心可调参数（您必须启用 CONFIG_SCHED_DEBUG）
/sys/kernel/debug/sched/base_slice_ns
可用于将调度器从 “桌面”（即，低延迟）调整为 “服务器”（即，良好的批处理）工作负载。它默认为适用于桌面工作负载的设置。SCHED_BATCH 也由 CFS 调度器模块处理。
如果 CONFIG_HZ 导致 base_slice_ns < TICK_NSEC，则 base_slice_ns 的值对工作负载几乎没有影响。
由于其设计，CFS 调度器不易受到当前针对 stock 调度器的启发式算法存在的任何 “攻击” 的影响：fiftyp.c、thud.c、chew.c、ring-test.c、massive_intr.c 都工作正常，不会影响交互性并产生预期的行为。
CFS 调度器对 nice 级别和 SCHED_BATCH 的处理比之前的 vanilla 调度器要强大得多：这两种类型的工作负载都被更积极地隔离。
SMP 负载均衡已经过重新设计/清理：负载均衡代码中不再使用运行队列遍历的假设，而是使用了调度模块的迭代器。因此，平衡代码变得相当简单。
5. 调度策略¶
CFS 实现了三种调度策略
SCHED_NORMAL (传统上称为 SCHED_OTHER)：用于常规任务的调度策略。
SCHED_BATCH：不像常规任务那样频繁抢占，从而允许任务运行更长时间并更好地利用缓存，但以交互性为代价。这非常适合批处理作业。
SCHED_IDLE：这甚至比 nice 19 还要弱，但它不是真正的空闲定时器调度器，目的是避免陷入会导致机器死锁的优先级反转问题。
SCHED_FIFO/_RR 在 sched/rt.c 中实现，并且符合 POSIX 规范。
util-linux-ng 2.13.1.1 中的命令 chrt 可以设置所有这些，除了 SCHED_IDLE。
6. 调度类¶
新的 CFS 调度器被设计为引入 “调度类”，即调度器模块的可扩展层次结构。这些模块封装了调度策略的细节，并由调度器核心处理，而核心代码不会对它们做过多的假设。
sched/fair.c 实现了上述的 CFS 调度器。
sched/rt.c 以比之前的 vanilla 调度器更简单的方式实现了 SCHED_FIFO 和 SCHED_RR 语义。它使用 100 个运行队列（用于所有 100 个 RT 优先级级别，而不是之前调度器中的 140 个），并且不需要过期数组。
调度类通过 sched_class 结构实现，该结构包含在发生有趣的事件时必须调用的函数的钩子。
这是钩子的（部分）列表
enqueue_task(...)
当任务进入可运行状态时调用。它将调度实体（任务）放入红黑树并递增 nr_running 变量。
dequeue_task(...)
当任务不再可运行时，将调用此函数以使相应的调度实体保持在红黑树之外。它递减 nr_running 变量。
yield_task(...)
此函数基本上只是一个出队操作，然后是一个入队操作，除非启用了 compat_yield sysctl；在这种情况下，它将调度实体放置在红黑树的最右端。
wakeup_preempt(...)
此函数检查进入可运行状态的任务是否应该抢占当前正在运行的任务。
pick_next_task(...)
此函数选择最适合接下来运行的任务。
set_next_task(...)
当任务更改其调度类、更改其任务组或被调度时调用此函数。
task_tick(...)
此函数主要从时间滴答函数调用；它可能会导致进程切换。这驱动了运行的抢占。
7. CFS 的组调度器扩展¶
通常，调度器对单个任务进行操作，并努力为每个任务提供公平的 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”伪文件系统创建任意的任务组。有关此文件系统的更多信息，请参阅 控制组。
当定义了 CONFIG_FAIR_GROUP_SCHED 时，将为使用伪文件系统创建的每个组创建一个“cpu.shares”文件。请参阅下面的示例步骤，了解如何使用“cgroups”伪文件系统创建任务组并修改其 CPU 份额。
# mount -t tmpfs cgroup_root /sys/fs/cgroup
# mkdir /sys/fs/cgroup/cpu
# mount -t cgroup -ocpu none /sys/fs/cgroup/cpu
# cd /sys/fs/cgroup/cpu
# mkdir multimedia # create "multimedia" group of tasks
# mkdir browser # create "browser" group of tasks
# #Configure the multimedia group to receive twice the CPU bandwidth
# #that of browser group
# echo 2048 > multimedia/cpu.shares
# echo 1024 > browser/cpu.shares
# firefox & # Launch firefox and move it to "browser" group
# echo <firefox_pid> > browser/tasks
# #Launch gmplayer (or your favourite movie player)
# echo <movie_player_pid> > multimedia/tasks