更少的核心，更高的赫兹¶

标题：Fewer Cores, More Hertz: Leveraging High-Frequency Cores in the OS Scheduler for Improved Application Performance

日期：2020/07/15

作者：Redha Gouicem and Damien Carver, Sorbonne University, LIP6, Inria; Jean-Pierre Lozi, Oracle Labs; Julien Sopena, Sorbonne University, LIP6, Inria; Baptiste Lepers and Willy Zwaenepoel, University of Sydney; Nicolas Palix, Université Grenoble Alpes; Julia Lawall and Gilles Muller, Inria, Sorbonne University, LIP6

链接：https://www.usenix.org/conference/atc20/presentation/gouicern

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

备注：这是我给出一些场景然后 GPT 推给我的论文。（其实是我太菜了有一个 bug 不知道怎么解，只能问这问那，甚至跟调度器并没有关系）实际完全对不上我的需求，不看了。

摘要¶

在现代服务器 CPU 中，单个内核可以以不同的频率运行，这允许对性能/能耗的权衡进行细粒度控制。然而，调整频率会产生很高的延迟。我们发现这可能导致一种频率倒置问题，即 Linux 调度器将一个新激活的线程放置在一个空闲的内核上，而这个内核需要几十到几百毫秒才能达到高频率，而就在此之前，另一个已经在高频运行的内核变为空闲。

在本文中，我们首先通过一个案例研究，说明了在一台 80 核 Intel® Xeon 机器上编译 Linux 内核期间调度器行为中，重复出现的频率倒置所带来的显著性能开销。接下来，我们提出了两种策略来减少 Linux 调度器中发生频率倒置的可能性。当在 Intel® Xeon 上对 60 个不同的应用程序进行基准测试时，表现更好的策略 $S_{move}$ 为 23 个应用程序带来了超过 5% 的性能提升（最高 56%，且无额外能耗开销），而仅有 3 个应用程序的性能下降超过 5%（最高 8%）。在一台 4 核 AMD Ryzen 机器上，我们获得了高达 56% 的性能提升。

1. 引言¶

在计算系统的发展中，寻求性能与能耗之间的平衡一直是一场斗争。几十年来，CPU 一直支持动态频率缩放（Dynamic Frequency Scaling, DFS），允许硬件或软件在运行时更新 CPU 频率。降低 CPU 频率可以减少能源使用，但也可能降低整体性能。尽管如此，对于那些经常空闲或不那么紧急的任务来说，性能下降是可以接受的，这使得在许多用例中通过降低频率来节省能源是可取的。

虽然在早期的多核机器上，一个 CPU 的所有内核都必须以相同的频率运行，但最近来自 Intel® 和 AMDR◯ 的服务器 CPU 使得可以更新单个内核的频率。这一特性允许进行更细粒度的控制，但同时也带来了新的挑战。

管理核心频率的挑战之一来自于频率转换延迟（Frequency Transition Latency, FTL）。实际上，将一个内核从低频转换到高频，或反之，其 FTL 长达几十到几百毫秒。FTL 在一些典型场景中会导致频率倒置问题，例如在使用标准的 POSIX fork() 和 wait() 系统调用创建进程时，或在生产者-消费者应用中轻量级线程之间的同步。

问题发生过程如下。首先，一个在内核 $C_{waker}$ 上运行的任务 $T_{waker}$ 创建或唤醒一个任务 $T_{woken}$ 。如果完全公平调度器（Completely Fair Scheduler, CFS），即 Linux 中的默认调度器，找到了一个空闲内核 $C_{CFS}$ ，它会将 $T_{woken}$ 放置在该内核上。此后不久， $T_{waker}$ 终止或阻塞，例如，因为它是一个父进程，在 fork 一个子进程后立即等待，或者因为它是一个线程，在完成生产数据后，作为其进入睡眠前的最后一个动作唤醒了一个消费者线程。现在 $C_{waker}$ 变为空闲状态，但由于直到最近还在运行 $T_{waker}$ ，它仍以高频运行；而运行着 $T_{woken}$ 的 $C_{CFS}$ ，则很可能因为之前处于空闲状态而以低频运行。因此， $C_{waker}$ 和 $C_{CFS}$ 的运行频率与内核上的负载相比发生了倒置。这种频率倒置问题直到 $C_{waker}$ 达到低频且 $C_{CFS}$ 达到高频时才能解决，即会持续整个 FTL 的时间。当前的硬件和软件 DFS 策略，包括最近添加到 CFS 中的 schedutil 策略，都无法防止频率倒置，因为它们的唯一决策就是更新内核频率，从而每次都要付出 FTL 的代价。频率倒置会降低性能，并可能增加能耗。

在本文中，我们首先通过一个在 80 核（160 个硬件线程）的 Intel® Xeon 机器上构建 Linux 内核的真实场景案例研究，展示了频率倒置问题。我们的案例研究发现在通过 fork() 和 wait() 系统调用创建进程时，会反复出现频率倒置，我们的性能分析轨迹清楚地表明，频率倒置导致任务在其执行的相当一部分时间内运行在低频内核上。

基于该案例研究的结果，我们建议在调度器层面解决频率倒置问题。我们的关键观察是，调度器在将任务放置到内核上时，可以通过考虑内核频率来避免频率倒置。为此，我们提出并分析了两种策略。我们的第一种策略 $S_{local}$ 是让调度器简单地将 $T_{woken}$ 放置在 $C_{waker}$ 上，因为频率倒置涉及的内核 $C_{waker}$ 很可能处于高频，并且可能很快变为空闲。该策略提高了内核构建的性能。然而，它也存在风险，即 $T_{waker}$ 可能不会迅速终止或阻塞，导致 $T_{woken}$ 在被调度前需要长时间等待。因此，我们的第二种策略 $S_{move}$ 在将 $T_{woken}$ 放置在 $C_{waker}$ 上时，额外启动一个高精度计时器，如果计时器在 $T_{woken}$ 被调度前到期，那么 $T_{woken}$ 将被迁移到 $C_{CFS}$ ，即 CFS 最初为它选择的内核。此外，当 $C_{CFS}$ 的频率高于最低频率时，即使是轻微延迟 $T_{woken}$ 将其放在 $C_{waker}$ 上也是不值得的。因此， $S_{move}$ 首先检查 $C_{CFS}$ 的频率是否高于最低值，如果是，则直接将 $T_{woken}$ 放置在 $C_{CFS}$ 上。

本文的贡献如下：

识别了频率倒置现象，该现象导致一些空闲内核以高频运行，而一些繁忙内核则在相当长的时间内以低频运行。
一个案例研究，在一台具有独立每核频率的 80 核服务器上构建 Linux 内核。
两种策略， $S_{local}$ 和 $S_{move}$ ，用于在 CFS 中防止频率倒置。实现这些策略仅需微小的代码改动：在 Linux 内核中分别修改了 3 行（ $S_{local}$ ）和 124 行（ $S_{move}$ ）代码。
对我们的策略进行了全面评估，涵盖了 60 个不同的应用程序，包括流行的 Linux 基准测试以及来自 Phoronix 和 NAS 基准测试套件的应用程序。评估同时考虑了当前 Linux 默认使用的 powersave CPU 调节器和实验性的 schedutil 调节器。评估还涉及两台机器：一台大型的 80 核 Intel® Xeon E7-8870 v4 服务器和一台小型的 4 核 AMD Ryzen 5 3400G 台式机。

在使用 powersave 调节器的服务器上，我们发现 $S_{local}$ 和 $S_{move}$ 总体表现良好：在评估的 60 个应用程序中， $S_{local}$ 和 $S_{move}$ 分别使 27 个和 23 个应用程序的性能提高了 5% 以上，而仅使 3 个应用程序的性能下降了 5% 以上。在最佳情况下， $S_{local}$ 和 $S_{move}$ 分别将应用程序性能提高了 58% 和 56%，且没有额外的能耗开销。然而， $S_{local}$ 在两个应用程序上表现非常差，最坏情况下甚至导致性能下降 80%，这对于一个通用调度器来说可能是不可接受的。 $S_{move}$ 在最坏情况下的表现要好得多：应用程序执行时间的增加仅为 8%，并且通过能耗方面 9% 的改善得到了缓解。使用 schedutil 的评估结果表明，该调节器并未解决频率倒置问题，并且在更多情况下 $S_{local}$ 表现非常差，而 $S_{move}$ 再次展现了更好的最坏情况性能。在台式机上的评估显示了类似的趋势，尽管规模较小。同样，在极端情况下， $S_{move}$ 的表现优于 $S_{local}$ 。

2. 一个案例研究：构建 Linux 内核¶

我们展示一个工作负载的案例研究，该研究引导我们发现了频率倒置现象：在一台 4 插槽 Intel® Xeon E7-8870 v4 机器上使用 320 个作业（-j 320）构建 Linux 内核 5.4 版本。该机器拥有 80 个核心（160 个硬件线程），标称频率为 2.1 GHz。得益于 Intel® SpeedStep 和 Turbo Boost 技术，我们的 CPU 可以独立地改变每个核心的频率，范围在 1.2 到 3.0 GHz 之间。一个核心的两个硬件线程频率是相同的。在本文的其余部分，为简单起见，我们使用“核心”一词来指代硬件线程。

[图 1 已忽略] 图 1：使用 320 个作业构建 Linux 内核 5.4 版本的执行轨迹。

图 1 展示了内核构建工作负载运行时，机器上每个核心的频率。该图是使用我们开发的两个工具 SchedLog 和 SchedDisplay 生成的。SchedLog 以极低的开销收集应用程序的执行轨迹。SchedDisplay 则生成这种轨迹的图形化视图。我们使用 SchedDisplay 生成了本文中所有的执行轨迹。SchedLog 记录了图 1 中显示的频率信息，在每个时钟节拍事件（CFS 中为 4ms）时记录一次。因此，这类轨迹中缺少彩色线条意味着 CFS 在该核心上禁用了时钟节拍。CFS 在不活跃的核心上禁用时钟节拍，以允许它们切换到低功耗状态。

在图 1 中，我们注意到执行过程中的不同阶段。在大约 2 秒时的一个短周期，在 4.5 秒到 18 秒之间的一个较长周期，以及大约 28 秒时的一个短周期，内核构建过程处于高度并行的阶段，所有核心都以高频率运行。这三个阶段中的第二个对应于编译的主体部分。在这三个阶段中，CPU 似乎被利用到了极限。此外，在 22 秒到 31 秒之间，有一个很长的阶段，大部分是顺序代码，只有很少的活跃核心，其中总有一个以高频率运行。在这个阶段，瓶颈是 CPU 的单核性能。

然而，在 0 到 4.5 秒之间，以及 18 到 22 秒之间，存在一些阶段，所有核心都被使用，但它们都以 CPU 的最低频率（1.2 GHz）运行。仔细观察后发现，这些阶段实际上主要是顺序执行的：放大后显示，虽然在整个阶段持续时间内所有核心都被使用过，但在任何给定时间点，只有一到两个核心在工作。这引出了两个问题：为什么一个近乎顺序的执行会使用这么多核心，以及为什么这些核心以如此低的频率运行。

我们关注开始的几秒钟，这部分的核心利用率似乎不是最优的。放大到 1 秒附近，我们首先查看运行队列大小和调度事件，如图 2a 所示。我们看到一种典型的、大部分为顺序执行的 shell 脚本的模式：进程通过 fork() 和 exec() 系统调用创建，并且通常一个接一个地执行。这些进程在图 2a 中很容易识别，因为它们以 WAKEUP_NEW 和 EXEC 调度事件开始。在核心 56 上的进程于 0.96 秒左右阻塞后，三个这样的短生命周期进程相继在核心 132、140 和 65 上执行。之后，两个运行时间较长的进程，一个在 0.98 秒左右运行于核心 69，另一个在 0.98 秒到 1.00 秒之间运行于核心 152。这种模式在图 2a 所示的整个执行期间持续进行，任务相继在核心 148、125、49、52、129、156、60 以及最后的 145 上创建。

[图 2 已忽略] 图 2：图 1 稀疏区域的放大图。

查看执行同一部分的内核频率，如图 2b 所示，为我们提供了一个线索，解释了为什么在这个阶段内核运行缓慢：从任务开始在内核上运行到内核频率开始增加之间似乎存在显著的延迟。例如，在 1.00 秒到 1.02 秒之间，核心 49 上的任务以低频率运行，只有当它在大约 1.04 秒结束时，该核心的频率才上升到最大值——然后在硬件注意到该核心上没有任务运行后几乎立即开始再次下降。同样的问题可以在 1.00 秒前不久的核心 152 上，以及 0.98 秒左右的核心 69 上观察到。在最后一个例子中，当任务开始时，该核心的频率甚至处于下降趋势，并且在任务结束后频率继续下降，直到 1.00 秒左右才最终再次上升。

看来，在所考虑的执行阶段，FTL 远高于任务的持续时间。由于相继执行的任务倾向于被调度到不同的核心上，它们很可能总是以低频率运行，因为在这个执行阶段，大多数核心大部分时间都处于空闲状态。

为了证实我们关于 FTL 的直觉，我们开发了一个细粒度的工具来监控单个核心在执行一个孤立的忙循环时的频率，使用的是 powersave 调节器。

[图 3 已忽略] 图 3：Xeon E7-8870 v4 CPU 的 FTL。

如图 3 所示，任务运行了 0.20 秒，如图中的起始和结束垂直线所示。为了适应这个任务，核心从最低频率 1.25 GHz 上升到最高频率 3.00 GHz 需要 29 毫秒的 FTL。当任务结束时，核心大约需要 10 毫秒恢复到其初始频率，但 FTL 的持续时间因频率在大约 98 毫秒内多次反弹后才稳定在核心的最低频率而变得更加复杂。这些测量结果与我们对图 2b 的解释一致：几十毫秒的 FTL 明显长于图中可见任务的执行时间，因为最长的任务在 1.00 秒和 1.02 秒之间运行了大约 20 毫秒。请注意，FTL 的持续时间主要是由于硬件检测负载变化然后决定改变频率所需的时间。先前的工作表明，在 Intel® CPU 上，核心改变频率的实际延迟只有几十微秒。

回到图 2a，我们一直观察到的现象如下。（近乎）顺序的 Linux 构建阶段中的计算任务是通过 fork() 和 wait() 系统调用顺序启动的进程，这些计算的执行时间比 FTL 要短。因此，核心在完成一次计算后会加速，尽管此时计算已经转移到新派生的进程上，而如果机器不是很忙，这些进程很可能运行在最近未被使用的核心上。确实，CFS 经常为任务唤醒选择不同的核心，如果大多数核心是空闲的，那么被选中的核心很可能最近没有被使用，因此以低频率运行。发起 fork() 的任务此后不久会执行 wait() 操作，这意味着它们引发的频率增加大部分被浪费了。我们正面临反复出现的频率倒置，这是由一个非常常见的场景引起的：启动一系列顺序进程，就像在 shell 脚本中常做的那样。

通过 fork() 和 wait() 系统调用顺序创建进程并不是导致反复频率倒置的唯一原因。这种现象也可能发生在轻量级线程之间相互唤醒和阻塞的情况下，这在生产者-消费者应用中很常见。实际上，CFS 中为新任务选择唤醒核心的代码也被用来为已经存在的、被唤醒的任务选择核心。注意，CFS 不会根据任务类型（即进程或线程）使用不同的代码路径。

3. 防止频率倒置的策略¶

由于频率倒置是调度决策的结果，我们认为必须在调度器层面解决它。根据我们的经验，对调度器的任何更改都可能对某些工作负载产生不可预测的后果，更改越复杂，后果就越不可预测。因此，提出对调度器进行广泛或复杂的更改，或完全重写，将使得性能提升的来源不明确。力求最小化、简单的更改可以与 CFS 进行公平的比较。

我们提出两种策略来解决频率倒置问题。第一种是一个简单的策略，性能良好，但在某些调度场景下会遭受严重的性能下降。第二种解决方案旨在获得与第一种解决方案相同的好处，同时以牺牲一些简单性为代价，最小化最坏情况的发生。

3.1 将线程本地放置¶

我们提出的第一个防止频率倒置的策略是 $S_{local}$ ：当一个线程被创建或唤醒时，它被放置在创建或唤醒它的进程所在的同一个核心上。在通过 fork() 和 wait() 系统调用创建单个进程的背景下，这个策略意味着被创建的进程更有可能运行在高频核心上，因为由于父进程的活动，该核心的频率可能已经很高。此外，如果父进程此后不久调用 wait()，那么两个进程在同一个核心上运行的时间将是有限的。

在生产者-消费者应用的背景下，当一个生产者线程唤醒一个消费者线程时，这个策略同样意味着消费者线程更有可能运行在高频核心上，并且如果生产者的最后一个动作是在阻塞或终止前唤醒消费者，那么两个进程在同一个核心上运行的时间也将是有限的。

然而，在某些情况下 $S_{local}$ 可能会损害性能：如果创建或唤醒另一个任务的任务没有迅速阻塞或终止，那么被创建或唤醒的任务将等待 CPU 资源一段时间。这个问题可以通过 Linux 调度器的周期性负载均衡器得到缓解，它会将其中一个任务迁移到另一个负载较低的核心。然而，等待下一次负载均衡事件可能相当长。在 CFS 中，周期性负载均衡是分层执行的，具有不同的周期：同一缓存域内的核心比不同 NUMA 节点上的核心更频繁地进行均衡。在大型机器上，这些周期可以从 4 毫秒到几百毫秒不等。

$S_{local}$ 通过完全替换其线程放置策略，显著改变了 CFS 的行为。此外，前述的缺点使其成为某些工作负载的高风险解决方案。这两个问题都使得这个解决方案不满足我们之前设定的先决条件。

3.2 延迟线程迁移¶

为了在不等待周期性负载均衡的情况下解决核心过载问题，我们提出了第二种策略， $S_{move}$ 。在原版 CFS 中，当一个线程被创建或唤醒时，CFS 决定它应该在哪个核心上运行。 $S_{move}$ 推迟使用这个选定的核心，以允许被唤醒的线程利用一个更有可能以高频率运行的核心。

让 $T_{woken}$ 是新创建或被唤醒的任务， $C_{waker}$ 是创建或唤醒 $T_{woken}$ 的任务 $T_{waker}$ 所在的核心， $C_{CFS}$ 是 CFS 选择的目标核心。调度器的正常行为是直接将任务 $T_{woken}$ 入队到 $C_{CFS}$ 的运行队列中。我们建议延迟这次迁移，以便在 $C_{CFS}$ 以低频率运行时， $T_{woken}$ 更有可能使用高频核心。

首先，如果 $C_{CFS}$ 的运行频率高于 CPU 的最低频率，我们将 $T_{woken}$ 入队到 $C_{CFS}$ 的运行队列。否则，我们启动一个高精度定时器中断，它将在 $D \mu s$ 后执行迁移，并将 $T_{woken}$ 入队到 $C_{waker}$ 的运行队列。如果 $T_{woken}$ 在 $C_{waker}$ 上被调度，该定时器将被取消。

$S_{move}$ 的基本原理是，如果任务可以被快速执行（当本地放置在一个很可能以高频运行的核心上时），我们希望避免唤醒低频核心。确实，在放置时 $T_{waker}$ 正在运行，这意味着 $C_{waker}$ 很可能以高频运行。

延迟 D 可以在运行时通过写入 sysfs 伪文件系统中的一个参数文件来更改。我们选择的默认值为 $50 \mu s$ ，这接近于我们 Linux 内核构建实验中 fork 和 wait 系统调用之间的延迟。我们发现，将此参数的值在 $25 \mu s$ 和 1 ms 之间变化，对第 4 节中使用的基准测试影响甚微。

4. 评估¶

本节旨在证明我们的策略在大多数工作负载上提高了性能，同时不降低能源消耗。我们运行了来自 Phoronix 基准测试套件、NAS 基准测试套件的各种应用程序，以及其他应用程序，如 hackbench（Linux 内核调度器社区中一个流行的基准测试）和 sysbench OLTP（一个数据库基准测试）。这些实验在一台服务器级的 4 插槽 NUMA 机器上进行，该机器配备了 80 核 Intel® CPU，以及一台配备了 4 核 AMDR◯ CPU 的台式机上。

[表 1 已忽略] 表 1：我们实验机器的配置。

两款 CPU 都可以为每个核心选择独立的频率。我们在最新的 LTS 内核，即 2019 年 11 月发布的 Linux 5.4 中实现了 $S_{local}$ 和 $S_{move}$ ，并将我们的策略与 Linux 5.4 进行比较。实现 $S_{local}$ （或 $S_{move}$ ）只需要修改 CFS 中的 3 行（或 124 行）代码。我们所有实验都运行 10 次。

在两台机器上，能源消耗都使用 Intel® RAPL 功能进行评估，该功能测量 CPU 插槽和 DRAM 的能源消耗。性能结果是每个基准测试报告的结果，因此它们涉及不同的指标，如执行时间、吞吐量或延迟，单位不一致。为了更好的可读性，以下所有图表都显示了与使用 CFS 的运行均值相比，在性能和能源使用方面的改进。因此，数值越高总是越好，无论测量的单位是什么。CFS 的结果均值以基准测试的单位显示在图表的顶部。

在 Linux 中，频率由一个称为调节器（governor）的子系统控制。在现代 Intel® 硬件上，powersave 调节器将频率的选择委托给硬件，因为硬件可以进行更细粒度的调整。硬件频率选择算法试图在对性能影响最小的情况下节省能源。硬件根据各种启发式方法（如已退役指令的数量）来估计核心的负载。这是大多数 Linux 发行版上 Intel® 硬件的默认调节器。

schedutil 调节器，自 Linux 4.7（2016 年 7 月）以来由 Linux 社区开发，试图将控制权交还给操作系统。它使用内核调度器 CFS 的内部数据来估计每个核心的负载，并相应地改变频率。Linux 中还有另外两个调节器，performance 和 ondemand，但我们不感兴趣：前者让所有核心以最高频率运行，从而禁用了动态缩放，而后者在现代 Intel® 处理器上不受支持。为了证明我们的工作与所使用的调节器是正交的，我们使用 powersave 和 schedutil 来评估我们的策略。

我们首先展示在 Intel® 服务器上的完整结果，并总结在 AMD 台式机上的结果。然后我们重新审视我们的内核构建案例研究，并研究一些最坏情况的结果（mkl，hackbench）。最后，我们讨论我们 $S_{move}$ 策略的开销。

4.1 使用 powersave 的执行¶

我们首先考虑在 powersave 下的执行。

[图 4a 已忽略] 图 4a：与使用 powersave 调节器的 CFS 进行比较。

我们认为不超过 5% 的改进或恶化与 CFS 相当。

性能。 $S_{local}$ 和 $S_{move}$ 总体表现良好，在 60 个应用程序中分别有 27 个和 23 个优于 CFS。这些策略的最佳结果，如预期的那样，出现在广泛使用 fork/wait 模式并因此表现出大量频率倒置的基准测试上。在最好的情况下， $S_{local}$ 和 $S_{move}$ 在 perl-benchmark-2 上分别获得了高达 58% 和 56% 的增益，该基准测试测量 perl 解释器的启动时间。这个基准测试从避免频率倒置中获益良多，因为它主要由 fork/wait 模式组成。在性能损失方面，两种策略都只恶化了 3 个应用程序的性能，但规模差异很大。 $S_{local}$ 使 mkl-dnn-7-1 的性能恶化了 80%，nas_lu.B-160 恶化了 17%，而 $S_{move}$ 的最坏情况恶化仅为 hackbench 上的 8.4%。

能源消耗。总体而言， $S_{local}$ 和 $S_{move}$ 都改善了能源使用。在我们 60 个应用程序中，与 CFS 相比，我们分别为 16 个和 14 个应用程序的能源消耗改善了 5% 以上。大多数改进都出现在性能也得到改善的基准测试上。在这些情况下，能源节省可能主要归因于应用程序较短的执行时间。然而，我们也在一些性能与 CFS 相当的应用程序上看到了一些改进。这是因为我们避免了唤醒处于低功耗状态的核心，从而节省了启动和运行这些核心所需的能源。在损失方面， $S_{local}$ 仅在一个应用程序 nas_lu.B-160 上比 CFS 消耗更多能源。这种损失是由 $S_{local}$ 在该应用程序上的糟糕性能解释的。该基准测试的指标是其执行时间，增加执行时间而没有相应地降低频率会增加能源消耗。 $S_{move}$ 在两个应用程序上比 CFS 消耗更多能源：hackbench，因为性能损失；以及 deepspeech，其结果的标准差过高，不具有显著性。

总体得分。为了比较我们策略的总体影响，我们计算所有运行的几何平均值，其中每次运行都相对于 CFS 的平均结果进行归一化。 $S_{move}$ 的性能提高了 6%，能源使用减少了 3%，两项指标结合后提高了 4%。 $S_{local}$ 的总体得分相似（均为 5%），但其最坏情况表明，对于通用调度器而言， $S_{move}$ 是一个更好的选择。这些微小的差异是预料之中的，因为我们评估的大多数应用程序在使用 CFS 和我们的策略时表现相似。我们还使用 t-检验评估了我们结果的统计显著性。p 值最多为 $3 \cdot 10^{-20}$ ，我们认为我们的结果具有统计显著性。

4.2 使用 schedutil 的执行¶

接下来，我们考虑在 schedutil 调节器下的执行。

[图 5 已忽略] 图 5：在服务器上，使用 CFS 的 schedutil 与 powersave 的性能比较。

作为基准，图 5 首先显示了 schedutil 调节器与 powersave 调节器在使用 CFS 时的性能和能源改进。总体而言，我们观察到 schedutil 调节器恶化了大多数应用程序的性能，同时改善了能源使用。这表明这个新的调节器在节能方面比硬件中实现的调节器更具侵略性。我们省略了原始值，因为它们已经在图 4a 和 4b 中提供。

[图 4b 已忽略] 图 4b：与使用 schedutil 调节器的 CFS 进行比较。

图 4b 展示了在使用 schedutil 调节器时，我们的策略与 CFS 相比在性能和能源消耗方面的改进。

性能。 $S_{local}$ 和 $S_{move}$ 在 60 个应用程序中分别有 22 个和 20 个优于 CFS。受影响的应用程序与使用 powersave 调节器时得到改善的应用程序相同。然而，在性能损失方面， $S_{local}$ 受 schedutil 调节器的影响比 $S_{move}$ 更大，有 7 个应用程序表现比 CFS 差，而 $S_{move}$ 只有 2 个。

能源消耗。schedutil 与 CFS 结合在能源使用方面的总体改善表明，我们可能会在 $S_{local}$ 和 $S_{move}$ 上看到相同的趋势。事实上，结果与我们在 powersave 调节器上观察到的非常相似。

总体得分。使用该调节器的几何平均值如下，对于 schedutil 和 $S_{move}$ ：性能 6%，能源 4%，两项指标结合后为 5%。 $S_{local}$ 的结果相似（分别为 2%，6% 和 4%），但最坏情况对于通用调度器来说仍然过于有害。这些结果也具有统计显著性，p 值最多为 $3 \cdot 10^{-20}$ 。

4.3 在台式机上的评估¶

我们还在表 1 中介绍的较小的 4 核 AMD® 台式 CPU 上评估了我们的策略。与 Intel® CPU 不同，AMD® CPU 上的 powersave 调节器总是使用最低可用频率，这在我们的情境下是不可用的。因此，我们在这台机器上使用 schedutil 调节器。

[图 6 已忽略] 图 6：在台式机上相对于 Linux 5.4 的性能改进（越高越好）。

如图 6 所示，我们观察到与我们的服务器机器上相同的总体趋势。 $S_{local}$ 和 $S_{move}$ 在有改进时表现相似，而 $S_{move}$ 在少数性能下降的基准测试上表现更好。我们测得 $S_{move}$ 最坏情况下降 11%，最好情况提速 52%，综合性能提升 2%。此外， $S_{move}$ 使 7 个应用程序的性能提高了 5% 以上，而仅使 4 个应用程序的性能下降了相同的幅度。 $S_{local}$ 策略在改进和下降的应用程序数量上给出了相同的结果，但遭遇了更差的边缘情况。其最佳性能改进为 42%，而最坏恶化为 25%，综合性能提升 1%。我们得出结论，即使没有重大的全局改进， $S_{move}$ 仍然是在核心数较少的机器上消除频率倒置的好策略。我们的性能结果具有统计显著性， $S_{move}$ 的 p 值为 $5 \cdot 10^{-4}$ ， $S_{local}$ 的 p 值为 $3 \cdot 10^{-2}$ 。

在能源消耗方面， $S_{local}$ 和 $S_{move}$ 与 CFS 相比似乎影响很小或没有影响。然而，我们用这三种策略收集到的测量值具有很大的方差，这在我们的 Intel® CPU 上没有观察到。我们怀疑这是由于 AMD® 处理器上可用的与能源相关的硬件计数器，或缺乏对这些计数器的良好软件支持所致。

4.4 深入分析¶

我们现在对一些在使用我们的解决方案时表现特别好或特别差的特定基准测试进行详细分析。在本节中，所有轨迹都是使用 powersave 调节器获得的。

kbuild

[图 7 已忽略] 图 7：使用 320 个作业构建 Linux 内核 5.4 版本的执行轨迹。

图 7 显示了如案例研究中介绍的 Linux 内核构建的执行情况，分别使用 CFS（上）和 $S_{move}$ （下）。在 CFS 上，多个核心以低频运行的（0-2 秒，2.5-4.5 秒，17-22 秒）大部分顺序阶段中， $S_{move}$ 使用更少的核心，但频率更高。这主要是由于 fork()/wait() 模式：当唤醒线程在 fork() 后不久调用 wait() 时， $S_{move}$ 计时器不会到期，被唤醒的线程仍然留在本地核心上以高频运行，从而避免了频率倒置。因此，例如，在长的并行阶段之前的阶段，在 CFS 上执行需要 4.4 秒，而使用 $S_{move}$ 只需 2.9 秒。

[图 8 已忽略] 图 8：使用 320 个作业构建 Linux 内核 5.4 sched 目录的执行轨迹。

为了更好地理解 $S_{move}$ 的影响，图 8 显示了 kbuild-sched-320 基准测试，该测试仅构建 Linux 内核的调度器子系统。在这里，并行阶段比完整构建短得多，因为要编译的文件更少，使得执行的顺序阶段更加明显。我们再次看到，使用的核心更少，但频率更高。

mkl

mkl-dnn-7-1 基准测试是 $S_{local}$ 的最坏情况场景：所有线程不断地阻塞和唤醒，因此避免了周期性负载均衡，并继续返回到同一组核心。因此，与另一个线程共享一个核心的线程在使用 $S_{local}$ 策略时会倾向于留在那里。

[图 9 已忽略] 图 9：mkl-dnn-7-1 执行期间每个核心的线程数。

图 9 显示了在使用 powersave 调节器的所有三种调度器下，每个核心运行队列中的线程数。黑线表示运行队列中有一个线程，红线表示有一个以上。CFS 迅速将线程分散到所有核心，并在不到 0.2 秒的时间内实现每个核心一个线程的平衡状态。另一方面， $S_{local}$ 试图最大化核心重用，并使 36 个核心过载。这导致永远无法使用所有核心，最多只能达到 85% 的 CPU 利用率，且多个核心过载。这是对工作守恒属性的持续违反，即如果一个核心的运行队列中有多个线程，则不应该有任何核心是空闲的。有趣的是，在我们的实验中，传播线程的均衡操作是由于系统或守护进程线程（例如 systemd）唤醒并立即阻塞，从而触发了调度器的空闲均衡。在一台后台没有任何东西运行的机器上，我们可能会长时间处于过载状态，因为空闲核心上的时钟节拍被停用，从而减少了周期性均衡的机会。我们可以在 nas-lu.B-160 上看到相同的模式，这是另一个与 $S_{local}$ 不兼容的基准测试。 $S_{move}$ 通过在一个可配置的延迟后，将使核心过载的线程迁移到可用的空闲核心来解决这个问题。

hackbench

hackbench-10000 基准测试是 $S_{move}$ 策略性能最差的应用程序。这个微基准测试对调度器的压力特别大，有 10,000 个正在运行的线程。然而，它所展现的模式对于更好地理解 $S_{move}$ 的缺点很有趣，并为如何改进我们的策略提供了见解。

该基准测试有三个阶段：线程创建、通信和线程终止。

[图 10 已忽略] 图 10：执行 hackbench 时的核心频率。

图 10 显示了在使用 CFS、 $S_{local}$ 和 $S_{move}$ 执行 hackbench 期间所有核心的频率。第一阶段对应于所有三种调度器上的前两秒。一个主线程使用 fork() 系统调用创建 10,000 个线程，所有子线程立即在一个屏障上等待。使用 CFS，子线程被放置在空闲核心上，当线程到达屏障时，这些核心再次变为空闲。这意味着所有核心大部分时间保持空闲。这也导致主线程在此阶段停留在同一个核心上。然而， $S_{local}$ 和 $S_{move}$ 将子线程本地放置，导致主线程核心的过载和负载均衡器的迁移。因此，主线程本身有时也会从一个核心迁移到另一个核心。

当所有线程创建完毕后，主线程释放等待在屏障上的线程并等待它们终止，从而开始第二阶段。在此阶段，子线程通过在管道中读写进行通信。CFS 试图在所有核心之间平均分配负载，但其启发式方法对跨 NUMA 节点的迁移给予了巨大的惩罚，因此单个节点以高频率运行（在我们的机器上，核心 0、4、8 等共享同一个节点），而其他节点工作很少，以较低频率运行。此阶段在 2.8 秒时结束。执行的其余部分是主线程回收其子线程并终止。

$S_{local}$ 积极地打包线程，导致第二阶段出现长运行队列，并因此由于引起的巨大过载而促进了跨节点的负载均衡。然而， $S_{local}$ 仍然没有使用所有核心，主要是避免在核心的超线程对上运行（在我们的机器上，核心 n 和 n+80 是超线程的）。 $S_{local}$ 运行第二阶段比 CFS 快，在 2.5 秒时终止，因为它一直以高频率使用一半的核心，并且许多其他核心以中等频率运行。

另一方面， $S_{move}$ 在第二阶段表现不佳，在 3.4 秒时完成。其行为似乎与 CFS 非常接近，每四个核心中有一个以高频率运行。然而， $S_{move}$ 在其他核心上导致了更多的空闲或低频。这是由于 $S_{move}$ 将线程本地放置：许多线程争夺本地核心；一些能够使用资源，而另一些在计时器中断触发时被迁移。与 CFS 相比，延迟导致了空闲，迁移使核心空闲，与 $S_{local}$ 相比降低了它们的频率。此外，当线程因计时器到期而被迁移时，它们都被放置在同一个核心上，使其过载。对于 hackbench 来说，选择中间路线是最差的策略。我们还可以注意到，由于此工作负载的高度易变性，负载均衡无法缓解这种情况。

hackbench 的这种设置是一种极端情况，在现实生活中不太可能发生，即机器严重过载（10,000 个线程）且应用程序高度易变。这个微基准测试仅用于研究我们策略的行为。尽管如此，总体而言， $S_{move}$ 的性能优于 $S_{local}$ 。

4.5 S_move 的调度开销¶

$S_{move}$ 比 $S_{local}$ 更复杂，因此我们分析了它与 CFS 相比的开销，作为我们策略的上限。我们确定了两个可能的开销来源：查询频率和使用计时器。

首先，我们评估查询核心频率的成本。查询核心频率主要包括读取两个硬件寄存器并执行一些算术运算，因为当前频率是这两个寄存器相除再乘以 CPU 的基础频率。尽管与调度器的其余部分相比，这是非常小的计算量，但我们通过在每个时钟节拍而不是每次需要时查询此信息来进一步最小化它。在我们的基准测试中，我们注意到在每个时钟节拍查询频率或不查询时，性能没有差异。

其次，我们评估在调度器中触发大量计时器的成本。为此，我们在两个版本的 Linux 上运行 schbench：原版 5.4 内核和一个修改版，其中计时器在与 $S_{move}$ 相同的条件下启动。然而，在这里，计时器处理程序不像在 $S_{move}$ 中那样迁移线程。我们选择 schbench 是因为它执行与 hackbench 相同的工作负载，但作为性能评估，它提供通过管道发送的消息的延迟，而不是完成时间。

[表 2 已忽略] 表 2：schbench 延迟（99.5 百分位数，单位 µsec）和触发的计时器数量。

表 2 显示了此基准测试的结果。总体而言，两个版本的内核的 99.5 百分位数延迟是相同的，除了 256 个线程时，计时器有负面影响。我们还可以观察到，触发的计时器数量随着线程数的增加而增加，但在 256 个线程后下降。这种行为是预期的：更多线程意味着更多唤醒，但当机器开始过载时，所有核心都以高频率运行，计时器启动的频率降低。这个转折点大约在 256 个线程时出现，因为 schbench 线程不断阻塞，这意味着通常少于 160 个线程是可运行的。

5. 讨论¶

如前所述，我们提出的解决方案 $S_{local}$ 和 $S_{move}$ 是有意为之的简单。我们现在讨论其他更复杂的解决频率倒置问题的方法。

高频核心池。一个可能的解决方案是保持一个核心池以高频运行，即使没有线程在上面运行。这将允许线程被立即放置在一个以高频运行的空闲核心上。然而，这个池可能会浪费能源，并降低繁忙核心可达到的最高频率，因为当活跃核心数量增加时，最高频率会降低。
调整放置启发式。我们可以向现有的放置策略中添加一个新的频率启发式。然而，使用一个运行在更高频率的核心与例如缓存局部性之间的权衡并不清楚，并且可能会根据工作负载和架构有很大差异。
频率模型。一个核心的频率对其他核心性能的影响是硬件特定的。如果调度器要做出与频率相关的决策，它还需要考虑其决策对所有核心频率的影响。目前还没有这样的模型，并且创建起来会很复杂。

6. 相关工作¶

动态频率缩放。使用 DFS 来减少能源使用已经被研究了二十多年。Weiser 等人是第一个提出根据 CPU 负载调整频率的，旨在最大化每焦耳百万指令数（MIPS/Joule）指标。此后，在 2000 年代初，Chase 等人以及 Elnozahy 等人提出降低在表现出工作负载集中的服务器集群中未充分利用的服务器的频率。Bianchini 和 Rajamony 在 2004 年的一篇综述中总结了这些早期工作。如今，在硬件方面，大多数 CPU 都支持 DFS，最新的系列具有精密的硬件算法，能够为同一芯片上的核心动态选择非常不同的频率，例如 Enhanced Intel SpeedStep® 和 AMD® SenseMI 等技术。尽管近年来 DFS 逻辑从软件端转向硬件端，但在 Linux 中开发实验性的 schedutil 调节器的决定是基于这样一个理念：软件在 DFS 中仍有作用，因为它更了解正在执行的负载。同样，我们的策略表明，由于 FTL 的存在，软件将任务放置在高频核心上可能比等待硬件在任务放置后提高核心频率更有效率。

追踪低效的调度器行为。Linux 内核附带的 Perf 支持通过 perf sched 命令监控调度器行为。虽然 perf sched 可以在简单的工作负载上以高精度分析调度器行为，但它在 Linux 内核构建和其他真实世界工作负载上会产生显著的开销。Lozi 等人识别了 Linux 调度器中的性能缺陷。为了分析它们，他们编写了一个基本的分析器，监控每个核心的排队线程数和负载。他们的基本分析器不监控调度事件。我们在本文中使用的 SchedLog 和 SchedDisplay，可以以低开销记录所有调度事件的相关信息，并通过强大且可脚本化的图形用户界面高效地浏览大量记录数据。Mollison 等人将回归测试应用于调度器。他们的重点仅限于实时调度器，并且没有考虑 DFS。更普遍地，一直有努力在测试和理解 Linux 调度器对性能的影响。自 2005 年以来，LKP 项目一直致力于寻找性能回归，社区也提出了大量可以识别内核中性能缺陷的工具。然而，这些工具的重点是检测内核代码内部的减速，而不是由内核决策引起的应用程序代码减速。因此，它们无法检测到糟糕的调度行为。

改进调度器行为。大多数先前的工作都集中于通过改进特定性能指标的新策略来改进通用操作系统调度，例如减少共享资源的争用、优化 CPU 缓存的使用、改善 NUMA 局部性或最小化空闲。这些论文在实验中系统地禁用了 DFS。Merkel 等人提出了一种调度算法，通过共同调度使用互补资源的应用程序来避免资源争用。他们通过降低执行不吉利工作负载的核心的频率来减少争用。Zhang 等人提出了一种用于多核架构的调度策略，以促进 DFS，尽管他们的主要重点是减少缓存干扰。他们只考虑了每芯片 DFS，因为当时每核心 DFS 还不普遍。Linux 内核开发人员最近关注 DFS 和睿频（turbo frequencies），因为发现一个在先前空闲核心上运行的短暂抖动进程可以使该核心切换到睿频，这反过来又可能降低其他核心使用的频率——即使在抖动进程完成后也是如此。为了解决这个问题，提出了一个补丁来明确标记抖动任务。调度器然后尝试将这些标记的任务放置在活跃并预期保持活跃的核心上。相比之下，我们识别的频率倒置问题并非由睿频特定引起：它可以在任何不同核心可能以不同频率运行的 DFS 策略中发生。

子进程优先运行。CFS 有一个可能看起来与我们的解决方案相关的功能：sched_child_runs_first。在线程创建时，此功能为子线程分配一个较低的 vruntime，使其优先级高于其父线程。如果 CFS 将线程放置在其父线程的同一个核心上，该线程将抢占父线程；否则，该线程只会在其他地方运行。此功能不影响线程放置，因此无法解决频率倒置问题。将此功能与 $S_{move}$ 结合使用会通过总是取消计时器而挫败 $S_{move}$ 的目的。该策略将类似于 $S_{local}$ ，只是子线程总是会抢占其父线程。

7. 结论¶

在本文中，我们识别了 Linux 中的频率倒置问题，该问题发生在具有每核心 DFS 的多核 CPU 上。频率倒置导致任务在低频核心上运行，并可能严重降低性能。我们在 Linux 5.4 CFS 调度器中实现了两种策略来防止此问题。实现这些策略只需少量代码更改：它们可以轻松移植到其他版本的 Linux 内核。在一组包含 60 个多样化应用程序的测试中，我们表明我们更好的解决方案 $S_{move}$ 经常显著提高性能。此外，对于不表现出频率倒置问题的应用程序， $S_{move}$ 在 3 个被评估的应用程序上仅引起 8% 或更小的性能损失。随着独立核心频率缩放成为最新一代处理器的标准功能，我们的工作将面向更多的机器。

在未来的工作中，我们希望通过将核心频率直接纳入放置算法来改进调度器中的线程放置。这项改进需要考虑各种参数，如特定于架构的 DFS、同时多线程以及维持缓存局部性。

致谢和可用性¶

这项工作部分得到了 Oracle 捐赠 CR 1930 的支持。我们还要感谢匿名审稿人和我们的指导者 Heiner Litz 的反馈。

$S_{local}$ 和 $S_{move}$ 的 Linux 5.4 补丁可在以下网址获取： https://gitlab.inria.fr/whisper-public/atc20