简介围绕 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 而不是 ticktick 频率可配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 衰减因子 yy^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 的边界上算一次负载时刻计算式负载贡献1023usL0 102310232047us1023 (L0 1) * y20253071us1023 (L1 1) * y30054095us1023 (L2 1) * y39635119us0 (L3 1) * y38776143us0 L4 * y37927167us0 L5 * y37098191us0 L6 * y3627规律一眼可见当前负载等于上一周期负载乘以 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 n1d1 是补齐上一个周期剩余部分的时间d2 是中间完整的周期d3 是当前周期还没走完的零头。p 是跨过的周期数等于 1 d2/1024。为什么要拆 d1因为上一次更新时留下了一个不足 1024us 的尾巴代码里用 period_contrib 记着。这个尾巴必须和新时间差拼在一起才能凑成完整周期去衰减否则每次更新都把零头丢掉长期下来负载会被系统性低估。代入原文的例子上一次负载 u 1010经过 d 2124us拆成 d1 1016、d2 1024、d3 84p 2。套公式u 1010 * y^2 1016 * y^2 1024 * y 84 30241010 * 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 32y^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 * 63y^2016 2^-6364 位整数里这个权重已经小到没有意义再算就是浪费指令。这条边界也解释了为什么负载曲线只记「最近 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 1u y^p。三个 sum 一起衰减load_sum、runnable_load_sum、util_sum。它们衰减的是同一段时间所以用的是同一个 periods。这里能看出 sched_avg 的设计意图三类负载共用一套时间轴和衰减逻辑只是累加时依据的状态不同。load 看 runnableutil 看 running。共用一套衰减的好处是代码路径短update 一次只算一遍周期数代价是三个 sum 必须同步更新漏掉一个就会出现 load_avg 和 util_avg 对不上的怪现象。3.3 Step 2__accumulate_pelt_segments 里的 c1、c2、c3Step 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 * n1 * * inf inf * 1024 ( \Sum y^n - \Sum y^n - y^0 ) * n0 np */ 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_{n0}^{inf} y^n等比数列自相似乘一个 y^p 等于把求和起点整体往后挪 p 位max * y^p 1024 * \Sum_{n0}^{inf} y^(np) 1024 * \Sum_{np}^{inf} y^n拿 max 减去 max * y^p中间那段就露出来了max - max * y^p 1024 * \Sum_{n0}^{p-1} y^n再减掉 n0 那一项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 把 n0 那一项也算进去了但完整周期的贡献从 n1 开始算所以要把 n0 的基准项扣掉。这也解释了后面 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; };字段含义时间口径last_update_time上次更新时间单位 ns用于算 deltaload_sum可运行时间的负载累计runnablerunnable_load_sum同上4.18 里与 load_sum 相等runnableutil_sum正在运行时间的累计running且乘 scale_cpuperiod_contrib上次更新不足 1024us 的零头时间残量load_avg / runnable_load_avg归一化后的平均负载runnableutil_avg归一化后的平均利用率runningload_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本文还有配套的精品资源点击获取
