The Linux Scheduler: a Decade of Wasted Cores
这是一篇介绍Linux调度问题的文章，源自这篇文章。文章中涉及到的一些问题可能已经得到解决，但可以学习一下本文所表达的思想和对CPU调度的理解。
这是EuroSys 2016系列论文中的第一篇，讲述了三个部分：首先，介绍了Linux内核调度任务的背景；其次，介绍了软件老化以及修改需求和维护是如何导致代码腐化的；最后，作者给出了Linux调度的四个错误，这些错误导致即使在有大量任务等待调度的前提下，仍然有CPU核处于空闲状态。因此，论文题目为"A Decade of Wasted Cores."
Linux调度的演化
Linux使用完全公平算法(CFS)，该算法使用了一个基于权重的公平队列。想象在单独的CPU系统上：CFS会给运行的线程分配时间片。该算法为系统上的每个线程设置了一个每次运行固定的最小运行间隔，该间隔会除以分配给线程的权重，进而算出时间片。
一个运行的线程会累积vruntime (runtime / weight)。当一个线程的vruntime 超过分配给它的时间片后，该线程将会被抢占。
到目前为止一切正常，下面考虑一下多核系统。
首先每个核都有一个run队列，这样可以快速地切换上下文。现在出现了一个新的问题，需要在多个run队列中进行负载均衡。
由于负载均衡的代价比较昂贵，因此会限制调度器执行的频率。除了周期性地进行负载均衡，调度器还可以在一个核空闲的时候触发紧急负载均衡。CFS会根据权重和负载(结合了线程的权重和平均CPU利用率)来均衡run队列。为了解决当一个进程具有多个线程而另一个进程具有很少的线程时可能发生的偏差，在Linux2.6.37版本中引入了一个组调度特性(cgroup)。
那么此时可以通过比较所有核的负载将任务从负载最大的核转移到负载最小的核吗？很不幸，这样会导致线程的迁移(而没有考虑缓存位置和NUMA)。因此负载均衡器会使用一个分层策略。层次体系中的每一级都称为一个调度域。最底层为单个核，更高级别的分组取决于如何共享计算机的物理资源。
看下面的例子：
上图展示了一个32核的机器，包含4个node(每个node 8个核)，每对核使用SMT级别的共享。四个灰色的区域表示与机器的第一个核相关的调度域。注意，层次体系中的第二级为一个三个节点构成的组，这是因为第一个核可以通过一跳到达这三个节点。在第四级，包含了机器上所有的节点，因为所有的节点都在两跳内可达。
调度程序会通过仅在给定调度域的指定核上运行负载均衡算法来防止重复工作。如果所有核都处于繁忙状态，则它是域中编号最小的核；如果一个或多个核处于空闲状态，则使用编号最小的空闲核。如果空闲核正在休眠（电源管理），那么使它们工作的唯一方法就是被另一个核唤醒。如果某个核认为自身已经过载，则会在一段时间内检查系统中是否存在空闲核，如果存在，则唤醒第一个，并使其代表自己和所有其他空闲核定期运行负载均衡实例。
四个调度错误
论文作者发现的四个错误为：组失衡错误，调度组构建错误，过载唤醒错误，以及丢失调度域错误。
组失衡
对于平均负载，Gil Tene(Azul Systems的CTO?)有说过：
可以通过比较最低负载而不是平均负载来修复这个问题。最低负载就是组中的最低负载的核上的负载。如果"调度组中的最低负载低于另外一个调度组的最低负载，则意味着，第一个调度组中存在一个核，其负载低于另外一个组中所有核的负载，因此第一个组中的核必须从第二个组中获取任务"。应用此修复程序后，使得一个执行R工作负载的完成时间减少了13％，使用60线程对具有四个单线程R进程的基准测试的运行速度提高了13倍。
调度组构建
Linux的taskset命令可以将应用固定到一组可用的核上。但将应用程序固定在相距两跳的节点上时，会存在阻止负载均衡算法在它们之间迁移线程的错误。
最终导致的结果是节点可能会包含到多个调度组中。假设节点1和节点2分到了两个组中：
不同的调度组(cgroup)应该使用不同的节点
过载唤醒
该实现的初衷是提高缓存的重用率，但通过让某些应用在run队列中等待来提高缓存重用率的方式并不可行。该问题是由配置有64个工作线程的广泛使用的商业数据库触发的。
该修复程序在第18个TPC-H查询上的性能提高了22.2％，在整个TPC-H工作负载上的性能提高了13.2％。
丢失调度域
最后的一个错误似乎是在维护期间无意中引入的。
在修复前，禁用然后启用一个核会导致所有应用的线程都跑在同一个核上，而不是分布在八个核上。毫无疑问，该系统的修复效果要好得多（某种情况下，提高了138倍！）。
经验教训和工具
改进的模块化是答案吗？
很难用传统的工具来捕获本论文描述的问题(这些问题并不会导致崩溃或内存耗尽)，并且使用htop，sar或perf等工具无法注意到丢失的短暂的CPU核空闲时间。
论文作者描述的第一个工具是sanity checker(具体可以参见原始论文)。它会在一个核的run队列中有等待的线程时，检测是否存在空闲的核。该工具允许短暂出现这种场景，但如果一直存在，则会告警。第二个工具可以可视化展示调度活动，这样就可以剖析并绘制run队列的大小，run队列的总负载，以及负载均衡期间可以考虑的核以及唤醒的线程。
论文作者的总结：
相关主题
在本篇文章的讨论中，有人提到了BFS调度算法，感兴趣的可以看下这篇文章。