虚拟运行时间（vruntime）概念

虚拟运行时间（vruntime）是 CFS 调度器的核心抽象，它将不同优先级的进程统一到一个公平的时间度量上。理解 vruntime 的定义及其与物理时间的转换关系，是掌握 CFS 调度原理的关键。

2.1 vruntime 定义

vruntime 是 CFS 为每个进程维护的一个虚拟时间戳，表示该进程在 CPU 上“应该”运行的时间量。CFS 通过红黑树按 vruntime 排序，总是选择 vruntime 最小的进程运行，从而实现完全公平。

2.2 物理时间与虚拟时间的转换公式

CFS 在每次时钟 tick 或进程切换时，根据当前进程的权重将物理运行时间转换为 vruntime 增量。转换公式是 CFS 调度算法的数学基础。

2.2.1 标准转换公式

vruntime_delta = 物理运行时间 × (NICE_0_LOAD / 进程权重)

其中：

• 物理运行时间：进程本次实际占用 CPU 的时间（单位：ns）
• NICE_0_LOAD：nice 值为 0 时的标准权重（内核定义为 1024）
• 进程权重：由进程的 nice 值查表得到（见下表）

2.2.2 nice 值与权重对照表

2.2.3 转换示例

假设两个进程 A 和 B 同时运行 10ms 物理时间：

• 进程 A：nice = 0，权重 = 1024
• 进程 B：nice = 5，权重 = 335

进程 A 的 vruntime 增量 = 10ms × (1024 / 1024) = 10ms
进程 B 的 vruntime 增量 = 10ms × (1024 / 335) ≈ 30.57ms

结果：权重较小的进程 B 的 vruntime 增长更快，在红黑树中会向右移动，让出 CPU 给权重更大的进程 A。

2.3 vruntime 更新流程

CFS 在以下时机更新 vruntime：

1. 时钟 tick 中断：周期性更新当前运行进程的 vruntime
2. 进程切换：在 schedule() 调用时更新被换出进程的 vruntime
3. 唤醒进程：被唤醒的进程可能获得 vruntime 补偿（避免被饿死）

2.4 vruntime 与红黑树的关系

下图展示了 vruntime 如何驱动 CFS 红黑树的调度决策：

2.5 关键代码实现

Linux 内核中 vruntime 更新的核心函数位于 kernel/sched/fair.c：

/*
 * 更新进程的 vruntime
 * @se: 调度实体
 * @delta_exec: 本次运行的物理时间增量
 */
static void update_curr(struct cfs_rq *cfs_rq)
{
    struct sched_entity *curr = cfs_rq->curr;
    u64 delta_exec;

    if (unlikely(!curr))
        return;

    delta_exec = curr->exec_start - rq_clock_task(rq_of(cfs_rq));
    if (unlikely((s64)delta_exec <= 0))
        return;

    curr->exec_start = rq_clock_task(rq_of(cfs_rq));

    /* 核心转换：物理时间 → vruntime */
    curr->vruntime += calc_delta_fair(delta_exec, curr);
}

/*
 * 权重归一化计算
 * @delta: 物理时间增量
 * @se: 调度实体（包含权重信息）
 */
static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
    if (unlikely(se->load.weight != NICE_0_LOAD))
        delta = __calc_delta(delta, NICE_0_LOAD, &se->load);

    return delta;
}

2.6 常见面试问题

• Q：vruntime 会溢出吗？ A：内核使用 64 位无符号整数，溢出需要数百年，实际不会发生。但 CFS 在红黑树比较时使用 s64 有符号差值，避免回绕问题。
• Q：新进程的 vruntime 初始值是多少？ A：新进程的 vruntime 初始化为当前红黑树中最左节点的 vruntime 值，避免新进程抢占过多 CPU。
• Q：休眠进程唤醒后 vruntime 如何处理？ A：休眠进程的 vruntime 会进行补偿（减去休眠时间），使其在唤醒后能较快获得 CPU，但不会超过调度周期的限制。