The Linux Scheduler: a Decade of Wasted Cores
这是一篇介绍Linux调度问题的文章，源自这篇文章。文章中涉及到的一些问题可能已经得到解决，但可以学习一下本文所表达的思想和对CPU调度的理解。
这是EuroSys 2016系列论文中的第一篇，讲述了三个部分：首先，介绍了Linux内核调度任务的背景；其次，介绍了软件老化以及修改需求和维护是如何导致代码腐化的；最后，作者给出了Linux调度的四个错误，这些错误导致即使在有大量任务等待调度的前提下，仍然有CPU核处于空闲状态。因此，论文题目为"A Decade of Wasted Cores."
在我们的实验中，这些性能错误会导致大量重同步的应用的性能下降数倍，增加13%的内核延迟，并导致通用的商用数据库的吞吐量下降14-23%。
Linux调度的演化
总的来说，到2000年为止，操作系统设计者考虑到调度是一个需要解决的问题，2004年终结了Dennard 缩放比例定律，迎来了多核时代，使能效成为计算机系统设计中的头等大事。这些事件使调度器再度热门起来，但同时也增加了复杂度，且经常会导致调度失效。
Linux使用完全公平算法(CFS)，该算法使用了一个基于权重的公平队列。想象在单独的CPU系统上：CFS会给运行的线程分配时间片。该算法为系统上的每个线程设置了一个每次运行固定的最小运行间隔，该间隔会除以分配给线程的权重，进而算出时间片。
一个线程的权重本质上是其优先级，或UNIX上的
nice值。具有最低nice值的线程具有最高的权重，反之亦然。
一个运行的线程会累积vruntime (runtime / weight)。当一个线程的vruntime 超过分配给它的时间片后，该线程将会被抢占。
线程会被组织在CPU的run队列中(该队列使用红黑树实现)，并按照vruntime从小到大排序。当一个CPU查找一个新线程运行时，它将选择红黑树中最左侧的节点，即具有最小vruntime的线程。
到目前为止一切正常，下面考虑一下多核系统。
首先每个核都有一个run队列，这样可以快速地切换上下文。现在出现了一个新的问题，需要在多个run队列中进行负载均衡。
考虑一个具有两个run队列且不会进行负载均衡的双核系统。假设一个队列包含1个最小优先级的线程，而另外一个队列包含10个高优先级的线程。如果每个核仅从本地run队列中查找线程，那么高优先级的线程可能会获得比低优先级线程更少的CPU时间，这是不我们想要的。可以让每个核不仅检查其run队列，还检查其他核的队列，但这么做又违背了单核单run队列的初衷。因此Linux和大多数类型的调度器会周期性地运行一个负载均衡算法，使队列大致保持平衡。
由于负载均衡的代价比较昂贵，因此会限制调度器执行的频率。除了周期性地进行负载均衡，调度器还可以在一个核空闲的时候触发紧急负载均衡。CFS会根据权重和负载(结合了线程的权重和平均CPU利用率)来均衡run队列。为了解决当一个进程具有多个线程而另一个进程具有很少的线程时可能发生的偏差，在Linux2.6.37版本中引入了一个组调度特性(cgroup)。
当一个线程属于一个cgroup时，其负载会除以其cgroup中的线程总数。此功能后来被扩展为自动将属于不同tty的进程分配给不同的cgroup（autogroup 功能）。
那么此时可以通过比较所有核的负载将任务从负载最大的核转移到负载最小的核吗？很不幸，这样会导致线程的迁移(而没有考虑缓存位置和NUMA)。因此负载均衡器会使用一个分层策略。层次体系中的每一级都称为一个调度域。最底层为单个核，更高级别的分组取决于如何共享计算机的物理资源。
看下面的例子：
上图展示了一个32核的机器，包含4个node(每个node 8个核)，每对核使用SMT级别的共享。四个灰色的区域表示与机器的第一个核相关的调度域。注意，层次体系中的第二级为一个三个节点构成的组，这是因为第一个核可以通过一跳到达这三个节点。在第四级，包含了机器上所有的节点，因为所有的节点都在两跳内可达。
每个调度域都会运行负载均衡，调度的方向为从底层到上层。在每一层中，每个域都会使用一个核运行负载均衡。这个核可以是调度域中第一个空闲的核(如果该域包含空闲的核，且可以为负载均衡分配足够的CPU周期)，也可以是调度域中的第一个核。此后，会计算调度域中的每个调度组的平均负载，并(根据偏好超载和不均衡组的启发式方法)选择最繁忙的组。如果最繁忙的组的负载低于本地组的负载，则会考虑在这一层进行负载均衡。否则，负载将在本地CPU和组中最繁忙的CPU之间进行负载均衡，并进行调整以确保即使在存在任务集的情况下，负载平衡也能正常工作。
调度程序会通过仅在给定调度域的指定核上运行负载均衡算法来防止重复工作。如果所有核都处于繁忙状态，则它是域中编号最小的核；如果一个或多个核处于空闲状态，则使用编号最小的空闲核。如果空闲核正在休眠（电源管理），那么使它们工作的唯一方法就是被另一个核唤醒。如果某个核认为自身已经过载，则会在一段时间内检查系统中是否存在空闲核，如果存在，则唤醒第一个，并使其代表自己和所有其他空闲核定期运行负载均衡实例。
四个调度错误
由于关于何时不执行负载均衡器的规则如此之多，因此很难推断出在有工作要做的情况下，一个空闲核应该保持多长时间的空闲状态，以及在系统中有空闲核的情况下，一个任务可能要在一个run队列中等待的时长。
论文作者发现的四个错误为：组失衡错误，调度组构建错误，过载唤醒错误，以及丢失调度域错误。
组失衡
对于平均负载，Gil Tene(Azul Systems的CTO?)有说过：
当一个核尝试从其他节点(或其他调度组)拿取任务时，它不会检查组中的每个核的负载，仅会查看组的平均负载。如果选中的调度组的平均负载高于其本身的负载，则它会尝试从这个组中获取任务，反之则不会。这也是为什么在我们的环境下，低负载核无法从其他节点的高负载核上获取任务的原因。这些低负载核会观察那些平均负载高于它们的节点上的调度组，然后从高负载R线程所在的节点中获取任务，这类线程歪曲了该节点的平均负载的含义，可能存在某些核本身就处于空闲状态的事实。同时在经过调度之后的节点上，即使在(获取到任务的CPU和提供任务的组的)平均负载大致相同的情况下，仍然有很多等待线程。
可以通过比较最低负载而不是平均负载来修复这个问题。最低负载就是组中的最低负载的核上的负载。如果"调度组中的最低负载低于另外一个调度组的最低负载，则意味着，第一个调度组中存在一个核，其负载低于另外一个组中所有核的负载，因此第一个组中的核必须从第二个组中获取任务"。应用此修复程序后，使得一个执行R工作负载的完成时间减少了13％，使用60线程对具有四个单线程R进程的基准测试的运行速度提高了13倍。
调度组构建
Linux的taskset命令可以将应用固定到一组可用的核上。但将应用程序固定在相距两跳的节点上时，会存在阻止负载均衡算法在它们之间迁移线程的错误。
该错误是由于调度组的构建方式导致的，我们的实验中使用了一个不适用于NUMA机器的调度组构建的方式。简而言之，这些组是从特定核(核0)的角度进行构建的，但它们应该从负责每个节点的负载均衡的核的角度进行构建。
最终导致的结果是节点可能会包含到多个调度组中。假设节点1和节点2分到了两个组中：
假设一个应用固定到了节点1和2，且在节点1上创建了所有线程(Linux会在与其父线程相同的核上生成线程；当一个程序在初始阶段生成多个线程时，这些线程极有可能会在相同的核上进行创建--通常是这么做的)。最终，我们想要在节点1和节点2之间进行负载均衡。然而，当一个节点2的核尝试获取任务时，它会按照上面描述的方式对比两个调度组之间的负载。由于调度组同时包含节点1和节点2，导致平均负载是相同的，这样节点2将无法获取到任何任务！
不同的调度组(cgroup)应该使用不同的节点
过载唤醒
当一个线程在节点X上休眠，而后续唤醒它的线程在同一节点上运行时，调度器仅会考虑使用节点X上的核来调度被唤醒的线程。如果节点X上的所有核都处于繁忙状态时，将会在一个已经繁忙的核上唤醒该线程，导致这个线程失去了在其他节点的空闲核上运行的机会。这会导致计算机的利用率严重不足，尤其是在线程频繁等待的工作负载上。
该实现的初衷是提高缓存的重用率，但通过让某些应用在run队列中等待来提高缓存重用率的方式并不可行。该问题是由配置有64个工作线程的广泛使用的商业数据库触发的。
为了修复这个错误，需要更改线程唤醒时执行的代码，修改为在本地核上唤醒线程，即，线程最后调度的核(如果该核是空闲的)；否则如果系统的其他地方有空闲的核，则在空闲时间最长的核上唤醒该线程。如果不存在空闲的核，则回退到原始算法来查找唤醒线程的核。
该修复程序在第18个TPC-H查询上的性能提高了22.2％，在整个TPC-H工作负载上的性能提高了13.2％。
丢失调度域
最后的一个错误似乎是在维护期间无意中引入的。
当使用/proc接口禁用一个核，然后启用该核时，所有NUMA节点之间将不会执行负载均衡。我们跟踪了问题根因，发现代码重新生成了机器的调度域。每禁用一个核，Linux都会重新生成调度域。重新生成调度域分为两步：内核重新生成NUMA节点内部的域，然后生成跨NUMA节点的域。不幸的是，Linux开发者在代码重构时丢弃了生成跨NUMA节点的域的函数。添加该函数之后，问题被修复。
在修复前，禁用然后启用一个核会导致所有应用的线程都跑在同一个核上，而不是分布在八个核上。毫无疑问，该系统的修复效果要好得多（某种情况下，提高了138倍！）。
经验教训和工具
新的调度器设计不断出现，但一个新的设计，即使最初是干净的且被认为没有任何错误的，也无法做作为一个长期的解决方案。Linux是一个大型的开源系统，由大量贡献者共同开发。在这种环境下，我们不可避免地会看到新功能和"hacks "被更新到源代码库中，以应对不断发展的硬件和应用程序。
改进的模块化是答案吗？
现在，我们了解到，如今硬件的快速发展将推动越来越多的调度器的优化。调取器必须能够提供一个合理的方式来轻松地集成并组合这些优化。我们设想了一个调度器，它是一系列模块的集合：核心模块和优化模块…
很难用传统的工具来捕获本论文描述的问题(这些问题并不会导致崩溃或内存耗尽)，并且使用htop，sar或perf等工具无法注意到丢失的短暂的CPU核空闲时间。
我们的经验促使我们建立了新的工具，使用这些工具可以有效地确认错误并理解错误发生的原因。
论文作者描述的第一个工具是sanity checker(具体可以参见原始论文)。它会在一个核的run队列中有等待的线程时，检测是否存在空闲的核。该工具允许短暂出现这种场景，但如果一直存在，则会告警。第二个工具可以可视化展示调度活动，这样就可以剖析并绘制run队列的大小，run队列的总负载，以及负载均衡期间可以考虑的核以及唤醒的线程。
论文作者的总结：
将CPU周期切分到线程的调度方式被认为是一种解决问题的途径。但在我们的展示中，情况并非如此。为了适应现代硬件的复杂性，一个简单的调度策略最终演变成了一个非常复杂且非常容易导致问题的实现。我们发现Linux调度器违反了一个基本的节省工作时采用的不可变因素：将等待线程调度到空闲核上。最终可能导致在系统中有空闲核的情况下，一些线程仍然阻塞在run队列中；应用的性能可能会下降很多倍。这些问题的本质使得很难用常用的工具进行探测。我们修复了这些错误，了解了其根本原因并提供了工具，这些工具可以方便地捕获和修复这些错误，参见http://git.io/vaGOW.。
相关主题
在本篇文章的讨论中，有人提到了BFS调度算法，感兴趣的可以看下这篇文章。