3. EEVDF 调度器原理：Earliest Eligible Virtual Deadline First

3.1 引入背景：为什么 CFS 需要进化？

完全公平调度器（CFS）自 Linux 2.6.23 引入以来，一直是主流调度器。它基于虚拟时间（vruntime）的“红黑树”模型，目标是让每个就绪进程获得近似相等的 CPU 时间片。然而，随着数据中心、实时音视频、交互式桌面等场景对低延迟和可预测性的要求越来越高，CFS 的固有缺陷逐渐暴露：

• 唤醒抢占延迟不可控：CFS 在唤醒进程时，仅比较 vruntime 大小决定是否抢占，缺乏对“截止时间”的感知，导致突发唤醒的进程可能长时间得不到调度。
• 权重分配与延迟解耦：nice 值控制权重，但权重相同的进程在 CFS 下无法区分“紧急程度”，交互式进程与批处理进程混跑时延迟抖动大。
• 缺乏显式延迟边界：CFS 没有“最晚完成时间”的概念，无法为实时或软实时任务提供确定性调度保证。

EEVDF（Earliest Eligible Virtual Deadline First）调度器在 Linux 6.6 合入主线，取代了 CFS 成为默认调度器。它保留了 CFS 的加权公平排队（WFQ）思想，但将调度决策从“最小 vruntime”改为“最早合格虚拟截止时间优先”。

3.2 核心算法：资格与截止时间的双重判定

EEVDF 的核心思想是：只有“合格”的进程才有资格参与调度，而在所有合格进程中，选择“虚拟截止时间”最早的进程运行。 这引入了两个关键概念：

调度决策流程如下：

1. 更新全局虚拟时间 V(t)：每次时钟 tick 或调度点到来时，根据当前运行进程的权重更新 V(t)。
2. 计算每个进程的合格时间 E：对于每个就绪进程，E = max(V(t), 该进程上次调度时的 deadline)。
3. 计算每个进程的虚拟截止时间 D：D = E + (进程分配的 slice / 进程权重)。
4. 选择调度：在所有 E ≤ V(t) 的“合格”进程中，选择 D 最小的进程运行。
5. 更新进程状态：进程被调度后，记录其本次调度的 deadline 为 D，用于下次计算 E。

3.3 与 CFS 的核心差异

EEVDF 并非完全推翻 CFS，而是在其基础上进行了关键性的算法升级。下表从多个维度对比两者的差异：

3.4 关键数据结构与算法细节

EEVDF 在内核中的实现围绕几个核心数据结构展开：

• struct sched_entity：每个调度实体包含 vruntime（虚拟运行时间）、deadline（上次调度时的虚拟截止时间）、slice（时间片长度）等字段。
• struct cfs_rq：就绪队列维护一棵红黑树，排序键为 deadline（即虚拟截止时间 D）。同时记录全局虚拟时间 min_vruntime（即 V(t)）。
• 资格检查函数：entity_eligible(cfs_rq, se) 判断 se->vruntime <= cfs_rq->min_vruntime 是否成立，或更精确地，判断 se->deadline 是否在合格范围内。

核心算法伪代码如下：

// EEVDF 调度选择主路径
struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
{
    struct sched_entity *se;
    struct rb_node *node;

    // 1. 更新全局虚拟时间
    update_min_vruntime(cfs_rq);

    // 2. 遍历红黑树（按 deadline 排序）
    for (node = rb_first(&cfs_rq->tasks_timeline);
         node; node = rb_next(node)) {
        se = rb_entry(node, struct sched_entity, run_node);

        // 3. 资格检查：E <= V(t)
        if (entity_eligible(cfs_rq, se)) {
            // 4. 选择第一个合格的实体（即 deadline 最小的）
            return se;
        }
    }

    // 5. 如果没有合格实体，返回树根（最左节点）
    return rb_entry(rb_first(&cfs_rq->tasks_timeline),
                    struct sched_entity, run_node);
}

// 资格检查简化逻辑
bool entity_eligible(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    // 合格时间 E = max(se->vruntime, se->deadline)
    s64 eligible_time = max(se->vruntime, se->deadline);
    // 全局虚拟时间 V(t)
    s64 virtual_time = cfs_rq->min_vruntime;

    return eligible_time <= virtual_time;
}

3.5 延迟测量与调优切入点

EEVDF 的引入为延迟测量提供了新的指标和调优方向：