重新审视调度器中的 wake_wide() 启发式搜索算法

原文链接：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”来描述任务之间唤醒的次数，以动态的区分主从关系。这种启发式算法在 wake_wide() 里实现，输入给 select_task_rq_fair() 并且指导其找到最合适的放置刚唤醒的任务的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）， wake_wide 会返回0来表示这个任务不应该在另一个LLC的domain上唤醒，这个时候，select_task_rq_fair() 会相应地把任务打包，只在一个LLC domain里找空闲的CPU。

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

历史从来不是一成不变的。最近Joel Fernandes 就 wake_wide() 的设计提出了一些问题，他说：“我不明白为啥要把 slave 的 flips 乘以 LLC_size”(即代码中的 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和分析工具来量化现本文中提到的行为是很简单的，但是如果要发明一个普适性的，可以同时提升所有负载类型的性能的方案，这是一个真正巨大的挑战。不过借用马老师的一段话，”梦想还是要有的，万一实现了呢？” 所以让我们拭目以待吧。