简介这是一份深入解析Linux内核CFS调度器与PELTPer Entity Load Tracking算法的技术资料主要面向内核开发、系统性能优化及调度器研究者。资源以PDF形式呈现全文围绕Linux 3.8引入PELT的背景、设计思路与实现细节展开对比说明此前基于运行队列负载跟踪的缺陷并基于Linux 4.18.0源码逐步推导负载贡献公式、衰减因子y的计算方式以及decay_load()函数和runnable_avg_yN_inv数组的优化原理。文中包含完整的公式演算与代码片段便于读者对照内核源码理解调度器的负载追踪机制。压缩包共1个文件类型为PDF整体大小约358KB内容紧凑、适合作为内核调度专题的参考笔记。目前已有572人学习下载对于希望深入理解CFS调度器负载追踪细节的读者具有实用参考价值。1. PELTper-entity load tracking为什么 rq 级负载会让 CFS 决策失灵一个稳定负载的系统里CFS 在 Linux 3.8 之前却常常做出让人看不懂的调度决策罪魁祸首恰恰是它自己的负载跟踪方式按 runqueue 记账。rq 级负载把十个任务压成一个总数来源不可见而且任务进出队会让总数大幅摆动哪怕真实负载纹丝不动。PELTper entity load tracking改变了记账粒度让每个调度实体自带宽衰减的历史账本从此 load_avg、util_avg 才有了可信的出处。要搞懂 PELT关键不是背公式而是理解三个机制1024us 周期如何切分物理时间、衰减因子 y 如何压缩历史、内核如何用整数运算避开浮点。下面这份基于 Linux 4.18.0 源码的拆解把这条链路从数学模型到数据结构完整过一遍。2. 负载贡献模型1024us 周期和衰减因子如何把历史压进一个数2.1 物理时间切片为什么周期定在 1024usPELT 使用的计时基准是物理时间不是 CFS 的虚拟时间。虚拟时间服务于公平性它把权重换算成 vruntime 去决定下一个跑谁而负载跟踪要回答的是「这个实体在过去一段真实时间里占用了多少 CPU 资源」这直接关系到功耗预测、迁移决策和频率调节所以必须用墙上时钟来量。时间被切成 1024us 的固定周期一个实体在某个周期内处于 runnable 状态的时间如果是 x那它对系统负载的贡献就是 x/1024。注意 runnable 包含两种状态正在 CPU 上执行以及在就绪队列里等待执行。这两者在后续的 load_sum 与 util_sum 中被拆成两个维度现在先统一当作「占坑」时间。1024us 约等于 1ms但选 1024 而不是 1000 不是巧合。内核里时间差以 ns 为单位delta 10就能把 ns 换算成 us一次右移完成除 1024如果周期是 1000us就得做一次除法。PELT 的更新路径在调度 tick 和 enqueue/dequeue 里频繁触发这里的开销差异会被放大。历史负载不能无限累积否则一个任务十年前跑过一毫秒今天贡献还是满的。PELT 的解法是衰减L L0 L1 * y L2 * y^2 ... Ln * y^n其中 Li 是第 i 个周期该实体的负载贡献y 是衰减因子。这个公式决定了负载跟踪是「带遗忘的滑动平均」越久远的历史权重越低而衰减的速度由 y 唯一决定。2.2 一个 task 的负载轨迹8 个时间点手工推演先不看源码把公式用手算一遍。假设一个 task 从 0 时刻加入 rq 后连续运行 4096us然后开始睡眠。文档里给出了 8 个采样时刻的负载贡献这里是完整推演时刻计算式负载贡献1023usL0 102310232047usL1 1023 1024y 1023 (L0 1)y20253071usL2 1023 1024y 1024y^2 1023 (L1 1)y30054095usL3 1023 1024y 1024y^2 1024y^3 1023 (L2 1)y39635119usL4 0 1024y 1024y^2 1024y^3 1024y^4 0 (L3 1)y38776143usL5 0 L4 * y37927167usL6 0 L5 * y L4 * y^237098191usL7 0 L6 * y L5 * y^2 L4 * y^33627从这张表能读出两个关键规律。运行期间前 4096us由于 4095us 时已经跑满了 4 个整周期加 1023us之后每个周期新增的贡献都是1024 * y^k的衰减叠加但当前周期不满的部分直接加上去。一旦任务进入睡眠L4 起不再有新增贡献负载只能按 y 等比衰减——这解释了为什么 PELT 输出的曲线是平滑衰减而不是阶跃归零。另一个规律是递推关系每个新时刻的负载只需要「上一时刻的负载总和乘以 y再加上当前不足一个周期的时间」就能算出来不需要回放全部历史。这个性质是后面accumulate_sum()只保留period_contrib一个残差字段的数学基础。2.3 通用公式d1/d2/d3 三段分解再看一个更一般的场景它要回答的问题是如果上一次更新负载的时刻并不恰好落在周期边界上中间经过了一段任意长度的时间该怎么算假设上一时刻负载贡献是 u当时已经在一个 1024us 周期里累计了 1022us。又过了 10us 后这 10us 里前 2us 和之前的 1022us 凑成了一个完整周期这个周期需要衰减一次剩下 8us 属于当前周期不需要衰减。于是负载变成1022 * y 2 * y 8 1010。注意那 2us 虽然物理上属于「新经过的时间」但它落在上一个不满周期里所以也要乘 y。如果把时间间隔拉长到 2124us情况更复杂。这 2124us 可以分解成三段1016us 补齐上一时刻不足 1024us 的部分1024us 一个完整周期84us 当前周期剩余。经历的总周期数 p 2于是负载贡献是1010 * y^2 1016 * y^2 1024 * y 84 3024。1010y^2 是旧负载经过两个周期的双重衰减1016y^2 是补齐部分的双重衰减1024y 是中间那个完整周期的一次衰减84 是当前残差。写成通用形式设上一时刻负载为 u经过时间 dd 被分解成 d1补齐上个不完整周期、d2完整周期、d3当前残差p 1 d2/1024则u (u d1) * y^p 1024 * (y y^2 ... y^(p-1)) d3这个公式的几何级数部分后面会被LOAD_AVG_MAX封闭成一个常数差的形式。现在记住它分两步先衰减旧值再叠加新贡献源码里对应accumulate_sum()的 Step 1 和 Step 2。3. decay_load()查表加移位内核怎么用整数算 val * y^n3.1 浮点不可用锚点 y^32 0.5上面所有推演里y 是一个浮点数 0.97857206。调度热路径上做浮点运算是大忌CFS 在每次 enqueue、dequeue、tick 都要更新负载浮点乘法的延迟和功耗都不可接受。内核的做法是把衰减计算变成整数查表和移位。关键在于 y 的一个性质y^32 0.5。也就是说每经过 32 个周期约 32ms历史负载衰减为原来的一半。这个锚点把任意次幂归约成两步每 32 次方右移一位除以 2余下的幂次查表。这是整套定点化方案能够成立的前提。3.2 预计算 runnable_avg_yN_inv把 y^n 存成 32 位整数要计算 val * y^n不能直接乘浮点数。内核把 y^n * 2^32 的结果预先算好存进runnable_avg_yN_inv数组。计算过程对应内核文档里的sched-pelt.c生成程序核心逻辑可归纳为static const u32 runnable_avg_yN_inv[] { 0xffffffff, 0xfa83b2da, 0xf5257d14, 0xefe4b99a, 0xeac0c6e6, 0xe5b906e6, 0xe0ccdeeb, 0xdbfbb796, 0xd744fcc9, 0xd2a81d91, 0xce248c14, 0xc9b9bd85, 0xc5672a10, 0xc12c4cc9, 0xbd08a39e, 0xb8fbaf46, 0xb504f333, 0xb123f581, 0xad583ee9, 0xa9a15ab4, 0xa5fed6a9, 0xa2704302, 0x9ef5325f, 0x9b8d39b9, 0x9837f050, 0x94f4efa8, 0x91c3d373, 0x8ea4398a, 0x8b95c1e3, 0x88980e80, 0x85aac367, 0x82cd8698, };数组索引 n 的值满足runnable_avg_yN_inv[n] y^n * 2^32n 的范围是 0 到 31。第 0 项是 0xffffffff等于 (1 32) - 1对应 y^0 1 的定点表示。每一项都略小于前一项正好体现 y 在 0 到 1 之间。之所以只需要存 32 项是因为超过 31 次方后可以利用 y^32 0.5 归约y^33 * 2^32 0.5 * y * 2^32也就是runnable_avg_yN_inv[1] 1。任意 y^n 都能拆成「右移 n/32 位」加「查表 n%32」这正是下一节decay_load()的实现思路。3.3 decay_load() 逐行2016 周期上限与 32 周期归约看一下内核里的实际实现/* * Approximate: * val * y^n, where y^32 ~ 0.5 (~1 scheduling period) */ static u64 decay_load(u64 val, u64 n) { unsigned int local_n; if (unlikely(n LOAD_AVG_PERIOD * 63)) /* 1 */ return 0; /* after bounds checking we can collapse to 32-bit */ local_n n; /* * As y^PERIOD 1/2, we can combine * y^n 1/2^(n/PERIOD) * y^(n%PERIOD) * With a look-up table which covers y^n (nPERIOD) * * To achieve constant time decay_load. */ if (unlikely(local_n LOAD_AVG_PERIOD)) { /* 2 */ val local_n / LOAD_AVG_PERIOD; local_n % LOAD_AVG_PERIOD; } val mul_u64_u32_shr(val, runnable_avg_yN_inv[local_n], 32); /* 3 */ return val; }第一个边界条件是 n 超过LOAD_AVG_PERIOD * 63即 2016 个周期时直接返回 0。这是用「半衰期」凑出来的精度上限y^2016 (y^32)^63 0.5^63大约等于 2 的 63 次方分之一。64 位整数里val 右移 63 位后必然归零所以在安全边界处提前返回避免无意义的计算。换句话说PELT 的负载记忆窗口大约是 2016 个周期约 2 秒超过这个窗口的历史视为彻底遗忘。第二个边界处理 n 大于等于 32 的情况。val local_n / LOAD_AVG_PERIOD完成除 2 的整数次幂local_n % LOAD_AVG_PERIOD把剩余幂次收敛到 0 到 31 的查表范围。这里的右移之所以安全是因为前面已经用 2016 上限保证移位次数不会超过 63 位。第三步是核心运算mul_u64_u32_shr(val, runnable_avg_yN_inv[local_n], 32)。它的语义是计算 64 位 val 乘 32 位查表值得到一个 96 位中间结果再右移 32 位取高 32 位作为最终值。因为查表值本身就是 y^n * 2^32右移 32 位恰好消掉放大因子得到的整数部分就是 val * y^n 的定点近似。整条路径只有一次乘法和两次移位没有任何浮点指令。4. accumulate_sum 与更新链路从公式到 sched_avg4.1 accumulate_sum()period_contrib 和 periods 怎么算上一章解决了「单次衰减怎么算」这一章要解决「一段任意长度的时间段怎么折算成周期贡献」。公式u (u d1)y^p 1024 * sum(y^n) d3在代码里被拆成两步先衰减旧值再累加新贡献。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; /* A period is 1024us (~1ms) */ /* 2 */ /* * Step 1: decay old *_sum if we crossed period boundaries. */ if (periods) { sa-load_sum decay_load(sa-load_sum, periods); /* 3 */ sa-runnable_load_sum decay_load(sa-runnable_load_sum, periods); sa-util_sum decay_load((u64)(sa-util_sum), periods); /* * Step 2 */ delta % 1024; contrib __accumulate_pelt_segments(periods, /* 4 */ 1024 - sa-period_contrib, delta); } sa-period_contrib delta; /* 5 */ 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; }sa-period_contrib记录的是上次更新时「当前周期内已累计但不足 1024us」的时间。新的 delta 加上它才能算出从上一个周期边界到现在一共跨过了多少个完整周期。periods delta / 1024得到周期数也就是公式里的 p。进入if (periods)分支后Step 1 对旧的三个 sum 统一做decay_load衰减衰减次数是 p。这一步对应公式里的u * y^p。Step 2 里delta % 1024得到当前周期残差 d3然后调用__accumulate_pelt_segments()计算 d1 和中间完整周期的贡献。最后sa-period_contrib delta存下本次残差作为下次更新的起点。注意contrib在if (periods)之外还有一个初值(u32)delta它处理的是 p 0 的情况两次更新间隔不足一个周期没有衰减直接累加当前运行时间。这也是热路径上的常见场景比如两次 tick 间隔只有几百微秒。4.2 __accumulate_pelt_segments()几何级数的封闭解contrib的核心计算在__accumulate_pelt_segments()里它把公式里的三段贡献合并成一个整数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 是 d1补齐上个不完整周期的残留时间经过 p 次衰减后的贡献直接用decay_load计算。c3 就是当前残差 d3乘以 y^0 1不需要衰减。c2 是最有意思的优化。它本来的定义是1024 * (y y^2 ... y^(p-1))一个 p 项几何级数求和。如果老老实实循环累加p 可能到几十甚至上百调度路径上不可接受。代码用了一个技巧定义 LOAD_AVG_MAX 为无穷级数1024 * (1 y y^2 ...)的和它收敛到一个常数于是有限项求和可以写成两个无穷级数之差再减掉首项c2 LOAD_AVG_MAX - (LOAD_AVG_MAX * y^p) - 1024LOAD_AVG_MAX * y^p正是decay_load(LOAD_AVG_MAX, periods)。整个 c2 的计算变成两次decay_load加一次减法与 p 的大小完全无关时间复杂度 O(1)。这个「用无穷级数封闭有限求和」的手法是 PELT 实现中最漂亮的数学化简。4.3 LOAD_AVG_MAX47742 是怎么收敛出来的LOAD_AVG_MAX 是无穷级数1024 * (1 y y^2 ...)的和理论值是 1024 / (1 - y)。把 y 0.97857206 代进去能算出约 47767。但内核文档里的生成程序calc_converged_max()不是用浮点除法而是用定点递推模拟真实计算路径void calc_converged_max(void) { int n -1; long max 1024; long last 0, y_inv ((1UL 32) - 1) * y; for (; ; n) { if (n -1) max ((max * y_inv) 32) 1024; /* * This is the same as: * max max*y 1024; */ if (last max) break; last max; } printf(#define LOAD_AVG_MAX %ld\n, max); }递推式max max * y 1024展开后就是等比数列部分和(max * y_inv) 32是定点版本的乘 y。循环一直迭代到两次结果相等为止这时候数值不再变化就是收敛点。用定点模拟跑出来的值是 47742和理论值 47767 差 25 左右差值来自每次右移 32 位的截断误差——这个误差在可接受范围内因为 PELT 本身是近似估计不追求精确到个位。47742 还有一个用途它决定了___update_load_avg()里平均值的除法器。divider LOAD_AVG_MAX - 1024 sa-period_contrib即负载总和除以这个 divider 得到归一化的平均负载。这个设计隐含了一个性质load_sum的理论最大值就是 LOAD_AVG_MAX 级别差一个1024 - period_contrib的残差项所以除法器恰好把满负载归一化到接近 100%。4.4 struct sched_avg 与更新入口四个字段各管什么负载信息落在struct sched_avg里每个调度实体se和每个 CFS 就绪队列cfs_rq各持有一份。字段语义如下字段含义更新时间维度last_update_time上次负载更新时间用于计算 delta每次更新load_sumrunnable 时间的负载贡献总和含等待与运行跨周期衰减 累加runnable_load_sum与 load_sum 同源针对 se 更新时两者相等同 load_sumutil_sumrunning 时间的负载贡献总和只算真正在 CPU 上执行跨周期衰减 累加period_contrib当前周期内不足 1024us 的残差每次更新load_avgload_sum 归一化后的平均值由 divider 换算util_avgutil_sum 归一化后的平均值由 divider 换算load_sum和util_sum的差别是关键。runnable 的 entity 可能在排队也可能在运行这两者都对「是否占坑」有意义所以计入 load_sum但只有真正占用 CPU 的时间才消耗计算资源、产生功耗所以计入 util_sum。EAS能耗感知调度依赖 util_avg 做频率调节CFS 的负载均衡依赖 load_avg 做任务迁移二者来自同一套衰减机制但看的是不同状态位。更新入口有三个enqueue_entity、dequeue_entity、scheduler tick。每次进入update_load_avg()后__update_load_avg_se()先处理 se 本身再更新它所属的 cfs_rq。___update_load_sum()里有一段关键代码处理时间差delta now - sa-last_update_time; delta 10; /* 1 */ if (!delta) return 0; sa-last_update_time delta 10; /* 2 */右移 10 位把 ns 转成 us。如果两次更新间隔不足 1usdelta 变成 0直接返回不更新——PELT 的最小时间粒度就是 1us高精度的纳秒差在这里被截断。last_update_time只累加已经换算成 us 的部分避免小数误差在多次更新中累积漂移。init_entity_runnable_average()的初始化逻辑区分了两种实体普通 task se 的runnable_load_avg和load_avg直接初始化为scale_load_down(se-load.weight)也就是满载权重。这么做的原因写在注释里新任务用「重任务」的身份起步避免刚创建时负载为 0 而被调度器误判为轻任务饿死。而 group se 初始化为全 0因为它刚创建时组里没有任何任务负载必须从零开始累积。5. 常见问题排查PELT 负载读数异常的四个诊断点5.1 新任务 load_avg 一上来就顶到权重值现象某开发者用 trace 观察一个新 fork 出来的任务发现它的load_avg初始值不是 0而是直接等于任务权重比如 nice 0 任务对应 1024看起来像「负载造假」。原因这不是统计错误而是init_entity_runnable_average()的有意设计。task se 初始化时sa-load_avg scale_load_down(se-load.weight)让新任务以满载姿态进入调度器。如果初始化为 0新任务要经历多个周期才能爬升到真实负载水平期间调度器可能把它当成空闲任务CPU 份额分配不足。解决读取负载曲线时把「新任务的前几个更新周期」视为预热期。预热期的 load_avg 偏高是特性不是 bug真实负载通常会在几十毫秒内收敛到实际水平。5.2 group se 的负载长期为 0现象启用了组调度CONFIG_FAIR_GROUP_SCHED后group se 的 load_avg 一直是 0哪怕组内任务在满载运行。原因group se 与 task se 的初始化策略相反init_entity_runnable_average()里 group se 的三个平均值全部初始化为 0因为创建时组里没有任务。负载要等任务 attach 并经历更新周期后才会累积。另一个常见坑是 group 下的 task 刚迁移进来时group se 的runnable_weight还没有来得及反映新成员。解决不要用瞬时值判断 group 负载至少先跑完几个 1024us 周期再读。关注runnable_weight字段它才是「组内当前可运行实体权重」的实时近似而 load_avg 是它的历史平滑版本。5.3 decay_load 结果突然变成 0现象自己写内核模块复算某个 se 的衰减负载时发现只要传入的周期数 n 超过 2016decay_load()直接返回 0中间没有任何过渡。原因这是decay_load()的显式边界。n LOAD_AVG_PERIOD * 63时decay_load认为历史贡献已经被衰减到 64 位整数无法表达的程度直接截断。2016 个周期约等于 2 秒的物理时间超过这个窗口的负载视为零。解决在做长时间跨度的负载回放时把窗口限制在 2016 个周期内。如果要验证长窗口衰减手动用y^32 0.5折半计算而不是依赖decay_load()的截断结果。5.4 高频读取 load_avg 却纹丝不动现象某同学在用户态用高精度计时器每 100us 采样一次/proc或 trace 里的util_avg发现数值长时间不变怀疑更新逻辑失效。原因___update_load_sum()里delta 10后如果 delta 为 0函数直接返回。PELT 的最小粒度是 1us两次更新间隔不足 1us 时不会产生任何变化即使超过 1us只要没有跨过 1024us 的周期边界衰减也不会发生只有period_contrib在累积。负载是一个慢变信号它的设计时间常数是毫秒级不是微秒级。解决采样周期对齐 PELT 的时间常数至少 1ms 以上再看趋势。微秒级采样看到的只能是量化噪声。5.5 load_sum 和 runnable_load_sum 数值完全相等现象分析 trace 时发现某个 task se 的 load_sum 和 runnable_load_sum 始终一样怀疑其中一个字段没更新。原因看__update_load_avg_se()的调用load和runnable两个参数在 task se 场景下都是!!se-on_rq。也就是说只要实体在 rq 上它既计入 load_sum 也计入 runnable_load_sum两者同源同量。真正的差异体现在util_sum它只统计cfs_rq-curr se的运行时间。解决别在 task se 层面对比 load_sum 和 runnable_load_sum它们是同一个维度的两个别名。要区分「可运行」和「正在运行」看util_sum要区分 task 和 group 的可运行权重看runnable_weight的更新逻辑。6. 设计取舍1ms 粒度、32 周期半衰期与定点精度换来了什么把 PELT 的整套设计还原成三个选择每个选择都对应一个代价。周期选 1024us换来的是右移换算和周期计数代价是 1ms 内的短任务负载被均摊到整个周期突发性瞬时负载被抹平。半衰期选 32 周期约 32ms换来的是对「调度相关时间尺度」的匹配——上下文切换、迁移延迟、CPU 频率调节的响应时间都在这个量级代价是超过 2 秒的长期历史被彻底遗忘低频慢任务的历史信息不可见。衰减计算选定点查表而不是浮点换来的是热路径上的低延迟代价是精度损失。LOAD_AVG_MAX 理论值 47767 与代码值 47742 的差异说明了一切每次右移 32 位的截断误差会在多次递推中累积。PELT 选择接受这个误差因为负载跟踪的价值在于相对趋势、在于多个实体之间的比较而不是绝对数值的精确性。验证这套实现是否自洽有一条很实用的路径先用Documentation/scheduler/sched-pelt.c的生成逻辑自己编一个数组和内核里的runnable_avg_yN_inv逐项比对再用手推的 8 个时间点1023us 到 8191us 的负载值去对账decay_load和__accumulate_pelt_segments的组合结果。这两个对照能覆盖从查表到累加的全部关键路径比单纯读代码容易发现问题。从那以后我每次看到某个 se 的 load_avg 数值异常都强制先走一遍「period_contrib 是否累加、periods 是否跨周期、衰减是否命中 2016 上限」的心算流程再下结论而不是急着怀疑内核统计有 bug。这个习惯帮我绕过了不少自以为是的误解。希望帮到你。本文还有配套的精品资源点击获取