从 CFS 到 EEVDF：Linux 内核调度器的演进与完全公平的革命性重构

3 阅读 0 评论 0 点赞

引言：调度器的核心地位

进程调度是操作系统内核最核心的职责之一。它决定哪个进程在何时获得 CPU 时间，直接影响系统的吞吐量、响应速度和公平性。自 Linux 2.6 以来，调度架构经历了三次重大变革：O(n) 调度器 → O(1) 调度器 → CFS（Completely Fair Scheduler），而 Linux 6.6 又带来了颠覆性的 EEVDF（Earliest Virtual Deadline First），取代 CFS 成为默认调度器。

本文将从调度器的基础概念出发，深入剖析 CFS 的设计哲学与实现细节，解释其为什么能在 2.6.23 中取代 O(1) 调度器并成为默认。随后，我们将探讨 CFS 在十余年运行中暴露的局限性，以及 Linux 6.6（2023年10月发布）引入的 EEVDF 调度器如何在保持公平性的同时，彻底解决交互延迟和 NUMA 不友好的问题。

一、从 O(1) 到 CFS：公平性的范式转移

1.1 O(1) 调度器的困境

在 CFS 之前，Linux 2.6 的 O(1) 调度器（Ingo Molnár 设计，2.5.42 引入）以效率著称——选择下一个进程的时间复杂度恒为 O(1)。然而，O(1) 的代价是复杂的启发式规则：

运行队列双数组：active 和 expired 两个优先级数组（各 140 级），时间片耗尽后进程从 active 移至 expired。
交互性启发式：通过平均睡眠时间判断进程是"交互式"还是"批处理"，给予交互式进程更高优先级和时间片奖励。这一启发式规则在实际场景中频繁误判——计算密集型长睡眠进程被错误标记为交互式，而短交互进程反而得不到优待。
时间片粒度问题：高优先级进程获得更长的时间片（如 200ms），导致高优先级交互式进程在切换时产生可感知的延迟。
NUMA 不感知：O(1) 调度器对 NUMA 拓扑缺乏原生支持，跨节点迁移策略简单粗暴。

1.2 CFS 的核心设计："虚拟运行时间"（vruntime）

CFS 由 Ingo Molnár 在 2007 年 Linux 2.6.23 中引入，其设计理念简洁而优雅：所有进程的 vruntime 以相同速率增长，调度器总是选择 vruntime 最小的进程运行。

CFS 不再使用时间片（timeslice），而是使用时间记账（time accounting）。每个进程拥有一个虚拟运行时间（vruntime），其增长速率与进程的权重（weight）成反比：

delta_vruntime = (delta_exec * NICE_0_LOAD) / weight

其中 NICE_0_LOAD 是 nice=0 进程的权重基准值（1024）。nice 值越低的进程（高权重）vruntime 增长越慢，获得更多 CPU 时间。

关键数据结构：红黑树（rbtree）

CFS 使用红黑树组织所有可运行进程，键值为 vruntime。最左侧节点（最小 vruntime）即为下一个被调度的进程。O(log n) 的插入/删除开销，对于现代系统数千个进程的规模，实际上完全可以接受。

struct cfs_rq {
    struct rb_root_cached tasks_timeline;  // 红黑树根
    struct rb_node *rb_leftmost;           // 最左节点缓存
    u64 min_vruntime;                      // 最小 vruntime 追踪
    ...
};

调度流程

时钟中断（tick）触发时，更新当前进程的 vruntime。若新 vruntime 超过最左节点的 vruntime，设置 need_resched 标志。在调度点（返回用户态或中断退出时），调用 pick_next_task_fair() 选择最左节点。

1.3 CFS 的公平性保证：理想多任务处理器

CFS 基于"理想多任务处理器"（Ideal Multitasking Processor）概念：如果处理器能同时运行 N 个进程（每个占 1/N），则它们是绝对公平的。CFS 通过追踪每个进程的实际运行时间，使其 vruntime 趋向这个理想分配。

当新进程被唤醒或创建时，其 vrunime 被设为 cfs_rq->min_vruntime（或稍低的值），避免饥饿也避免不公平优势。新进程的补偿策略经历了多次演化：

vruntime 继承：新进程继承父进程的 vruntime（避免 fork 后疯狂抢占）
min_vruntime 补偿：新进程 vruntime 设为 cfs_rq->min_vruntime，给予"半次调度周期"的让步
sched_child_runs_first：控制 fork 后父还是子先运行（exec 前子进程通常先运行以利用 COW 零页）

二、CFS 的实现深度剖析

2.1 组调度（cgroups CPU controller）

CFS 原生支持组调度。每个 cgroup 有自己的 cfs_rq，组间公平分配 CPU，组内再公平分配。两层公平的嵌套结构使得容器、系统服务等场景获得精确的 CPU 份额控制：

// 组调度核心结构
struct sched_entity {
    struct load_weight load;    // 权重
    struct rb_node run_node;    // 红黑树节点
    u64 vruntime;               // 虚拟运行时间
    u64 exec_start;             // 开始执行时间
    u64 sum_exec_runtime;       // 累计执行时间
    // ...
};

2.2 NUMA 感知与负载均衡

CFS 的负载均衡策略在 SMP 和 NUMA 系统中通过调度域（sched_domain）层次化实现。从 SMT → MC → DIE → NUMA 节点，逐层向上进行负载均衡。load_balance() 函数在 IDLE 或周期性时钟中断中触发：

IDLE 负载均衡：CPU 空闲时立即将繁忙 CPU 上的进程迁移过来
周期性负载均衡：tick 触发，检查是否需要迁移
NUMA 平衡：将进程迁移到其内存所在的 NUMA 节点
Wake-up 平衡：唤醒进程时选择最优的 CPU（考虑缓存亲和性）

2.3 休眠进程的 vruntime 补偿问题

CFS 面临一个经典难题：长时间休眠的进程醒来时 vruntime 远小于活跃进程，导致其垄断 CPU 很长一段时间。CFS 通过 min_vruntime 限制休眠进程的 vruntime 最小值来缓解此问题（place_entity() 函数）：

static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
    u64 vruntime = cfs_rq->min_vruntime;
    if (initial)          // 新进程
        vruntime += sched_vslice(cfs_rq, se);
    else                  // 唤醒的休眠进程
        vruntime -= sysctl_sched_latency;  // 轻微奖励
    se->vruntime = max_vruntime(se->vruntime, vruntime);
}

三、CFS 的局限性与 EEVDF 的诞生契机

尽管 CFS 在 2007 年是一项革命性设计，但近 20 年的运行暴露了一些结构性问题：

3.1 交互式延迟的"唤醒抢占"问题

CFS 对唤醒进程的补偿（sysctl_sched_latency，默认 6ms）在实际场景中常常过于激进。当数千个进程竞争 CPU 时，即使是有轻微 vruntime 惩罚的唤醒进程，仍可能获得显著优势，导致关键的交互进程等待时间不可预测。

3.2 "紧密耦合"的调度策略

CFS 的公平性算法与调度策略（SCHED_NORMAL/SCHED_BATCH/SCHED_IDLE）耦合在一起。任何一处修改（如修复休眠补偿问题）都可能影响其他策略的表现。Ingo Molnár 本人曾在 2016 年的重置补丁中承认，CFS 的代码已经过于复杂且难以维护。

3.3 NUMA 负载均衡的局限

CFS 对 NUMA 系统的自动平衡策略在面对高度 NUMA 敏感的应用（如数据库、HPC）时表现不稳定。"NUMA balancing" 需要独立的页故障迁移路径，与 CFS 调度器耦合度受限。

四、EEVDF：经典的复兴

4.1 核心思想：最早虚拟截止时间优先

EEVDF（Earliest Virtual Deadline First）由 Stoica 和 Zhang 在 1995 年提出，是一种经典的实时调度算法。其核心规则极其简单：

总是选择虚拟截止时间最早的进程运行。

EEVDF 的关键概念映射：

virtual deadline = runtime / weight = vruntime / weight × 常数

与 CFS 的"最小 vruntime"不同，EEVDF 引入显式的截止时间概念。每个进程获得一个"虚拟运行时间配额"的槽位，当进程用完自己的配额时，被重新赋予一个新的截止时间并放入队列。

4.2 EEVDF 的数学模型

给定进程 i 的权重 w_i 和已运行时间 r_i，其虚拟运行时间和虚拟截止时间定义为：

虚拟运行时间：vruntime_i = r_i × (W_total / w_i)，其中 W_total 是总权重
虚拟截止时间：vdeadline_i = vruntime_i + (lag_i / w_i) × W_total

其中 lag_i 是进程的理论运行时间与实际运行时间之差。lag 为负意味着进程"欠债"（获得多于公平份额），应延后调度。

4.3 EEVDF 的算法特性

EEVDF 满足以下关键性质：

公平性：在任意长度为 T 的时间窗口内，每个进程获得的 CPU 时间趋近于 w_i / W_total × T（与 CFS 相同）
O(log n) 复杂度：与 CFS 相同的红黑树结构，键值为 vdeadline
延迟边界可证：相对 CFS，EEVDF 为交互式进程提供最坏情况下更严格的延迟上界
无补偿机制：EEVDF 通过显式的 lag 计算取代了 CFS 的启发式补偿，调度决策更一致

五、Linux 6.6 中 EEVDF 的实现

5.1 代码结构

Linux 6.6 的 EEVDF 实现在 kernel/sched/fair.c 中（后迁至 kernel/sched/eevdf.c），核心结构沿用 sched_entity 但重新定义了调度逻辑：

// EEVDF 调度实体（简化）
struct sched_entity {
    u64 deadline;       // 虚拟截止时间（替代 vruntime 作为红黑树键）
    u64 vruntime;       // 虚拟运行时间（仍用于公平性衡量）
    u64 avg_runtime;    // 平均运行时间估算
    s64 lag;            // 理论 vs 实际的偏差
    // ... 负载权重等字段继承
};

5.2 调度流程对比

步骤	CFS	EEVDF
选择下一个	min(vruntime)	min(deadline)
时间片耗尽	重新插入红黑树	重新赋予 deadline = vruntime + qual/w_i
唤醒补偿	min_vruntime + latency/2	计算 lag，负 lag 自动延后
期限检查	无	检查 deadline 过期 → 触发重新调度

5.3 关键改进：无 tick 运行

EEVDF 支持更激进的无_tick（tickless）行为。由于存在明确的 deadline 检查，EEVDF 可以更长时间不触发 tick（如 H tickless 模式），减少中断开销的同时保证调度准确。在延迟敏感场景（游戏、音视频播放）中，这减少了不必要的上下文切换。

六、实验测量与性能表现

Linux 社区对 EEVDF 与 CFS 进行了大量基准测试，主要结论如下：

6.1 桌面交互性

在桌面合成器场景（Mutter/KWin + Chromium + 后台编译），EEVDF 下 99 分位帧延迟降低 15-30%。根因：EEVDF 的延迟边界更严格，避免了 CFS 偶尔出现的"大段时间片持有者"阻塞交互线程的情况。

6.2 服务器吞吐量

在 Web 服务器（nginx）和数据库（PostgreSQL）场景中，EEVDF 与 CFS 的吞吐量差异在 ±2% 以内——这正是预期之内，因为公平性保证相同。

6.3 极端压力测试

在 256 核 NUMA 系统、10000 个 CPU 密集型线程的压力下，EEVDF 的调度延迟抖动（jitter）比 CFS 降低约 20%，体现在任务完成时间的方差更小。

七、前沿发展与社区讨论

sched_ext（调度器可扩展框架）：Linux 6.12 引入 sched_ext，允许用户空间编写调度器 BPF 程序，实现"调度器即插件"。EEVDF 提供了更干净的接口基础。
实时性与公平性融合：EEVDF 被视为统一 SCHED_NORMAL 和 SCHED_FIFO/SCHED_RR 调度类的可能路径，SCHED_DEADLINE 类已使用 EDF 算法。
异构调度：面对 Intel Hybrid（P-core/E-core）和 ARM big.LITTLE，EEVDF 为异构调度器（ITMT）提供了更明确的 deadline 计算基础。

八、总结

EEVDF 不是对 CFS 的"推翻"，而是其理念的延续和强化。两者的核心目标一致——"完全公平"。区别在于手段：CFS 通过"补偿启发式"逼近公平，EEVDF 通过"显式 deadline 计算"精确保证公平。EEVDF 将实时系统中的经典 EDF 算法与 CFS 的 CGroup 支持融合，为 Linux 调度器提供了理论上更坚实的延迟边界保证。

对于系统程序员而言，理解 CFS → EEVDF 的演进是掌握现代操作系统调度设计的绝佳案例：当启发式遇到瓶颈，回归经典理论往往是最优雅的解决方案。

参考资料

Ingo Molnır, "CFS: Completely Fair Scheduler", Linux 2.6.23 commit message
Stoica, I. & Zhang, H., "Earliest Eligible Virtual Deadline First: A Flexible and Accurate Mechanism for Proportional Share Resource Allocation", 1995
Linux 6.6 Release Notes — EEVDF becomes default scheduler
Linux Kernel Documentation: Documentation/scheduler/sched-design-CFS.rst

点赞(0) 打赏

本文分类：Linux内核
本文标签：Linux内核进程调度 CFS EEVDF
浏览次数：3 次浏览
发布日期：2026-10-17 08:36:34
本文链接：https://www.ybb.press/linux-kernel/18236.html

上一篇 > Linux 内核 RCU 机制深度剖析：从 Read-Copy-Update 到 grace period 内核实现

从 CFS 到 EEVDF：Linux 内核调度器的演进与完全公平的革命性重构

引言：调度器的核心地位

一、从 O(1) 到 CFS：公平性的范式转移

1.1 O(1) 调度器的困境

1.2 CFS 的核心设计："虚拟运行时间"（vruntime）

关键数据结构：红黑树（rbtree）

调度流程

1.3 CFS 的公平性保证：理想多任务处理器

二、CFS 的实现深度剖析

2.1 组调度（cgroups CPU controller）

2.2 NUMA 感知与负载均衡

2.3 休眠进程的 vruntime 补偿问题

三、CFS 的局限性与 EEVDF 的诞生契机

3.1 交互式延迟的"唤醒抢占"问题

3.2 "紧密耦合"的调度策略

3.3 NUMA 负载均衡的局限

四、EEVDF：经典的复兴

4.1 核心思想：最早虚拟截止时间优先

4.2 EEVDF 的数学模型

4.3 EEVDF 的算法特性

五、Linux 6.6 中 EEVDF 的实现

5.1 代码结构

5.2 调度流程对比

5.3 关键改进：无 tick 运行

六、实验测量与性能表现

6.1 桌面交互性

6.2 服务器吞吐量

6.3 极端压力测试

七、前沿发展与社区讨论

八、总结

参考资料

评论列表共有 0 条评论

发表评论取消回复

从 CFS 到 EEVDF：Linux 内核调度器的演进与完全公平的革命性重构

引言：调度器的核心地位

一、从 O(1) 到 CFS：公平性的范式转移

1.1 O(1) 调度器的困境

1.2 CFS 的核心设计："虚拟运行时间"（vruntime）

关键数据结构：红黑树（rbtree）

调度流程

1.3 CFS 的公平性保证：理想多任务处理器

二、CFS 的实现深度剖析

2.1 组调度（cgroups CPU controller）

2.2 NUMA 感知与负载均衡

2.3 休眠进程的 vruntime 补偿问题

三、CFS 的局限性与 EEVDF 的诞生契机

3.1 交互式延迟的"唤醒抢占"问题

3.2 "紧密耦合"的调度策略

3.3 NUMA 负载均衡的局限

四、EEVDF：经典的复兴

4.1 核心思想：最早虚拟截止时间优先

4.2 EEVDF 的数学模型

4.3 EEVDF 的算法特性

五、Linux 6.6 中 EEVDF 的实现

5.1 代码结构

5.2 调度流程对比

5.3 关键改进：无 tick 运行

六、实验测量与性能表现

6.1 桌面交互性

6.2 服务器吞吐量

6.3 极端压力测试

七、前沿发展与社区讨论

八、总结

参考资料

CXL 内存池化与架构演进：从服务器级扩展机架级资源分解的工业实践

从 CFS 到 EEVDF：Linux 内核调度器的演进与完全公平的革命性重构

Linux内核网络栈深度实战：从Socket到网卡驱动的全路径数据流转剖析

Linux 内核 RCU 机制深度剖析：从 Read-Copy-Update 到 grace period 内核实现

评论列表 共有 0 条评论

发表评论 取消回复

评论列表共有 0 条评论

发表评论取消回复