CFS负载跟踪PELT与调度延迟的联合优化方法 - 第4节

4.1 PELT 算法数学基础

PELT（Per-Entity Load Tracking）是 CFS 调度器用于跟踪每个调度实体（task 或 task_group）负载贡献的核心算法。其数学本质是一个一阶低通滤波器，通过指数加权移动平均（EWMA）的方式，将离散的调度事件（任务运行/睡眠）平滑为连续的负载信号。

4.1.1 递推公式

PELT 的负载更新遵循以下递推关系：

L_t = L_{t-1} * y + delta * (1 - y)

其中：

• L_t：当前时刻的负载贡献值。
• L_{t-1}：上一时刻的负载贡献值。
• y：衰减因子（0 < y < 1），决定历史负载的衰减速度。
• delta：当前周期内新增的运行时间（通常以 1ms 或 1024us 为粒度）。
• (1 - y)：新运行时间的缩放系数，用于将新增时间归一化到与历史负载相同的量纲。

该公式的物理意义是：新负载 = 衰减后的旧负载 + 归一化的新运行时间。

4.1.2 离散时间与周期

PELT 将时间划分为固定长度的周期（Period），每个周期称为一个 PELT 窗口。内核默认窗口大小为 1024us（约 1ms）。在每个窗口结束时，触发一次负载更新。

4.2 半衰期衰减机制

半衰期（Half-life）是 PELT 衰减机制的核心参数，它决定了历史负载信息在多长时间后衰减为原始值的一半。内核默认的半衰期为 32ms。

4.2.1 衰减因子的计算

衰减因子 y 由半衰期和窗口大小共同决定。假设半衰期包含 n 个 PELT 窗口，则经过 n 次衰减后，负载应衰减为原来的 1/2：

y^n = 0.5
y = 0.5^(1/n)

当 n = 32（半衰期 32ms / 窗口 1ms）时：

y = 0.5^(1/32) ≈ 0.97857

这意味着每个窗口（1ms）过去，历史负载乘以 0.97857，即衰减约 2.143%。

4.2.2 衰减曲线与时间窗口

下表展示了不同时间点历史负载的剩余比例：

4.3 负载贡献的累加与衰减

PELT 的负载贡献计算分为两个阶段：累加（任务运行时）和衰减（任务睡眠或时间流逝时）。内核通过 ___update_load_sum 和 ___update_load_avg 两个核心函数实现。

4.3.1 累加过程

当任务在 CPU 上运行时，每个 PELT 窗口结束时，内核执行以下操作：

1. 读取当前时间：获取自上次更新以来的时间差 delta。
2. 计算完整窗口数：delta / 1024us，得到完整经过的 PELT 窗口个数。
3. 衰减历史负载：对每个完整窗口，将历史负载乘以 y。
4. 累加新负载：将当前窗口内的运行时间（可能不足 1024us）归一化后累加到负载中。

// 内核源码简化示意（kernel/sched/pelt.c）
static __always_inline int
___update_load_sum(u64 now, struct sched_avg *sa,
                   unsigned long load, unsigned long runnable, int running)
{
    u64 delta;
    int periods;

    delta = now - sa->last_update_time;
    delta >>= 10;  // 转换为以 1024us 为单位的周期数
    periods = delta;

    // 对每个完整周期进行衰减
    if (periods) {
        sa->load_sum = decay_load(sa->load_sum, periods);
        sa->runnable_sum = decay_load(sa->runnable_sum, periods);
        sa->util_sum = decay_load(sa->util_sum, periods);
    }

    // 累加当前周期的贡献
    if (load)
        sa->load_sum += load * period_contrib;
    if (runnable)
        sa->runnable_sum += runnable * period_contrib;
    if (running)
        sa->util_sum += running * period_contrib;

    sa->last_update_time = now;
    return 1;
}

4.3.2 衰减过程

当任务睡眠或时间流逝但任务未运行时，PELT 仍然会执行衰减操作：

• 任务睡眠：睡眠期间不产生新的运行时间，但历史负载持续衰减。睡眠时间越长，负载贡献越低。
• 空闲 CPU：即使 CPU 空闲，PELT 也会在每次更新时衰减历史负载，反映 CPU 逐渐变空闲的趋势。

4.3.3 负载贡献的三种类型

PELT 为每个调度实体维护三种负载贡献：

4.3.4 负载平均值的计算

除了累加和（sum）之外，PELT 还维护负载平均值（avg），用于归一化比较：

load_avg = div_u64(load_sum, LOAD_AVG_MAX)

其中 LOAD_AVG_MAX 是负载累加和的理论最大值，即任务持续运行无限长时间后的负载和：

LOAD_AVG_MAX = 1024 * (1 + y + y^2 + ... + y^n) = 1024 / (1 - y)

当 y = 0.97857 时：

LOAD_AVG_MAX ≈ 1024 / 0.02143 ≈ 47780

这意味着一个持续运行的 CPU 密集型任务的 load_avg 约为 47780，归一化后对应 100% CPU 利用率。