PELT负载跟踪：从rq到se的调度器负载均衡与调频原理

简介：面向Linux内核调度与性能调优方向的学习者，这份PDF围绕CFS调度器中的PELT（per-entity load tracking）机制展开，重点回答Linux 3.8之前以运行队列跟踪负载时无法定位负载来源、负载值波动大的问题，并说明按调度实体跟踪负载的思路。内容涉及1024us周期划分、负载贡献计算、衰减因子与负载累加公式，还结合实例推演任务连续运行4096us后进入睡眠时各时间点的负载值，并讲解decay_load()函数如何用移位与乘法替代浮点运算，以及runnable_avg_yN_inv数组的预计算方式，代码分析基于Linux 4.18.0。资源包为1个PDF文件，约358KB，篇幅紧凑，适合作为调度器负载跟踪的专题笔记查阅。已有573人学习，可供内核初学者建立PELT概念框架，也便于开发者对照源码理解负载衰减与计算细节。

1. PELT：为什么调度器不再信任“队列总负载”这个数字

一个反直觉的事实：在 Linux 3.8 之前，CFS 判断“这个 CPU 有多忙”，看的是运行队列（rq）的总负载。听起来很合理，但实际会翻车——当队列里同时有 1 个重任务和 9 个轻任务时，rq 负载只告诉你“很忙”，却完全说不清是谁在忙。更糟的是，即使工作负载稳定，rq 级别的负载值也会剧烈抖动，因为任务进出队列、睡眠唤醒都在不断改变统计口径。调度器拿着这个模糊又抖动的数字去做负载均衡和调频决策，结果就是该迁移的不迁移、该降频的不降频。PELT（Per-Entity Load Tracking）要解决的就是这件事：把负载跟踪的粒度从“队列”下沉到“调度实体”，让每个 se 自己带一份可衰减、可累积的负载账本。搞懂它，你才能理解 CFS 为什么能在吞吐和功耗之间做出像样的取舍。

2. 从 rq 到 se：负载跟踪为什么要下沉一个层级

2.1 rq 级负载的两个硬伤

Linux 3.8 之前的 CFS 用 rq 的load.weight和运行时间做粗粒度统计。第一个硬伤是来源不可追溯：rq 负载是队列里所有 se 的加权和，一旦数值偏高，你无法判断是某个 CPU 密集任务在跑，还是大量短任务频繁唤醒造成的。负载均衡器需要知道“哪个任务重、该往哪搬”，rq 级数字给不出答案。

第二个硬伤是统计抖动。rq 负载在任务 enqueue/dequeue 时直接加减，一个任务睡眠再唤醒，负载值会瞬间跳变。对于调频（schedutil 的前身）和负载均衡这类需要平滑输入的策略来说，抖动意味着误判。PELT 的设计动机很直接：每个 se 维护自己的sched_avg，rq 负载由旗下 se 的负载累加而来，来源清晰；同时引入时间衰减，让负载变化是渐进的而不是阶跃的。

2.2 调度实体 se 的两种身份

PELT 跟踪的对象是struct sched_entity，它有两种形态。task se 对应一个普通进程，se->load.weight就是进程优先级映射出的权重；group se 对应一个任务组（开启CONFIG_FAIR_GROUP_SCHED时），它的权重来自组调度配额。两者都内嵌struct sched_avg avg，但初始化策略不同：

void init_entity_runnable_average(struct sched_entity *se) { struct sched_avg *sa = &se->avg; memset(sa, 0, sizeof(*sa)); /* * task se 初始化为满负载，避免新任务被误判为轻量； * group se 初始化为 0，因为组里可能还没有任务。 */ 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 的load_avg初值直接等于权重，注释写得很明白——新任务在真实负载稳定之前，先按“重任务”对待。这是一种保守策略，防止刚 fork 出来的进程因为历史为空而被调度器轻视。group se 则初始化为 0，因为组实体本身不代表具体工作，它的负载要等子任务 enqueue 后才逐步累积。runnable_weight对 task se 恒等于load.weight，对 group se 则是“组内可运行部分的权重”，后续会动态更新，这个区分在计算组负载时很关键。

2.3 sched_avg 里每个字段的职责

struct sched_avg是 PELT 的黑匣子，字段不多但每个都有明确分工：

load_sum和util_sum的区别是理解 PELT 的关键：runnable 时间包含“在 rq 里等 CPU”和“正在 CPU 上跑”两部分，而 running 时间只算真正占用 CPU 的部分。前者反映“这个实体多想跑”，后者反映“它实际跑了多少”。负载均衡看 runnable，调频看 util，两个口径服务不同策略，这也是 PELT 比 rq 级统计更“聪明”的地方。

3. 1024us 周期与衰减因子：PELT 的数学骨架

3.1 负载贡献的级数定义

PELT 把物理时间切成 1024us 的周期，每个周期内一个 se 对负载的贡献是runnable_time / 1024。但负载不能只算当前周期，历史贡献要按衰减因子 y 逐周期打折。设第 i 个周期的贡献为 Li，总负载为：

L = L0 + L1*y + L2*y^2 + L3*y^3 + ... + Ln*y^n

其中y^32 = 0.5，即每 32 个周期（约 32ms）历史负载衰减一半，y ≈ 0.97857206。这个半衰期的选择不是拍脑袋：32ms 大致对应一个调度周期，既能保留近期负载特征，又不会让远古负载长期干扰判断。

原文给了一个具体例子：一个 task 从 0 时刻开始连续运行 4096us 后睡眠，在 1023us、2047us、3071us、4095us、5119us、6143us、7167us、8191us 各时刻的负载贡献依次是 1023、2025、3005、3963、3877、3792、3709、3627。可以看到前四个时刻负载在累积上升，4096us 后任务睡眠，后续时刻只做衰减不再新增，数值平滑下降。这就是 PELT 的“记忆”特性：负载不会因为任务一睡眠就瞬间归零，而是按半衰期慢慢消退。

3.2 递推公式：为什么不需要记录全部历史

从例子能看出一个规律：当前负载 = 上一时刻负载 × 衰减系数 + 当前周期新增贡献。更一般地，假设上一时刻负载为 u，经过 d 时间后：

d = d1 + d2 + d3 p = 1 + d2/1024 u' = (u + d1) * y^p + 1024 * Σ(n=1..p-1) y^n + d3

d1 是补齐上一个不完整周期的余量，d2 是完整周期总时间，d3 是当前不完整周期的已过时间。这个公式把“历史衰减”和“新增贡献”拆成两部分，代码里对应accumulate_sum的 Step 1 和__accumulate_pelt_segments的 Step 2。关键洞察是：不需要保存每个周期的历史值，只要记住上一刻的 sum 和period_contrib，就能递推出当前值。这让 PELT 的空间复杂度是 O(1)，每个 se 只多出几十字节。

3.3 decay_load：用定点数替代浮点

公式里频繁出现val * y^n，内核不能直接用浮点。做法是把y^n * 2^32预先算好存进runnable_avg_yN_inv数组，乘法后右移 32 位还原：

static u64 decay_load(u64 val, u64 n) { unsigned int local_n; if (unlikely(n > LOAD_AVG_PERIOD * 63)) return 0; /* 超过 2016 周期，衰减为 0 */ local_n = n; /* y^32 = 1/2，所以 y^n = (1/2)^(n/32) * y^(n%32) */ if (unlikely(local_n >= LOAD_AVG_PERIOD)) { val >>= local_n / LOAD_AVG_PERIOD; /* 整周期部分直接右移 */ local_n %= LOAD_AVG_PERIOD; } val = mul_u64_u32_shr(val, runnable_avg_yN_inv[local_n], 32); return val; }

LOAD_AVG_PERIOD是 32。当 n 超过 32 时，利用y^32 = 0.5把 n 拆成“整 32 周期”和“余数”两部分：整周期部分等价于右移，余数部分查表。这样任意 n 的衰减都是常数时间。数组只存 0 到 31 共 32 个值，runnable_avg_yN_inv[0] = 0xffffffff对应y^0 * 2^32，最后一个0x82cd8698对应y^31 * 2^32。超过 2016 个周期（约 2 秒）直接返回 0，因为y^2016已经小到可以忽略，这个边界检查避免了无意义的计算。

提示：mul_u64_u32_shr是内核提供的 64×32 乘法并右移的辅助函数，在 32 位架构上也能正确处理溢出，不要自己写val * table[n] >> 32，否则在 32 位平台上会翻车。

4. accumulate_sum 与 LOAD_AVG_MAX：源码级实现拆解

4.1 两步计算的分工

accumulate_sum是 PELT 的核心函数，它把第 3 章的公式拆成两步。先看整体结构：

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; u64 periods; scale_freq = arch_scale_freq_capacity(cpu); scale_cpu = arch_scale_cpu_capacity(NULL, cpu); delta += sa->period_contrib; /* 补上上次余量 */ periods = delta / 1024; /* 完整周期数 */ if (periods) { /* Step 1: 历史 sum 整体衰减 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); /* Step 2: 计算跨越周期边界的新增贡献 */ delta %= 1024; contrib = __accumulate_pelt_segments(periods, 1024 - sa->period_contrib, delta); } sa->period_contrib = delta; 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; }

几个参数的含义需要说清：delta是距上次更新的时间（us），load/runnable/running是布尔标志，决定这次更新是否计入对应口径。scale_freq和scale_cpu是 CPU 频率和算力归一化因子，让不同频率、不同算力的 CPU 负载可比——这是 PELT 支持异构调度的基础。period_contrib在函数末尾更新为delta % 1024，即本次不足一个周期的余量，留给下次计算补齐。

4.2 __accumulate_pelt_segments 的巧妙化简

Step 2 要算d1*y^p + 1024*Σ(n=1..p-1)y^n + d3，其中中间那个等比数列求和如果直接循环，p 可能很大。内核用了一个数学技巧：

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

推导逻辑是：设max = 1024 * Σ(n=0..∞) y^n，则max * y^p = 1024 * Σ(n=p..∞) y^n，两者相减再减去1024*y^0就得到1024 * Σ(n=1..p-1) y^n。这样无论 p 多大，c2 都只需要一次decay_load调用，O(1) 完成。LOAD_AVG_MAX是1024 * Σ(n=0..∞) y^n的收敛值，代码算出来是 47742。这个值不是解析解，而是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; if (last == max) break; last = max; } printf("#define LOAD_AVG_MAX %ld\n", max); }

迭代到max不再变化即收敛。用定点数迭代会有取整误差，所以 47742 和数学解析值略有出入，但这不影响正确性——所有计算都用同一个常量，误差是系统性的。

4.3 从 sum 到 avg：divider 的作用

___update_load_avg负责把 sum 转成 avg：

static __always_inline void ___update_load_avg(struct sched_avg *sa, unsigned long load, unsigned long runnable) { u32 divider = LOAD_AVG_MAX - 1024 + sa->period_contrib; sa->load_avg = div_u64(load * sa->load_sum, divider); sa->runnable_load_avg = div_u64(runnable * sa->runnable_load_sum, divider); /* util_avg 类似，略 */ }

divider是当前时刻理论上的最大可能 sum 值：LOAD_AVG_MAX - 1024是完整周期的最大累积，加上period_contrib是当前不完整周期的余量。用sum / divider归一化，得到的 avg 就落在[0, weight]区间内，物理意义是“这个实体平均有多想跑/跑了多少”。这也解释了为什么 task se 初始化时load_avg = weight——满负载时 sum 接近 divider，avg 自然接近 weight。

4.4 update_load_avg 的调用时机

update_load_avg在三个场景被调用：enqueue_entity（任务入队）、dequeue_entity（任务出队）、scheduler tick（周期更新）。函数先更新 se 自己的 avg，再更新所属 cfs_rq 的 avg：

static inline void update_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) { u64 now = cfs_rq_clock_task(cfs_rq); struct rq *rq = rq_of(cfs_rq); int cpu = cpu_of(rq); int decayed; if (se->avg.last_update_time && !(flags & SKIP_AGE_LOAD)) __update_load_avg_se(now, cpu, cfs_rq, se); decayed = update_cfs_rq_load_avg(now, cfs_rq); /* ... */ }

SKIP_AGE_LOAD标志用于迁移场景：任务刚搬到新 CPU 时，不希望立刻用新 CPU 的时间戳去衰减旧负载，否则会算出一段虚假的空闲期。这个细节是血泪经验——早期实现里迁移后的负载计算经常出现异常跳变，后来才用标志位把“迁移”和“正常更新”区分开。__update_load_avg_se里对 task se 还会刷新runnable_weight = se->load.weight，保证权重变化后口径一致。

5. 避坑与排查：PELT 相关问题的常见翻车点

5.1 负载值长期不收敛，怀疑衰减没生效

现象：某个任务的util_avg一直停在接近满值，任务早已睡眠，数值却降不下来。原因：last_update_time没有推进，或者更新路径被SKIP_AGE_LOAD跳过，导致delta为 0，accumulate_sum直接返回。解决：检查该 se 是否长期不在任何 rq 上、是否被反复迁移；用 tracepointsched_load_avg_se观察更新频率，确认 tick 路径确实走到了update_load_avg。

5.2 新任务一上来就被当成重负载

现象：刚 fork 的轻量任务在负载均衡时被频繁迁移，系统抖动。原因：init_entity_runnable_average把 task se 的load_avg初始化为满权重，这是有意为之的保守策略，但短命任务还没来得及衰减就结束了。解决：这不是 bug，是设计取舍。如果业务对短任务敏感，应关注任务生命周期而非改 PELT 初值；调参方向是调度周期和迁移阈值，不是衰减因子。

5.3 异构 CPU 上负载不可比

现象：大小核平台上，小核上的任务 util 看起来和大核差不多，调频策略误判。原因：accumulate_sum里scale_cpu没生效，或者平台没实现arch_scale_cpu_capacity。解决：确认 CPU 容量表正确注册，检查util_sum累加时是否乘了scale_cpu；cap_scale对contrib的缩放也要确认scale_freq返回值合理，否则频率归一化会失真。

5.4 32 位平台上衰减结果异常

现象：32 位 ARM 上decay_load结果偏小或溢出。原因：自己实现了val * table[n] >> 32，32 位乘法溢出。解决：必须用内核的mul_u64_u32_shr，它内部处理了高低位拆分。这是典型的“看起来一样、跑起来不一样”的坑。

5.5 组调度下 runnable_weight 不更新

现象：开启组调度后，group se 的负载长期偏高或偏低。原因：runnable_weight只在 task se 路径刷新，group se 的runnable_weight依赖update_cfs_rq_load_avg里的重算逻辑，如果组内任务频繁进出而更新路径没覆盖，值会失真。解决：检查update_cfs_rq_load_avg是否在每次 cfs_rq 负载变化时被调用，确认se_runnable()取值路径正确。

6. 设计取舍：为什么是 1024us、y^32=0.5 和定点数

PELT 的参数不是随便定的，每一个都对应一组权衡。1024us 的周期长度，本质是在“响应速度”和“计算开销”之间找平衡：周期太短，tick 频繁触发衰减计算，开销上升；周期太长，负载对突发变化反应迟钝。1024us 约 1ms，和 CFS 的调度粒度同量级，既能让负载在几十毫秒内完成有意义的变化，又不会让每次 tick 都做重活。

y^32 = 0.5的半衰期选择更微妙。32 个周期约 32ms，大致是一个调度周期的量级。半衰期太短，负载记忆只有几毫秒，调度器会变得“健忘”，频繁误判；半衰期太长，历史负载拖尾严重，任务睡眠后负载迟迟不降，导致 CPU 被过度占用。32ms 是社区在多种工作负载下试出来的经验值，兼顾了交互式任务的快速响应和后台任务的稳定统计。

定点数替代浮点是内核的硬约束。runnable_avg_yN_inv表把y^n * 2^32预计算好，运行时只做乘法和移位，避免了浮点上下文保存和架构差异。代价是精度损失：LOAD_AVG_MAX的 47742 和解析值有偏差，但这种系统性误差在所有 se 上一致，不影响相对比较。decay_load里n > 2016直接返回 0 也是取舍——继续算下去数值已经小于 1，没有实际意义，不如省掉分支。

如果要验证自己对 PELT 的理解，我一般会做两件事：一是用sched-pelt.c重新生成runnable_avg_yN_inv和LOAD_AVG_MAX，对比内核里的常量是否一致；二是在模拟环境里构造“运行 4096us 后睡眠”的场景，用 tracepoint 抓sched_load_avg_se，看负载曲线是否和原文的 1023→2025→3005→3963→3877→3792→3709→3627 对得上。对不上就说明某个环节的period_contrib或衰减次数算错了。

从那以后我每次读调度相关代码，都会先把sched_avg的字段和更新路径画一遍，确认 sum 和 avg 的口径再往下看，否则很容易把 runnable 和 running 搞混。希望帮到你。

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