The Linux Scheduler: a Decade of Wasted Cores 译文 一

摘要

​ 作为资源管理的核心部分，OS的线程调度器必须保持下面这样简单，不变的特性: 确保ready状态的线程总是被调度到有效的CPU核上。虽然它看起来是简单的，我们发现这个不变性在Linux上经常被打破。当ready状态的线程在runqueue中等待时，有些CPU核却还会空闲几秒。以我们的经验，这类性能方面的问题会导致重度依赖同步的应用的性能成倍的下降，针对Kernel编译会多造成高达13%的延迟，针对广泛使用的商用数据库会造成23%的吞吐量降低。传统的测试技术和调试工具对于确认和了解这类问题是无效的，因此这些问题的症状经常是难以捕获的。为了能够推动我们的调查，我们构建了新的工具来在线检测这种违反不变性的情况并且将调度行为可视化。这些工具是简单的，易于在多个kernel版本间移植的并且使用的代价很小。我们相信这些工具将成为内核开发者工具链的一部分来帮助其避免这类问题的出现。

引言

你必须要明白没有多少东西比调度器还古老。这也恰恰是调度是容易的另一个证据。 ​ Linux Torvalds, 2001

​ 经典的调度问题围绕着设置调度量的长度来提供交互式响应，并同时最小化上下文切换的开销，在单一系统中同时提供批处理和交互式工作负载，同时需要有效地管理调度器的运行队列。到了2000年，操作系统的设计者认为调度是一个已经被解决的问题。Linux Torvalds的引文也是当时这一普遍观点的准确反映。

​ 到了2004年，我们步入了多核时代并且能效成为了计算机系统设计中的首要问题。很多事情又一次使调度器变得有趣起来，但同时也让它变得更复杂和更容易出错。

​ 我们最近使用Linux调度器的经验是关于压榨现代硬件设备的性能挑战上，比如NUMA的访问延迟，cache一致性和同步的高成本，分散的CPU和内存的延迟，导致调度器的实现异常复杂。其结果就是，确保可运行的线程使用空闲CPU核的这一调度器的最基本功能，被忽视。

​ 这篇论文的主要作者发现并研究了Linux调度器的四个性能问题。这些问题导致Linux调度器在有可运行线程等待转变成运行状态的情况下还使CPU核空闲。导致针对典型的Linux工作负载情况，其性能下降了13-24%，在某些极端场景下性能下降138倍之多。因为这些问题对kernel子系统造成了损伤，会导致大的甚至是巨大的性能下降，并且它们逃避掉了传统的测试和调试技术，搞清楚他们的本质和起源是很重要的。

​ 这些问题是不同的根本原因，但是他们的外在表现都是一样的。这个调度器在有可运行的线程 在运行队列中等待的时候无意间并且是长时间的让CPU核处于空闲状态。短期内出现这种情况是可以允许的：这个系统临时进入到某种状态，比如线程退出或者阻塞或者一个线程刚创建或者变成非阻塞。如果是长期的那就不是我们所期待的行为了。这个Linux调度器永远不应该在有工作可作时让CPU核空闲。这种现象如果长期存在，是没有意义的：它会导致bug并且损害性能。

​ 我们提出了这些问题的解决方案，并且观察到性能的实质性改善。同步密集型的应用的速度有了数倍的提升；一些内存屏障敏感性的科学应用运行速度有了高达138倍的提升。Kernel编译和在广泛使用的商用DBMS系统上跑的TPC-H工作负载性能提升了13%-14%。 受bug影响最大的TPC-H查询速度提高了23% 。

​ 侦测到这些bug是困难的。它们不会导致系统崩溃或者挂起，但是却会吞掉系统性能，而且这种行为经常是很难使用标准性能监控工具来通知的。针对 TPC-H工作负载，比如这种现象发生的时间可能贯穿执行的始终，但是每一次它可能仅仅有几百毫秒，这对于像htop, sar或者是perf这些工具来说侦测时间太短了。即使这种现象的发生持续很长一段时间，这个根本原因还是很难发现的，因为它可能是这个调度器的多个异步事情共同作用的结果。

​ 当我们在TPC-H数据库工作负载中观察到不能解释的性能问题时，我们初步怀疑是调度器的bug。传统的工具不能帮助我们确认或弄清楚它们的根本原因。为了搞明白这一些，我们设计了两个新工具。第一个工具我们称为 “sanity checker”, 周期性的检测前面提到的不变量的违规操作，在当前系统中捕获bug并且为离线分析收集相关信息。第二个工具为了加速调试能够可视化调度行为。这两个工具都很容易在从Linux 3.17到 4.3的内核版本间移植，运行它们的开销很小，把它们保留在标准工具链里能够帮助减少此类bug的发生。

Linux 调度器

我们首先讨论一下Linux的完全公平调度算法在单核，单用户系统上是如何工作的。从这个角度看，这个算法是相当简单的。接着我们会解释现代多核系统的限制是如何强迫开发者绕过潜在的性能瓶颈的。

在单CPU系统上，CFS是相当简单的

Linux的CFS是一个加权公平队列调度算法的实现，它将一个有效的CPU周期按权重比例分配给各个线程。为了支持这个抽象，CFS像其他大多数CPU调度器一样将CPU切分成时间片分到运行中的线程。完成这个调度器的关键讨论是：如何确定线程的时间片和如何选择下一个被调度执行的线程。

​ 这个调度器定义一个固定的时间间隔，在这个间隔期间系统中的每一个线程都至少要运行一次。这个时间间隔按权重比例被分配到各处线程。这个被分配后生成的时间间隔我们就叫作时间片。一个线程的权重本质上就是它的优先级，或者是UNIX系统所说的niceness。有更低niceness值的线程有更高的权重，反之亦然。

​ 当一个线程运行时，它会统计其vruntime(这个runtime就是这个线程按其权重被分配到的运行时间)。一旦一个线程的vruntime超过了它被分配的时间片，如果此时有其它可运行的线程，那么当前这个线程将被从当前线程抢占。如果有最小的vruntime值的其它线程被唤醒，那么光前这个线程也可能被抢占。

​ 所有的线程都被组织进用红-黑树实现的运行队列中，且按照它们的vruntime递增顺序排序存储。当一个 CPU是查找一个新的线程来运行时，它就直接获取这个红-黑树最左侧的叶子节点，因为这个节点包含的线程有最小的vruntime。

在多核系统上，CFS变得相当复杂

在多核环境中这个调度器的实现要变得复杂得多。需要使用pre-core的运行队列来解决伸缩性问题。采用pre-core 运行队列的动机是在上下文切换时，CPU核只访问其本地的运行队列。上下文切换处在关键路径上，因此它的执行必须快。仅仅访问本核的队列能够避免调度器遇到潜在的同步访问的代价，如果没有pre-cpu的运行队列，那只能访问全局共享的运行队列，这会有加锁的代价。

​ 然而，在存在pre-cpu运行队列的情况下为了使调度算法依然有效和正确，这个运行队列必须保持平衡。考虑一个有两个运行队列的双核系统，它的运行队列是不平衡的。假设一个队列有一个低优先级的线程并且另一个有10个高优化级的线程。如果每个核只从自己的运行队列来查找运行的线程，那么高优先级的线程获取到的CPU时间将远少于低优先级的线程 ，这不是我们希望看到的（译者注：在相同的CPU周期内，低优先级任务独占它自己的一个核，高优先级的10个任务瓜分另一个核的一个CPU周期，这样分配一个高优先级任务上的时间片就很少了）。我们可以让每个核不仅只检查他自己的队列，同时也检查其他核的队列，但这样又背离了per-code运行队列的目的。因此，Linux和其他的调度器都会周期性的运行负载均衡算法来保持各队列大致的均衡。

​ 从概念上讲，负载均衡是简单的。在2001年， CPU大部分还是单核的并且商用服务系统典型的还只有很少的处理器。因此，很难预知现代多核系统负载均衡将变成挑战。负载均衡对于今天的系统来说是很昂贵的过程，从计算角度讲，它需要遍历所有的运行队列，从通讯的角度讲，它会更改最新缓存数据，导致非常昂贵的cache miss和同步。其结果就是，调度器应竭力避免经常的负载均衡操作。同时，如果不经常性的负载均衡又会使运行队列不均衡。当这种情况发生时，即使有工作需要作，有些核也可能变成空闲状态，从而降低性能。因此除了周期性的负载均衡外，调度器可以仅在有核变为空闲时作“紧急”的负载均衡，并且在新线程创建或者唤醒时作负载均衡逻辑。如果有工作可以作，这个机制可以保证各个核保持忙碌状态。

​ 接下来我们会来描述下负载是如何工作的，首先我们来解释下这个算法并且讲解下使这个调度器保持低开销和节能方面的优化。最后我们展示一下一些优化使代码变得更复杂并导致了bug。

负载均衡算法

​ 弄明白负载均衡算法的关键是这个CFS调度器用来跟踪负载的metric。我们先解释下这些metric，然后描述下这个实际的算法。

​ 一个假的负载均衡算法只是简单的确保每个运行队列有大致相同数量的线程，这不是我们想要的。考虑这样一个场景，有两个运行队列，其中一个有一些高优先级的线程，另一个是同样多的低优先级线程，然后这些高优先级线程将得到与低优先级线程同样多的CPU时间，这不是我们希望的。均衡应该是基于线程权重的，而不是基于它们的数量的（因此，这个load metric不应该只是线程的数量）。

​ 不幸的是，仅仅依据线程权重来均衡负载是不够的。考虑这样一种场景，有十个线程在两个运行队列里：一个线程是高优先级的并且另外九个是低优先级的。让我们假设这个高优先级线程的权重是 低优先级的九倍。如果依据线程权重作负载均衡，一个运行队列将包含这个高优先线线程，另一个运行队列将包含其余的九个线程，这恰好是我们希望的。然而，假设这个高优先级线程经常会有短暂的睡眠，因此这第一个核将经常空闲。这个核就会频繁地从其他的核来拉取任务来保持自己的忙碌状态。然而我们不希望这是一种常态，因为它破坏了per-coer运行队列的设计目的。考虑到实际上高优先级线程不需要整个核，我们实际希望的是通过一种更聪明的方法来均衡运行队列。

​ 为了达到这个目的，CFS不仅仅基于权重来均衡运行队列，它还基于称为load的metric来作均衡。它组合了线程的权重和平均CPU使用率。如果一个线程没有使用太多的CPU，它的负载将会相应的降低。

​ 另外，这个负载跟踪指标的统计也要考虑在不同进程中的多个线程。考虑这样一种场景，我们有一个进程，它有大量的线程；另一个进程只有少量的线程，那么第一个进程分配的CPU时间将远远大于第二个进程。这是不公平的。因此在Linux 2.6.38版本增加了组调度特性来使线程组之间调度趋于公平。当线程属于某个cgroup时，它的负载将进一步除以这个cgroup组里的线程数上计算得出。这个特性后来扩展为将属于不同ttys的进程自动赋给不同的cgroup。

​ 一个基本的负载均衡算法将比较所有核上的负载然后将任务从负载高的核迁移到负载低的核。不幸的是，这将导致线程在机器上迁移，没有考虑到缓存本地化或者NUMA架构。作为替代，负载均衡器将使用分层策略。我们先来将一下分层调度域的概念。

1.jpg

在上面这张图中，这个机器上有32个核，四个node, 这个node8个核并且SMT层是在核间共享的。这四块灰色区域表示相对于机器的第一个核心的调度域。第二层是一个由三个node组成的组，因为这三个node从第一个核开始都可以在1跳内到达。在第四层，我们拥有这机器上的所有node,因为它们都可以在两跳内到达。

上面这个是原文的直译，我觉得没能很好的表达出分层调度域的概念，我们再简要地说明下。先说明一个目前的计算机CPU架构: 机器上可以用多个处理器，每个处理器又可以有多个核心，每个核心又可以开启超线程技术来点亮逻辑CPU，上面这个架构基本可以说成是SMP架构，多个SMP架构又可以构成NUMA架构。上面说的这些每一个层次都可以作为一个调度域。我们用下图（借了dog250的图，诚表谢意，若侵删）表示：

2.jpg

越向下的层级，在其内部迁移线程的代价越小，因此负载均衡尽量在最低层级内完成。

​ 我们来看下负载均衡算法的伪码。如下图是针对每个CPU的负载均衡算法：

3.jpg

负载均衡算法针对每一个调度域都会运行，并且是从调度域的低层级向高层级运行。在每一层次，调度域中的一个核负责均衡这个负载。如果当前调度域中有空闲的核可以用来作负载均衡，那此时就选取出这个空闲核中的第一个，或者调度域中剩余核的第一个（Line 2-9）。接下来，计算当前调度域中每个调度组的负载，然后选出一个最忙的组。如果这个最忙组的负载小于当前本地group的负载，这一层的负载被认为是均衡的（Line 16）。否则，需要在这个本地CPU和最忙CPU间作负载均衡。如果有tasksets存在，不能作均衡，我们需要重新返回到Line 18行，选取新的最忙的CPU。

负载均衡算法优化

​ 调度器针对给定的调度域通过在指定的核上运行负载均衡算法来避免重复性工作。当每个活动的核接收到周期性的时钟中断时开始运行负载均衡算法，它首先会检查它自己是不是这个域内的最小编号的核或者是否是最小编号的空闲的号。如果这个条件满足，这个核被认为是这次负载均衡操作认定的核，开始负载均衡操作。

​ 能耗相关的优先是进一步减少空闲核上负载均衡的频率。起初空闲核总是被每次时间周期唤醒并且运行负载均衡算法。但在Linux 2.6.21版本后多了一个选项（现在已经是默认行为）来避免周期性的唤醒睡眠的核：它们会进入到tickless空闲状态，每种状态下能够减少能耗。这种状态下的核心获取到工作的唯一方法是被过载的其他核唤醒。为了作到这一点，在每一个调度时钟周期内，如果一个核认定自己是过载的，它将检查此时系统中是否存在tickless状态的空闲核并且将NOHZ balancer的规则施加其上。 这个NOHZ均衡器核心负责在每一个时钟周期内运行自己的周期性负载均衡程序，并且代表了所有无时钟的空闲的核心 。

​ 在周期性负载均衡之上，调度器在线程被唤醒时也会作负载均衡。睡眠或等待特定资源后，这个线程被唤醒，调度器尝试将它放入一个空闲核。当这个线程被另一线程唤醒后，一个特殊规则将被应用，在这种情况下调度器在选择核时偏爱这个唤醒者所有的核，这样有利用cache复用。