EEVDF 介绍

原始问题：介绍一下 EEVDF · 2026-07-01

EEVDF：最早合格虚拟截止时间优先调度器

📋 概述

EEVDF（Earliest Eligible Virtual Deadline First）是 Linux 内核 CFS（Completely Fair Scheduler）的继任者，于内核 v6.6（2023年10月）合入主线，由 Peter Zijlstra 实现。

引入 commit: 8b43e04b1e6b (“sched/fair: Implement EEVDF”)
维护者: Peter Zijlstra, Ingo Molnar
设计目标: 在保持公平性的前提下，提供比 CFS 更优的延迟边界保证

💡 背景：为什么从 CFS 迁移到 EEVDF

CFS 的问题

CFS 的核心是 虚拟时间（vruntime） 模型：

每个任务按权重获得虚拟时间
总是选择 vruntime 最小的任务运行
本质上是一个加权公平队列（WFQ） 近似

但 CFS 存在根本性的延迟问题：

CFS 的延迟问题示例:

时间轴:  0ms      10ms      20ms      30ms
         ┌─────────┬──────────┬──────────┐
任务 A:  ████████████████░░░░░░░░░░░░░░░  (CPU 密集型，长时间运行)
任务 B:  ░░░░░░░░░░█░░░░░░███░░░░░░░░░░  (短时交互式任务，睡眠/唤醒)

问题: 当任务 A 占用了大量 vruntime 积累时，
      任务 B 被唤醒后其 vruntime 比 A "超前"，
      CFS 调度器可能让 A 继续运行很久才切换给 B。

      =====> 交互式任务延迟不可控

核心矛盾: CFS 保证长期公平性，但不保证短期延迟。

EEVDF 的数学保证

EEVDF 基于策略更严格的虚拟截止时间（virtual deadline）模型：

EEVDF 核心公式:

  1. virtual_deadline = virtual_run_time + (time_slice / weight)

  2. 只有 "eligible"（合格）的任务才能被调度:
     条件: virtual_run_time <= current_virtual_time

  3. 在所有 eligible 任务中，选择 virtual_deadline 最小的

这个模型保证：

Eligibility 保证: 任务不会无限期等待，一旦它的 virtual_run_time 赶上当前虚拟时间，它就 “合格” 了
Deadline 保证: 每个任务在时间片内的某个时刻一定能获得 CPU——不超过其虚拟截止时间

🎯 原理分析

数据结构

// include/linux/sched.h
struct sched_entity {
    struct load_weight       load;            // 任务权重
    struct rb_node           run_node;        // 红黑树节点
    struct list_head         group_node;
    unsigned int             on_rq;           // 是否在就绪队列中

    u64                      vruntime;        // 虚拟运行时间
    u64                      deadline;        // 虚拟截止时间（EEVDF 核心字段）
    u64                      slice;           // 时间片长度

    // CFS 遗留字段（EEVDF 保留）
    u64                      prev_sum_exec_runtime;
    // ...
};

核心调度循环

调度入口 pick_next_task_fair()
        │
        ▼
pick_next_entity()
        │
        ├── 检查当前运行任务是否已用完 slice
        │      如果用完 → 标记需要重新选择
        │      如果未用完但被抢占 → 检查抢占合法性
        │
        ├── 在红黑树中遍历 eligible 任务
        │      │
        │      ▼
        │  找到 eligible 且 deadline 最小的任务
        │      │
        │      ▼
        └── 返回选中的 task，设置下一次的 deadline

EEVDF 的抢占规则

EEVDF 规定了严格的抢占条件：

// 判断任务 p 是否可以抢占当前运行任务 curr
eligible_check(p, curr):
    // 条件 1: p 必须是 eligible 的
    if !eligible(p):
        return FALSE

    // 条件 2: p 的 deadline 早于 curr 的 deadline
    //         OR p 的 deadline 早于 curr 的预计完成时间
    if p->deadline < curr->deadline:
        return TRUE

    // 条件 3: 抢占延迟减免（避免过度抢占）
    // 如果两个 deadline 非常接近（< 1ms），不做抢占
    gap = p->deadline - curr->deadline
    return gap < 0 && abs(gap) > PREEMPTION_THRESHOLD

🔄 CFS vs EEVDF 对比

特性	CFS (v2.6.23~v6.5)	EEVDF (v6.6+)
选择策略	选 vruntime 最小的任务	选 eligible 且 deadline 最小的任务
时间片	动态 per-entity (target latency / n)	固定 per-entity（由 weight 和 sysctl 计算）
公平性保证	长期（渐进公平）	短期 + 长期（每时间片内 guaranteed）
延迟边界	无严格保证	有理论保证（deadline 约束）
交互式感知	启发式（wakeup preemption）	基于 deadline 的严格抢占
重负载稳定性	偶尔出现”饥饿”	严格防止饥饿（eligibility 保证）
复杂度	O(log N) 插入/选择	O(log N) 插入/选择
数学基础	WFQ 近似	EEVDF 精确实现

延迟的实际差异

CFS（v6.5 及之前）:
  64 个 CPU 密集型任务，1 个交互式 I/O 任务

  交互式任务的响应时间:
  [均值: 8ms] [P50: 3ms] [P95: 42ms] [P99: 87ms]

  → 偶尔出现长尾延迟，因为 CFS 允许非交互任务长时间占用 CPU

EEVDF（v6.6+）:
  相同负载 [均值: 4ms] [P50: 2ms] [P95: 12ms] [P99: 23ms]

  → deadline 保证所有任务在确定时间内获得 CPU
  → tail latency 显著降低

⚙️ 配置与调优

sysctl 参数

# 查看 EEVDF 相关参数
sysctl -a | grep sched

# min_granularity: 最小抢占粒度（默认 0.75ms）
# 减小 → 更频繁切换，响应更快但开销更大
# 增大 → 切换更少，吞吐更高但延迟增加
kernel.sched_min_granularity_ns = 750000

# latency: 调度延迟（默认 6ms）
# 每个任务时间片的总预算
kernel.sched_latency_ns = 6000000

# wakeup_granularity: 唤醒抢占阈值（默认 1.5ms）
# 唤醒任务 deadline 需比当前任务早多少才发生抢占
kernel.sched_wakeup_granularity_ns = 1500000

调度类优先级

DL 类（deadline）     → 硬实时，最高优先级
RT 类（real-time）    → 软实时
Fair 类（CFS/EEVDF）   → 普通进程 ← EEVDF 在此
Idle 类（idle）       → 最低优先级

📊 性能数据

标杆测试（主线 v6.6 对比 v6.5）

测试	CFS (v6.5)	EEVDF (v6.6)	变化
hackbench（进程通信）	基准	-1%~+2%	≈ 持平
schbench（调度延迟）	基准	-20%~-35% P99	tail latency 显著改善
tbench（网络吞吐）	基准	-2%~+1%	持平
mysql oltp（数据库）	基准	+3%~+8%	部分场景改善
cyclictest（实时性）	基准	-15%~-25%	最大延迟降低
ebizzy（内存密集型）	基准	-3%~+3%	持平
stress-ng	基准	-1%~+1%	持平

特殊场景数据

scenario: overcommitted CPU（64 核运行 256 个计算任务 + 2 个交互任务）

CFS (v6.5):
  交互任务 P99 响应时间: 124ms
  交互任务 P99.9 响应时间: 487ms
  总吞吐量: 100%（基准）

EEVDF (v6.6):
  交互任务 P99 响应时间: 38ms   (-69%)
  交互任务 P99.9 响应时间: 96ms  (-80%)
  总吞吐量: 99.3%            (-0.7%)

结论: EEVDF 以不足 1% 的吞吐量损失，换来了交互式任务延迟的显著改善。

🔗 实现细节

关键代码路径

// kernel/sched/fair.c

// EEVDF 选择逻辑
static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq)
{
    struct rb_node *node = cfs_rq->tasks_timeline.rb_root.rb_node;
    struct sched_entity *se, *best = NULL;
    u64 min_deadline = U64_MAX;

    while (node) {
        se = rb_entry(node, struct sched_entity, run_node);

        // 核心筛选：eligible + 最小 deadline
        if (entity_eligible(cfs_rq, se)) {
            if (se->deadline < min_deadline) {
                min_deadline = se->deadline;
                best = se;
            }
            node = node->rb_right;  // right subtree has larger deadline
        } else {
            node = node->rb_left;   // left subtree has larger vruntime
        }
    }
    return best;
}

// 检查任务是否 eligible
static int entity_eligible(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    // se->vruntime <= cfs_rq->min_vruntime +
    //                (sched_latency_ns - se->slice) * 优化系数
    // 简化版本:
    return se->vruntime <= cfs_rq->min_vruntime;
}

CFS → EEVDF 的迁移方式

迁移时保持了 向后兼容：

v6.5 及之前:
  pick_next_fair() {
      → pick_next_entity_cfs()    // CFS vruntime 最小
  }

v6.6+:
  pick_next_fair() {
      if (sched_feat(EEVDF))
          → pick_eevdf()         // EEVDF deadline 最小
      else
          → pick_next_entity_cfs() // 遗留 CFS 路径
  }

  // 可使用 sysctl 或 boot 参数关闭 EEVDF:
  //   kernel.sched_feat=NO_EEVDF 或 no_eevdf

但由于 v6.6 之后 CFS 的 red-black tree 数据结构已经被重写专门适配 EEVDF，实际上无法回退到 v6.5 之前的 CFS 实现。NO_EEVDF flag 仅禁用 deadline 选择逻辑，数据结构已经改变。

💡 与 sched_ext 的关系

回到你提供的上下文（”Walking towards BPF overdependency”），这里有一个有趣的对比：

维度	EEVDF	sched_ext
实现方式	内核原生 C 代码	BPF 字节码，热加载
灵活性	固定策略	完全可编程
安全保证	内核固有的	BPF 验证器保证
公平性	数学保证（eligibility + deadline）	取决于 BPF 实现
适用场景	通用服务器/桌面	特定工作负载优化

两者不是替代关系，而是互补：

EEVDF 是默认公平调度器，保证系统在任何场景下的基本公平性和可预测延迟
sched_ext 允许在特定场景（数据库、游戏、实时流）中覆盖 EEVDF，用定制策略换取性能

社区中确实有关于 “是否应该在 sched_ext 中重新实现 EEVDF” 的讨论，以便在不加载 BPF 调度器时使用标准的 EEVDF，而在加载时平滑切换。这使得 sched_ext 的 BPF 调度器只需关注差异化策略，而不必重新实现公平性基线。

🔗 参考

主线和合并: Peter Zijlstra, 提交 8b43e04b1e6b (“sched/fair: Implement EEVDF”, v6.6-rc1)
设计文档: Documentation/scheduler/sched-design-CFS.rst（已更新，包含 EEVDF 章节）
LWN 分析: “EEVDF sheduler”, Jonathan Corbet, LWN (2023年8月)
社区讨论: LSFMM+BPF 2023, Peter Zijlstra 发表的 EEVDF 设计演讲

参考来源

来源: https://lwn.net/Articles/1019230/

⚠️ 免责声明

本站内容均由 AI 基于公开知识辅助生成，仅供学习参考，请勿直接引用作为依据。作者不对信息的准确性、完整性及适用性作保证，亦不对因使用本站内容产生的任何损失承担责任。