简介：围绕 Linux CFS 调度器引入 PELT 负载跟踪算法这一主题，PDF 讲义面向具备一定内核基础、想弄清调度负载统计机制的开发者与性能调优人员。内容先剖析 Linux 3.8 之前以运行队列（rq）为单位跟踪负载的局限：负载来源无法定位，稳定负载下数值仍剧烈波动；随后展开 1024us 周期划分、衰减因子、负载贡献累加公式与运行后转入睡眠的实例推演，并说明 decay_load() 与预计算数组如何用移位和乘法替代浮点运算（代码基于 Linux 4.18.0）。整包仅 1 个 PDF 文件，约 358KB，篇幅紧凑，便于随时翻阅与公式对照。已有 573 人学习，可借此理清 per-entity 负载的数学来源，掌握衰减计算与内核定点数优化思路。

1. PELT 为什么出现：rq 级负载看不清来源，也压不住抖动

linux CFS 的负载跟踪在 3.8 换过一次底层实现，换进来的就是 PELT，全称 per entity load tracking。换之前，负载是挂在运行队列上的一个数；换之后，负载变成了每个调度实体自己的一份独立记录。这个改动听起来只是统计粒度变细，但它真正解决的问题是：队列级的数在稳定负载下也会自己抖，而且你根本看不出是谁在抖。

两个任务交替跑，rq 的负载读数会一会儿高一会儿低；一个任务睡一觉再醒来，队列负载直接跳一截。调度器拿这种数去做负载均衡，就像拿一个一直在晃的秤称重，只能靠滤波硬压，压完又迟钝。PELT 换了个问法：不问「队列现在多重」，改问「过去这几十毫秒里，每个调度实体有多想跑」。这个问法一旦成立，负载就能跟着任务走，任务迁到哪个 CPU，账本就跟到哪个 CPU。后面 load_avg、util_avg 这些数看着简单，底下压着时间口径、衰减窗口、定点近似三层假设，不了解这层，看 trace 就是看玄学。

2. 1024us 与衰减因子：一条负载曲线是怎么被切出来的

2.1 为什么把时间切成 1024us，而不是按 tick 数

PELT 用的是物理时间，不是虚拟时间。虚拟时间会被权重缩放，拿来算负载就绕回去了。物理时间被切成 1024us 一段的序列，每个周期里，一个调度实体对系统负载的贡献等于它处于 runnable 状态的时间除以 1024。runnable 包括两段：正在 CPU 上跑的时间，以及在 rq 里排队等 CPU 的时间。这两段合起来才是「它想跑多久」，只算 running 会漏掉排队。

为什么是 1024us 而不是 tick？tick 频率可配，100Hz、250Hz、1000Hz 都有人用，tickless 内核里 tick 还会被关掉。拿 tick 当计量单位，同一份代码在不同配置下算出来的负载曲线不一样，这没法做跨平台调优。1024us 大约 1ms，和常见 tick 同量级，但完全独立于 tick 配置，tick 来不来都不影响衰减计算。这一点在 NO_HZ 场景下很关键：CPU 睡了 50ms 醒来，中间没有 tick，负载照样要按 50 个周期衰减，不能当无事发生。

还有一个细节容易被忽略。PELT 内部把时间差右移 10 位来换算单位，也就是拿 1024ns 当一个小刻度，而不是严格除以 1000。这是故意的：1024 是 2 的幂，编译出来就是一条移位指令，代价比除法低得多，代价是 2.4% 左右的时间膨胀误差。内核在很多地方都做过这种取舍，用一点点数值误差换取常数时间的算术。

2.2 衰减因子 y：y^32 = 0.5 是怎么定出来的

负载不能只记当前周期，那样和 rq 级负载一样抖。PELT 的做法是把历史周期也累计进来，但越久远的周期权重越低，低到一定程度就近似为零。衰减因子 y 取 0.97857206，满足 y^32 = 0.5。也就是说，32 个周期之前的贡献，权重只剩一半；64 个周期之前，只剩四分之一。

32 这个数字不是拍脑袋。CFS 的调度周期 sched_latency 默认在 6ms 量级，32 个 1ms 周期大约 32ms，能盖住好几个调度周期，既不会把很久以前的一次突发记到现在，也不会因为窗口太短而让负载曲线剧烈跳动。把 y 调小，负载对突发更敏感，但抖动回潮；把 y 调大，曲线更平滑，但任务负载下降后要很久才反映出来，调度器会误判它还很重。

从数学上看，这是一个等比数列。一个实体一直 runnable 时，它的负载总和收敛到：

L_max = 1024 * (1 + y + y^2 + y^3 + ...) = 1024 / (1 - y)

解析解约 47789。内核实际算出来的常量 LOAD_AVG_MAX 是 47742，差的那几十来自定点数迭代中的取整误差，不是推导错了。后面讲 c2 化简时会反复用到这个上限。

用原文那个例子可以把递推关系看得很清楚。一个 task 从 0 时刻开始跑，4096us 后一直睡眠，在每 1024us 的边界上算一次负载：

规律一眼可见：当前负载等于上一周期负载乘以 y，再加上本周期的新增贡献。任务睡眠后新增贡献是 0，曲线就纯衰减。这意味着实现上不需要保存所有历史周期，只留一个累计值加一个衰减因子就够了，空间复杂度从 O(n) 降到 O(1)。

2.3 通用公式：d 为什么必须切成 d1、d2、d3

上面例子里每次更新都刚好落在周期边界上，现实中不会这么凑巧。一次负载更新的时间差 d 可能是 2124us、也可能是 37us，必须有一个能处理任意 d 的公式。PELT 的做法是把 d 切成三段：

d1 d2 d3 ^ ^ ^ | | | |<->|<----------------->|<--->| |---x---|------| ... |------|-----x (now) p-1 u' = (u + d1) y^p + 1024 \Sum y^n + d3 y^0 n=1

d1 是补齐上一个周期剩余部分的时间，d2 是中间完整的周期，d3 是当前周期还没走完的零头。p 是跨过的周期数，等于 1 + d2/1024。为什么要拆 d1？因为上一次更新时留下了一个不足 1024us 的尾巴，代码里用 period_contrib 记着。这个尾巴必须和新时间差拼在一起，才能凑成完整周期去衰减，否则每次更新都把零头丢掉，长期下来负载会被系统性低估。

代入原文的例子：上一次负载 u = 1010，经过 d = 2124us，拆成 d1 = 1016、d2 = 1024、d3 = 84，p = 2。套公式：

u' = 1010 * y^2 + 1016 * y^2 + 1024 * y + 84 = 3024

1010 * y^2 是旧负载衰减两次；1016 * y^2 是补齐部分衰减两次；1024 * y 是中间那个完整周期衰减一次；84 是当前零头，不衰减。

公式再展开一步，就变成了源码里的两步结构：

u' = u y^p (Step 1) + d1 y^p + 1024 \Sum y^n + d3 (Step 2)

Step 1 只做一件事：把旧的 sum 整体衰减 p 次。Step 2 负责把新跨过的时间折算成贡献。这个拆分不是为了好看，是因为 Step 1 可以复用已有的 decay_load()，Step 2 则能把求和化简掉，下一章的代码就是照这个结构写的。

2.4 定点数近似：y^n 为什么提前算成一张表

内核态不用浮点。保存浮点上下文代价高，而且不同架构的浮点行为不一致，调度器这种核心路径不能冒这个险。所以 y^n 的计算全部走定点：把 y^n 乘以 2^32，存成 32 位整数，用的时候乘完再右移 32 位。

decay_load(val, n) = val * y^n * 2^32 >> 32

y^n * 2^32 提前算好放进 runnable_avg_yN_inv 数组，n 从 0 到 31。生成脚本在 Documentation/scheduler/sched-pelt.c 里，核心就一行：

runnable_avg_yN_inv[i] = ((1UL << 32) - 1) * pow(0.97857206, i);

数组前几项长这样：

static const u32 runnable_avg_yN_inv[] = { 0xffffffff, 0xfa83b2da, 0xf5257d14, 0xefe4b99a, 0xeac0c6e6, 0xe5b906e6, 0xe0ccdeeb, 0xdbfbb796, 0xd744fcc9, 0xd2a81d91, 0xce248c14, 0xc9b9bd85, ... 0x85aac367, 0x82cd8698, };

只存 32 项，因为 y^32 = 0.5 这个条件让任意 n 都能拆：y^n = 2^(-n/32) * y^(n%32)。n 大于等于 32 时，先把 val 右移 n/32 位（等价于乘 2^(-n/32)），再对 n%32 查表。这样一次移位加一次乘法就能算出任意 n 的衰减，时间复杂度是常数，和 n 多大无关。

n 超过 2016 时直接返回 0。2016 是 32 * 63，y^2016 = 2^-63，64 位整数里这个权重已经小到没有意义，再算就是浪费指令。这条边界也解释了为什么负载曲线只记「最近 64 个半衰期」，再往前的东西对现在没有影响。

3. accumulate_sum：一次负载更新被拆成了哪两步

3.1 入口：delta 先加 period_contrib

真正干活的函数是 accumulate_sum()。它的第一个动作不是算周期数，而是把上次留下的零头并进来：

static __always_inline u32 accumulate_sum(u64 delta, int cpu, struct sched_avg *sa, unsigned long load, unsigned long runnable, int running) { unsigned long scale_freq, scale_cpu; u32 contrib = (u32)delta; /* p == 0 -> delta < 1024 */ u64 periods; scale_freq = arch_scale_freq_capacity(cpu); scale_cpu = arch_scale_cpu_capacity(NULL, cpu); delta += sa->period_contrib; /* 1 */ periods = delta / 1024; /* ~1ms */ /* 2 */ if (periods) { sa->load_sum = decay_load(sa->load_sum, periods); sa->runnable_load_sum = decay_load(sa->runnable_load_sum, periods); sa->util_sum = decay_load((u64)(sa->util_sum), periods); delta %= 1024; contrib = __accumulate_pelt_segments(periods, 1024 - sa->period_contrib, delta); /* 3 */ } sa->period_contrib = delta; /* 4 */ contrib = cap_scale(contrib, scale_freq); if (load) sa->load_sum += load * contrib; if (runnable) sa->runnable_load_sum += runnable * contrib; if (running) sa->util_sum += contrib * scale_cpu; return periods; }

注释 1 加 period_contrib，是为了让零头参与这次周期划分。注释 2 算跨过的完整周期数。注释 3 里的1024 - sa->period_contrib就是 d1，注意这里用的是更新前的旧值，因为要补的是上一次留下的缺口。注释 4 把新零头写回去，给下次用。

contrib初值赋成 delta 有个前提：p 等于 0 时 delta 一定小于 1024，直接当贡献用没问题。进入 if 分支后 contrib 会被 Step 2 的结果覆盖，所以这个初值只服务于「没跨周期」的快路径。

load、runnable、running这三个参数在调用点传的是 0 或 1，不是权重。它们决定这笔贡献记不记到对应的 sum 上：实体在 rq 上，load 和 runnable 都为 1；实体正在 CPU 上跑，running 才为 1。权重是在后面归一化时才乘上去的，这个分工要分清楚，否则看代码会觉得 load_sum 的单位很怪。

3.2 Step 1：跨周期时旧 sum 先整体衰减

if (periods)里面的三行 decay_load 就是公式里的 Step 1，u y^p。三个 sum 一起衰减：load_sum、runnable_load_sum、util_sum。它们衰减的是同一段时间，所以用的是同一个 periods。

这里能看出 sched_avg 的设计意图：三类负载共用一套时间轴和衰减逻辑，只是累加时依据的状态不同。load 看 runnable，util 看 running。共用一套衰减的好处是代码路径短，update 一次只算一遍周期数；代价是三个 sum 必须同步更新，漏掉一个就会出现 load_avg 和 util_avg 对不上的怪现象。

3.3 Step 2：__accumulate_pelt_segments 里的 c1、c2、c3

Step 2 被单独抽成函数：

static u32 __accumulate_pelt_segments(u64 periods, u32 d1, u32 d3) { u32 c1, c2, c3 = d3; /* y^0 == 1 */ /* * c1 = d1 y^p */ c1 = decay_load((u64)d1, periods); /* * p-1 * c2 = 1024 \Sum y^n * n=1 * * inf inf * = 1024 ( \Sum y^n - \Sum y^n - y^0 ) * n=0 n=p */ c2 = LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, periods) - 1024; return c1 + c2 + c3; }

c1 和 c3 很直白：d1 补的是最远的缺口，要衰减 p 次；d3 是当前零头，不衰减。c2 是中间完整周期的贡献总和，如果老老实实写循环，p 大的时候要做几十次乘加，每次 tick 都这么干，开销不能接受。

3.4 c2 的等比数列化简：LOAD_AVG_MAX 为什么能当常数用

c2 的化简是这段代码里最巧的地方。先把 LOAD_AVG_MAX 的定义写清楚：

max = 1024 * \Sum_{n=0}^{inf} y^n

等比数列自相似，乘一个 y^p 等于把求和起点整体往后挪 p 位：

max * y^p = 1024 * \Sum_{n=0}^{inf} y^(n+p) = 1024 * \Sum_{n=p}^{inf} y^n

拿 max 减去 max * y^p，中间那段就露出来了：

max - max * y^p = 1024 * \Sum_{n=0}^{p-1} y^n

再减掉 n=0 那一项（1024 * y^0 = 1024），剩下的正好是 c2 要的 n 从 1 到 p-1 的求和：

c2 = max - max * y^p - 1024

一次减法加一次 decay_load，把 p-1 次乘加压成了常数时间。这是整个 PELT 实现里性能最关键的一步，没有它，periods 大的时候每次更新都要线性扫一遍历史周期。

c2 里减 1024 还有一层物理含义：LOAD_AVG_MAX 把 n=0 那一项也算进去了，但完整周期的贡献从 n=1 开始算，所以要把 n=0 的基准项扣掉。这也解释了后面 divider 为什么是LOAD_AVG_MAX - 1024 + period_contrib：满负载时 sum 的上界就是这个值。

3.5 乘权重与 capacity 缩放

最后三行把贡献记到三个 sum 上，其中两处缩放值得单独说：

contrib = cap_scale(contrib, scale_freq); if (running) sa->util_sum += contrib * scale_cpu;

scale_freq 是 CPU 当前频率相对最大频率的比例，scale_cpu 是这颗 CPU 的最大算力。同样跑 1ms，大核和小核的 util 贡献不一样，降频时和满频时也不一样。这是 PELT 支持异构 CPU 和 DVFS 的接口：调度器眼里「一个 CPU 有多忙」不能用时间直接除，得按算力折算。

注意 load_sum 和 runnable_load_sum 没有乘 scale_cpu，只有 util_sum 乘了。因为 load 衡量的是「任务想占多少权重」，跟 CPU 多强没关系；util 衡量的是「这颗 CPU 被占用了多少算力」，必须按算力归一。两个口径混用，负载均衡就会把重任务往小核上推。

4. sched_avg 与 update_load_avg：负载记在哪、什么时候刷新

4.1 sched_avg 的 8 个字段分别对应什么时间口径

负载信息装在 struct sched_avg 里，每个调度实体 se 和每个 cfs_rq 都带一份：

struct sched_avg { u64 last_update_time; u64 load_sum; u64 runnable_load_sum; u32 util_sum; u32 period_contrib; unsigned long load_avg; unsigned long runnable_load_avg; unsigned long util_avg; };

load_sum 和 runnable_load_sum 在 4.18 里数值相等，原因是 __update_load_avg_se() 调用时两个参数都传了!!se->on_rq。这两个字段并存是为了兼容组调度：group se 的 runnable 属性可能和 load 属性分开算，task se 上暂时看不出区别。看到两个字段就以为有两条独立曲线，是读这段代码常见的误会。

4.2 task se 与 group se 的初始化差异

se 初始化走 init_entity_runnable_average()：

void init_entity_runnable_average(struct sched_entity *se) { struct sched_avg *sa = &se->avg; memset(sa, 0, sizeof(*sa)); /* * Tasks are initialized with full load to be seen as heavy tasks until * they get a chance to stabilize to their real load level. * Group entities are initialized with zero load to reflect the fact that * nothing has been attached to the task group yet. */ if (entity_is_task(se)) sa->runnable_load_avg = sa->load_avg = scale_load_down(se->load.weight); se->runnable_weight = se->load.weight; }

task se 初始化成满权重，group se 初始化成 0。task 这边是刻意高估：新任务还没跑过，调度器不知道它重不重，宁可先当重任务对待，让它有机会上 CPU，也不能先当轻任务，结果被塞到一个已经很忙的核上。高估的代价是会误迁移几次，低估的代价是延迟爆炸，两害相权取其轻。group 那边初始化为 0 就好理解，组里还没挂任务，负载当然是 0。

runnable_weight 是给 group se

本文还有配套的精品资源，点击获取