2.7.1 负载追踪 - 简介
介绍什么是负载追踪，以及什么是PELT（Per-entity Load Tracking）
提到负载，首先会让人想到命令 uptime 或 top 输出中的系统平均负载（load average），例如 uptime 的输出结果如下：
load average的三个值分别代表过去1分钟、5分钟、15分钟的系统平均负载，这三个值实际上来自于 /proc/loadavg, Linux的系统平均负载是系统中处于 runnable 与 uninterruptible 两个状态的任务总数与CPU数量的比值。
load average 的计算逻辑在
fs/proc/loadavg.c 中, 这里不再详述。通常情况下，在评估负载时系统只会计算处于runnable状态的任务，Linux 将uninterruptible状态的任务也考虑在内的原因可以详见Brendan Gregg的这篇文章
从系统角度而言，平均负载反映了系统面临的总体压力，而如果我们将视角切换到任务的话，那么从本质上来说，系统负载代表着任务对系统资源的渴求程度。
现在我们抛开系统负载，继续回到调度器中来。调度器想要更好地完成工作，就必须知道每个任务的负载，例如调度器可以通过一个任务过去的负载来对将来的调度策略进行修正，还有调度器在SMP架构下做负载均衡时，了解每个任务的负载情况也更有利于做出合理的任务迁移决策。准确地说，调度器需要知道的是每个调度实体（sched entity）的负载，而如何对其进行量化，是我们首先需要考虑的问题。
负载代表着一个se对系统资源的渴求程度，当在调度器的语境下讨论时，系统资源仅局限在CPU上，那么我们如何量化一个se对CPU的渴求程度呢？
我们知道权重决定了一个任务的时间配额，那可以直接将权重当成任务的负载使用吗？一个权重更高的任务对CPU的需求更加强烈，这听起来是合理的，但要注意权重是一个静态量，而负载却是一个动态量，而且还是一个瞬时量，它反应的是任务在当前时刻对CPU的需求。如果一个高优先级任务此时处于睡眠状态，而低优先级的任务此时处于可运行状态，那么当前情况下低优先级的任务反而负载更高，因为此时低优先级任务对CPU有需求，而高优先级没有。
也就是说除了权重，我们还需要考虑任务的运行时间，准确地说应该是任务处于可运行状态的时间，因为这个时间才代表了任务对CPU的所有潜在需求。在总时间T中，如果任务处于可运行状态的时间总量为t, 那么 load = weight * t/T 看起来是一个合理的负载表达方式，如下图所示：
虽然上述公式中我们已经考虑了与负载相关的所有变量，但仍然存在问题，考虑这种情况：权重相同的任务A与任务B在昨天同一时刻启动，A先狂飙了半天然后进入了睡眠状态，而B先睡眠了半天然后一直狂飙到现在，很明显当前时刻B的负载 要远远高于A，但上述公式却会得到一样的结果。根本原因是上述公式实际上计算的是负载的累计值，我们可以将图中的负载拆分成 load = (t1/T + t2/T + t3/T + t4/T) * weight, 而在累计过程中，过去的时间与当前时间对结果的影响是等价的，也就是说 t1/T 与 t4/T 这两个分量对最终结果的贡献相同。而实际上距离当前时间越远的任务负载，对当前时刻负载的影响应该越小，也就是说，我们的公式在累计历史负载时，应该对其进行一定程度的衰减（decay）。为了修正上述公式，我们引入衰减因子y, 那么上图中更合理的负载计算公式应该长得像这样： load = weight * (t1 * y^3 + t2 * y^2 + t3 * y + t4)/T
顺着这个思路，我们就可以设计出最终的负载计算公式了：将时间划分为一定粒度的周期，然后将所有周期的负载按照一定的衰减比例累加起来。Linux中计算负载的公式如下： L = L0 + L1*y + L2*y^2 + L3*y^3 + ..., 其中时间周期为1ms(为了计算方便，系统将其约等于1024us), 衰减因子y满足 y^32 = 0.5, 也就是说负载的半衰期为32ms, 而每个周期的负载贡献Ln就是当前周期内任务处于runnable状态的时间（包括实际运行的时间以及在rq中等待调度的时间）。
Linux中对调度实体（sched entity）的负载追踪叫着PELT(Per-entity Load Tracking), 详细介绍可以参考文章：https://lwn.net/Articles/531853/
Last updated
