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

Bugs

决定一次负载均衡是否要发生有很多的规则，因此也就很难推断如果有工作可作时一个空闲核能够维持空闲多久，也很难推断在系统中有空闲核时，任务变为可运行状态前还要在运行队列里等待多久。因为之前极少数的开发者可以在第一次就写出完美的代码，这种复杂性又导致了bug的出现。弄明白这个bug是必要的，这样才能搞明白为什么他们避开了传统的测试和调试工具。因此，我们首先将描述这引起bug, 延后在展示我们所使用的工具。

Group负载不均衡问题

当我们在执行一个kernel编译和使用R语言机器学习包作数据分析时，我们在多用户机器上遇到了这个bug。我们假设这个系统是有8个节点，64个核的NUMA服务器，对于大量线程的计算并没有用到所有的核，作为替代的所有这些线程都挤在了很少的几个节点上。我们使用我们的可视化工具演示了这个bug，参见下图中的2a和2b。

上图中显示了一个时间周期内的数据，这台机器使用64个线程执行一个kernel的编译任务，同时运行两个单线程的R进程。这个Make任务和这两个R进程使3个不同的ssh连接来运行。图2a是一个每个核的运行队列中跑的线程数量的热力图，越是暖颜色，这个核上承载的线程数越多；白色表示这个是个空闲的核。这个图表显示了有两个节点，它们的core上只运行了一个线程或者完全没有运行线程，其余的节点则处于过载状态。

调查后，我们发现调度器没有作负载均衡，因为(1) 这个跟踪负载的统计是复杂的 (2) 当前负载均衡的分层设计。让我们先关注于这个负载。应该还记得我们将负载定义为权重和它需要使用多少CPU的组合吧。当系统开启了autogroup特性后，这个线程的负载同样要除以它的父autogroup中的线程数。在我们的情况中，拥有64个线程的make进程中的一个线程的负载（因为它所在的autogroup中有64个线程 ，所以一个线程的负载要变为1/64）大约是R进程中这个单线程负载的1/64。

线程间负载的差异如图2b所示，它显示了每个核上运行队列中所有线程负载之和：更深的颜色表示越高的负载。节点0和4，上面各运行一个R进程，每个节点上都有一个核（每个节节点8个核，那么这两个节点上就有7个核是空闲的）的负载很高。Linux的负载均衡器会基于负载从其他的运行队列中来窃取工作任务；目前看起来很显然节点0和4上无负载的核不会从它们自己节点上的过载的核上来拿取工作任务，因为这核上只有一个单线程进程在运行。

应该还记得由于负载均衡算法复杂度的限制，这种负载均衡算法使用层级设计。当一个核从其他节点窃取工作任务时，或者换句话说，从其他调度组窃取工作任务时，它并不会检查这个组里每个核的负载，它只看这个组的平均负载。如果这个被它选取的组的平均负载大于它自己的负载，它就会尝试从这个组窃取工作任务；反之不会。这就是为什么在我们的场景中无负载的核无法从其他节点过载的核窃取工作任务的准确原因。在这里观察到这些被评估的节点的调度组的平无负载都没有大于当前节点的负载。试图窃取工作任务的核运行在和这个高负载R线程相同的节点上；这个线程扰乱了这个节点的平无负载，它隐藏了其他核实际上是空闲的事实。与此同时，在那些有大致相同负载的其他节点上，存在大量等待的线程。

一个合理的问题是在这种情况下工作窃取是否要发生，因为理论上我们希望有高负载的线程比低负载的线程获取到更多的CPU时间。这个问题的答案是"yes": Linux的CFS调度器本质上是work-conserving的（这个不知道怎么翻译成中文，意思是这种调度器尽量使调度资源始终处于忙碌的状态），因此一些线程在系统中有空闲核时可能会获取到比公平共享情况下更多的CPU周期；换句话说，空闲核将总是分配给等待的线程。但是正如我们在上图看到的，事实并非如此。

为了修复这个问题，我们改变了比较调度组负载的算法的一部分，我们比较最小负载来代替比较平均负载。这个最小负载是一个组里面最小负载的核的负载。如果这个调度组的最小负载小于另一个调度组的最小负载，它意味着第一个调度组有核的负载小于其他组的所有核的负载，因为这第一个组里的核必须要从第二个组里窃取任务工作。这个算法确保当第一个组里有轻负载的核时第二个组里没有核心维持在高负载。注意这个修复是工作的，因为同一个组内的负载同样是均衡的。这个改变不会增加法算法的复杂度，计算这个最小负载和计算平均负载有着相同的成本。以我们的经验，这个修复不会导致在调度组之前迁移的数量增加。

调度组构建的问题

Linux上有个命令叫taskset, 它允许将应用固定在有效的CPU核心的一个子集上运行。这一节中我们描述的问题发生在当应用被固定在相距两跳的两个节点上时。在下图4中显示我们的NUMA机器的拓扑结构。

其中节点1和节点2相距两跳。这个bug将会阻止负载均衡算法在这两个节点间迁移工作任务。由于线程总是和创建它的父线程位于相同的节点上，这样就造成了被固定的应用的所有线程都跑在同一个节点。

这个问题是由于调度组的构成方式导致的，它已经不适用于我们在实验中所使用的NUMA机器。简单来讲，这个调度组是从特定核(core 0)的视角云构建的，实际上应该是从每个节点上负责负载均衡的节点的视角云构建。

在我们的机器上，像上图所显示的，第一个调度组包括节点0，加上到它相距一跳的所有节点，包括节点1，2，4和6。第二个调度组包括不在第一个组中的第一个节点的核，即节点3，再加上和节点3相距一跳的所有节点的核: 节点1，2，4，5，7。因为这两个调度节点是：

我们注意到节点1和2包含在两个调度组里，进一步注意到这两个节点实际上彼此之间相距两跳。如果从节点1的角度来构建这个调度组，节点1和节点2不会同时出现在所有组里。让我们看看这意味着什么。

假设应用被固定在节点1和节点2上并且它所有的线程都是在节点1上创建的。最终我们希望在节点1和2之间负载均衡。但是，当节点2上的核心查找它可以窃取的工作任务时，它将比较前面显示的两个调度组的负载。因为每个调度组都包括了节点1和2，它们的平无负载是相同的，因此节点2将不会窃取任何的工作任务。

这个问题源自我们尝试改进大型NUMA系统的性能。在引入这个问题之前，Linux将在NUMA节点内部来均衡负载，然后是跨所有的NUMA节点来均衡。新的层级结构的引入是为了增加线程的创建尽量保持在原来的NUMA节点上的可能性。

为了修复这个问题，我们更改了调度组的构造方法，因此当前每个核都使用从它自身角度来构建的调度组。修复后，当节点1和2的核心尝试从机器这个层级来窃取工作任务时，节点1和2不再包含在所有调度组里。这些核心因此能够侦测到负载不均衡并可以窃取任务。

线程被唤醒时发生过载的问题

这个问题是说当系统中有空闲核时，一个睡眠的线程被唤醒后可能会运行在一个过载的核心。这个bug是因为一个唤醒代码里的优化（select_task_rq_fair）而被引入的。当一个线程睡眠在节点X上并且稍后唤醒它的线程也运行在相同的节点上时，调度器只会考虑将这个被唤醒的线程调度到节点X所在的核心上。如果节点X上所有的核心都在忙，这个线程被唤醒在已经很忙的核心而没有机会使用其他节点上的核。这将导致相当低的机器处用率，特别是在线程频繁等待的工作负载上。

这个优化背后的基本原理是最大化cache的复用。调度器尽量将唤醒的线程放到物理上靠近执行唤醒的线程，即它们两者运行在共享最后一级cache的核心上，认为对于生产-消费类型的工作负载，这个唤醒线程将消费由被唤醒线程生产数据。这看起来是个合理的想法，但对于为了更好的cache复用目的而等待在运行队列中的那些工作任务，是没有回报的。

这个bug是被一个配置了64个工作线程并且执行一个TPC-H工作负载的广泛使用的商用数据库触发的。这个工作负载搭配上其他应用程序的大量短暂线程，触发了调度组不均衡和唤醒时过载这两个问题。因为我们已经在上一节中描述了调度驵不均衡的问题，所以在实验中为了更好的演示唤醒时过载的问题，我们禁用了auto-groups功能。

上图演示了唤醒bug的几种形式。在第一个时间周期，有一个核是空闲的，理想情况下线程将调度到这个核上，但事实上却保持唤醒在那个忙碌的核上了。在第二个时间周期内，有三个核已经空闲很久，另外三个线程却被在其他忙碌的核上被唤醒。

这个唤醒后过载的问题是典型地由短暂线程被调度到运行数据库线程的核上引起的。这发生在内核运行那些执行时间小于一毫秒的背景操作，比如logging或是IRQ处理。当这种情况发生时，这个负载均衡器在运行短暂线程的节点观察到很重的负载，并且迁移一个线程到其他节点。如果被迁移的是这个短暂线程，那这不是问题，但如果是数据库线程，那这个唤醒后过载的问题将命中。节点B现在运行额外的数据库线程，这个线程经常睡眠又被唤醒，即使在这个节点上没有空闲的核，依然保持其在节点B上被唤醒。这种情况会发生，是因主为唤醒逻辑代码为了更好的复用cache, 仅会考虑会本地节点选择核。

现在我们明白了即使系统中有空闲核，但线路是为何还在本地的核心上被唤醒的。请注意在上面中系统最终从负载不均衡中恢复了：这个负载均衡算法最终将线程从过载的核心迁移到了空闲的核心。问题是，为什么它过了一段时间才完成这个恢复？

注意到系统中有两类空闲内核：短期的和长期的。短期空闲核是针对短周期的，因为数据库线程运行在这样的核上，会由于同步或 IO事件而间歇性的睡眠。理想情况下我们希望这个负载均衡是从过载的核迁移到长期空闲的核上。迁移到短期空闲的核上只有很小的帮助：曾经运行在这个核上的线程将很快被唤醒，并且就如我们所见，由于cache本地化的优化，调度器可能放置它到相同节点的其他过载的核心上。这样负载不均衡将因此而持续。

遗憾的是，当调度器考虑将线程从过载的核心迁移到哪里的时候，它不会区分短期有效还是长期有效。从前面的章节我们应该还记得这个负载均衡算法是被“特定的核”在不同的层级上调用的。如果有多个空闲核都是符合要求的特定的核，只会从中选择一个。如果我们足够幸运，这个长期的空闲核被选中并且负载将恢复。这正好是上面图中发生的事情，系统最终恢复了负载均衡。然而，就像我们看到的，单纯靠幸运是不足以维护系统性能的。

为了修复这个问题，我们更改了线程唤醒时执行的代码。如果该线程最后一次被调度的核是空闲的，我们就在这个本地核上唤配它；否则，如果系统中有空闲核，我们就在有最久空闲时间的核上唤醒它。如果系统中没有空闲核，我们回退到原始的算法找到可以使用的核。

在长期空闲的核心上唤醒线程可能会影响能源消耗。长期处于空闲状态的核心通常会进入到低能效状态。在这样的核心上唤醒线程将强制核心退出这种状态并运行在全功率模式。由于这个原因，我们仅仅在系统能源策略不允许进入低能效的情况下使用这种新的唤醒策略。此外，我们的修复仅仅作用于工作负载线程经常睡眠和被唤醒并而系统间歇性的过载的情况下。在这种场景下，在长期空闲核心上唤醒线程是有意义的。在其他场景下，因为线程唤醒是不常发生的，我们的修复不会改变调度器的行为。

在系统中查找长期空闲的核心没有增加这个唤醒函数的开销：内核已经维护了一个所有空闲核心的列表，只需要取第一个就可以，耗时是常量时间。

缺少调度域的问题

当一个核心被禁用然后又允许后，在任意NUMA节点间的负载均衡都不会再执行。这个bug是由于用来表示机器上调度域数量的全局变量的错误更新所导致的。当核心被禁用时，这个变量被设置为NUMA节点内部的调度域的数量，其结果是这个主调度循环将比预期的提前退出。

结果是，一些线程只能运行在核心被禁用前所在的节点上。对于禁用核心后创建的进程，所有的线程都运行在父进程相同的节点上。因为所有进程通常都是从相同的“root”进程创建的，这个问题通常将导致所有新创建的线程仅运行在机器上的一个节点上，而有线程的数量无关。

上图是这个问题的可视化呈现。这个有16个线程的应用程序运行在这台机器上。当线程被创建后，节点1上的所有核运行两个线程。其中蓝色竖直的线源自core 0, 表示当尝试窃取工作任务时， Core 0会考虑的核心。因为调度循环提前退出，Core 0仅会考虑他所在的节点上的核心，并且不会考虑节点1上的核心。

我们跟踪了这个问题的根本原因并且重构了重新产生调度域的代码。Linux在每次core被禁用时重新产生调度域。这分为两个阶段：首先是kernel产生NUMA节点内部的调度域，然后是跨NUMA节点的调度域。

讨论

要问的第一个问题是这些bug能否通过一个新的，整洁的调度器设计来解决，并且这个设计有很少的错误，容易调试，但是依然保持着我们今天已有的功能特性。从历史上来看，这看起来不像是一个长期的解决方案，除了新设计需要从头实现和测试这个事实。Linux调度器经过了几次重新设计。其中最初的调度器有很大的算法复杂度，在有大量的多线程工作负载情况下性能表现不佳。在2001年，它被O(1)调度器取代，它在SMP系统上有更好的扩展性。它最初是成功的，但随着像NUMA和SMT这种新架构的出现它也需要作出改变。同时，用户需要有针对桌面系统更好的支持，比如交互场景等。尽管进行了大量的更改，这个O(1)调度器还是不能满足期望，最终在2007年被CFS调度器取代。有趣的是，CFS损失了O(1)算法的O(log n)的时间复杂度，但是它是值得的，原于它提供了人们要想的功能。

由于硬件和工作负载变得越来越复杂，CFS最终屈从于这个bug。Autogroups和层级式负载均衡的一起加入导致了调度组不均衡的bug。越来越复杂的NUMA系统导致了调度组构建的问题。现代多节点计算机上缓存一致性的开销推动了缓存本地化优化，这导致了唤醒时过载的问题。

在最近发布的Linux 4.3 内核引起了load metric的新的实现。简化这个load metric能够摆脱掉调度组不均衡的问题。然而，我们确认使用我们的工具观察，这个问题依然存在。内核开发者依赖彼此code review和测试来避免引入问题。这对于像缺少调度域和调度组构建这样容易获取到的bug来说是有效的，但是对其他类型的bug就不一定了。

通过测试或传统的性能监控工作来捕获这些bug是困难的。它们不会导致系统崩溃或者内存溢出，它们会默默地吃掉系统性能。就像我们看到的调度组不均衡和唤醒时过载的bug, 他们导致了短暂的空闲周期，在不同的核心间来回往复。这些微小的空闲周期不能被像htop, sar或perf这些的性能监控工作所捕获。标准的性能常规测试同样无法捕获这个问题，它们发生在非常特殊的场景。