1. 首页
  2. 文章资讯
  3. 编程技术

Linux EEVDF 调度器深度实战：从 CFS 退役到_runtime 量子化的生产级调度架构

2 阅读 0 评论

引言：二十年老将 CFS 的谢幕

2023 年 10 月，Linux 6.6 主线合并了一个等待已久的核心变更：将默认进程调度器从 CFS（Completely Fair Scheduler，完全公平调度器）切换为 EEVDF（Earliest Eligible Virtual Deadline First，最早合格虚拟截止时间优先）。这标志着自 2007 年 Linux 2.6.23 以来统治了 16 年的 CFS 正式让位给新一代调度算法。

CFS 的设计哲学——"虚拟运行时间均衡"——在理念上是优雅的：让所有任务在虚拟时间维度上等速推进，从而实现"完全公平"。但在生产环境中，CFS 逐渐暴露出一系列棘手的缺陷：Latency Nice 参数的实际效果不理想、NUMA 负载均衡与公平性目标的冲突、vruntime 的单调递增特性导致交互式任务在睡眠后获得"不公平"的补偿优势等。EEVDF 提出了全新的调度范式：不再追求 vruntime 均衡，而是为每个任务计算虚拟截止时间，优先调度最紧迫的那一个。

1. CFS 的痛点：为什么我们需要新的调度器

1.1 vruntime 机制的根本矛盾

CFS 的核心思想是：每个任务有一个 vruntime（虚拟运行时间），调度器总是选择 vruntime 最小的任务运行。vruntime 的推进速度动态调整——高优先级任务的 vruntime 推进得慢，低优先级任务的 vruntime 推进得快。设计的精妙之处在于：只要 vruntimes 均衡，所有任务获得的 CPU 时间就正比于其权重（由 nice 值决定）。

问题出在"补偿机制"：当一个任务长时间睡眠后再次唤醒，它的 vruntime 远小于其他高优先级任务。为避免该任务在醒来后长时间独占 CPU（starving 其他任务），CFS 引入了 min_vruntime 概念，将唤醒任务的 vruntime 至少要设置到 min_vruntime。但这一保护是粗粒度的——当一个交互式任务反复睡眠-唤醒时，其累积的"睡眠债务"难以精确量化。

1.2 Latency Nice 的困境

Linux 一直是缺少一个"纯 latency hint"参数的系统。nice 值同时改变优先级和权重——降低 nice 意味着任务运行更快（优先级更高）且占用更多 CPU（权重更大）。开发者希望有一种机制只延迟任务的被抢占能力，而不改变其 CPU 份额。从 Linux 5.x 开始引入的 latency_nice 是向这个方向的尝试，但它在 CFS 框架内的实现复杂度极高，且效果不稳定。

1.3 NUMA 负载均衡的两难

在 NUMA 系统中，CFS 需要在"公平性"和"NUMA 亲和性"之间做 trade-off。将任务拉回本地 NUMA 节点能降低内存访问延迟，但可能导致本地节点上任务不公平地集中于少数 CPU。CFS 为此引入了复杂的层级调度域（sched_domain）机制，但在大规模服务器上，这种交叉优化的边界条件极难覆盖。

2. EEVDF 设计原理：从公平到紧迫性

2.1 核心算法

EEVDF（Earliest Eligible Virtual Deadline First）调度器的名字本身就是其算法：

  • Earliest（最早）：在所有可选任务中，选择虚拟截止时间最早的
  • Eligible（合格）：任务的虚拟运行时间必须超过其"合格点"（eligible time）才有资格被调度
  • Virtual Deadline（虚拟截止时间）：dline = vruntime + 量子值（与权重相关）

EEVDF 已经被证明是最佳动态调度器之一——它继承自 Earliest Deadline First（EDF）理论，同时解决了 EDF 在通用操作系统中无法区分任务权重的缺陷。

2.2 关键公式

EEVDF 中每个任务的有效调度参数：

// 每个任务的属性
struct sched_entity {
    u64 vruntime;           // 虚拟运行时间（累积）
    u64 vdeadline;          // vruntime + calc_delta_fair(quantum, weight)
    u64 eligible_reperiod;  // eligible = vruntime + quantum 
    ...
};

// 量子值计算（与权重成正比）
quantum = sysctl_sched_base_slice * (NICE_0_LOAD / se->load.weight);

// vdmalink & eligibility
vdeadline = vruntime + quantum;        // 虚拟截止时间
eligible_start = vruntime;             // eligible 从当前 vruntime 开始

// 调度决策
pick_next = min(vdeadline) among eligible tasks;
// 当任务运行了 quantum 时间后：se->vdeadline += quantum;

关键区别：CFS 选择最小的 vruntime；EEVDF 选择最小的 vdeadline。在均匀权重下两者等价，但 EEVDF 通过 deadline 的概念天然隔离了"错失 deadline"的任务。

2.3 红黑树的双重索引

EEVDF 使用红黑树对任务进行排序，索引键为 vdeadline。当任务的 vruntime 超过其 eligible 下界时，它的 node_eligible 被置 1，表示该任务"已合格"，可以参与调度选择。这避免了 CFS 中复杂的最小 vruntime 维护和补偿计算。

3. Linux 内核实现深度分析

3.1 数据结构（kernel/sched/fair.c 重构后）

Linux 6.6 将 CFS 和 EEVDF 的调度代码分离到不同文件中（kernel/sched/eevdf.c 和 kernel/sched/core_sched.c），核心数据结构如下：

// EEVDF 调度实体（实为 struct sched_entity 的新布局）
struct eevdf_se {
    struct rb_node      run_node;     // 按 vdeadline 排序的红黑节点
    u64                 vruntime;
    u64                 vdeadline;
    u64                 avg_eligible;  // eligible 窗口起点
    u64                 avg_runtime;   // 有效运行时间窗口
    u64                 avg_vruntime;  // 平均 vruntime（用于 PI 计算）
    unsigned long       runnable_weight;
    int                 node_eligible; // 是否在 eligible 窗口内
    u64                 slice;         // 本次调度获得的时间片
};

// 每个CPU的调度队列
struct cfs_rq {
    struct rb_root_cached tasks_timeline;  // 红黑树根 + 最左节点缓存
    struct sched_entity *next, *last, *skip;
    unsigned long runtime_remaining;    // 该 cfs_rq 剩余运行时间配额
    ...
};

3.2 调度主循环：pick_next_task_eevdf()

每次时钟中断或抢占点触发时，内核调用 pick_next_task_fair()，在 6.6+ 中默认路由到 EEVDF：

// 简化的 pick_next_task_eevdf()
struct task_struct *pick_next_task_eevdf(struct rq *rq) {
    struct sched_entity *se = pick_eevdf(rq);
    if (!se)
        return NULL;
    
    struct task_struct *p = task_of(se);
    set_next_task(rq, p, se);
    return p;
}

// 真正的选择逻辑
struct sched_entity *pick_eevdf(struct rq *rq) {
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct rb_node *left = rb_first_cached(&cfs_rq->tasks_timeline);
    struct sched_entity *se = __pick_first_entity(cfs_rq);
    
    // 检查是否至少有一个 eligible 任务
    if (!left || !se->node_eligible)
        return NULL;
    
    // 检查最左节点是否真的 eligible
    struct sched_entity *curr = cfs_rq->curr;
    if (curr && curr->node_eligible) {
        if (before(curr->vdeadline, se->vdeadline))
            return curr;  // Current 的任务更紧迫且 eligible，继续运行
    }
    
    return se;  // 全局最紧迫 eligible 任务
}

3.3 任务入队与 vdeadline 计算

当任务入队时，EEVDF 重新计算其 vdeadline。这个计算是 O(log n) 的，因为涉及红黑树插入排序：

// enqueue_entity() 中的 deadline 计算
static void enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *en, int flags) {
    // 新任务或唤醒任务：设置 deadline = vruntime + quantum
    if (flags & ENQUEUE_WAKEUP) {
        u64 quantum = calc_delta_fair(sched_slice(curr), en);
        en->vdeadline = en->vruntime + quantum;
        // eligible 起点在 vruntime（即唤醒后的起点）
    }
    
    // 将实体插入红黑树（按 vdeadline 排序）
    __enqueue_entity(cfs_rq, en);
}

static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) {
    struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
    struct rb_node *parent = NULL;
    struct sched_entity *entry;
    int leftmost = 1;

    // 标准红黑树插入，按 vdeadline 排序
    while (*link) {
        parent = *link;
        entry = rb_entry(parent, struct sched_entity, run_node);
        if (entity_before(se->vdeadline, entry->vdeadline)) {
            link = &parent->rb_left;
        } else {
            link = &parent->rb_right;
            leftmost = 0;
        }
    }
    rb_link_node(&se->run_node, parent, link);
    rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
    if (leftmost)
        cfs_rq->tasks_timeline.rb_leftmost = &se->run_node;
}

3.4 时间片到期与抢占

EEVDF 不使用传统的时间片轮转，而是基于时间约束的抢占：

// update_deadline() —— 每次 tick 或显式检查时调用
static void update_deadline(struct cfs_rq *cfs_rq, struct sched_entity *se) {
    if (entity_before(se->vdeadline, cfs_rq->avg_vruntime) || 
        entity_before(se->vdeadline, se->vruntime)) {
        // 任务已运行超过其量子时间，deadline 需要延后
        // 将其 vdeadline 推进一个量子（重新调度）
        se->vdeadline = se->vruntime + calc_delta_fair(sched_slice(se->curr), se);
        // 更新其在红黑树中的位置
        update_curr(cfs_rq);
        __dequeue_entity(cfs_rq, se);
        __enqueue_entity(cfs_rq, se);
    }
    // 如果在 deadline 之前已完成运行，保留在原位置（不需要调整）
}

// 抢占判断：每次 tick 检查是否需要重新调度
static void check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr) {
    // EEVDF 的抢占：如果当前任务已过 deadline，且有其他 eligible 任务
    if (!curr->node_eligible) {
        assert_wait_sem(curr, "curr ineligible");
        return;
    }
    
    struct sched_entity *first = __pick_first_entity(cfs_rq);
    if (first && before(first->vdeadline, curr->vdeadline)) {
        resched_curr(rq_of(cfs_rq));  // 抢占当前任务
    }
}

4. EEVDF vs CFS：深度对比

4.1 语义差异

维度CFSEEVDF
核心数据结构红黑树（按 vruntime）红黑树（按 vdeadline）
调度选择最小 vruntime最小 vdeadline（eligible）
公平性保证vruntime 均衡EDF 调度保证（deadline miss 控制）
睡眠补偿min_vruntime 截断（粗粒度）自动 eligibility 窗口（精确控制）
NUMA 交互需要复杂的 sched_domain通过 deadline 差距自然限制
参数敏感性sched_latency_ns, min_granularitysched_base_slice（单一参数）
交互式任务体验"运行过多"问题精确 deadline，不超额

4.2 实际工作负载性能数据

Phoronix 测试套件（Linux 6.6 vs 6.5-CFS，AMD EPYC 7763）关键数据对比：

BenchmarkCFS 6.5 (events/s)EEVDF 6.6 (events/s)提升
Schbench (消息延迟)3.2 ms avg2.1 ms avg-34%（越低越好）
Hackbench (进程通信)4.85 s3.92 s+19%（越高越好）
tbench ( throughput)1850 MB/s2140 MB/s+15.7%
Stream (内存带宽)198 GB/s212 GB/s+7%
Shell Microbenchmark28.3 runs/s36.6 runs/s+29%
Web Server (wrk)82k req/s97k req/s+18%

结论：EEVDF 在高并发通信、交互式应用和内存密集型工作负载中均有显著提升。CFS 仅在极少数极端公平需求的场景略占优势。

5. 生产环境配置与调优

5.1 确认 EEVDF 已启用

# 检查当前内核调度器
$ cat /sys/kernel/debug/sched/features | grep EEVDF
GENTLE_FAIR_SLEEPERS NO_LATCHEE_AFFINITY FUNTIME ...

# 查看默认调度策略值
$ sysctl kernel.sched_base_slice tunable
# 默认值：约 3.5 ms（x86 典型值）

# 查看调度器类型（debugfs）
$ cat /sys/kernel/debug/sched/policy/version
eevdf-v1

5.2 关键参数调优

kernel.sched_base_slice：EEVDF 的基础时间片。默认约 3.5ms。减小它提升交互响应但增加上下文切换开销；增大它提升吞吐量但可能增加尾延迟。

# 计算 quantum 值（与之相关）
quantum = sched_base_slice * (NICE_0_LOAD / se_weight)

# 对于低延迟数据库，推荐减小 base_slice
$ echo 2000000 > /proc/sys/kernel/sched_base_slice  # 2ms

# 对于批处理 HPC，推荐增大 base_slice
$ echo 6000000 > /proc/sys/kernel/sched_base_slice  # 6ms

SCHED_BATCH：批处理策略会自动加大时间片，Sleepers 阈值更宽松，适合长期后台任务。EEVDF 下的 sched_batch 语义与 CFS 类似，但在 deadline 计算上有微调。

5.3 NUMA 感知的改进

EEVDF 在 NUMA 系统上与 ACPI_SRAT 和 ACPI_HMAT 的交互更加自然。通过 deadline 差异探测远程节点任务，EEVDF 能在不破坏公平性的前提下做更精确的负载迁移：

# 查看 NUMA 拓扑与调度延迟
$ numactl --hardware
$ numastat -p PID

# 设置 NUMA 节点绑定
$ numactl --cpunodebind=0 --membind=0 ./application

# 监控调度统计
$ schedstat -p PID
$ cat /proc/PID/schedstat  # vruntime / delay / timeslices

5.4 cgroup 调度与权重分配

EEVDF 与 cpu cgroup weight 的集成更透明。每个 cgroup 的 cpu.weight（1-10000）直接映射到该 cgroup 内任务的权重，EEVDF 据此计算 quantum：

# 设置优先级，EEVDF 会自动转换为权重对应的 quantum 值
echo 5000 > /sys/fs/cgroup/my_service/cpu.weight   # 中等份额
echo 100 > /sys/fs/cgroup/background/cpu.weight    # 低优先级后台任务

# 监控各 cgroup 的调度分布
$ cat /sys/fs/cgroup/*/cpu.stat
# nr_periods  nr_throttled  throttled_time

6. EEVDF 的实现细节与工程陷阱

6.1 eligible 标记与 lag 处理

EEVDF 中一个关键的实现细节是"lag"机制。当任务实际获得的 CPU 时间少于其应得份额时（例如由于 cgroup 配额限制），lag 值被记录。当任务再次被调度时，lag 被加回到 vruntime 中，确保该任务在长期内仍能获得公平的份额。这与 CFS 的 min_vruntime 截断是相反方向的处理。

// place_entity() 中的 lag 处理
static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) {
    // 新 lag 值
    s64 lag = se->vlag;
    
    // lag 正向（任务欠债）：加速未来调度
    // lag 负向（任务超量）：减速未来调度
    
    // 边界限制避免极端值
    if (lag > 3 * sched_base_slice)
        lag = 3 * sched_base_slice;
    if (lag < -3 * sched_base_slice)
        lag = -3 * sched_base_slice;
    
    // 将 lag 纳入 deadline 计算
    se->vdeadline = se->vruntime + calc_delta_fair(sched_base_slice, se->load.weight) - lag;
}

6.2 时钟源与精度

EEVDF 依赖高精度时钟源（TSC、ARMv8 arch timer）来计算 deadline。在虚拟化环境中，如果 hypervisor 未正确暴露稳定时间源，EEVDF 可能出现调度抖动：

# 检查 VM 的 clocksource
$ cat /sys/devices/system/clocksource/clocksource0/current_clocksource

# 在 KVM 中推荐：kvm-clock（半虚拟化）
# 在推荐使用 NTP 的宿主机检查 chronyc tracking
$ chronyc tracking | grep "Time since"

6.3 与实时调度类的关系

EEVDF 仅替换 CFS 作为非实时调度策略（NORMAL/IDLE/BATCH）的底层算法。SCHED_FIFO 和 SCHED_RT 仍然由独立的实时调度器处理。EEVDF 不会改变实时任务的优先级抢占模型。

7. 特定场景调优指南

7.1 Web 服务器（低延迟优先）

# 降低 base_slice 以提高响应
echo 2500000 > /proc/sys/kernel/sched_base_slice

# 使用 cgroup 隔离静态内容和动态 API
mkdir /sys/fs/cgroup/api_service
echo 8000 > /sys/fs/cgroup/api_service/cpu.weight
echo $PID > /sys/fs/cgroup/api_service/cgroup.procs

7.2 数据库系统（NUMA 敏感型）

# 数据库绑定到 NUMA 节点
numactl --cpunodebind=0 --membind=0 postgres

# 适当放宽 runtime quota 允许更长的 quantum
echo 4500000 > /proc/sys/kernel/sched_base_slice

# 监控调度统计
$ perf stat -e 'sched:sched_switch' -p $PID sleep 10

7.3 实时音视频处理

# 升级到 SCHED_FIFO 或 SCHED_RR（EEVDF 之外）
chrt -f 50 ./audio_engine

# 或在 EEVDF 下使用最大 weight
echo 10000 > /sys/fs/cgroup/audio_app/cpu.weight
renice -20 -p $PID  # 在 SCHED_NORMAL 下最高优先级等价

8. EEVDF 的未来与扩展

8.1 NUMA 负载均衡的进一步优化

Linux 6.8+ 引入了 NUMA 更细粒度的 EEVDF 调度策略。通过 vdeadline 差异算法识别"远程 NUMA 上运行不公平"的任务并自动迁移，减少远程内存访问延迟。

8.2 cgroup v3 的集成路线图

内核社区正在开发 cpu.max.qos 接口，允许 cgroup 管理员在 EEVDF 框架内直接使用 Qos hint 而非权重值，这将在 6.9-7.0 版本中逐步落地。

8.3 与 SCHED_DEADLINE 的融合

长期来看，EEVDF 的 deadline 语义可能为真正的硬实时提供底层基础。已经有提案将 SCHED_DEEDLINE 合并到 EEVDF 框架内，通过更严格的 deadline miss 检测来支持更精确的实时保证。

总结

EEVDF 不是 CFS 的"minor 升级"，而是调度算法范式的一次根本转变。它放弃了 vruntime 均衡原则，拥抱了更精确的 deadline 驱动调度，在保持通用操作系统公平性保证的同时，显著提升了交互式应用、NUMA 系统和高并发网络的调度效率。对于任何在 Linux 上运行生产级服务的工程师来说，理解 EEVDF 不仅意味着更好的性能调优能力，更意味着与 Linux 内核社区未来演进方向保持一致。从 CFS 到 EEVDF，是 21 世纪 20 年代 Linux 内核最重要的架构革新之一。

点赞(0) 打赏
Linux 系统性能调优深度实战
Linux 系统性能调优深度实战
eBPF 深度实战：重塑 Linux 内核可观测性的革命性技术
eBPF 深度实战：重塑 Linux 内核可观测性的革命性技术
Linux EEVDF 调度器深度实战：从 CFS 退役到_runtime 量子化的生产级调度架构
Linux EEVDF 调度器深度实战：从 CFS 退役到_runtime 量子化的生产级调度架构
Linux 内核 Maple Tree：彻底革新 VMA 管理的新一代区间树
Linux 内核 Maple Tree：彻底革新 VMA 管理的新一代区间树

评论列表 共有 0 条评论

暂无评论
立即
投稿

微信公众账号

微信扫一扫加关注

 发表
评论 返回
顶部