英语

CFS 调度器

1. 概述

CFS 代表“完全公平调度器”，是由 Ingo Molnar 实现并合并到 Linux 2.6.23 中的“桌面”进程调度器。 最初合并时，它是对先前 vanilla 调度器的 SCHED_OTHER 交互性代码的替代。 如今，CFS 正在为 EEVDF 让路，有关 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 调度器没有先前调度器那样的“时间片”概念，也没有任何启发式方法。 只有一个中心可调参数

/sys/kernel/debug/sched/base_slice_ns

可用于将调度器从“桌面”（即低延迟）调整为“服务器”（即良好的批处理）工作负载。 它默认为适合桌面工作负载的设置。 SCHED_BATCH 也由 CFS 调度器模块处理。

如果 CONFIG_HZ 导致 base_slice_ns < TICK_NSEC，则 base_slice_ns 的值对工作负载几乎没有影响。

由于其设计，CFS 调度器不易受到当今针对库存调度器的启发式方法的任何“攻击”：fiftyp.c、thud.c、chew.c、ring-test.c、massive_intr.c 都可以正常工作，并且不会影响交互性，并且产生预期的行为。

与之前的 vanilla 调度器相比，CFS 调度器对 nice 级别和 SCHED_BATCH 的处理要强得多：两种类型的工作负载都被更积极地隔离。

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