Reconsidering the scheduler's wake_wide() heuristic

英文链接：https://lwn.net/Articles/728942/

在多核系统上，内核的调度子系统不仅仅要去决策下一个任务跑啥，还得决策下一个任务跑在哪个核上。通常情况下，这种决策被称为“启发式搜索算法”，即一种基于经验法则的最佳实践模式。2015年，有一个关键的“Task-placement heuristic（任务放置启发式搜索算法）”出现了，不过最近的一场讨论让人们开始重新审视它的合理性。

调度器唤醒这事儿总是在发生：任务经常会等待一个事件（比如：定时器过期，POSIX信号，futex()系统调用等等）；这类事件发生的时候，任务被唤醒并继续执行。调度器的任务是找到最适合这个刚被唤醒的任务运行的CPU，所谓核心选得好，任务回家早，选对正确的核心对应用的性能极其关键。一些消息传递型的负载，如果运行在同一个CPU上，性能会更好。比如说 pipetest，它有一对收发任务轮流执行，这对任务永远不用也不会并行执行，这样如果他们的数据都保存在一个CPU的cache里，性能就会好得多。

不过在现实生活中，应用程序不会有这么密集的通信，而大多数负载也不会这么轮流发消息，所以一般的高并发的应用都是在响应外部输入后发出消息，而发出消息的时机都是随机的。这里一个非常典型的例子是生产者消费者模型，一个主任务唤醒多个从任务。这种类型的负载，如果其任务同时运行于多个CPU上，性能就会好很多。不过现在机器上CPU很多，怎么挑选一个最好的CPU来跑我们的任务变得非常重要。

另一方面，调度时对CPU的选择也会影响功耗，如果把任务堆在少部分CPU上运行，那么剩下的CPU就可以进入节能模式，如果一个 Socket 上的CPU都空闲了，那么可以更加省电。如果一个节能模式下的空闲CPU被调度上来一个任务，由于CPU从低功耗转变为耗能模式，成本就相应增加了。

所以综上所述，调度器需要根据唤醒模式来猜测负载是什么类型的，并以此来决策上面的任务是要集中运行于少部分CPU上以增加 cache 命中率并节能，还是要全打散来获得更高的CPU利用率。这便是当初 wake_wide() 函数被发明的背景。这个函数是让调度器变得更加错综复杂的众多启发式搜索算法之一，它决定一个刚被唤醒的任务是应该团结在唤醒它的那个任务所运行的CPU附近，还是应该志在远方，跑到另一个 NUMA 节点上去运行。这里面会有个 tradeoff，把任务打包在一起的方式可以提高本地缓存命中率，做过头了却也容易让CPU忙不过来，增加runq的调度延迟。

历史

下面让我们回到过去，wake_wide() 的功能是 Mike Galbraith 在 2015 年引入的。当时的背景是基于 Facebook 的 Josef Bacik 的一段问题描述：Facebook有一堆对延迟敏感的重度多线程应用，使用的是生产者-消费者模型，其中每个NUMA节点都有一个主任务。如果调度器尝试把任务集中到临近的CPU，那么任务唤醒时很可能会被丢到忙的CPU上，导致应用性能急剧下降。对于此应用，共享本地Cache的需求并没有那么迫切，更加重要的是要尽快找到一个空闲的CPU来运行任务。

所以 Galbraith 发明了一个切换算法，用"flips"来描述任务之间唤醒的次数，以动态的区分主从关系。这种启发式算法在 wakewide() 里实现，输入给 selecttaskrqfair() 并且指导其找到最合适的放置刚唤醒的任务的CPU。这个函数可简单了，下面就是全部的代码：

static int wake_wide(struct task_struct *p)
{
    unsigned int master = current->wakee_flips;
    unsigned int slave = p->wakee_flips;
    int factor = this_cpu_read(sd_llc_size);
    if (master < slave)
        swap(master, slave);
    if (slave < factor || master < slave * factor)
        return 0;
    return 1;
}

如果 slave 任务少于共享一个 LLC 的CPU数（按：一般来说是一个 Socket 下的所有核共享一个LLC）， wakewide 会返回0来表示这个任务不应该在另一个LLC的domain上唤醒，这个时候，selecttaskrqfair() 会相应地把任务打包，只在一个LLC domain里找空闲的CPU。

如果任务比CPU多，或者没找到主从对应关系，任务就会允许在另一个LLC domain上运行，更耗时的全局搜索空闲CPU的逻辑就会被执行。如果另一个LLC domain上的空闲CPU被选中，当前的功耗状态会影响调度选择，从一个更低功耗的状态中退出进入高功耗执行状态会耗费一段时间，所以调度器会倾向于选择功耗状态相对最高的空闲CPU，这样唤醒延迟会尽可能最小。

新方向？

历史从来不是一成不变的。最近Joel Fernandes 就 wakewide() 的设计提出了一些问题，他说：“我不明白为啥要把 slave 的 flips 乘以 LLCsize”(即代码中的 master < slave * factor）。Bacik也回应说，现在的代码或许打包任务打包得太激进了，特别是当大家共享一个LLC却没什么收益的时候，他还说：“我在怀疑 slave < factor 这个判断条件，我想当本地缓存没那么要紧的时候，这个标准定得太高了。”他建议把这个判断表达式去掉可能可以修复激进打包的问题。

原作者（Matt Fleming）提供了一些数据来证明去掉这个判断条件可以提升 hackbench 的性能，原因和前面 Bacik 说的那个例子有关系，当任务被打包得太密集的时候，就会有这个现象。 hackbench 里的任务不是一对对简单的读写关系，而是所有任务在整体内部相互通信。如果 hackbench fork 出更多这种适合在一个LLC domain里运行的任务，那么最终 benchmark 开始的时候，任务就会平均分配到不同的LLC domain里，接下来任务间的通信就有可能会跨LLC domain来回往复进行，这样就会引起极差的cache使用率，性能也就相应差了。

Galbraith 迅速回应并警告说，对 wake_wide() 函数草率地改动是不明智的：“如果你有想法去改进或者替换当前的启发式算法，去做就是了，不过一定要保证成本要足够的低。启发式算法不是这里糟糕就是那里糟糕，问题就在于人们总是想过度优化他”。不过 Bacik 还是想全局利用整个系统的CPU资源，调节调度器不要那么激进地把任务打包到一个LLC domain中去。他怀疑当时 Facebook 的那个 case 中，如果一个 LLC domain 内部没有空闲CPU的时候执行系统全局搜索空闲CPU，那么Facebook当时的负载情况下延迟能进一步降下来。

遗憾的是，在这些讨论中我们并没有听到来自那些把功耗视作第一要务，而把性能排在第二位的开发者的观点，而他们的意见对于这个讨论非常重要。因为如果把 wake_wide() 的打包模式改得不那么激进，那么很可能会有潜在的功耗相关的 Regression，到时候又有人要跳了。

回到原点

讨论到最后也没有任何一方占据上风。Bacik也承认这个修改建议或许有点太重了。也许大家最终想看到的是一个权衡居中的方案。所以基于这个修改的测试和分析还会继续。不过即便如此，我们悲观的认为最后很可能也不会有一个完美的解决方案。理由么，其实很简单；用benchmark和分析工具来量化现本文中提到的行为是很简单的，但是如果要发明一个普适性的，可以同时提升所有负载类型的性能的方案，这是一个真正巨大的挑战。不过借用马老师的一段话，”梦想还是要有的，万一实现了呢？” 所以让我们拭目以待吧。