Dec 1, 2017

Toward Better Cpu Load Estimation

https://lwn.net/Articles/741171/ @思适

1. 负载跟踪的基本介绍：

首先，先介绍一个术语“负载跟踪”（load tracking），其解释如下：内核会不断尝试跟踪每一个运行的进程，来监测系统CPU上会因此增加äº多少的负载量（load），这个过程就叫负载跟踪。好的负载跟踪会根据系统近期的需求作出一些合理的预测，相应的，它（好的负载跟踪）也可以被用来优化进程的位置（具体在哪个cpu上）和CPUé¢率参数；很显然，不好的负载跟踪最后得到的结果就不是最佳的。尽管目前看起来，开发者还无法做出一个完美的负载跟踪，但是要想做到比当前内核所做的还要好，这个还是非常可行的。Patrick Bellasi最近做的一套补丁（the utilization estimation patch set）就能够让调度器（scheduler）的负载跟踪运行的很好，即便是在负载量很大的情况下。

一直到现在，我们还是无法知道内核中的每个进程ä¼给CPU增加多少的负载量，内核可以追踪每一个进程的CPU使用率，但是这个和追踪运行状态的进程中有多少可用的CPU时间相比而言，二者是完全不同的，前者也是不如后者更加有用。在2013年时候ï¼per-entity load-tracking (PELT) mechanism的代码被合并了，它可以监控得到每个正在运行的进程对CPU需求量的平均值。随着时间的推移，这个平均值会很快地衰减，也就是说进程最近的行为对于负载跟踪的贡献比之前行为的贡献要大。只要当进程被阻断（blocked）时候，PELT的值（平均值）会被保存（也在继续衰减中）起来，可以更好地展现了它们进程的CPU使用情况。

PELT代码能够在很大程度上æ¹善调度器的现状，慢慢地我们就能够去预测一定数量的进程可能会对CPU的需求量大小了，然后就可以将这些进程平均分配到每个CPU上，这个“schedutil”CPU频率控制器（CPU-frequency governor）可以在ç³»统能够承受当前负载量的CPU级别上，设置内核CPU的频率，但是内核无法操作CPU更加高的级别。短期内来看，PELT机制还是推动了内核的CPU调度器的发展。

1. 负载跟踪的问题

但是这个并不意味着PELT是完美的。实际上来说，自从它被合并到内核后，开发者几乎走到了一个瓶颈，移动设备（mobile）和嵌入式（embedded）社区对此代码一直抱怨着，他们最关心的问题一直是CPU的响应性（responsiveness）：EPLT的缺点是需要很长一段时间才能响应系统负载的变化。例如，用户在移动设备上打开浏览器时，肯定是希望能够快速打开它，但是有了PELT代码的话，它将会消耗几个32ms的测量周期（measurement cycles）去监测浏览器会给系统带来多少的负载量，在这段时间内，浏览器可能会被很不幸运的切换掉（包括其他CPU的密集型进程），其次CPU可能不会以正常来说那么高的频率去运行。实际ä¸，在CPU上以一个非常慢的频率去运行这样的进程，这会导致PELT消耗更加多的时间去计算预测值。

在这个补丁（the first posting of the utilization estimation patch set， 2017年八月份的）中，Bellasi以另一个方式表述了这样一个问题：“在移动设备的世界中，一些比较重要的进程会和帧缓冲区刷新的速率同步更新，所以它们以每16ms周期去运行是非常常见的。所有工作都在这一个16ms的新帧生成的时é´内发生，所以能够具体知道在这段时间内每个进程运行时候需要CPU的带宽是多少是非常重要的。”

PELT运行的时间比16ms长很多，所以在进程负载的情况下，会消耗一些时间（几个时间周期）才è½拿到进程句柄（handle）。当然PELT的累计时间是可以改变的，例如，PELT通过decay算法计算得到了负载预测值（load estimate），这个值可能会随着时间的变化而变化，甚至当相关进程在周期性运行时ä¹是如此，依然会不断的变化着。如果一个进程没有做任何事情而睡眠了一段时间，那么它的负载预测值（load estimate）将会非常快速的下降到0，这个意味着此进程一旦开始运行，调度器就不会保存它需要的有用的信息了。

为了提升PELT的性能，开发者已经做出了很多的尝试了。这个算法（the window-assisted load tracking, WALT算法）主要是解决掉负载预测值的衰减情况，然后关注CPU最近的行为æ况。现在已经有一些设备上使用WALT算法了，但是这个算法还没有合并到主线上，可能是担心在某些情况下会让负载跟踪变得效果更差。Qualcomm（高通公司）往前迈了很大一步，它用很多尚未被å并的变量（根据系统不同情况而改变）来代替了调度器的大部分代码，这些新的代码还没有被提交到内核邮件列表上，也没有考虑到是否要合并到主线上这个问题。

1. 负载跟踪的改善

现在，å©用率预估（utilization estimation）有了一个更加简单的方法，可以有更好的机会能遍历所有的用例（use cases），这个是基于观察得到的结果：尽管PELT可能会很费劲去描述一个长时间没有运行当进程æ¶，这时等待它从停止运行然后去睡眠的点来预测是一个很好的选择。但是PELT衰减得很快，那些信息很快就会没了，然后不得不等到下一次进程运行的时候PELT才重新运行了。如果内核要能够做到那些end-of-run的测试，那么就能很好地知道进程在下一次运行时需要什么了。

所以利用率预估的补丁并没有改变PELT算法，相反地，无论何时只要一个进程不再运行，当前的利用率值（utilization value）就会被添加到一个平均数（这个数字是不断变化的）中，这个平均数代表了内核对进程下次运行时会需要什么的一个最佳的猜测值。设计者将这个值设计的相对变化的比较慢，也不会因为进ç¨不再运行就会衰减，所以即使进程休眠了很长一段时间，这个值（full value）也是一直存在的，。

无论何时，如果一个系统需要观察一个运行的进程带来的负载量时，要么计算总的CPU负载量或设置CPU的频率时，系统都会在已经保存的估测值和当前由PELT计算得到的值中选择更大的一个作为估测值，换句话说，这个估测值会在计算进程负载量时作为最下限（lower bound），如果PELT计算得到了一个更高的值时，这个更高的值就会被使用。当一个进程变成运行状态时，它的负载量就会马上被设置到当前保存的估测值中，考虑到调度器情况，在合适的情况下这个估测值就会代替进程，然å设置CPU的操作参数。

这个估测代码的代价是，如果运行这个benchmark基准测试（perf bench sched messaging）时，大约会有1%的性能损失（performance hit），如果长期运行的话那个可能是一种损失（hit）ï¼但是面向吞吐量（throughput-oriented）负载量不希望有这样的性能损失，所以这个补丁集默认情况下设置不开启利用率预估（utilization estimation），如果想要开启它，需要设置SCHED_UTILEST调度器的比特位才行。

1. 负载跟踪的现状

很少有人去写这个补丁集的review评论，所以目前看来想让这个代码合并进入主线还是一件很困难的事情，因为很大程度上可能会回滚一些人的工作。在这种情况下，就不会有什么人去改动这部分负载跟踪的代码了，所以只有回滚的可能性应该会非常低的。也许在主线内核里针对这个调度器一直以来存在的问题，开发者们还是有足够的时间和精力可以去做出ä¸些改变的。