调度器之战：ULE vs. CFS¶

标题：The Battle of the Schedulers: FreeBSD ULE vs. Linux CFS

日期：2018/07/11

作者：Justinien Bouron, Sebastien Chevalley, Baptiste Lepers, and Willy Zwaenepoel, EPFL; Redha Gouicem, Julia Lawall, Gilles Muller, and Julien Sopena, Sorbonne University/Inria/LIP6

链接：https://www.usenix.org/conference/atc18/presentation/bouron

注意：此为 AI 翻译生成 的中文转录稿，详细说明请参阅仓库中的 README 文件。

备注：只是比结果，没有我想看的。

摘要¶

本文分析了两种广泛使用的开源调度器——ULE（FreeBSD 的默认调度器）和 CFS（Linux 的默认调度器）——在设计和实现上的选择对应用程序性能的影响。我们在其他条件完全相同的情况下对 ULE 和 CFS 进行了比较。我们已将 ULE 移植到 Linux，并用它来调度所有通常由 CFS 调度的线程。我们在运行 ULE 的修改版内核和运行 CFS 的标准 Linux 内核上，比较了一大套应用程序的性能。观察到的性能差异完全是调度决策的结果，并不反映 FreeBSD 和 Linux 之间其他子系统的差异。

研究表明没有绝对的赢家。在许多工作负载下，两个调度器的性能相似，但对于某些工作负载，存在显著甚至令人惊讶的差异。ULE 可能会导致饥饿，即使在执行具有相同线程的单个应用程序时也是如此，但这种饥饿现象实际上可能为某些工作负载带来更好的应用程序性能。CFS 更复杂的负载均衡机制能更快地对工作负载变化做出反应，但从长远来看，ULE 实现了更好的负载均衡。

1. 引言¶

操作系统内核调度器负责维持硬件资源（CPU 核心、内存、I/O 设备）的高利用率，同时为延迟敏感型应用提供快速响应时间。它们必须能够应对工作负载的变化，并以最小的开销处理大量的核心和线程。本文对两个部署最广泛的开源操作系统的默认调度器进行了比较：Linux 中使用的完全公平调度器（CFS）和 FreeBSD 中使用的 ULE 调度器。我们的目标不是要宣布一个总体的胜利者。事实上，我们发现对于某些工作负载，ULE 更好，而对于其他工作负载，CFS 更优。我们的目标是阐明这两种调度器在设计和实现上的差异如何反映在不同工作负载下的应用程序性能上。

ULE 和 CFS 都旨在调度大型多核机器上的大量线程。出于可扩展性的考虑，两种调度器都采用了每核心运行队列（per-core runqueues）。在上下文切换时，一个核心只访问其本地运行队列来寻找下一个要运行的线程。在周期性以及特定时刻（例如，当一个线程被唤醒时），ULE 和 CFS 都会执行负载均衡，即它们试图平衡不同核心运行队列中等待的工作量。

然而，ULE 和 CFS 在设计和实现上的选择有很大差异。FreeBSD ULE 是一个简单的调度器（在 FreeBSD 11.1 中有 2,950 行代码），而 Linux CFS 则复杂得多（在最新的 LTS Linux 内核，Linux 4.9 中有 17,900 行代码）。FreeBSD 的运行队列是 FIFO（先进先出）的。在负载均衡方面，FreeBSD 致力于均衡每个核心的线程数量。在 Linux 中，一个核心根据线程先前的执行时间、优先级和感知的缓存行为来决定下一个要运行的线程。Linux 并非致力于均衡核心间的线程数量，而是致力于均衡平均待处理工作量。

比较 ULE 和 CFS 的主要挑战在于，应用程序性能不仅取决于调度器，还取决于其他操作系统子系统，如网络、文件系统和内存管理，这些在 FreeBSD 和 Linux 之间也存在差异。为了分离 CFS 和 ULE 差异的影响，我们将 ULE 移植到了 Linux，并将其用作默认调度器来运行机器上的所有线程（包括通常由 CFS 调度的内核线程）。然后，我们比较了这个修改过的使用 ULE 的 Linux 与默认的使用 CFS 的 Linux 内核之间的应用程序性能。

我们首先通过运行应用程序来检验 ULE 和 CFS 做出的每核心调度决策的影响。

2. CFS 和 ULE 概述¶

2.1 Linux CFS¶

每核心调度（Per-core scheduling）： Linux 的 CFS 实现了一种加权公平队列算法：它根据线程的优先级（由其 niceness 值表示，高 niceness 意味着低优先级，反之亦然）在线程之间平均分配 CPU 周期。为此，CFS 按一个称为 vruntime 的多因素值对线程进行排序，该值代表一个线程已经使用的 CPU 时间除以其优先级。具有相同优先级和相同 vruntime 的线程已经执行了相同的时间，这意味着核心资源在它们之间得到了公平共享。为了确保所有线程的 vruntime 公平推进，当当前运行的线程被抢占时，CFS 会调度 vruntime 最低的线程接下来运行。

自 Linux 2.6.38 起，CFS 中的公平性概念已从线程间的公平演变为应用程序间的公平。在 Linux 2.6.38 之前，每个线程被视为一个独立的实体，并获得与系统中其他线程相同的资源份额。这意味着使用许多线程的应用程序会比单线程应用程序获得更多的资源。在较新的内核版本中，同一应用程序的线程被分组到一个称为 cgroup 的结构中。一个 cgroup 有一个 vruntime，它对应于其所有线程的 vruntime 之和。然后，CFS 将其算法应用于 cgroup，确保线程组之间的公平性。当一个 cgroup 被选中进行调度时，其内部 vruntime 最低的线程会被执行，从而确保 cgroup 内部的公平性。cgroup 也可以是嵌套的。例如，systemd 会自动配置 cgroup 以确保不同用户之间的公平，然后再确保给定用户的应用程序之间的公平。

CFS 通过在给定的时间段内调度所有线程来避免线程饥饿。对于执行少于 8 个线程的核心，默认时间段为 48ms。当一个核心执行超过 8 个线程时，时间段会随着线程数量的增加而增长，等于 6 * 线程数 ms；选择 6ms 的值是为了避免过于频繁地抢占线程。具有较高优先级的线程会获得该时间段中更大的份额。由于 CFS 调度 vruntime 最低的线程，CFS 需要防止某个线程的 vruntime 远低于其他等待调度线程的 vruntime。如果发生这种情况，vruntime 低的线程可能会长时间运行，导致其他线程饥饿。实际上，CFS 确保任意两个线程之间的 vruntime 差异小于抢占周期（6ms）。它在两个关键点做到这一点：（i）当一个线程被创建时，该线程以等于运行队列中等待线程最大 vruntime 的 vruntime 开始；（ii）当一个线程在睡眠后被唤醒时，它的 vruntime 会被更新，使其至少等于等待调度线程的最小 vruntime。使用最小 vruntime 还能确保经常睡眠的线程被优先调度，这在桌面系统上是一个理想的策略，因为它最小化了交互式应用的延迟。大多数交互式应用大部分时间都在睡眠，等待用户输入，一旦用户交互，它们就会被立即调度。

CFS 还使用启发式方法来改善缓存使用。例如，当一个线程被唤醒时，它会检查其 vruntime 与当前运行线程的 vruntime 之间的差异。如果差异不显著（小于 1ms），当前运行的线程就不会被抢占——CFS 牺牲延迟以避免频繁的线程抢占，因为这可能会对缓存产生负面影响。

负载均衡（Load balancing）： 在多核环境中，Linux 的 CFS 会均衡机器上所有核心的工作量。这与均衡线程数量不同。例如，如果一个用户运行 1 个 CPU 密集型线程和 10 个大部分时间在睡眠的线程，CFS 可能会将这 10 个大部分睡眠的线程调度到同一个核心上。

为了平衡工作量，CFS 为线程和核心使用一个负载度量。线程的负载对应于一个线程的平均 CPU 利用率：一个从不睡眠的线程比一个经常睡眠的线程有更高的负载。与 vruntime 一样，线程的负载也由其优先级加权。一个核心的负载是该核心上可运行线程的负载之和。CFS 试图均衡核心的负载。

CFS 在创建或唤醒线程时会考虑核心的负载。调度器首先决定哪些核心适合承载该线程。这个决定涉及许多启发式方法，例如发起唤醒的线程唤醒其他线程的频率。例如，如果 CFS 检测到一个一对多的生产者-消费者模式，它会将消费者线程尽可能地分散在机器上，并且机器上的大多数核心都被认为是适合承载被唤醒线程的。在一个一对一的通信模式中，CFS 将适合的核心列表限制为与发起唤醒的线程共享缓存的核心。然后，在所有适合的核心中，CFS 选择负载最低的核心来唤醒或创建线程。

负载均衡也会周期性地发生。每 4ms，每个核心都会尝试从其他核心窃取工作。这种负载均衡会考虑机器的拓扑结构：核心会更频繁地尝试从“近”的核心（例如，共享缓存的核心）窃取工作，而不是从“远”的核心（例如，在远程 NUMA 节点上）窃取。当一个核心决定从另一个核心窃取工作时，它会尝试通过从另一个核心窃取多达 32 个线程来均衡两个核心之间的负载。当核心变为空闲时，它们也会立即调用周期性负载均衡器。

在大型 NUMA 机器上，CFS 不会比较所有核心的负载，而是以分层的方式平衡负载。例如，在一台有 2 个 NUMA 节点的机器上，CFS 会平衡 NUMA 节点内部核心的负载，然后比较 NUMA 节点的负载（定义为其核心的平均负载）来决定是否在节点之间平衡负载。如果节点之间的负载差异很小（实践中小于 25%），则不执行负载均衡。两个核心（或核心组）之间的距离越大，CFS 平衡负载所需的失衡度就越高。

2.2 FreeBSD ULE¶

每核心调度（Per-core scheduling）： ULE 使用两个运行队列来调度线程：一个运行队列包含交互式线程，另一个包含批处理线程。第三个称为 idle 的运行队列在核心空闲时使用。这个运行队列只包含空闲任务。

设置两个运行队列的目标是优先处理交互式线程。批处理进程通常在没有用户交互的情况下执行，因此调度延迟不那么重要。ULE 使用一个介于 0 到 100 之间的交互性惩罚度量来跟踪线程的交互性。该度量被定义为线程运行时间 r 和自愿睡眠时间 s（不包括等待 CPU 的时间）的函数，计算如下：

scaling_factor = m = 50
penalty(r, s) = { 
    s / (s + r) * m          如果 s > r
    (r - s) / r * m + m      其他情况
}

惩罚值在范围的下半部分（≤ 50）意味着线程自愿睡眠的时间多于运行的时间，而惩罚值在范围的上半部分则相反。

为睡眠和运行时间保留的历史量（默认情况下）仅限于线程生命周期的最后 5 秒。一方面，保留大量的历史会延长检测批处理线程所需的时间。另一方面，太少的历史会在分类中引入噪声。

为了对线程进行分类，ULE 首先计算一个分数，定义为交互性惩罚 + niceness。如果一个线程的分数低于某个阈值（在 FreeBSD 11.1 中默认为 30），它就被认为是交互式的。对于 niceness 值为 0 的情况，这大致对应于花费超过 60% 的时间在睡眠。否则，它被归类为批处理线程。负的 niceness 值（高优先级）使线程更容易被视为交互式。

当一个线程被创建时，它继承其父线程的运行时间和睡眠时间（以及因此的交互性）。当一个线程死亡时，它在最后 5 秒的运行时间会返回给其父线程。这会惩罚那些在交互式状态下派生批处理子线程的父线程。

在交互式和批处理运行队列内部，线程会根据优先级进一步排序。交互式线程的优先级是其分数的线性插值（即，惩罚值为 0 的线程具有最高的交互式优先级，而惩罚值为 30 的线程具有最低的交互式优先级）。在交互式运行队列内部，每个优先级都有一个 FIFO 队列。要将一个线程添加到运行队列中，调度器会将该线程插入到由其优先级索引的 FIFO 队列的末尾。从这个运行队列中选择一个线程来运行，只需从最高优先级的非空 FIFO 队列中取出第一个线程即可。

批处理线程的优先级取决于它们的运行时间：一个线程运行得越多，其优先级就越低。线程的 niceness 值被添加进来，以在优先级上产生线性效应。在批处理运行队列内部，每个优先级也有一个 FIFO 队列。插入和移除的操作与交互式情况类似，但略有不同。为了避免批处理线程之间的饥饿，ULE 试图在批处理线程之间保持公平，通过最小化线程之间的运行时间差异，这与 CFS 对 vruntime 的处理类似。

在选择下一个要运行的线程时，ULE 首先在交互式运行队列中搜索。如果一个交互式线程准备好被调度，它就返回那个线程。如果交互式运行队列为空，ULE 则在批处理运行队列中搜索。如果两个运行队列都为空，那意味着核心是空闲的，没有线程被调度。

ULE 搜索运行队列的顺序有效地给予了交互式线程相对于批处理线程的绝对优先权。如果机器执行了太多的交互式线程，批处理线程可能会潜在地饿死。然而，人们认为，由于交互式线程根据定义睡眠的时间比执行的时间多，饥饿现象不会发生。

一个线程运行的时间是有限的，这个时间段被称为时间片（timeslice）。与 CFS 不同，一个线程时间片到期的速率与其优先级无关。然而，时间片的值会随着核心上当前运行的线程数量而变化。当一个核心执行 1 个线程时，时间片是 10 个 tick（78ms）。当有多个线程运行时，这个值会被线程数量除，同时被限制在一个 1 tick（秒的 1/127）的下限。在 ULE 中，完全抢占是禁用的，这意味着只有内核线程可以抢占其他线程。

负载均衡（Load balancing）： ULE 的目标仅仅是均衡每个核心的线程数量。在 ULE 中，一个核心的负载被简单地定义为该核心上当前可运行的线程数量。与 CFS 不同，ULE 不会将线程分组到 cgroup 中，而是将每个线程视为一个独立的实体。

在为新创建或被唤醒的线程选择核心时，ULE 使用一种亲和性启发式方法。如果线程在其上次运行的核心上被认为是缓存亲和的，那么它就被放置在该核心上。否则，ULE 会在被认为是亲和的拓扑结构中找到最高级别，或者如果都不可用，则选择整个机器。从那里，ULE 首先尝试找到一个核心，其最低优先级高于该线程的优先级。如果失败，ULE 会再次尝试，但这次是在机器的所有核心上。如果这也失败了，ULE 就简单地选择运行线程数最少的核心。

ULE 也会周期性地平衡线程，每 500-1500ms 一次（周期的持续时间是随机选择的）。与 CFS 不同，周期性负载均衡只由核心 0 执行。核心 0 只是试图在所有核心之间均衡线程数量，具体如下：一个来自负载最重的核心（donor，捐赠者）的线程，被迁移到负载最轻的核心（receiver，接收者）。一个核心只能成为一次捐赠者或接收者，负载均衡器会迭代直到找不到捐赠者或接收者，这意味着一个核心在每次负载均衡调用中最多只能给出或接收一个线程。

当一个核心的交互式和批处理运行队列都为空时，ULE 也会平衡线程。ULE 试图从与空闲核心共享缓存的负载最重的核心窃取线程。如果 ULE 无法窃取线程，它会尝试在更高的拓扑级别上进行，以此类推，直到最终成功窃取一个线程。与周期性负载均衡器一样，空闲窃取机制最多只窃取一个线程。

ULE 中的周期性负载均衡比 CFS 中发生的频率要低，但在 ULE 的线程放置过程中选择核心时涉及更多的计算。其基本原理是，拥有更好的初始线程放置可以避免频繁运行全局负载均衡器的需要。¹

¹在最近版本的 FreeBSD 中，由于一个 bug，周期性负载均衡器从未执行. 在我们的 ULE 代码中，我们修复了这个 bug，并且负载均衡器会周期性地执行。

3. 将 ULE 移植到 Linux 内核¶

在本节中，我们描述了将 ULE 移植到 Linux 时遇到的问题，以及我们的移植版本与原始 FreeBSD 代码之间的主要差异。

Linux 内核提供了一个 API 来向内核添加新的调度器。调度器必须实现表 1 中呈现的函数集。这些函数负责在运行队列中添加和移除线程、选择要调度的线程以及在核心上放置线程。

FreeBSD 不提供这样的调度器 API。相反，它声明了必须被定义的函数原型，这意味着一次只能使用一个调度器，这与 Linux 不同，在 Linux 中多个调度类可以共存。幸运的是，ULE 调度器内部的函数可以很容易地映射到它们在 Linux 中的对应部分（见表 1）。在少数接口不匹配的情况下，我们能够找到一种变通方法。例如，Linux 使用一个单一的函数来将新创建的线程和被唤醒的线程入队，而 FreeBSD 使用两个函数。Linux 在其函数中使用一个标志参数来区分这两种情况。因此，只需使用这个标志来选择相应的 FreeBSD 函数就足够了。

[表格1：Linux 调度器 API 及其在 FreeBSD 中的等效函数。内容已忽略]

除了接口之外，CFS 和 ULE 在一些底层假设上也有所不同。最显著的差异与当前线程在运行队列数据结构中是否存在有关。Linux 的调度类机制依赖于这样一个假设：当前线程在它运行于一个核心上时，仍然保留在运行队列数据结构中。在 ULE 中，一个在核心上运行的线程会从运行队列数据结构中移除，并在其时间片耗尽时被加回，以保持 FIFO 属性。当尝试在 Linux 中实现这种行为时，我们遇到了几个会导致系统崩溃的问题，例如线程试图改变其调度类时导致的内核崩溃。我们决定转而遵循 Linux 的方式，将当前运行的线程保留在运行队列中。因此，我们必须稍微修改 ULE 的负载均衡，以避免迁移当前正在运行的线程。

此外，在 ULE 中，当一个线程从一个 CPU 迁移到另一个时，调度器会获取两个运行队列的锁。在 Linux 中，这种锁机制会导致死锁。因此，我们修改了 ULE 的负载均衡代码，使其使用与 CFS 相同的机制。

最后，在 FreeBSD 中，ULE 负责调度所有线程，而 Linux 对不同的优先级范围使用不同的调度策略（例如，为高优先级线程使用实时调度器）。在这项工作中，我们主要感兴趣的是比较优先级落在 CFS 范围（100-139）的工作负载。因此，我们缩小了 ULE 的惩罚分数以适应 CFS 的范围。

4. 实验环境¶

4.1 机器¶

我们在一个拥有 32 个核心（AMD Opteron 6172）和 32GB RAM 的机器上评估 ULE。所有实验都在最新的 LTS Linux 内核（4.9）上进行。我们还在一台较小的桌面机（8 核 Intel i7-3770）上运行了实验，得出了类似的结论。由于篇幅限制，我们省略了这些结果。

4.2 工作负载¶

为了评估 CFS 和 ULE 的性能，我们使用了合成基准测试和真实应用程序。Fibo 是一个计算斐波那契数的合成应用程序。Hackbench 是一个由 Linux 社区设计的基准测试，用于给调度器施加压力。它创建大量运行时间很短并通过管道交换数据的线程。我们还从 Phoronix 测试套件中根据它们的完成时间选择了 16 个应用程序。我们排除了那些在单个核心上完成时间超过 10 分钟，或者时间太短以至于无法进行可靠时间测量的 Phoronix 应用程序。这 16 个 Phoronix 应用程序是：编译基准测试（build-apache, build-php），压缩（7zip, gzip），图像处理（c-ray, dcraw），科学计算（himeno, hmmer, scimark），加密（john-the-ripper）和 web（apache）。我们使用 NAS 基准测试套件来测试 HPC 应用程序，使用 Parsec 基准测试套件来测试并行应用程序，并使用带有 MySQL 和 RocksDB 的 Sysbench 作为数据库基准测试。我们对 sysbench 和 RocksDB 使用读写工作负载，以调度具有不同行为的线程。

5. 每核心调度的评估¶

在本节中，我们在单个核心上运行应用程序，以避免负载均衡器可能引入的副作用。CFS 和 ULE 在每核心调度方面的主要区别在于对批处理线程的处理：CFS 试图对所有线程公平，而 ULE 则优先考虑交互式线程。我们首先通过在同一个核心上共同调度一个批处理和一个交互式应用程序来分析这个设计决策的影响，并展示在 ULE 下批处理应用程序可能会遭受无限时间的饥饿。然后我们展示，即使系统只运行一个单一的应用程序，ULE 下的饥饿也可能发生。我们通过比较 37 个应用程序的性能来结束本节，并展示了关于线程抢占的不同选择如何影响性能。

5.1 共同调度应用时的公平性与饥饿¶

在本节中，我们分析了 CFS 和 ULE 在运行一个多应用工作负载时的行为，该工作负载包含一个从不睡眠的计算密集型线程（fibo，计算数字），以及一个线程主要睡眠的应用程序（sysbench，一个使用 80 个线程的数据库）。在数据中心，每个核心拥有超过 80 个线程并不罕见。这些线程不会一直都处于活动状态；它们主要等待传入的请求或存储在磁盘上的数据。

Fibo 单独运行 7 秒，然后启动 sysbench。两个应用程序随后运行至完成。图 1(a) 展示了 fibo 和 sysbench 在 CFS 上的累积运行时间，图 1(b) 展示了在 ULE 上的相同数据。

[图1：fibo 和 sysbench 在 (a) CFS 和 (b) ULE 上的累积运行时间。内容已忽略]

在 CFS 上，sysbench 在 235 秒内完成，然后 fibo 单独运行。fibo 和 sysbench 的线程共享机器。当 sysbench 执行时，fibo 的累积运行时间进展速度大约是其单独运行时的一半，这意味着 fibo 获得了 50% 的核心。这是符合预期的：CFS 试图在两个应用程序之间公平地共享核心。实际上，由于舍入误差，fibo 获得的 CPU 时间略少于一半。

在 ULE 上，sysbench 能够在 143 秒内完成相同的工作负载，然后 fibo 自行运行。当 sysbench 运行时，fibo 处于饥饿状态。sysbench 的线程主要睡眠，因此它们被归类为交互式线程，并获得相对于 fibo 的绝对优先权。由于 sysbench 使用 80 个线程，这些线程能够饱和一个核心，并阻止 fibo 运行。图 2 展示了 fibo 和 sysbench 的交互性惩罚随时间的变化。两个应用程序开始时都是交互式的（惩罚为 0）。fibo 的惩罚迅速上升到最大值，然后 fibo 不再被认为是交互式的。相比之下，sysbench 的线程在整个执行过程中保持交互式（惩罚低于 30 的限制）。因此，sysbench 线程获得了相对于 fibo 线程的绝对优先权。这种情况会一直持续到 sysbench 运行结束（即，饥饿时间不受 ULE 限制）。

[图2：线程的交互性惩罚随时间的变化。内容已忽略]

表 2 展示了 fibo 和 sysbench 在 CFS 和 ULE 上的总执行时间，以及 sysbench 的请求延迟。Sysbench 在 CFS 上运行慢了 50%，因为它与 fibo 共享 CPU，而不是像在 ULE 上那样独立运行（CFS 下 290 事务/秒 vs. ULE 下 532 事务/秒）。在 ULE 上执行 sysbench 期间，Fibo 被“停止”了，但之后它可以自己执行，因此可以比与 sysbench 同时运行时更有效地使用缓存。因此，fibo 在 ULE 上比在 CFS 上运行得稍快。

[表格2：使用 CFS 和 ULE 的 fibo 和 sysbench 的执行时间，以及 sysbench 中请求的平均延迟。内容已忽略]

我们发现 ULE 调度器使用的策略非常适合延迟敏感型应用程序。这些应用程序通常被正确地分类为交互式，并获得优先于后台线程的权利。要在 Linux 中实现相同的结果，延迟敏感型应用程序将需要由实时调度器执行，该调度器相对于 CFS 具有绝对优先权。

5.2 单一应用内的公平性与饥饿¶

ULE 在上述多应用场景中表现出的饥饿现象也发生在单应用工作负载中。我们现在使用 sysbench 来举例说明这种行为。

在 ULE 中，新创建的线程继承其父线程在 fork 时的交互性惩罚。在 sysbench 中，主线程是以其派生自的 bash 进程的交互性惩罚创建的。由于 bash 主要在睡眠，sysbench 被创建为一个交互式进程。sysbench 的主线程初始化数据并创建线程。在此过程中，它从不睡眠，其交互性惩罚增加。最先被创建的线程是在交互性惩罚低于交互阈值时创建的，而其余的线程则是在交互性惩罚高于该阈值时创建的。因此，最先创建的线程获得了相对于其余线程的绝对优先权。由于这些线程大部分时间都在等待新的请求，它们的交互性惩罚保持在低水平（它会降至 0），并且它们的优先级仍然高于那些在初始化过程中较晚被 fork 的线程的优先级。如果交互式线程始终保持 CPU 繁忙，后者 sysbench 线程可能会永远饿死。

图 3 展示了 sysbench 线程的累积运行时间，图 4 展示了它们的交互性惩罚。Sysbench 配置为使用 128 个线程。早期创建的线程执行，其交互性惩罚降至 0。后期创建的线程从未执行。

[图3：ULE 上 sysbench 线程的累积运行时间。内容已忽略] [图4：图3 中线程的交互性惩罚。内容已忽略]

与直觉相反，在这个基准测试中，ULE 实际上比 CFS 表现得更好，因为它避免了过度订阅：机器只运行它能运行的那么多线程。因此，ULE 的平均延迟比 CFS 低。总的来说，我们发现这种饥饿机制，虽然在纸面上看起来有问题，但在所有线程竞争完成相同工作的应用程序中表现得非常好。

与 sysbench 相比，我们测试的科学应用程序不受饥饿的影响，因为它们的线程从不睡眠。经过短暂的初始化期后，所有线程都被视为后台线程，并以公平的方式进行调度。

5.3 性能分析¶

我们现在分析每核心调度对 37 个应用程序性能的影响。我们将“性能”定义如下：对于数据库工作负载和 NAS 应用程序，我们比较每秒的操作数，对于其他应用程序，我们比较“1/执行时间”。“性能”越高，调度器的表现就越好。图 5 展示了 CFS 和 ULE 在单个核心上的性能差异，百分比高于 0 意味着应用程序在 ULE 上执行得比 CFS 快。

[图5：ULE 相对于 CFS 在单个核心上的性能。内容已忽略]

总的来说，调度器对大多数工作负载的影响很小。确实，大多数应用程序使用的线程都执行相同的工作，因此 CFS 和 ULE 最终都会以轮询方式调度所有线程。平均性能差异为 1.5%，有利于 ULE。然而，scimark 在 ULE 上慢了 36%，而 apache 在 ULE 上快了 40%。

Scimark 是一个单线程的 Java 应用程序。它启动一个计算线程，Java 运行时在后台执行其他 Java 系统线程（用于垃圾回收、I/O 等）。当应用程序使用 ULE 执行时，计算线程可能会被延迟，因为 Java 系统线程被认为是交互式的，并优先于计算线程。

apache 工作负载由两个应用程序组成：主服务器（httpd）运行 100 个线程，以及一个单线程的负载注入器 ab。ULE 和 CFS 之间的性能差异可以通过关于线程抢占的不同选择来解释。

在 ULE 中，完全抢占是禁用的，而 CFS 在刚被唤醒的线程的 vruntime 远小于当前执行线程的 vruntime 时（实践中差异为 1ms），会抢占正在运行的线程。在 CFS 中，ab 在基准测试期间被抢占了 200 万次，而在 ULE 中它从未被抢占。这种行为的解释如下：ab 开始时向 httpd 服务器发送 100 个请求，然后等待服务器响应。当 ab 被唤醒时，它检查哪些请求已被处理，并向服务器发送新的请求。由于 ab 是单线程的，发送给服务器的所有请求都是顺序发送的。在 ULE 中，ab 能够发送与其收到的响应一样多的新请求。在 CFS 中，ab 发送的每个请求都会唤醒一个 httpd 线程，该线程会抢占 ab。

6. 负载均衡器的评估¶

在本节中，我们分析了负载均衡和线程放置策略对性能的影响。在 CFS 和 ULE 中，负载均衡会周期性地发生，而线程放置则在线程被创建或唤醒时发生。我们首先分析周期性负载均衡器在机器所有核心上平衡静态工作负载所需的时间。然后，我们分析 CFS 和 ULE 在放置线程时所做的设计选择。接下来，我们比较 37 个应用程序在 CFS 与 ULE 上运行的性能。最后，我们分析多应用工作负载的性能。

6.1 周期性负载均衡¶

CFS 依赖于一个相当复杂的负载度量。它使用一个每 4ms 运行一次的分层负载均衡策略。ULE 只尝试均衡核心上的线程数量。负载均衡发生的频率较低（周期在 0.5s 和 1.5s 之间变化），并且忽略硬件拓扑。我们现在评估这些策略如何影响在机器上平衡负载所需的时间。

为此，我们将 512 个自旋线程（spinning threads）固定在核心 0 上，我们启动一个 taskset 命令来解除这些线程的固定，然后让负载均衡器在核心之间平衡负载。所有线程都执行相同的工作（一个无限的空循环），所以我们期望负载均衡器在 32 个核心中的每个核心上放置 16 个线程。图 6 展示了每个核心上的线程数量随时间的变化。图中，32 条线中的每一条都代表一个给定核心上的线程数量。解除线程固定的 taskset 命令在 14.5s 时启动。

[图6：在 (a) ULE 和 (b) CFS 上，每个核心的线程数随时间的变化。内容已忽略]

在 ULE 上，一旦线程被解除固定，空闲的核心就会从核心 0 窃取线程（每个核心最多一个），因此在解除固定后，核心 0 有 512 - 31 = 481 个线程，而其他每个核心有 1 个线程。随着时间的推移，周期性负载均衡器被触发并试图平衡线程数。然而，由于负载均衡器每次只从核心 0 迁移一个线程，它需要超过 450 次负载均衡器调用或大约 240 秒才能达到平衡状态。

CFS 平衡负载的速度快得多。在解除固定后 0.2 秒，CFS 已经从核心 0 迁移了超过 380 个线程。令人惊讶的是，CFS 从未实现完美的负载均衡。CFS 仅在两个 NUMA 节点之间的不平衡“足够大”（实践中为 25% 的负载差异）时才平衡它们之间的负载。所以一个节点中的核心可以有 18 个线程，而另一个节点中的核心只有 15 个。

虽然 CFS 使用的负载均衡策略非常适合解决系统中的大负载不平衡问题，但当完美的负载均衡对性能至关重要时，它就不那么适合了。

6.2 线程放置¶

我们使用 c-ray（一个来自 phoronix 基准测试套件的图像处理应用程序）来研究线程的放置。C-ray 开始时创建 512 个线程。线程在创建时没有被固定，因此调度器为每个线程选择一个核心。然后所有线程在执行计算前在一个屏障（barrier）上等待。由于所有线程的行为方式相同，我们期望 ULE 在这种配置下表现得比 CFS 更好：ULE 总是将线程 fork 到线程数最少的核心上，所以负载从一开始就应该是完美平衡的。

图 7 展示了每个核心上可运行线程数的演变。在 ULE 中，负载总是平衡的，但令人惊讶的是，ULE 需要超过 11 秒才能使所有线程都变为可运行状态，而 CFS 只需 2 秒。这种延迟是由饥饿解释的。C-ray 使用一个级联屏障，其中线程 0 唤醒线程 1，线程 1 唤醒线程 2，依此类推。线程最初以不同的交互性惩罚创建，一些线程最初是交互式的，而其他线程最初是批处理的（原因与 sysbench 中相同，见第 5.2 节）。当一个批处理线程被唤醒时，它可能会饿死，直到所有交互式线程都完成，或者直到它的惩罚增加到足以让它被降级到批处理运行队列。实际上，在 c-ray 中，线程在屏障之后从不睡眠，所以最终所有线程都变成批处理线程，但是，在它们这样做之前，那些最初被归类为批处理的线程无法唤醒其他线程。因此，需要 11 秒才能使所有线程在屏障后被唤醒。

[图7：c-ray 在 (a) ULE 和 (b) CFS 上每个核心的线程数随时间的变化。内容已忽略]

CFS 则相反，是公平的，所有线程都被迅速唤醒。然后，CFS 会遇到我们在第 6.1 节中解释过的不完美负载均衡问题。

尽管存在这些负载均衡差异，c-ray 在 CFS 和 ULE 上的完成时间相同，因为 c-ray 创建的线程比核心多，并且两个调度器都始终保持所有核心繁忙。抢占在 CFS 上发生得更频繁，但不影响性能。

6.3 性能分析¶

图 8 展示了 CFS 和 ULE 在多核环境下的性能差异。CFS 和 ULE 之间的平均性能差异很小：2.75%，有利于 ULE。

[图8：ULE 相对于 CFS 在多核上的性能。内容已忽略]

MG，来自 NAS 基准测试套件，从 ULE 的负载均衡策略中获益最多：它在 ULE 上比在 CFS 上快 73%。MG 产生的线程数与机器核心数相同，并且所有线程执行相同的计算。当一个线程完成其计算后，它在一个自旋屏障上等待 100ms，如果还有线程在计算，它就会睡眠。ULE 正确地将每个核心放置一个线程，然后就再也不迁移它们了。线程在屏障上等待彼此的时间非常短，并且从不睡眠。相比之下，CFS 会对核心负载的微小变化（例如，由于一个内核线程被唤醒）做出反应，有时会错误地将两个 MG 线程放在同一个核心上。由于 MG 使用屏障，被安排在同一个核心上的两个线程最终会延迟整个应用程序。延迟超过 50%，因为单独在其核心上调度的线程会进入睡眠状态，然后必须被唤醒，从而增加了屏障的延迟。这种次优的线程放置也解释了 CFS 和 ULE 在 FT 和 UA 上的性能差异。ULE 使用的平衡线程数量的简单方法在 HPC 类应用程序上效果更好，因为它最终将每个核心放置一个线程，然后就再也不迁移它们了。

Sysbench，由于 ULE 负载均衡器的开销，在 ULE 上运行得更慢。当一个线程被唤醒时，ULE 会扫描机器的核心来为该线程找到一个合适的核心，在最坏的情况下，可能会扫描所有核心三次。在 sysbench 中，这种最坏情况在大多数唤醒时都会发生，导致所有 CPU 周期的 13% 被用于扫描核心。为了验证这个假设，我们用一个简单的函数替换了 ULE 的唤醒函数，该函数返回线程之前运行的 CPU，然后观察到 ULE 和 CFS 之间没有差异。

在我们测试的所有基准中，13% 是我们在 ULE 中观察到的调度器花费的最高时间，而 2.6% 是我们在 CFS 中观察到的调度器花费的最高时间。请注意，ULE 在 sysbench 中遇到了一个极端情况，但在其他基准测试中开销很低，即使它们产生了大量的线程：例如在 hackbench（32,000 个线程）中，ULE 的开销是 1%（相比之下 CFS 是 0.3%）。

6.4 多应用工作负载¶

最后，我们使用一组不同的应用程序来评估交互式和后台工作负载的组合：c-ray + EP (来自 NAS) 是一个两个应用都被 ULE 视为后台的工作负载，fibo + sysbench 和 blackscholes + ferret 是只有一个应用是交互式的工作负载，而 apache + sysbench 是一个完全交互式的工作负载。图 9 显示了 CFS 和 ULE 的性能，相对于应用程序在机器上单独运行的性能（越高越好）。总的来说，当与另一个应用程序共同调度时，大多数应用程序运行得更慢。

[图9：CFS 和 ULE 在多应用工作负载下的性能，相对于在 CFS 上单独运行时的性能提升。内容已忽略]

当两个应用程序都是非交互式的（c-ray + EP）时，CFS 和 ULE 的表现相似。这是符合预期的，因为它们以相似的方式调度后台线程。EP 在单独执行时在 ULE 上运行得稍快，当它与 c-ray 共同调度时，这个性能差异仍然存在。当两个应用程序都是交互式的时，CFS 和 ULE 的表现也相似。

对于 blackscholes + ferret，ULE 优先考虑交互式应用程序，ferret 不受与 blackscholes 共同调度的影响。然而，Blackscholes 运行速度慢了 80% 以上。在这种情况下，blackscholes 并没有完全饿死，因为 ferret 没有使用所有核心的 100%。CFS 则相反，公平地共享 CPU，两个应用程序都受到同等的影响（共同调度对这些应用程序的影响小于 50%，因为 ferret 和 blackscholes 都不能扩展到 32 个核心）。

令人惊讶的是，当与 fibo 共同调度时，sysbench 在 ULE 上的表现比在 CFS 上差，尽管它被正确地归类为交互式并优先于 fibo 线程。ULE 中缺乏抢占解释了性能差异。MySQL 无法实现完美的扩展性，当在 32 个核心上执行时，锁竞争迫使线程在等待锁释放时睡眠。因此，fibo 不会饿死。当一个 MySQL 锁被释放时，ULE 不会抢占当前正在运行的线程（通常是 fibo）来调度一个新的 MySQL 线程进入临界区。这给 sysbench 的执行增加了延迟（延迟最高可达 fibo 的时间片长度，介于 7.8ms 和 78ms 之间）。

7. 相关工作¶

以前的工作已经比较了 FreeBSD 和 Linux 的设计选择。Abaffy 等人比较了调度器运行队列中线程的平均等待时间。Schneider 等人比较了两个操作系统的网络栈性能。FreeBSD 的设计选择也经常在 Linux 内核邮件列表上被讨论。本研究的方法不同：我们不是比较两个完整的操作系统，而是将 FreeBSD ULE 调度器移植到 Linux。据我们所知，这是第一次对 ULE 和 CFS 的设计进行“苹果对苹果”的比较。

Linux 调度器的设计在以前的工作中也得到了讨论。Torrey 等人将 Linux 调度器的延迟与一个多级反馈队列的自定义实现进行了比较。Wong 等人将 CFS 的公平性与 2.6.23 之前的默认 Linux 调度器 O(1) 调度器以及 RSDL 调度器（旋转楼梯最后期限调度器）进行了比较。Groves 等人将 CFS 的开销与 BFS（Brain Fuck Scheduler）进行了比较，BFS 是一个旨在提高少数核心机器响应性的简化调度器。其他工作研究了调度器的开销。Kanev 等人报告称，仅 CFS 就占了所有数据中心周期的 5% 以上。

操作系统的性能经常通过测量内核版本之间的性能演变来评估。Linux 内核性能项目于 2005 年启动，以测量 Linux 内核中的性能回归。Mollison 等人提出了 Litmus 测试来发现调度器中的性能回归。操作系统中的性能问题也经常在系统社区中被报告。Lozi 等人报告了 Linux 调度器中的错误，这些错误可能导致核心在有工作等待被调度到其他核心时永久空闲。Harji 等人在早期的内核版本中报告了类似的性能错误。在本文的工作中，我们还向 FreeBSD 社区报告了调度器中的错误。在本研究中，我们选择比较 ULE 和 CFS 的“无故障”版本，通过修复那些不是调度器设计特性的明显错误。

8. 结论¶

在多核机器上调度线程是一项艰巨的任务。在本文中，我们对两种广泛使用的调度器——来自 FreeBSD 的 ULE 调度器和来自 Linux 的 CFS——的设计选择进行了公平的比较。我们表明，即使在简单的工作负载上，它们的行为也不同，并且没有哪个调度器在所有工作负载上都比另一个表现得更好。

参考文献¶

[参考文献列表已翻译，但为保持简洁，此处省略具体条目。原始文档中的引用编号和内容均已记录。]