📚 课程目录第3章虚拟运行时间计算

3. 虚拟运行时间计算：vruntime 的计算公式、nice 值与权重映射表、calc_delta_fair 函数解析

CFS（Completely Fair Scheduler）的核心思想是让每个进程都能公平地获得 CPU 时间。为了实现这一目标，CFS 引入了 虚拟运行时间（vruntime） 的概念。vruntime 是 CFS 调度器选择下一个运行进程的唯一依据：vruntime 值最小的进程，就是当前最需要被调度执行的进程。

核心理解： 物理时间是绝对的，但虚拟运行时间是经过权重修正后的时间。一个高优先级（低 nice 值）的进程，其虚拟时间流逝得比物理时间慢；而低优先级（高 nice 值）的进程，其虚拟时间流逝得比物理时间快。这使得 CFS 能够在单位物理时间内，让高优先级进程获得更多的 CPU 执行机会。

3.1 vruntime 的计算公式

vruntime 的计算并非简单的物理时间累加，而是基于进程权重对实际运行时间进行归一化处理。其核心公式如下：

vruntime += 实际运行时间 * (NICE_0_LOAD / 进程权重)

其中：

实际运行时间：进程在 CPU 上真实执行的物理时间（通常以 ns 为单位）。
NICE_0_LOAD：nice 值为 0 时的标准权重（内核中定义为 1024）。
进程权重：根据进程的 nice 值从全局权重映射表中查表得到的权重值。

这个公式的直观含义是：以 nice 0 进程为基准，如果当前进程的权重是 NICE_0_LOAD 的两倍（即优先级更高），那么它的 vruntime 增长速率就是物理时间的一半；反之，如果权重是 NICE_0_LOAD 的一半（优先级更低），vruntime 增长速率就是物理时间的两倍。

  关键结论： 在 CFS 中，所有进程的 vruntime 都以相同的“速率”在理想公平环境下前进。权重高的进程通过“少加”虚拟时间，获得了更多的物理 CPU 时间；权重低的进程通过“多加”虚拟时间，被限制了物理 CPU 时间。

3.2 nice 值与权重映射表

Linux 内核维护了一个全局的静态数组 prio_to_weight[]，用于将进程的 nice 值（-20 到 19）映射到对应的权重值。这个映射表是 CFS 实现公平调度的基础数据。nice 值每相差 1，权重变化约为 10%，这保证了 nice 值差异对 CPU 时间分配的影响是平滑且可预测的。

以下是内核中 prio_to_weight[] 映射表的核心数据（节选）：

nice 值	权重 (weight)	权重 / NICE_0_LOAD	说明
-20	88761	≈ 86.7	最高优先级，权重极大
-10	9548	≈ 9.3	高优先级
-5	3121	≈ 3.0	较高优先级
0	1024	1.0	基准权重 (NICE_0_LOAD)
5	335	≈ 0.33	较低优先级
10	110	≈ 0.11	低优先级
19	15	≈ 0.015	最低优先级，权重极小

注意： nice 值范围是 -20 到 19，共 40 个级别。内核数组 prio_to_weight[40] 的索引 0 对应 nice -20，索引 39 对应 nice 19。权重值从 88761 到 15，跨度超过 5900 倍，这确保了不同优先级进程之间的 CPU 时间分配差异足够显著。

内核中对应的数据结构定义如下：

/*
 * 优先级到权重的映射表
 * 索引 0 对应 nice -20，索引 39 对应 nice 19
 */
static const int prio_to_weight[40] = {
 /* -20 */ 88761, 71755, 56483, 46273, 36291,
 /* -15 */ 29154, 23254, 18705, 14949, 11916,
 /* -10 */ 9548,  7620,  6100,  4904,  3906,
 /*  -5 */ 3121,  2501,  1991,  1586,  1277,
 /*   0 */ 1024,  820,   655,   526,   423,
 /*   5 */ 335,   272,   215,   172,   137,
 /*  10 */ 110,   87,    70,    56,    45,
 /*  15 */ 36,    29,    23,    18,    15,
};

3.3 calc_delta_fair 函数解析

calc_delta_fair 是 CFS 调度器中用于计算进程 vruntime 增量的核心函数。它封装了 vruntime 计算公式，将进程的实际运行时间（物理时间）转换为虚拟运行时间增量。该函数位于内核源码 kernel/sched/fair.c 中。

函数原型与核心逻辑如下：

/*
 * calc_delta_fair - 计算虚拟运行时间增量
 * @delta:     进程实际运行的物理时间（ns）
 * @se:        调度实体（sched_entity），包含进程权重信息
 *
 * 返回值：    虚拟运行时间增量（ns）
 */
static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
    /* 如果进程权重等于 NICE_0_LOAD，直接返回物理时间 */
    if (unlikely(se->load.weight == NICE_0_LOAD))
        return delta;

    /*
     * 调用 __calc_delta 进行加权计算：
     * vruntime_delta = delta * NICE_0_LOAD / se->load.weight
     */
    return __calc_delta(delta, NICE_0_LOAD, &se->load);
}

函数执行流程分析：

快速路径优化：如果进程的权重恰好等于 NICE_0_LOAD（即 nice 0），则直接返回物理时间 delta，无需进行乘除法运算。这是最常见的优化场景。
加权计算：对于非标准权重的进程，调用 __calc_delta 执行核心计算：delta * NICE_0_LOAD / weight。内核使用 64 位乘法和移位操作来避免浮点运算，保证计算精度和性能。
结果返回：返回计算后的虚拟运行时间增量，该值将被累加到进程的 vruntime 字段中。

  性能优化细节： __calc_delta 内部使用了 mul_u64_u32_shr 等高效乘法函数，并通过预先计算的 inv_weight 逆权重数组来避免除法运算。内核将除法转换为乘法 + 移位操作，这在没有硬件除法器的嵌入式系统上能显著提升性能。

3.4 综合案例：不同 nice 值的 vruntime 增长对比

假设三个进程 A、B、C 同时运行，每个进程都获得了 10ms 的物理 CPU 时间。它们的 nice 值分别为 -5、0、10。通过 calc_delta_fair 计算各自的 vruntime 增量：

进程	nice 值	权重	物理时间 (ms)	vruntime 增量 (ms)	说明
A	-5	3121	10	10 × 1024 / 3121 ≈ 3.28	高权重，vruntime 增长慢
B	0	1024	10	10 × 1024 / 1024 = 10.00	基准权重，vruntime = 物理时间
C	10	110	10	10 × 1024 / 110 ≈ 93.09	低权重，vruntime 增长极快

案例解读： 在相同的 10ms 物理时间内，高优先级进程 A 的 vruntime 只增加了约 3.28ms，而低优先级进程 C 的 vruntime 却增加了约 93.09ms。这意味着在 CFS 的红黑树中，进程 C 的 vruntime 会迅速变大，很快被推到树的后端，从而让出 CPU 给 vruntime 更小的进程 A。这正是 CFS 实现“优先级越高，获得 CPU 时间越多”的核心机制。

通过以上对 vruntime 计算公式、nice 值与权重映射表以及 calc_delta_fair 函数的深入解析，我们可以看到 CFS 调度器如何通过精巧的数学变换，将优先级差异转化为可量化的虚拟时间增量，从而实现完全公平的调度目标。