企业官网建设流程全解析

简介：一份面向Linux内核调度器学习者的PDF技术文档，细致讲解CFS调度器中的PELT（Per 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 上放。PELT（Per Entity Load Tracking）就是为这道题目而生的答案。在它引入之前，内核在 rq（runqueue）粒度跟踪负载，这只知道整个队列整体有多忙，一旦任务被迁移、睡眠、唤醒，队列负载立刻失真，调度器就像一个看不到乘客分布的出租车调度员。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 执行单元真正被占据了百分之几。前者的典型使用者是负载均衡器，后者的典型使用者是 EAS（Energy-Aware Scheduling）与调频驱动，只有 running 才能反映真实的 CPU 占用率。

2.3 struct sched_avg：一个结构体如何承载衰减时间序列

内核用 struct sched_avg 来记录这些信息，它同时挂在调度实体 se 和 cfs_rq 上。关键成员之间的关系，看这张表：

你可以把 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。到 4095us，L3 = 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.5，64ms 前的负载还占相当权重，系统的反应会变得迟钝。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 (n<PERIOD) * * 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 是 32，n > 2016 时直接返回 0。注释里没有明说，但推理很简单：当 n = 2016，val 会右移 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 = 1024，n = 32，decay_load 会先右移一位，变成 512，查表 n%32 = 0，表值 0xffffffff，mul_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 * 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 是 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 是 task，runnable_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 不是精确的无穷级数和，而是一个被取整打磨过的常数。从那以后，我每看一个内核算法都会先问一句：它的衰减常数是怎么定的，误差容忍度在哪，换一个常数会怎样。用这种方式给自己做一个最小的心智模型，再读调度器代码就不容易迷路。希望帮到你。

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