CFS：Linux 中完全公平的进程调度

Linux 对处理器调度采用模块化方法，可以使用不同的算法来调度不同的进程类型。调度类指定哪种调度策略适用于哪种进程类型。完全公平调度 (CFS) 在 2007 年成为 Linux 2.6.23 内核的一部分，是正常进程（相对于实时进程）的调度类，因此被命名为 SCHED_NORMAL。

CFS 专为桌面环境中的交互式应用程序而设计，但可以配置为 SCHED_BATCH 以支持批量工作负载，例如，在高容量 Web 服务器上。在任何情况下，CFS 都与所谓的“经典抢占式调度”截然不同。此外，“完全公平”的说法必须以技术眼光看待；否则，这种说法可能看起来像空洞的吹嘘。

让我们深入探讨 CFS 与其他进程调度程序的不同之处——实际上是优于其他进程调度程序的地方。让我们从快速回顾一些核心技术术语开始。

一些核心概念

Linux 继承了 Unix 对进程的看法，即进程是正在执行的程序。因此，进程必须与其他进程竞争共享系统资源：内存用于保存指令和数据，至少一个处理器用于执行指令，以及 I/O 设备用于与外部世界交互。进程调度是操作系统 (OS) 如何将任务（例如，处理一些数字、复制文件）分配给处理器——然后运行的进程执行任务。一个进程有一个或多个执行线程，它们是机器级指令序列。调度进程就是在一个处理器上调度它的一个线程。

为了简化操作，Linux 通过将调度的进程视为单线程来将进程调度转换为线程调度。如果一个进程是具有 N 个线程的多线程进程，那么需要 N 个调度操作来覆盖这些线程。多线程进程中的线程仍然是相关的，因为它们共享内存地址空间等资源。Linux 线程有时被描述为轻量级进程，其中轻量级强调了进程内线程之间资源的共享。

尽管进程可以处于各种状态，但其中两种状态在调度中特别重要。阻塞进程正在等待某些事件（例如 I/O 事件）完成。该进程只有在事件完成后才能恢复执行。可运行进程是当前未被阻塞的进程。

如果进程主要消耗处理器资源而不是 I/O 资源，则该进程是处理器密集型（也称为计算密集型），反之亦然；因此，处理器密集型进程主要是可运行的，而 I/O 密集型进程主要是阻塞的。例如，处理数字是处理器密集型的，而访问文件是 I/O 密集型的。尽管整个进程可能被描述为处理器密集型或 I/O 密集型，但给定进程在其执行的不同阶段可能属于其中一种或另一种。交互式桌面应用程序（如浏览器）往往是 I/O 密集型的。

一个好的进程调度程序必须平衡处理器密集型和 I/O 密集型任务的需求，尤其是在像 Linux 这样在如此多的硬件平台上蓬勃发展的操作系统中：台式机、嵌入式设备、移动设备、服务器集群、超级计算机等等。

经典抢占式调度与 CFS

Unix 普及了经典抢占式调度，包括 VAX/VMS、Windows NT 和 Linux 在内的其他操作系统后来也采用了这种调度。这种调度模型的中心是固定时间片，即任务被允许占用处理器的时间量（例如，50 毫秒），直到被抢占以支持其他任务。如果被抢占的进程尚未完成其工作，则必须重新调度该进程。该模型功能强大，因为它通过处理器时间共享支持多任务处理（并发），即使在昨天的单 CPU 机器上也是如此。

经典模型通常包括多个调度队列，每个队列对应一个进程优先级：较高优先级队列中的每个进程都在较低优先级队列中的任何进程之前被调度。例如，VAX/VMS 使用 32 个优先级队列进行调度。

CFS 取消了固定时间片和显式优先级。给定任务在处理器上的时间量是根据系统生命周期内调度上下文的变化动态计算的。以下是动机和技术细节的概述

• 想象一个处理器 P，它是理想化的，它可以同时执行多个任务。例如，任务 T1 和 T2 可以同时在 P 上执行，每个任务接收 P 的 50% 的神奇处理能力。这种理想化描述了完美的多任务处理，CFS 努力在实际的而不是理想化的处理器上实现这种完美的多任务处理。CFS 旨在近似完美的多任务处理。

• CFS 调度程序具有目标延迟，这是每个可运行任务至少获得一次处理器运行机会所需的最小时间量——理想化为一个无限小的持续时间。如果这样的持续时间可以无限小，那么每个可运行任务将在任何给定的时间跨度内（无论多么小，例如 10 毫秒、5 纳秒等）获得处理器运行机会。当然，理想化的无限小持续时间必须在现实世界中近似，默认近似值为 20 毫秒。然后，每个可运行任务获得目标延迟的 1/N 片，其中 N 是任务数。例如，如果目标延迟为 20 毫秒，并且有四个竞争任务，则每个任务获得 5 毫秒的时间片。顺便说一句，如果在调度事件期间只有一个任务，那么这个幸运的任务将获得整个目标延迟作为其时间片。CFS 中的公平体现在分配给每个争用处理器的任务的 1/N 片中。

• 1/N 片确实是一个时间片——但不是固定的时间片，因为这样的时间片取决于 N，即当前争用处理器的任务数。系统随时间变化。一些进程终止，新的进程被派生；可运行进程阻塞，阻塞进程变为可运行。N 的值是动态的，因此，为每个争用处理器的可运行任务计算的 1/N 时间片也是动态的。传统的 nice 值用于加权 1/N 片：低优先级 nice 值意味着只给任务分配 1/N 片的一部分，而高优先级 nice 值意味着给任务分配 1/N 片的成比例更大的部分。总之，nice 值不决定时间片，而只是修改代表争用任务之间公平性的 1/N 片。

• 每当发生上下文切换时，操作系统都会产生开销；也就是说，当一个进程被抢占以支持另一个进程时。为了防止这种开销变得过大，任何调度的进程在被抢占之前都必须运行的最短时间量（通常设置为 1 毫秒到 4 毫秒）。这个最小值称为最小粒度。如果有许多任务（例如，20 个）争用处理器，则最小粒度（假设为 4 毫秒）可能大于 1/N 片（在本例中为 1 毫秒）。如果最小粒度结果大于 1/N 片，则系统过载，因为有太多任务争用处理器——公平性荡然无存。

• 何时发生抢占？CFS 试图最大限度地减少上下文切换，考虑到它们的开销：花在上下文切换上的时间是其他任务不可用的时间。因此，一旦任务获得处理器，它将在被抢占以支持其他任务之前运行其整个加权 1/N 片。假设任务 T1 已运行其加权 1/N 片，并且可运行任务 T2 当前在争用处理器的任务中具有最低的虚拟运行时 (vruntime)。vruntime 以纳秒为单位记录任务在处理器上运行的时间。在这种情况下，T1 将被抢占以支持 T2。

• 调度程序跟踪所有任务（可运行和阻塞）的 vruntime。任务的 vruntime 越低，任务就越应该获得处理器时间。因此，CFS 将低 vruntime 任务移向调度队列的前面。细节即将到来，因为队列是作为树而不是列表实现的。

• CFS 调度程序应该多久重新调度一次？有一种简单的方法可以确定调度周期。假设目标延迟 (TL) 为 20 毫秒，最小粒度 (MG) 为 4 毫秒

  TL / MG = (20 / 4) = 5 ## 五个或更少的任务是可以的

  在这种情况下，五个或更少的任务将允许每个任务在目标延迟期间获得一次处理器运行机会。例如，如果任务数为五个，则每个可运行任务的 1/N 片为 4 毫秒，这恰好等于最小粒度；如果任务数为三个，则每个任务获得接近 7 毫秒的 1/N 片。在任何一种情况下，调度程序都将在 20 毫秒（目标延迟的持续时间）内重新调度。

  如果任务数（例如，10 个）超过 TL / MG，则会发生问题，因为现在每个任务必须获得 4 毫秒的最小时间，而不是计算出的 1/N 片（为 2 毫秒）。在这种情况下，调度程序将在 40 毫秒内重新调度

  （任务数）* MG = (10 * 4) = 40 毫秒 ## 周期 = 40 毫秒

早于 CFS 的 Linux 调度程序使用启发式方法来促进对交互式任务进行公平的调度处理。CFS 采取了截然不同的方法，让 vruntime 事实主要为自己说话，这恰好支持睡眠者公平性。交互式任务本质上倾向于睡眠很多，因为它等待用户输入，因此变为 I/O 密集型；因此，此类任务倾向于具有相对较低的 vruntime，这倾向于将任务移向调度队列的前面。

特殊功能

CFS 支持对称多处理 (SMP)，其中任何进程（无论是内核进程还是用户进程）都可以在任何处理器上执行。然而，可配置的调度域可用于对处理器进行分组以实现负载平衡甚至隔离。如果多个处理器共享相同的调度策略，则可以在它们之间进行负载平衡；如果特定处理器的调度策略与其他处理器不同，则该处理器将在调度方面与其他处理器隔离。

可配置的调度组是 CFS 的另一个功能。例如，考虑在我的台式机上运行的 Nginx Web 服务器。在启动时，此服务器有一个主进程和四个工作进程，这些工作进程充当 HTTP 请求处理程序。对于任何 HTTP 请求，处理请求的特定工作进程是无关紧要的；重要的是请求得到及时处理，因此四个工作进程共同提供了一个池，从中可以提取任务处理程序来处理传入的请求。因此，将四个 Nginx 工作进程作为一个组而不是单独的个体进行调度处理似乎是公平的，并且可以使用调度组来做到这一点。可以将四个 Nginx 工作进程配置为在它们之间共享单个 vruntime，而不是单独的 vruntime。配置以传统的 Linux 方式通过文件完成。对于 vruntime 共享，将创建一个名为 cpu.shares 的文件，详细信息通过熟悉的 shell 命令给出。

如前所述，Linux 支持调度类，以便不同的调度策略及其实现算法可以在同一平台上共存。调度类作为 C 语言代码模块实现。CFS，即到目前为止描述的调度类，是 SCHED_NORMAL。还有专门用于实时任务的调度类，SCHED_FIFO（先进先出）和 SCHED_RR（轮循）。在 SCHED_FIFO 下，任务运行到完成；在 SCHED_RR 下，任务运行直到它们耗尽固定时间片并被抢占。

CFS 实现

CFS 需要高效的数据结构来跟踪任务信息和高性能代码来生成调度。让我们从调度中的一个中心术语开始，即运行队列。这是一个表示调度任务时间线的数据结构。尽管名称如此，但运行队列不需要以传统方式（作为 FIFO 列表）实现。CFS 打破了传统，使用按时间排序的红黑树作为运行队列。该数据结构非常适合这项工作，因为它是一个自平衡二叉搜索树，具有高效的 insert 和 remove 操作，这些操作在 O(log N) 时间内执行，其中 N 是树中节点的数量。此外，树是一种优秀的数据结构，用于根据特定属性（在本例中为 vruntime）将实体组织成层次结构。

在 CFS 中，树的内部节点表示要调度的任务，而整个树像任何运行队列一样，表示任务执行的时间线。红黑树在调度之外被广泛使用；例如，Java 使用这种数据结构来实现其 TreeMap。

在 CFS 下，每个处理器都有一个特定的任务运行队列，并且没有任务同时出现在多个运行队列中。每个运行队列都是一棵红黑树。树的内部节点表示任务或任务组，这些节点按其 vruntime 值索引，以便（在整个树中或在任何子树中）左侧的内部节点具有比右侧的内部节点更低的 vruntime 值

    25     ## 25 is a task vruntime
    /\
  17  29   ## 17 roots the left subtree, 29 the right one
  /\  ...
 5  19     ## and so on
...  \
     nil   ## leaf nodes are nil

总之，vruntime 最低的任务（因此，对处理器的需求最大）位于左子树的某个位置；vruntime 相对较高的任务聚集在右子树中。被抢占的任务将进入右子树，从而使其他任务有机会在树中向左移动。vruntime 最小的任务最终会出现在树的最左侧（内部）节点中，因此它是运行队列的前面。

CFS 调度程序有一个实例，即 C task_struct，用于跟踪有关每个要调度的任务的详细信息。此结构嵌入了一个 sched_entity 结构，该结构反过来具有特定于调度的信息，特别是每个任务或任务组的 vruntime

struct task_struct {       /** info on a task **/
  ...
  struct sched_entity se;  /** vruntime, etc. **/
  ...
};

红黑树以熟悉的 C 方式实现，以指针为重点以提高效率。cfs_rq 结构实例嵌入了一个名为 tasks_timeline 的 rb_root 字段，该字段指向红黑树的根。树的每个内部节点都有指向父节点和两个子节点的指针；叶节点的值为 nil。

CFS 说明了如何以简单但高效的方式实现一个直接的想法——为每个任务提供公平的处理器资源份额。值得重申的是，CFS 在没有传统的人工制品（如固定时间片和显式任务优先级）的情况下实现了公平高效的调度。当然，对更好调度程序的追求仍在继续；然而，就目前而言，CFS 对于通用处理器调度来说已经非常好了。