简介一份面向Linux内核调度器学习者的PDF技术文档细致讲解CFS调度器中的PELTPer Entity Load Tracking算法。文档针对Linux 3.8之前基于运行队列runqueue跟踪负载时无法确定负载来源、且负载波动剧烈的痛点解释了为何需要引入逐实体负载追踪机制。整个资源仅包含1个PDF文件压缩包大小358KB内容精炼且自成体系适合内核开发、系统调优及操作系统相关课程学习者阅读。截至当前已有572人学习/下载是内核调度算法专题下较受关注的参考资料。作者结合Linux 4.18.0源码系统梳理了PELT的核心思路将时间划分为1024us的周期按实体可运行时间计算负载贡献并利用衰减因子y进行历史累加同时包含decay_load()函数与runnable_avg_yN_inv数组的代码级解析以及连续运行4096us再睡眠的负载计算示例可帮助读者掌握从负载公式到内核实现的全链路从而理解CFS如何更聪明地平衡吞吐量与功耗。1. PELT 的核心命题调度器凭什么知道负载在哪Linux 的 CFS 调度器表面上是把一个虚拟时间按权重切给每个 runnable 的 task实际上它在做一道更难的题目系统到底有多忙负载是谁产生的以及接下来该把任务往哪个 CPU 上放。PELTPer Entity Load Tracking就是为这道题目而生的答案。在它引入之前内核在 rqrunqueue粒度跟踪负载这只知道整个队列整体有多忙一旦任务被迁移、睡眠、唤醒队列负载立刻失真调度器就像一个看不到乘客分布的出租车调度员。PELT 的价值在于它把负载跟踪从 rq 下沉到调度实体 entity 本身用一套带衰减的时间积分让内核随时知道一个 task 在过去约 32ms 的半衰期内到底贡献了多少负载。搞懂 PELT等于搞懂了整个 CFS 负载均衡、调频调压与睡眠唤醒决策的底层逻辑。2. 从 rq 级到 per-entity 级CFS 负载跟踪的觉醒时刻2.1 runqueue 级跟踪的三大缺陷来源不明、波动放大、长尾失明在 Linux 3.8 之前CFS 的负载跟踪粒度是整个 rq。粒度粗带来的是信息熵的丢失。第一个问题是来源不明rq 负载 80你只知道这上面挺忙但不知道是哪个 task 在忙是一个 CPU 密集型的任务还是 1000 个睡眠任务中偶尔醒来的那个。第二个问题更隐蔽即使工作负载完全稳定比如系统里一直有 5 个同等权重的 task 在运行rq 粒度下的负载值依然会有很大波动。原因是负载的计算方式高度依赖采样时刻一个任务恰好刚醒来一个任务恰好刚睡眠rq 上的瞬时 runnable 集合变了负载值就变了。这种波动直接传导给负载均衡器和调频 governor会造成不必要的任务迁移和频率抖动。第三个问题是长尾失明一个任务运行了 100ms 后睡眠rq 负载立刻归零但它在过去 100ms 内明明消耗了大量 CPU这些历史贡献被直接丢弃一旦它再次唤醒调度器对它的负载认知要从零开始。2.2 PELT 的分层抽象period、runnable、running 三个维度PELT 的解法是把时间切成固定宽度的周期。物理时间被分成 1024us 的序列一个 entity 在每个周期内对系统负载的贡献等于该周期内它处于 runnable 状态的时间除以 1024。这里要注意runnable 范围很宽它包含了两种状态等待 CPU 调度的排队时间和正在 CPU 上执行的时间。而 running 范围更窄只统计正在 CPU 上执行的那段时间。所以 PELT 内部用三个维度来描述负载load_sum 基于 runnable 时间util_sum 基于 running 时间这两个值再分别派生出 load_avg 和 util_avg。它们含义不同。load_avg 回答的是就绪队列里有多少任务份额util_avg 回答的是 CPU 执行单元真正被占据了百分之几。前者的典型使用者是负载均衡器后者的典型使用者是 EASEnergy-Aware Scheduling与调频驱动只有 running 才能反映真实的 CPU 占用率。2.3 struct sched_avg一个结构体如何承载衰减时间序列内核用 struct sched_avg 来记录这些信息它同时挂在调度实体 se 和 cfs_rq 上。关键成员之间的关系看这张表字段类型含义典型消费方last_update_timeu64上次负载更新的时间戳ns 单位计算本次更新间隔 deltaload_sumu64基于 runnable 时间的衰减负载总和派生 load_avgrunnable_load_sumu64与 load_sum 几乎同步区分可运行权重CFS 均衡器的 runnable 负载util_sumu32基于 running 时间的衰减负载总和派生 util_avgperiod_contribu32上次更新时不足 1024us 的残余时间跨周期计算load_avgunsigned long平均化的可运行负载负载均衡util_avgunsigned long平均化的运行负载EAS 和调频你可以把 sched_avg 看作一个带遗忘因子的积分器。它不存历史序列只保存累计值和上次更新时间每次更新时把新时间窗内的负载增量按规则叠加上去老时间窗按衰减因子等比缩小。这种设计的关键收益是空间复杂度 O(1)无论经过多少周期内核都不需要记录一个长历史数组。3. 衰减机制为什么是 y^32 0.5 而不是滑动窗口3.1 时间价值论设计一个能忘记历史的公式如果负载跟踪只用简单的平均值那么一个 task 过去 10 秒的极端 CPU 占用会永远以同权重拖住当前判断。这不合理。一个 task 的负载贡献应该有“保鲜期”最近 1ms 的贡献最有价值32ms 前的贡献价值减半再往前随时间推移按比例继续衰减。PELT 的公式把历史贡献按等比级数压缩设 Li 表示第 i 个周期内该 entity 对系统负载的贡献则总的负载贡献为 L L0 L1 * y L2 * y² L3 * y³ ... Ln * yn。其中 y 就是衰减因子它决定了历史负载的遗忘速度。这个公式暗含一个很优雅的性质第 0 个周期最近的周期权重是 y^0 1完全保留第 1 个周期权重是 y第 2 个周期权重是 y²。y 小于 1所以越久远的负载被压缩得越狠。整个序列收编成一个等比级数如果 y 的 32 次方恰好等于 0.5那么系统有很清晰的物理含义每经过 32 个周期历史权重重减半。这就是 y^32 0.5 的来历。3.2 从等比级数到递推公式如何只靠上一刻值算当前贡献如果直接按 L L0 L1y L2y² 公式计算每次都要遍历所有历史周期代价太高。但观察等比级数的结构可以把它改写成递推形式。核心规律是计算当前时间的负载只需要上个周期负载贡献总和乘以衰减系数 y并加上当前时间点的负载增量。套用作者的例子task 从 0 时刻连续运行 4096us 后睡眠在 1023us 时刻负载就是 L0 1023到 2047us经历了一个满周期加残余时间负载变成 L1 1023 1024 y而 1023 加 1 恰好是上一个计算周期的负载累积值于是可以写成 L1 (L0 1) * y。到 4095usL3 1023 1024y 1024y² 1024y³ (L2 1) * y。这个递推链条非常好用但要小心一点它成立的前提是 task 一直处于 runnable 状态。如果 task 睡眠了从 5119us 开始L4 0 (L3 1) * y 变成了 0 加上历史衰减量也就是说睡眠后不再有新的负载增量只是历史累计值继续被 y 压缩。每到下一个周期负载值大约是上一个周期的 y 倍呈现指数级衰减。这种设计的效果是一个曾经很忙的 task 睡眠后它的负载贡献不会瞬间清零而是指数下降调度器仍保留着对它的历史记忆。3.3 半衰期选了 32 个周期为什么定这个参数y 的值不是拍脑袋定的。内核要求 y^32 0.5解方程得到 y 0.97857206。选择 32 是基于经验判断的。太短了比如 y^16 0.5那么 16ms 前的负载就只剩一半一些周期较长的批处理任务会让负载频繁抖动太长了比如 y^64 0.564ms 前的负载还占相当权重系统的反应会变得迟钝。32ms 与调度器 tick 频率、常见交互任务的响应长度、NUMA 迁移的时间尺度大致匹配是一个工程折中的结果。值得注意的是这个半衰期只与负载的指数衰减部分相关而负载的累加还有上限这个上限由 LOAD_AVG_MAX 决定也就是 1024(1 y y² ... y^n) 的收敛值。4. 源码级实现decay_load() 如何把浮点刁难变成移位乘法4.1 淘汰浮点数学y^n 的定点化与查表PELT 在负载计算中要频繁算 val * y^n如果每次都用浮点 pow 函数内核调度路径上的开销完全不可接受。而且内核代码在有些体系结构上禁止浮点运算。所以实现思路是把 y^n 预先定点化用 32 位整数表示 y^n 乘以 2^32 的乘积。定义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 项等于 y^n × 2^32。比如 n 1 时值是 0xfa83b2da把它除以 2^32 再乘以 val就是 val × y。由于头 32 项已经覆盖了 y 的 0 到 31 次幂而 y^32 0.5所以任何 n 大于等于 32 的情况都可以折叠到 n 小于 32 的查表加上移位。公式是 y^n 2^(-n/32) × y^(n%32)也就是说做 n/32 次右移一位再查 y^(n%32) 的表。这让时间从 O(n) 降到 O(1)。4.2 decay_load() 源码边界条件如何保护计算decay_load 的完整实现如下/* * 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; }先说第 1 个边界条件LOAD_AVG_PERIOD 是 32n 2016 时直接返回 0。注释里没有明说但推理很简单当 n 2016val 会右移 2016/32 63 位一个 u64 最多 64 位val 自身最多 64 位移位后基本为 0只剩极低位可能残留所以直接归零既省了后续移位也避免移位溢出产生非零垃圾值。第 2 个条件是核心折叠逻辑当 n 大于等于 32先右移 n/32 位把 1/2^(n/32) 部分做掉再用余数查表。最后调用 mul_u64_u32_shr这个函数在 32 位平台上会被展开成多步乘法和移位在 64 位平台上直接用硬件指令完成 64 位乘法和右移 32 位。整个过程没有一次浮点运算全部是整数乘法和移位。4.3 表的生成从 sched-pelt.c 到 do_div这张表不是手写的内核的文档目录里有一个 sched-pelt.c 生成器用一段用户态程序计算并打印数组。计算方式就是 runnable_avg_yN_inv[i] ((1UL 32) - 1) * pow(0.97857206, i)i 从 0 到 31。注意这里用 (1UL 32) - 1 而不是 1UL 32这是为了避免溢出当 i 0 时y^0 1乘以 0xffffffff 刚好是表里第一个值它代表 1 的定点化表达即 1 × 2^32 减 1相当于 0.9999999998这个微小的误差在 32 次迭代中会被控制在可接受范围内。当 n 31 时表只存了 32 项所以 sched-pelt.c 里还要处理周期性折叠实际生成器输出时已经把所有 n 的 y^n 都转成了 32 项。4.4 对照实验手工算一遍检查表是否与数学一致验证表是否可靠可以取 n 1 来算。0xfa83b2da 转十进制是 4203985114除以 2^32 约等于 0.97857与 y 理论值吻合。再看 n 32 的折叠如果 val 1024n 32decay_load 会先右移一位变成 512查表 n%32 0表值 0xffffffffmul_u64_u32_shr(512, 0xffffffff, 32) 结果仍约等于 512即 1024 × 2^(-1)。这和直接计算 1024 × y^32 的结果一致因为 y^32 约等于 0.5。这套折叠算法在 n 大于等于 64 的时候也成立只要 val 不为 0最多做 63 次右移然后查表搞定余数部分。5. accumulate_sum()把一次负载更新拆成三段衰减5.1 通用公式d1、d2、d3 与 period 的切分负载更新不是只在每个整周期边界发生而是在任意时刻都可能发生任务被唤醒、任务睡眠、tick 到来都会调用更新函数。这样一来从上次更新到当前时刻的时间差 delta 往往横跨多个周期。上文提到的例子很典型上一次负载是 u经过了 d 时间当前负载怎么算。答案是把 d 拆成三段d1从上一次更新的时刻到上一个整周期边界之间的距离也就是补齐上次不足周期的那部分d2中间完整经过的整个周期数d3当前周期内已经经过但还不满 1024us 的那段。对应的更新公式是u (u d1) * y^p 1024 * (y y^2 ... y^(p-1)) d3这里 p 1 d2/1024。它读起来就是上一次负载 u 先加上补齐的 d1整体经过 p 个周期的衰减中间每个完整周期各贡献 1024分别衰减不同次数最后当前周期的 d3 不衰减。5.2 源码拆解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; /* 2 */ 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); delta % 1024; contrib __accumulate_pelt_segments(periods, 1024 - sa-period_contrib, delta); /* 4 */ } 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; }第 1 步先把上次更新遗留的 period_contrib不足 1024us 的时间补进来再除以 1024 才算准确的周期数。这个细节容易漏如果直接把 delta 除以 1024上一次遗留的几百 us 就被丢掉了周期数会偏小。第 2 步算出 periods。如果 periods 非零说明跨过了周期边界需要先衰减旧的负载累计值再计算新增贡献。如果 periods 为 0说明 delta 很小连一个完整周期都没跨过那就不需要做任何衰减直接走最后的自加路径即可。这里有一个潜在的性能优化点periods 为 0 时contrib (u32)delta也完全正确因为该 delta 不可能超过 1023us。5.3 核心匠心__accumulate_pelt_segments() 的 c2 计算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 次衰减后的值。c2 是从第一个完整周期到第 p-1 个完整周期之间所有完整周期 1024us 贡献的衰减和是一个 p-1 项的多项式求和。如果直接循环求 1024y 1024y² ... 1024y^(p-1)每次更新都要做 p 次乘法p 可能高达几十甚至上百在调度热路径上不可接受。这里的内核技巧多项式求和可以用等比级数收敛闭合公式。LOAD_AVG_MAX 是整个等比级数收敛的最大值等于 1024/(1-y) ≈ 47742。那么 c2 就可以用“全部级数和减去前 p 项级数和再减去第 0 项”来算。decay_load(LOAD_AVG_MAX, periods) 恰好等于 LOAD_AVG_MAX × y^p也就是从第 p 项开始的所有无穷级数的和。两者相减再减去 1024对应 y^0 时的 1024剩下的就是 1024y^1 到 1024y^(p-1) 的和。复杂度从 O(p) 降到了 O(1)这是 PELT 实现里最漂亮的一笔。5.4 收敛值 47742 是怎么算出来的LOAD_AVG_MAX 的收敛值通过 calc_converged_max() 计算本质上就是等比级数求和但当 y 不是标准 0.5 而是 0.97857206 时直接用初等数学公式会有浮点误差。内核的生成器代码是从 max 1024 开始反复执行 max max*y 1024直到 max 的值不再变化然后输出。这个迭代过程模拟了 PELT 的实际累加路径因此得到的值是计算机整数运算下的精确收敛值不是数学上的完美值。读者如果手算 1024/(1-0.97857206)会得到 47780 左右而内核取 47742差了几十个单位这正是因为整数运算每轮取整积累的误差被保留了下来。这个误差不影响实际使用因为所有关键除法都基于同一个 LOAD_AVG_MAX 值误差在计算内部被自洽消掉了。6. 常见问题与避坑period_contrib、睡眠衰减与 init 权重6.1 现象task 睡眠后负载没有立刻归零负载均衡反而老惦记它在 NUMA 系统上一个 CPU 密集任务睡眠后别的 CPU 的负载均衡器依然会在数秒内看到它的负载衰减残影可能导致它在错误的时刻被迁移。原因PELT 不会在睡眠时清空负载而是利用 decay_load 逐周期衰减历史负载负载值要经过约 2016 个周期的衰减后才归零即约 2 秒的残留时间。解决这不是 bug 而是特性。调度器希望 task 唤醒后还能继承历史负载避免反复从零起步。如果真要在睡眠时清空需要显式调用 dequeue_entity 后把 sa-load_sum 清零但这会破坏 PELT 的连续性假设不推荐。6.2 现象新创建的 task 负载直接拉满 rq 的平均负载在 init_entity_runnable_average() 中如果 se 是 taskrunnable_load_avg 和 load_avg 被直接初始化成 se-load.weight也就是满载。这意味着一个新 fork 出来的 task 会被当成一个繁重任务直到它的真实负载经过约 32ms 的半衰期逐步稳定下来。原因这是设计权衡新任务刚 fork 完很可能马上进入运行态如果从 0 开始累积负载在它真正拉起负载之前负载均衡器可能把它迁移到别的 CPU 上。解决理解这个初始化逻辑是合理的。对于 group se初始化则为零因为刚创建的任务组还没有任何 task attach 到它负载预期为零。6.3 现象period_contrib 一直累加导致负载值膨胀超过 LOAD_AVG_MAX有开发者手工模拟 PELT 时发现如果把 delta 直接除以 1024 后取余作为新的 period_contrib时间一长负载值会超过理论上限。原因accumulate_sum 在处理 delta 时第一步就把 sa-period_contrib 叠加进了 delta然后才做除法和取余。取余后得到的新 period_contrib 不会超过 1023不存在膨胀问题。但要注意如果底层调用方传入的 delta 不是以 ns 为单位而是 us 或其他单位period_contrib 就会完全失真。解决核心调用路径必须保证 now 是 cfs_rq_clock_task() 返回的 ns 时间不允许自定义单位。6.4 现象se-load_sum 和 se-runnable_load_sum 的值长期相等怀疑代码写错看诊断数据时发现两个值一样这是正常的。__update_load_avg_se() 在调用 ___update_load_sum() 时传入的 load 和 runnable 都是 !!se-on_rq对单个 task se 来说它在 runnable 排队和 running 执行期间都被记为可运行所以两者的 base 相同load_sum 必然等于 runnable_load_sum。真正的差异出现在 runnable_weight 上group se 里有一部分权重属于不可运行的任务所以 group se 的 runnable_load_sum 会小于 load_sum。若想观察差异需要开启 CONFIG_FAIR_GROUP_SCHED 并构造多任务组。6.5 现象migration 之后负载值跳变task 从一个 CPU 迁移到另一个 CPU 后se 的负载值经常发生明显跳变。原因是 PELT 的 sched_avg 存放在 se 上而不是 rq 上迁移时 se 被 detach 再 attach但负载数据本身跟随 se 走。真正跳变的原因是迁移前后 cfs_rq 不同在 attach 到新 rq 时当前 rq 的 cfs_rq-avg 需要重新累加这个 se 的负载贡献而此时负载值又恰好被上一个 CPU 的衰减周期影响过。解决理解迁移后的现象不要直接归咎于数据错乱先检查 attach 和 detach 路径是否调用了 update_load_avg以及是否传入了正确的 SKIP_AGE_LOAD 标志。实践中调度域的负载是变化的这种跳变是收敛过程的一部分通常过 2-3 个负载周期就会回到稳态。7. 设计取舍与延伸精度、性能与可维护性的三角平衡PELT 的整个实现围绕一个核心权衡展开用 O(1) 的整数运算模拟 O(n) 的指数衰减积分。为了做到这一点它牺牲了数学上的绝对精确比如衰减表存在 ±1 的取整误差LOAD_AVG_MAX 也与理论值有偏差但当所有除法、累加都基于同一套误差体系时误差被自洽抵消了。这套取舍换来了调度热路径上的确定性无论系统经历了多少周期计算时间恒定没有浮点异常没有平台依赖在嵌入式环境也能稳定工作。另一个值得思考的取舍是周期宽度的选择。1024us 接近 1ms这个数值与内核的调度粒度相称。如果周期更长历史衰减会更慢负载均衡对瞬时突发的反应就会迟钝如果周期更短计算频率会上升衰减表会膨胀而且与 tick 周期的耦合会变得敏感。选择 1024us 同时兼顾了 32 周期半衰期的直觉表达32ms恰好是一个典型调度时间片的几十倍量级既不过于激进也不过于保守。从维护角度看PELT 是一个高度熵减的设计。它用一个 32 项查找表加移位运算替代了浮点数学用 sched-pelt.c 生成了引擎数据用 accumulate_sum 的 O(1) 闭合公式替代了显式求和。这套体系能运行十几年而不过时根本原因是它抓住了负载的本质负载不是瞬时快照而是一个带遗忘曲线的历史积分任何基于窗口的滑动平均方案都无法兼顾响应速度和历史记忆。我在读这段源码时最大的感受是真正复杂的不是公式本身而是公式背后的取舍意识。y^32 0.5 不是一个数学真理而是一个工程决定LOAD_AVG_MAX 47742 不是精确的无穷级数和而是一个被取整打磨过的常数。从那以后我每看一个内核算法都会先问一句它的衰减常数是怎么定的误差容忍度在哪换一个常数会怎样。用这种方式给自己做一个最小的心智模型再读调度器代码就不容易迷路。希望帮到你。本文还有配套的精品资源点击获取