Linux调度器：十年的核心浪费¶
标题：The Linux Scheduler: a Decade of Wasted Cores
日期：2016/04/18
作者：Jean-Pierre Lozi, Baptiste Lepers, Justin Funston, Fabien Gaud, Vivien Quéma, Alexandra Fedorova
链接：https://people.ece.ubc.ca/sasha/papers/eurosys16-final29.pdf
注意：此为 AI 翻译生成 的中文转录稿，详细说明请参阅仓库中的 README 文件。
备注：发现知乎也有人做了翻译，但是我烤肉太快了没留意。
摘要¶
作为资源管理的核心部分，操作系统线程调度器必须维持以下简单的不变性原则：确保就绪的线程被调度到可用的CPU核心上。尽管这看起来很简单，但我们发现这个原则在Linux中经常被打破。核心可能会空闲数秒，而与此同时，就绪的线程却在运行队列（runqueues）中等待。在我们的实验中，这些性能错误导致了同步密集型科学应用出现多倍的性能下降，内核编译（kernel make）的延迟增加了13%，以及一个广泛使用的商业数据库的TPC-H吞吐量下降了14-23%。这项工作的主要贡献在于发现和分析这些错误，并提供修复方案。传统的测试技术和调试工具在确认或理解这类错误方面效果不佳，因为它们的症状通常难以捉摸。为了推动我们的调查，我们构建了新的工具，用于在线检查对不变性原则的违反情况并可视化调度活动。这些工具简单、易于跨内核版本移植，并且运行时开销可以忽略不计。我们相信，将这些工具纳入内核开发人员的工具箱，将有助于抑制这类错误的发生。
1. 引言¶
“你必须认识到，没有多少东西能像调度器一样经久不衰。这恰恰证明了调度是多么容易。”
— Linus Torvalds, 2001
经典的调度问题围绕着设置调度时间片的长度，以便在提供交互式响应性的同时，最小化上下文切换的开销，并能同时满足单个系统中的批处理和交互式工作负载，以及高效地管理调度器运行队列。总的来说，到2000年，操作系统设计者们认为调度是一个已经解决的问题；Linus Torvalds的引言准确反映了当时普遍的看法。
2004年，登纳德缩放比例（Dennard scaling）定律终结，多核时代来临，能源效率成为计算机系统设计的首要关注点。这些事件再次让调度器变得引人关注，但同时也使其变得越来越复杂，并常常出现问题。
我们最近在Linux调度器上的经验表明，为了应对现代硬件带来的挑战性特性，如非均匀内存访问（NUMA）延迟、高昂的缓存一致性和同步成本，以及不断增大的CPU和内存延迟差距，开发者们面临着巨大的压力，这导致调度器的实现变得异常复杂。结果，调度器最基本的功能——确保可运行的线程使用空闲核心——被忽视了。
这项工作的主要贡献是发现并研究了Linux调度器中的四个性能错误。这些错误导致调度器在有可运行线程等待运行时，却让核心保持空闲¹。由此导致的性能下降，对于典型的Linux工作负载来说在13-24%的范围内，在某些极端情况下甚至达到了138倍。能源浪费与此成正比。由于这些错误破坏了一个关键的内核子系统，导致了实质性的、有时甚至是巨大的性能下降，并且能够规避传统的测试和调试技术，因此理解它们的性质和来源至关重要。
¹ 这种情况的发生，并非因为调度器被明确配置为通过有意保留核心不用以进入低功耗状态来节省能源。
这些错误有不同的根本原因，但症状是共通的。调度器无意中、且长时间地让核心保持空闲，而同时有可运行的线程在运行队列中等待。这种情况的短期发生是可以接受的：例如，当一个线程退出或阻塞，或者一个线程被创建或解除阻塞时，系统可能会暂时进入这种状态。但长期发生则不是预期的行为。Linux调度器是“工作保守”（work-conserving）的，这意味着只要有工作可做，它就不应该让核心空闲。因此，这种症状的长期存在是无意的：它是由错误引起的，并且损害了性能。
我们为这些错误提供了修复，并观察到了显著的性能提升。同步密集型应用经历了多倍的加速；一个重度依赖屏障（barrier）的科学应用运行速度提高了138倍²。内核编译和在广泛使用的商业DBMS上运行的TPC-H工作负载的性能分别提升了13%和14%。受错误影响最严重的TPC-H查询速度提升了23%。
检测这些错误是困难的。它们不会导致系统崩溃或挂起，但会侵蚀性能，其方式通常很难用标准的性能监控工具注意到。例如，在TPC-H工作负载中，该症状在整个执行过程中多次出现，但每次只持续几百毫秒——时间太短，无法用htop、sar或perf等工具检测到。然而，这些发生次数的总和足以使受影响最严重的查询减慢23%。即使在症状持续时间更长的情况下，根本原因也很难发现，因为它是调度器中许多异步事件共同作用的结果。
我们最初是在评估一个用于不同项目的TPC-H数据库工作负载时，观察到无法解释的性能问题，从而怀疑调度器存在错误。传统工具在确认错误或理解其根本原因方面对我们毫无帮助。为此，我们设计了两个新工具。第一个工具，我们称之为健全性检查器（sanity checker），它会周期性地检查上述不变性原则是否被违反，在实时系统上捕获错误，并收集相关信息的追踪数据以供离线分析。第二个工具将调度活动的追踪数据可视化，以加速调试过程。这些工具很容易在不同内核版本（从Linux 3.17到4.3）之间移植，运行时开销可以忽略不计，并且能持续检测到不变性违规。将它们保留在标准工具箱中，有助于减少未来此类错误的发生。
本文的其余部分组织如下。第2节描述Linux调度器的架构。第3节介绍我们发现的错误，分析其根本原因，并报告它们对性能的影响。第4节介绍这些工具。在第5节中，我们反思了从这项研究中学到的教训，并指出了开放的研究问题。第6节讨论相关工作，第7节总结我们的发现。
² 正如我们稍后解释的，调度的缺陷加剧了锁竞争。
2. The Linux调度器¶
我们首先描述Linux的完全公平调度（Completely Fair Scheduling, CFS）算法在单核单用户系统上是如何工作的（第2.1节）。从这个角度看，该算法非常简单。然后，在（第2.2节）我们解释现代多核系统的局限性如何迫使开发者们解决潜在的性能瓶颈，这导致了一个实质上更复杂且容易出错的实现。
2.1 在单CPU系统上，CFS非常简单¶
Linux的CFS是加权公平队列（weighted fair queueing, WFQ）调度算法的一种实现，其中可用的CPU周期按线程的权重比例进行分配。为了支持这种抽象，CFS（像大多数其他CPU调度器一样）在运行的线程之间对CPU进行时间分片。调度器做出的关键决策是：如何确定一个线程的时间片？以及如何选择下一个要运行的线程？
调度器定义了一个固定的时间间隔，在此期间系统中的每个线程必须至少运行一次。这个间隔根据线程的权重按比例分配给各个线程。得到的（分配后的）间隔就是我们所说的时间片。一个线程的权重本质上就是它的优先级，在UNIX术语中称为niceness。niceness值较低的线程拥有较高的权重，反之亦然。
当一个线程运行时，它会累积vruntime（线程的运行时间除以其权重）。一旦一个线程的vruntime超过了其分配的时间片，如果还有其他可运行的线程，该线程就会被从CPU上抢占。如果另一个具有更小vruntime的线程被唤醒，当前线程也可能被抢占。
线程被组织在一个运行队列中，实现为一个红黑树，其中线程按其vruntime的递增顺序排序。当CPU寻找新线程运行时，它会选择红黑树中最左边的节点，该节点包含了vruntime最小的线程。
2.2 在多核系统上，CFS变得相当复杂¶
在多核环境中，调度器的实现变得非常复杂。可伸缩性的考虑要求使用每核心（per-core）运行队列。使用每核心运行队列的动机是，在上下文切换时，核心只需访问其本地的运行队列来寻找要运行的线程。上下文切换位于关键路径上，因此必须快速。只访问核心本地队列可以防止调度器进行可能昂贵的同步访问，而如果访问全局共享的运行队列，这种访问将是必需的。
然而，为了使调度算法在存在每核心运行队列的情况下仍然能正确且高效地工作，运行队列之间必须保持平衡。考虑一个双核系统，其两个运行队列不平衡。假设一个队列有一个低优先级线程，另一个队列有十个高优先级线程。如果每个核心只在其本地运行队列中寻找工作，那么高优先级线程获得的CPU时间将远少于低优先级线程，这并非我们所期望的。我们可以让每个核心不仅检查自己的运行队列，还检查其他核心的队列，但这会违背使用每核心运行队列的初衷。因此，Linux和大多数其他调度器所做的是周期性地运行一个负载均衡算法，以保持队列的大致平衡。
“我怀疑，让调度器使用每CPU队列，并加上一些跨CPU的负载均衡逻辑，可能非常简单。补丁已经存在了，我感觉人们不会把这几百行代码搞砸。”
— Linus Torvalds, 2001
从概念上讲，负载均衡很简单。在2001年，CPU大多是单核的，商用服务器系统通常也只有少数几个处理器。因此，很难预见到在现代多核系统上负载均衡会变得具有挑战性。在今天的系统上，负载均衡是一个昂贵的过程，无论是在计算上（因为它需要遍历数十个运行队列）还是在通信上（因为它涉及修改远程缓存的数据结构，导致极其昂贵的缓存未命中和同步）。因此，调度器会尽力避免频繁执行负载均衡过程。但同时，执行得不够频繁又可能导致运行队列不平衡。当这种情况发生时，核心可能会在有工作可做时变得空闲，从而损害性能。因此，除了周期性的负载均衡，调度器在核心变为空闲时还会调用“紧急”负载均衡，并在新创建或新唤醒的线程放置时实现一些负载均衡逻辑。理论上，这些机制应该确保在有工作可做时，核心能保持忙碌。
接下来我们描述负载均衡的工作原理，首先解释算法，然后是调度器为维持低开销和节省电力而采用的优化。稍后我们会展示，其中一些优化使得代码更加复杂并导致了错误的产生。
2.2.1 负载均衡算法¶
理解负载均衡算法的关键在于CFS调度器用来追踪负载的指标。我们首先解释这个指标，然后描述实际的算法。
负载追踪指标 (The load tracking metric)。一个简单的负载均衡算法可能只是确保每个运行队列有大致相同数量的线程。然而，这不一定是我们想要的。考虑一个场景，有两个运行队列，一个队列有若干高优先级线程，另一个队列有相同数量的低优先级线程。那么高优先级线程将获得与低优先级线程相同的CPU时间量。这不是我们想要的。因此，一个想法是根据线程的权重来平衡队列，而不是它们的数量。
不幸的是，仅仅根据线程权重来平衡负载也是不够的。考虑一个场景，有两个运行队列中有十个线程：一个线程是高优先级的，九个是低优先级的。假设高优先级线程的权重是低优先级线程的九倍。如果负载根据线程权重进行平衡，那么一个运行队列将包含高优先级线程，而另一个将包含九个低优先级线程。高优先级线程将获得比低优先级线程多九倍的CPU时间，这似乎是我们想要的。然而，假设高优先级线程经常为短期睡眠，导致第一个核心经常空闲。这个核心将不得不频繁地从另一个核心的运行队列中“窃取”工作来保持自己忙碌。但是，我们不希望工作窃取成为常态，因为这违背了每核心运行队列的初衷。我们真正想要的是以一种更智能的方式来平衡运行队列，考虑到高优先级线程并不需要一整个核心。
为了实现这个目标，CFS不仅根据权重，还根据一个称为**负载（load）**的指标来平衡运行队列，该指标是线程权重和其平均CPU使用率的组合。如果一个线程不使用太多CPU，它的负载会相应减少。
此外，负载追踪指标还考虑了不同进程中多线程级别的差异。考虑一个场景，我们有一个有很多线程的进程，和另一个只有少量线程的进程。那么第一个进程的线程合起来将接收到比第二个进程的线程多得多的CPU时间。结果，第一个进程将使用大部分CPU周期，并饿死另一个进程。这是不公平的。因此，从2.6.38版本开始，Linux增加了一个组调度功能，以在线程组之间实现公平性（cgroup功能）。当一个线程属于一个cgroup时，它的负载会进一步除以其cgroup中的总线程数。这个功能后来被扩展为自动将属于不同tty的进程分配到不同的cgroup中（autogroup功能）。
负载均衡算法 (The load-balancing algorithm)。一个基本的负载均衡算法会比较所有核心的负载，然后将任务从最繁忙的核心转移到最不繁忙的核心。不幸的是，这将导致线程在机器上迁移，而没有考虑缓存局部性或NUMA。相反，负载均衡器使用一种层级策略。
核心在逻辑上被组织成一个层次结构，其底部是单个核心。核心在层次结构中更高层级的组合方式取决于它们如何共享机器的物理资源。
[图1 被忽略] 图1：一台拥有32个核心、四个节点（每个节点八个核心）和核心对之间SMT级别共享的机器。四个灰色区域代表相对于机器第一个核心的调度域。注意，在层次结构的第二层，我们有一个由三个节点组成的组。这是因为这三个节点可以从第一个核心通过一跳到达。在第四层，我们拥有机器的所有节点，因为所有节点都可以在两跳内到达。图4显示了我们系统上节点之间的连接性。
[算法1 被忽略] 算法1：简化的负载均衡算法。
核心根据它们共享机器物理资源的方式进行组织。在我们提供的示例中，我们描述了我们实验机器上的层次结构（见表5），其中成对的核心共享功能单元（例如，FPU），而八个核心组成的组共享一个末级缓存（LLC）。共享一个LLC的八个核心组构成一个NUMA节点。不同的NUMA节点有不同的连接性，如下文和图4所示。因此，在我们的目标系统上，层次结构的第二层是成对的核心，下一层是八个核心的组，每个组共享一个LLC（例如，一个NUMA节点）。NUMA节点根据它们的连接级别进一步分组。彼此相距一跳的节点将在下一层，依此类推。这种层次结构的一个例子如图1所示。层次结构的每一层都称为一个调度域（scheduling domain）。
负载均衡算法在算法1中进行了总结。负载均衡针对每个调度域运行，从底层到顶层。在每一层，每个域中的一个核心负责平衡负载。如果域中有空闲核心，其空闲的CPU周期可用于负载均衡，则该核心是调度域的第一个空闲核心；否则是调度域的第一个核心（第2-9行）。接着，计算调度域中每个调度组的平均负载（第10行），并根据偏好过载和不平衡组的启发式方法选出最繁忙的组（第10行）。如果最繁忙组的负载低于本地组的负载，则认为该级别的负载是平衡的（第16行）。否则，在本地CPU和最繁忙组的最繁忙CPU之间进行负载均衡，并进行微调以确保负载均衡在存在taskset的情况下也能工作（第18-23行）。
暂时假设，这个算法由所有核心在每个负载均衡周期内运行；在下一节中，我们将解释，作为一种优化，并非所有核心都实际这样做。执行该算法的核心从层次结构的倒数第二层开始，平衡下一层的负载。例如，在图1的系统上，核心将从核心对级别开始，平衡其中包含的两个独立核心之间的负载。然后，它将前进到NUMA节点级别，平衡下一层的负载（在这种情况下，是核心对之间），但不是NUMA节点的各个核心之间。在一个调度域中，执行负载均衡的核心集合称为调度组（scheduling groups）。在NUMA节点域，将有四个调度组，每个对应一个核心对。该核心将找到除自己所在组之外的最繁忙的调度组，并从该组中最繁忙的核心窃取任务。
2.2.2 优化¶
调度器通过仅在给定调度域的指定核心上运行负载均衡算法来防止重复工作。当每个活动核心接收到周期性的时钟节拍并开始运行负载均衡算法时，它会检查自己是否是域中编号最低的核心（如果所有核心都忙），或者是否是编号最低的空闲核心（如果有任何核心空闲）。如算法第2行所示。如果这个条件成立，该核心就认为自己被指定，并继续运行算法。
与功耗相关的优化可能会进一步降低空闲核心上负载均衡的频率。最初，空闲核心在每次时钟节拍时都会被唤醒；此时它们会运行负载均衡算法。然而，自2.6.21版本起，Linux有了一个选项（现在默认启用）来避免周期性地唤醒休眠的核心：它们进入一个无节拍空闲（tickless idle）状态，在此状态下可以降低能耗。处于此状态的核心获得工作的唯一方式是被另一个核心唤醒。为此，在每次调度节拍时，如果一个核心认为自己“过载”，它会检查系统中是否有一段时间存在无节拍空闲核心，如果是，它会唤醒第一个无节拍空闲核心，并赋予它NOHZ均衡器的角色。NOHZ均衡器核心负责在每次节拍时为自己和所有无节拍空闲核心运行周期性负载均衡例程。
除了周期性负载均衡，调度器在唤醒线程时也会进行负载均衡。当一个线程在睡眠或等待资源（例如，锁，I/O）后醒来时，调度器会尝试将其放置在最空闲的核心上。当线程被另一个线程（唤醒者线程）唤醒时，会应用特殊规则。在这种情况下，调度器将偏好与唤醒者线程共享缓存的核心，以提高缓存复用。
3. Bugs¶
“除了我，没有人能在第一次就写出完美的代码。但世界上只有一个我。”
— Linus Torvalds, 2007
关于负载均衡何时发生或不发生的规则如此之多，以至于很难推断出，当有工作可做时，一个空闲核心会保持空闲多久，以及当系统中有空闲核心时，一个任务在运行队列中等待运行的时间会有多长。由于“第一次就写出完美代码”的开发者很少，这种复杂性导致了错误的产生。理解这些错误对于体会它们为何能规避常规测试和调试工具是必要的。因此，我们先描述错误，并将我们用来确认和理解它们的工具的介绍推迟到第4节。表4总结了本节描述的错误。
3.1 组不平衡错误 (The Group Imbalance bug)¶
错误 (The bug)。我们在一个多用户机器上遇到了这个错误，我们用它来进行内核编译和使用R机器学习包进行数据分析。我们怀疑这个系统，一个64核、八节点的NUMA服务器，没有为高线程计算使用所有可用的核心，而是将所有线程拥挤在少数几个节点上。我们用我们的可视化工具的输出来说明这个错误，如图2a和2b所示。
在图中所示的时间段内，机器正在执行内核编译（make，使用64个线程），并运行两个R进程（每个进程一个线程）。make和两个R进程是从3个不同的ssh连接（即3个不同的tty）启动的。图2a是一个热力图，用颜色编码了每个核心运行队列中随时间变化的线程数。颜色越暖，核心承载的线程越多；白色对应于空闲核心。图表显示，有两个节点的核要么只运行一个线程，要么根本没有线程，而其余节点则过载，许多核心的运行队列中有两个线程。
经过调查，我们发现调度器没有进行负载均衡，原因是（i）负载追踪指标的复杂性，以及（ii）层级化设计。让我们首先关注负载。回想一下，线程的负载是其权重和所需CPU量的组合。通过autogroup，线程的负载还会被其父autogroup中的线程数所除。在我们的案例中，一个64线程make进程中的线程的负载，大约比一个单线程R进程中的线程负载小64倍。
线程负载之间的差异如图2b所示，它显示了每个核心运行队列中线程的组合负载：颜色越深对应于负载越高。节点0和4，即运行R进程的节点，每个都有一个负载非常高的核心。这些是运行R线程的核心。Linux负载均衡器根据负载从其他运行队列窃取工作；显然，节点0和4上的欠载核心不应该从它们自己节点上的过载核心窃取，因为那个核心只运行一个线程。然而，它们必须能够从其他节点上更繁忙的核心窃取。为什么情况不是这样呢？
回想一下，为了限制算法复杂性，负载均衡算法使用层级化设计。当一个核心试图从另一个节点（换句话说，从另一个调度组）窃取工作时，它不会检查该组中每个核心的负载，它只看该组的平均负载（算法1的第11行）。如果受害者调度组的平均负载大于其自身的平均负载，它就会尝试从该组窃取；否则就不会。这正是我们情况下欠载核心未能从其他节点上的过载核心窃取工作的原因。它们观察到受害者节点的调度组的平均负载并不比它们自己的大。试图窃取工作的核心与高负载的R线程在同一个节点上运行；那个线程拉高了该节点的平均负载，并掩盖了某些核心实际上是空闲的事实。与此同时，受害者节点上的核心，其平均负载大致相同，却有很多等待的线程。
一个有效的问题是，在这种情况下是否应该发生工作窃取，因为理论上我们希望负载较高的线程获得比负载较低的线程更多的CPU时间。答案是“是”：Linux CFS调度器本质上是工作保守的，所以如果系统中有空闲核心，线程可能会获得超过其公平份额的CPU周期；换句话说，空闲核心应该总是被分配给等待的线程。正如我们在这里所展示的场景中，情况并非总是如此。
[图2 被忽略] 图2：组不平衡错误。Y轴显示CPU核心。节点编号为0-7。每个节点包含八个核心。(a) 每个核心运行队列中随时间变化的线程数。(b) 每个核心运行队列随时间变化的负载。(c) 与(a)相同，但应用了修复。
修复 (The fix)。为了修复这个错误，我们修改了算法中比较调度组负载的部分。我们不再比较平均负载，而是比较最小负载（算法1的第11行和第15行）。最小负载是该组中负载最低的核心的负载。如果一个调度组的最小负载低于另一个调度组的最小负载，这意味着第一个调度组有一个核心的负载低于另一个组中的所有核心，因此第一个组中的一个核心必须从第二个组窃取。这个算法确保了第一个组的核心在负载较小的情况下，第二个组的核心不会保持过载，从而在核心间平衡负载。请注意，这个修复是可行的，因为负载在组内部也是平衡的（由于在层次结构较低级别调用了负载均衡）。与原始算法一样，我们使用组不平衡的特殊情况（算法1的第13行）来处理由于taskset引起的极端情况。这些修改没有给调度器增加算法复杂性，因为计算调度组的最小负载和平均负载的成本相同。根据我们的经验，这个修复不会导致调度组之间迁移次数的增加（即乒乓效应）。
对性能的影响 (Impact on performance)。图2c是应用了修复后该工作负载执行的追踪（以与图2a相同的方式显示运行队列大小的热力图）。修复错误后，在本节前面描述的make/R工作负载中，make作业的完成时间减少了13%。两个R进程的完成时间没有变化。在其他情况下，性能影响可能要大得多。例如，在一个运行NAS基准测试³中lu程序（60个线程）和四个单线程R进程的工作负载中，修复组不平衡错误后，lu的运行速度快了13倍。lu经历了超线性加速，因为当多个lu线程在同一个核心上运行时，该错误加剧了锁竞争。
³ NAS基准测试包含一组旨在帮助评估超级计算机性能的小程序。
3.2 调度组构建错误 (The Scheduling Group Construction bug)¶
错误 (The bug)。Linux定义了一个名为taskset的命令，它能将应用程序固定到可用核心的子集上运行。本节我们描述的错误发生在应用程序被固定在相距两跳的节点上时。例如，在图4中，它展示了我们NUMA机器的拓扑结构，节点1和2相距两跳。这个错误会阻止负载均衡算法在这两个节点之间迁移线程。由于线程是在其父线程所在的节点上创建的，最终效果是固定的应用程序只在一个节点上运行，无论它有多少个线程。
这个错误是由于调度组的构建方式不适应现代NUMA机器，比如我们实验中使用的那种。简而言之，这些组是从特定核心（核心0）的角度构建的，而它们应该从每个节点上负责负载均衡的核心的角度来构建。我们用一个例子来解释。
[图4 被忽略] 图4：我们8节点AMD Bulldozer机器的拓扑结构。
在我们的机器上，如图4所示，第一个调度组包含节点0的核心，加上所有与节点0相距一跳的节点的核心，即节点1、2、4和6。第二个调度组包含未被第一个组包含的第一个节点的核心（节点3），加上所有与节点3相距一跳的节点的核心：节点1、2、4、5、7。因此，前两个调度组是：
{0, 1, 2, 4, 6}, {1, 2, 3, 4, 5, 7}
请注意，节点1和2都包含在两个调度组中。再进一步注意，这两个节点实际上彼此相距两跳。如果调度组是从节点1的角度构建的，那么节点1和2就不会被包含在一起。让我们看看这对负载均衡意味着什么。
假设一个应用程序被固定在节点1和2上，并且它的所有线程都在节点1上创建（Linux在其父线程所在的同一个核心上派生线程；当一个应用程序在其初始化阶段派生多个线程时，它们很可能在同一个核心上被创建——所以这通常会发生）。最终我们希望负载在节点1和2之间得到平衡。然而，当节点2上的一个核心寻找工作来窃取时，它会比较前面显示的两个调度组的负载。由于每个调度组都包含节点1和2，它们的平均负载将是相同的，所以节点2不会窃取任何工作！
这个错误源于一次试图提高Linux在大型NUMA系统上性能的尝试。在引入这个错误之前，Linux会在NUMA节点内部进行负载均衡，然后再跨所有NUMA节点进行。引入了新的层次结构级别（相距1跳的节点，相距2跳的节点等）以增加线程保持在其原始NUMA节点附近的概率。
修复 (The fix)。我们修改了调度组的构建方式，使得每个核心使用从其自身角度构建的调度组。修复后，当节点1和2的核心试图在机器级别窃取任务时，节点1和2不再被包含在所有的调度组中。因此，核心能够检测到不平衡并窃取工作。
对性能的影响 (Impact on performance)。表1展示了有无调度组构建错误时，NAS应用程序的性能差异。应用程序在两个节点上启动，线程数与核心数相同。lu经历了最大27倍的减速。这个减速比预期的2倍要大得多，是由于锁效应。NAS应用程序使用自旋锁和自旋屏障；当所有线程因taskset错误而被迫在同一个节点上执行时，执行关键部分的线程可能会被取消调度，而另一个将通过自旋浪费其时间片的线程取而代之。lu是这种现象的一个极端例子：它使用流水线算法来并行化工作；线程等待其他线程处理的数据。当多个线程被迫在同一个核心上执行时，这会导致巨大的性能损失。
[图3 被忽略] 图3：过载唤醒错误的几个实例。
[表1 被忽略]
表1：存在和不存在调度组构建错误时NAS应用程序的执行时间。所有应用程序都使用 numactl --cpunodebind=1,2 <app> 启动。
3.3 过载唤醒错误 (The Overload-on-Wakeup bug)¶
错误 (The bug)。这个错误的要点是，一个正在睡眠的线程可能会在一个过载的核心上醒来，而系统中其他核心却是空闲的。这个错误是由唤醒代码（select_task_rq_fair函数）中的一个优化引入的。当一个线程在节点X上进入睡眠，并且稍后唤醒它的线程也在同一个节点上运行时，调度器只考虑节点X上的核心来调度被唤醒的线程。如果节点X的所有核心都忙，该线程将在一个已经繁忙的核心上醒来，错失使用其他节点上空闲核心的机会。这可能导致机器的严重未充分利用，尤其是在线程频繁等待的工作负载上。
这个优化背后的理由是最大化缓存复用。本质上，调度器试图将被唤醒的线程物理上放置在靠近唤醒者线程的位置，例如，这样两个都在共享末级缓存的核心上运行，考虑到生产者-消费者工作负载中，被唤醒的线程将消耗唤醒者线程产生的数据。这看起来是一个合理的想法，但对于某些工作负载来说，为了更好的缓存复用而在运行队列中等待是不值得的。
这个错误是由一个广泛使用的商业数据库触发的，该数据库配置了64个工作线程（每核心1个线程）并执行TPC-H工作负载。这个工作负载，与其他应用程序产生的瞬时短生命周期线程相结合，同时触发了组不平衡错误和过载唤醒错误。由于我们已经在3.1节中描述了组不平衡错误，我们在这个实验中禁用了autogroup，以便更好地说明过载唤醒错误。
图3展示了唤醒错误的几个实例。在第一个时间段（标记为①），一个核心是空闲的，而一个理想情况下应该被调度到那个核心上的线程却一直在其他繁忙的核心上醒来。在第二个时间段（标记为②），这个错误出现了三次：三个核心长时间空闲，而三个本应被调度到这些核心上的额外线程却一直在其他繁忙的核心上醒来。
过载唤醒错误通常在瞬时线程被调度到一个运行数据库线程的核心上时发生。这发生在内核启动持续时间不到一毫秒的任务来执行后台操作时，如日志记录或IRQ处理。当这种情况发生时，负载均衡器观察到运行瞬时线程的节点（节点A）负载较重，并将其中一个线程迁移到另一个节点（节点B）。如果被迁移的是瞬时线程，这不是问题，但如果是数据库线程，那么过载唤醒错误就会发生。节点B现在运行一个额外的数据库线程，而这些线程经常睡眠和唤醒，却一直选择在节点B上唤醒，即使那个节点上没有空闲核心。这是因为唤醒代码为了更好的缓存复用，只考虑本地节点的核心。
我们现在理解了为什么在系统中有空闲核心的情况下，一个线程可能会在一个繁忙的核心上醒来。注意在图3中，系统最终会从负载不平衡中恢复过来：负载均衡算法最终会将线程从过载核心迁移到空闲核心。问题是，为什么这需要几毫秒（甚至几秒钟）才能恢复？
注意系统中有两种空闲核心：短期和长期。短期空闲核心之所以空闲，是因为运行在其上的数据库线程因同步或I/O事件而间歇性睡眠。理想情况下，我们希望负载均衡事件将一个线程从过载核心迁移到一个长期空闲核心。迁移到一个短期空闲核心帮助不大：之前在该核心上运行的线程很快就会醒来，并且正如我们所见，调度器可能会因为缓存局部性优化而将其放置在同一节点上的另一个繁忙核心上。因此，不平衡将持续存在。
不幸的是，当调度器考虑从过载核心迁移线程时，它不区分短期和长期空闲核心。它所做的只是在负载均衡器被调用时检查该核心是否空闲。回想2.2.1节，负载均衡算法由“指定核心”在层次结构的不同级别上调用。如果有多个空闲核心有资格被“指定”，只有一个会被选中。如果我们幸运，长期空闲核心被选中，平衡就恢复了。这正是图3中发生的情况，当系统最终从不平衡中恢复时。然而，正如我们所观察到的，纯粹的运气不足以维持最佳性能。
修复 (The fix)。为了修复这个错误，我们修改了线程唤醒时执行的代码。我们将线程唤醒在本地核心——即线程上次被调度的核心——如果它是空闲的；否则，如果系统中有空闲核心，我们将线程唤醒在空闲时间最长的核心上。如果没有空闲核心，我们回退到原始算法来寻找线程应该唤醒的核心。
将线程唤醒在长期空闲核心上可能会对功耗产生影响。长时间空闲的核心通常会进入低功耗模式。将线程唤醒在该核心上将迫使其退出该模式并全功率运行。因此，我们只在系统的电源管理策略不允许核心进入低功耗状态时才强制执行新的唤醒策略。此外，我们的修复只对线程频繁睡眠和唤醒且系统间歇性超载（线程多于核心）的工作负载有意义。在这些情况下，将线程唤醒在长期空闲核心上是有道理的。在其他情况下，由于线程唤醒很少见，我们的修复不会显著改变调度器的行为。
在系统中寻找一个长期空闲核心不会给唤醒函数增加开销：内核已经维护了一个所有空闲核心的列表，所以选择第一个（即空闲时间最长的那个）只需要常量时间。
对性能的影响 (Impact on performance)。这个错误对数据库TPC-H工作负载有重大影响，因为线程经常互相等待，这意味着任何两个被卡在同一个核心上的线程最终会减慢所有剩余的线程。这个效应在图3中可见：在①和②期间，许多线程的执行中有间隙，即它们都在同一时间睡眠，等待共享一个核心的“掉队”线程。当所有错误的实例都解决后（图的最右侧部分），间隙消失了。
[表2 被忽略] 表2：过载唤醒和组不平衡错误修复对一个流行商业数据库的影响（数值为五次运行的平均值）。
表2显示了我们的错误修复对商业数据库中过载唤醒和组不平衡错误的影响。我们使用两种工作负载：（1）TPC-H的第18个查询，这是对该错误最敏感的查询之一，以及（2）完整的TPC-H基准测试。我们对过载唤醒的错误修复使TPC-H第18个查询的性能提高了22.2%，在完整TPC-H工作负载上提高了13.2%。在过载唤醒错误修复的基础上再使用组不平衡错误修复，使TPC-H第18个查询的性能提高了22.6%，在完整TPC-H工作负载上提高了14.2%。组不平衡错误的影响在这些实验中很小，因为它只发生在核心对的级别上（即，一个核心空闲而另一个过载），并且只在实验的某些部分发生。
3.4 缺失调度域错误 (The Missing Scheduling Domains bug)¶
错误 (The bug)。当一个核心通过/proc接口被禁用然后重新启用时，任何NUMA节点之间的负载均衡将不再执行。这个错误是由于一个代表机器中调度域数量的全局变量更新不正确所致。当一个核心被禁用时，这个变量被设置为一个NUMA节点内部的域数量。结果是，主调度循环（算法1的第1行）会比预期提前退出。
结果是，线程只能在核心被禁用前它们运行的那个节点上运行（即使它们运行的节点与被禁用和重新启用的核心所在的节点不同）。对于在核心禁用后创建的进程，所有线程都将与其父进程在同一个节点上运行。由于所有进程通常都是从同一个“根”进程（例如，sshd守护进程和它派生的ssh进程）创建的，这个错误通常导致所有新创建的线程都在机器的单个节点上执行，无论线程数量多少。
图5展示了这个错误的可视化。一个有16个线程的应用程序在机器上启动。线程创建后，节点1上的所有核心都运行两个线程（橙色水平线）。从核心0发出的蓝色垂直线代表核心0在尝试窃取工作时考虑的核心。因为循环比它应该的提前退出，核心0只考虑其本地节点的核心，而不考虑节点1的核心。
修复 (The fix)。我们追溯到这个错误的根本原因，是重新生成机器调度域的代码。Linux每次禁用一个核心时都会重新生成调度域。重新生成调度域是一个两步过程：内核重新生成NUMA节点内部的域，然后是跨NUMA节点的域。不幸的是，在代码重构期间，Linux开发者删除了生成跨NUMA节点域的函数调用。我们把它加了回去，这样做就修复了错误。
[表3 被忽略] 表3：有无缺失调度域错误时NAS应用程序的执行时间（秒）。
[图5 被忽略] 图5：从核心0的角度看缺失调度域错误。
对性能的影响 (Impact on performance)。表3总结了缺失调度域错误对几个NAS应用程序的影响，在系统中禁用并重新启用一个核心后。应用程序以64个线程启动，这是我们64核机器上的默认配置。缺失调度域错误导致应用程序的所有线程都在一个节点而不是八个节点上运行。在某些情况下，性能影响大于人们预期的8倍减速，考虑到线程获得的CPU时间比没有错误时少8倍（它们在一个节点而不是八个节点上运行）。例如，lu运行速度慢了138倍！当线程频繁使用锁或屏障进行同步时，会出现超线性的减速：如果线程在一个被取消调度的线程持有的锁上自旋，它们将浪费更多的CPU时间，对整个应用程序的性能造成级联效应。一些应用程序不能理想地扩展到64个核心，因此受该错误的影响稍小。最小的减速是4倍。
[表5 被忽略] 表5：我们AMD Bulldozer机器的硬件配置。
3.5 讨论¶
首先要问的问题是，这些错误是否可以通过一个新的、更清晰的、不易出错且易于调试的调度器设计来修复，同时仍然保持我们今天拥有的功能。然而，从历史上看，这似乎不会是一个长期的解决方案，此外新设计还需要从头开始实现和测试。Linux调度器已经经历了几次重大的重新设计。最初的调度器算法复杂度很高，导致在高度多线程工作负载变得普遍时性能不佳。2001年，它被一个新的具有O(1)复杂度和在SMP系统上更好可伸缩性的调度器所取代。它最初是成功的，但很快就需要为像NUMA和SMT这样的新架构进行修改。同时，用户希望对桌面用例（如交互式和音频应用）有更好的支持，这需要更多的改变。尽管有许多修改和提出的启发式方法，O(1)调度器未能满足期望，并于2007年被CFS取代。有趣的是，CFS为了O(log n)的复杂度牺牲了O(1)的复杂度，但这被认为是值得的，以提供所需的功能。
随着硬件和工作负载变得更加复杂，CFS也 succumbed to bugs. 自动分组（autogroups）的增加，加上层级化的负载均衡，引入了组不平衡错误。新的、日益复杂的NUMA系统中的不对称性触发了调度组构建错误。现代系统的“NUMA特性”是缺失调度域错误的原因。现代多节点机器上的缓存一致性开销促使了导致过载唤醒错误的缓存局部性优化。
关键的结论是，新的调度器设计来来去去。然而，一个新的设计，即使最初是干净且据称无错误的，也不是一个长期的解决方案。Linux是一个由数十名贡献者开发的大型开源系统。在这种环境下，我们不可避免地会看到新的功能和“hack”被改造到源代码库中，以应对不断变化的硬件和应用。
最近发布的Linux 4.3内核采用了一种新的负载指标实现。据报道，这一变化“以一种显著降低代码复杂性的方式完成”。简化负载指标可以消除与之直接相关的组不平衡错误。然而，我们使用我们的工具确认，该错误仍然存在⁶。
内核开发者依赖相互的代码审查和测试来防止引入错误。这对于像缺失调度域和调度组构建这样在代码中更容易发现的错误可能有效（当然，在这些情况下它仍然无效），但对于更神秘类型的错误，它不太可能是可靠的。
用测试或常规性能监控工具捕获这些错误是棘手的。它们不会导致系统崩溃或内存耗尽，它们只是悄悄地侵蚀性能。正如我们在组不平衡和过载唤醒错误中所看到的，它们引入了在不同核心之间“移动”的短期空闲期。这些微观的空闲期无法用像htop、sar或perf这样的性能监控工具注意到。标准的性能回归测试也不太可能捕获这些错误，因为它们发生在非常特定的情况下（例如，从不同的tty启动的具有不同线程计数的多个应用程序）。在实践中，Linux上的性能测试通常是在专用机器上一次只运行一个应用程序——这是限制可能解释性能差异因素的标准方法。
总之，常规的测试技术和调试工具在我们最初怀疑它们存在后，无论是确认错误还是理解其根本原因方面都没有帮助。我们的经验促使我们构建新的工具，使用这些工具我们可以高效地确认错误并理解它们发生的原因。下一节将描述这些工具。
⁶ 我们所有的修复将很快提交给内核开发者。
4. 工具¶
4.1 在线健全性检查器 (Online Sanity Checker)¶
健全性检查器是我们用来描述一种定期检查必须由软件维护的不变性的机制的术语。
[表4 被忽略] 表4：我们使用工具在调度器中发现的错误。
[算法2 被忽略] 算法2：“当另一个核心过载时，没有核心保持空闲”
我们的健全性检查器验证的不变性如算法2所示。它验证了当另一个核心的运行队列有等待线程时，没有核心是空闲的。我们努力保持代码简单，也许是以更高的算法复杂性为代价，以最小化健全性检查器本身出现错误的机会。
我们的健全性检查器与断言或看门狗不同，因为在我们的情况下，它必须专门为检查在短时间内可接受但在持续存在时不可接受的条件而量身定做。断言会在期望的不变性被违反时立即触发，而健全性检查器必须最小化标记短期瞬时违规的概率，并以高概率捕获长期违规。
为了满足这个要求，我们按如下方式实现健全性检查器。不变性检查以间隔S周期性地调用。如果检测到不变性违规，我们在一个短时间段M内主动监控额外的调度器事件（如下所述），看这是否是一个被调度器迅速修复的“合法”短期违规。如果它没有被修复，我们记录分析信息（如下所述）并标记一个错误。
我们设置S和M以最小化开销和假阳性概率，并最大化检测实际错误的概率。我们对S的设置是一秒；这有助于确保除了非常短的程序外，不变性违规都能被检测到，并保持低开销。我们测量的开销在我们的系统上对于多达10,000个线程的工作负载，当S=1时低于0.5%。
负载均衡器每4ms运行一次，但由于层级化设计，在无错误的系统中可能需要多次负载均衡尝试才能从不变性违规中恢复。我们保守地将M设置为100ms，以几乎消除假阳性的概率。在此期间发生的监控会跟踪线程迁移、创建和销毁，因为正是这些事件可以帮助系统恢复。跟踪这些事件需要在move_thread、fork和exit函数中添加一个函数调用，检查线程迁移到哪里。这个函数调用的开销可以忽略不计。
检测实际错误的概率，即长期不变性违规，取决于不变性违规的频率和持续时间。在我们描述的大多数情况下，一旦错误触发了不变性违规，系统就永远不会恢复。这种不变性违规很容易被健全性检查器检测到。在一种情况下（过载唤醒错误），不变性违规持续时间较短，大约几百毫秒，然后消失又重新出现。在这种情况下，捕获违规的概率取决于系统处于不良状态的总时间比例。如果比例很小，检测到错误的几率也很小，但对性能的影响也小。持续时间更长和/或更频繁发生的违规以更高的概率被检测到。此外，如果触发错误的工作负载持续运行，健全性检查器在至少一次检查中检测到错误的几率会不断增加。
如果检测到错误，健全性检查器开始收集分析信息以包含在错误报告中。我们使用systemtap来分析所有负载均衡函数（例如，load_balance，select_task_rq_fair）的调用，以及这些函数执行的所有语句和它们使用的变量的值。我们使用这些分析来理解负载均衡函数是如何执行的以及为什么它们未能平衡负载。注意，我们不记录错误触发时的执行部分，但这不成问题，因为我们只想了解为什么所有负载均衡调用在一段显著时间内都失败了。
4.2 调度器可视化工具¶
我们即将描述的可视化工具在衡量错误症状的性质和进一步理解其根本原因方面非常有帮助。该工具随时间展示了显著的调度活动（本工具的图表已用于说明前一节中的错误）。这些图表依赖于对内核的额外检测，其开销可以忽略不计。我们的可视化工具可以分析并绘制（1）运行队列的大小，（2）运行队列的总负载，以及（3）在周期性负载均衡和线程唤醒期间被考虑的核心。为了提供最大的准确性，它不使用采样，而是记录运行队列大小或负载的每一次变化，以及每次负载重新均衡或线程唤醒事件中被考虑的核心集合。为了保持低开销，我们将所有分析信息存储在一个静态大小的内存中的大型全局数组中。此数组的每个元素都是一个对应于（1）、（2）或（3）的事件：
对于（1），我们检测内核函数
add_nr_running和sub_nr_running，这是唯一直接改变存储每个运行队列大小的变量的函数。在这些函数中，我们在我们的全局数组中存储一个事件，其中包含时间戳、核心号和新的运行队列大小。类似地，对于（2），我们检测内核函数
account_entity_enqueue和account_entity_dequeue，这是唯一直接改变存储每个运行队列负载的变量的函数。在这些函数中，我们在我们的全局数组中存储一个事件，其中包含时间戳、核心号和新的负载。最后，对于（3），我们检测内核函数
select_idle_sibling、update_sg_lb_stats、find_busiest_queue和find_idlest_group。在这些函数中，我们在我们的全局数组中存储一个事件，其中包含时间戳，以及一个位字段，其中0表示在该操作期间未被考虑的核心，1表示被考虑的核心。
在Linux内核中实现这些更改的代码不到150行。为了写入一个事件，一个线程使用原子增量指令来找到数组中写入事件的位置；然后它将事件写入内存，这可能会导致缓存未命中。在我们的架构上，存储每个事件需要20字节。在第3节中，产生事件频率最高的应用是商业数据库：它每秒产生约60,200个类型（1）的事件，每秒58,000个类型（2）的事件，以及每秒68,000个类型（3）的事件，总共每秒约186,200个事件。因此，当活动时，我们的分析器在一台有64个核心的机器上每秒使用3.6 MB的RAM。在实践中，分析器仅在检测到错误时才活动，其对非错误情况下的性能影响可以忽略不计。
除了对Linux内核的更改，我们还编写了一个内核模块，使得可以按需开始和结束分析会话，并将全局数组输出到文件中。我们还编写了绘制结果的脚本。图2、4和5是这些图的例子。
根据我们的经验，在我们开发了这些工具之后，确认和理解本文中描述的棘手性能错误，并在不同内核版本中检测它们，变得非常高效。由于这些工具能捕获重要的错误，同时又简单、几乎无开销且易于跨内核版本移植，我们相信将它们作为标准内核开发者工具带的一部分是一个好主见。
5. 经验教训¶
我们现在反思从这项研究中学到的教训，并指出开放的问题。
我们描述的错误是由于开发者希望在调度器中加入越来越多的优化，其目的主要是为了适应现代硬件的复杂性。结果，曾经是内核中一个简单独立部分的调度器，变成了一个复杂的怪物，其触角伸向了系统的许多其他部分，如电源和内存管理。本文中研究的优化是Linux主线的一部分，但研究界提出了更多的调度优化。
大约从2000年起，数十篇论文描述了新的调度算法，以应对资源竞争、一致性瓶颈和现代多核系统的其他特性。有算法调度线程以最小化共享缓存、内存控制器和多线程CPU流水线的竞争。有算法减少共享数据的线程之间的通信距离，并确定分配给多线程工作负载的最佳核心数。有算法解决了在非对称多核CPU上调度线程的问题，以及将调度与电源和温度管理集成的算法。最后，有算法管理NUMA系统上的内存，这与线程如何被调度密切相关，以及调度线程以最小化在具有非对称互连的系统上的通信延迟的算法。所有这些算法都显示出积极的好处，无论是在性能还是功耗方面，对于某些实际应用都是如此。然而，很少有被主流操作系统采纳，主要是因为不清楚如何将所有这些想法安全地集成到调度器中。
如果每个好的调度想法都被作为一个附加功能拍在一个单一的、庞大的调度器上，我们将面临更多的复杂性和更多的错误，正如我们在本文的案例研究中所看到的。我们需要的是重新思考调度器的架构，因为它再也不能保持为内核中一个小的、紧凑的、很大程度上孤立的部分。我们现在明白，我们今天目睹的硬件的快速发展将推动越来越多的调度器优化。调度器必须能够轻松地集成它们，并有一种方法来推理如何组合它们。我们设想一个由模块集合组成的调度器：核心模块和优化模块。核心模块体现了调度器的最基本功能：将可运行的线程分配给空闲核心，并以某种公平的方式在它们之间共享周期。优化模块对基本算法提出特定的增强。例如，一个负载均衡模块可能建议一个避免过度开销的替代负载均衡调度。一个缓存亲和性模块可能建议在一个线程最近运行过的核心上唤醒它。一个资源竞争模块可能建议一种减少竞争引起的性能下降的线程放置方式。核心模块应该能够接受来自优化模块的建议，并在可行时采取行动，同时始终维持基本的不变性，比如不让核心在有可运行线程时闲置。如何在多个优化冲突时组合它们，例如，如果一个缓存亲和性模块和一个资源竞争模块建议不同的线程放置，或者如果一个负载均衡器在移动线程到不同的运行队列时有破坏内存节点亲和性的风险，这是一个调度中困难的开放问题。
我们从这项工作中得到的另一个教训是可视化工具的至关重要性。如果不通过可视化与问题相关的执行事件，我们描述的错误的根本原因是不可能被理解的。可视化执行绝对不是一个新想法。虽然孤立的系统开发者集群（例如，Google的某些工程团队）已经接受了它，但整个开发者社区却缺少有效的可视化工具。有许多很棒的追踪收集工具，如systemtap，Pivot Tracing，或Intel Processor Tracing。然而，没有有效的可视化，开发者倾向于只总结和聚合追踪中可用的信息，这掩盖了导致错误和性能问题的异常值（想想过载唤醒错误！）。尽管可视化在概念上很简单，但实现有效的工具并不容易。执行追踪可能非常大，所以可视化所有东西既不可行也无用。理解要可视化什么，以及当用户不知道他们在寻找什么时如何让用户有效地探索追踪，是一个重要的开放问题。在可视化社区中肯定有关于这个主题的研究，但系统社区需要更积极地拥抱这些技术，并根据我们解决的系统问题的特殊性来调整它们。
6. 相关工作¶
性能错误 (Performance bugs)。性能错误是操作系统中一个反复出现的问题。Linux内核性能项目于2005年启动，旨在对抗性能回归。尽管做出了这些努力，操作系统研究人员仍反复报告性能错误。Boyd等人报告了各种可伸缩性错误，Harji等人报告了2.6内核中的其他类型性能错误。
Mollison等人提出了一个专门为调度器执行回归测试的工具。它针对作为LInux Testbed for MUltiprocessor Scheduling in Real-Time Systems (LITMUSRT)项目插件实现的实时调度器。该工具有限（例如，它不考虑阻塞）并且不针对Linux内核的公平调度策略（CFS）。
为了对抗性能错误，Perl等人建议在内核中添加断言，以检查函数调用是否及时完成。Shen等人建立了一个吞吐量模型来检查I/O的性能。这些技术使用断言来检测性能错误，这不适用于检测调度器中存在问题的负载不平衡。临时的负载不平衡是预期的，而不是问题。因此，我们的在线健全性检查器使用不同的设计来区分有问题和无问题的不变性违规。
内核正确性 (Kernel correctness)。大量工作也已在验证系统正确性方面完成。RacerX和Eraser检测死锁和竞争条件。Erickson等人检测内核模块中的数据竞争。将这些系统扩展到针对不一定导致系统崩溃的性能错误将是理想的；然而，这是一个难题，因为在我们的环境中，短期的不变性违规是可以接受的。
D3S，Likely Invariants，和ExpressOS使用不变性和谓词来检查简单操作的正确性（例如，确保变量在某个范围内）。我们的在线健全性检查器使得可以检测系统更微妙的不正确状态（即，当其他核心过载时，核心长时间空闲的系统），并且可以集成到操作系统中以验证更高层次的设计选择。
模型检查 (Model checking) 也已被用于检测内核中的错误。CMC向内核注入状态以发现实现错误。Yang等人使用模型检查在文件系统中发现了错误（例如死锁）。模型检查是发现在错误发生前找到它们的一种有用方法。由于可能的工作负载数量巨大以及与硬件行为（例如，拓扑结构，休眠核心的行为）的复杂性，调度器特别难以进行模型检查。模型检查器可以用来发现调度器中的崩溃错误，但据我们所知，这些工作中没有一个可以用来检测更微妙的性能错误。
形式化验证 (Formal verification) 是一种通过分析源代码来证明软件正确性的方法。传统上，形式化验证仅限于小型代码库和C以外的语言，但最近，通过几位操作系统研究人员的巨大努力，形式化验证被应用于操作系统内核。即便如此，这些最先进的方法也不适用于这里描述的错误，因为它们仅限于单线程环境，并且没有办法对时间进行推理。形式化工具通过将系统描述为一系列状态转换、前置条件和后置条件来工作，然后推理任何状态转换是否可能在给定可能的前置条件的情况下导致违反后置条件。问题在于，在我们的环境中，后置条件的短期和间歇性违规（即在有等待线程的情况下存在空闲核心）是完全可以接受的。有问题的是长期违规。不幸的是，现有工具没有允许推理时间如何影响不变性的瞬时违规的机制。将这些工具扩展到在多线程环境中工作并对时间进行推理可能会使它们更适用，但让Linux开发者编写形式化规范将是采纳这些工具的另一个障碍。
追踪 (Tracing)。由于我们遇到的一些错误的复杂性，特别是过载唤醒错误，分析工具不足以完全理解其原因：我们需要追踪来精确地跟踪调度器的行为。
已经提出了许多追踪工具来帮助检测性能错误。Event Tracing for Windows和DTrace是使得可以追踪应用程序和内核事件（包括一些调度器事件）的框架，适用于Microsoft Windows、Solaris、MacOS X和FreeBSD操作系统。Linux内核自带了一套追踪器，如Ftrace和SystemTap。一些额外的工具，如KernelShark，可以生成图形化追踪。
我们的在线健全性检查器不提供一种新颖的监控事件的方式，并且直接依赖于SystemTap来实现此目的。然而，我们的健全性检查器所做的而这些工具中不包含的是，检测不变性违规以便仅在性能错误发生时监控事件：一直运行现有的追踪工具对于检测性能错误几乎没有用，因为它们会产生大量数据，其中绝大多数由非错误执行的追踪组成，没有办法跳转到错误的追踪部分。此外，我们的可视化工具能够监控非常细粒度的调度器事件，这对于理解本文中提出的一些性能错误至关重要，例如单个调度事件（这使得可以绘制出每次线程跨核心移动时哪个调度事件负责），或工作窃取循环中的单个迭代（这使得可以监控在负载均衡期间考虑了哪些核心）。
7. 结论¶
调度，即在线程之间分配CPU周期，曾被认为是一个已解决的问题。我们表明情况并非如此。为了适应现代硬件的复杂性，一个简单的调度策略导致了一个非常复杂且容易出错的实现。我们发现Linux调度器违反了一个基本的工作保守不变性：将等待的线程调度到空闲核心上。结果是，当系统中有空闲核心时，可运行的线程可能会在运行队列中被卡住数秒；应用程序性能可能会多倍下降。这些错误的性质使得用传统工具难以检测它们。我们修复了这些错误，理解了它们的根本原因，并提出了工具，使得捕获和修复这些错误变得更加容易。我们的修复和工具将在 http://git.io/vaGOW 上提供。
（参考文献列表已省略）