Linux 内核调度器深度解析：从 CFS 到 EEVDF 的演进之路

在操作系统中，调度器是内核最核心的组件之一，它负责决定哪个进程在何时获得 CPU 时间片。随着硬件架构和工作负载的持续演变，Linux 内核的调度器也经历了从简单的轮转调度到完全公平调度器 (CFS)，再到如今最新的最早符合虚拟截止时间优先 (EEVDF) 的变革。本文将深入剖析这一演进历程，带你理解每个阶段的设计思想和实现原理。

一、调度器的历史背景

Linux 内核调度器的演变并非一蹴而就，而是伴随着硬件架构和工作负载的深刻变化而发展的。早期的 Linux 内核使用了简单的 O(n) 调度器，其时间复杂度随进程数量线性增长，在服务器负载较高时成为明显瓶颈。

2002 年，Ingo Molnár 提出了 O(1) 调度器，它解决了扫描所有进程的性能问题，但引入了复杂的启发式算法来判断进程是 "交互式" 还是 "CPU 密集型"，这些硬编码规则在实际场景中常常表现不稳定。

2007 年，Molnár 再次出手，设计了 CFS（Completely Fair Scheduler），将调度器的设计理念从 "猜测进程行为" 转向了 "数学上的公平"，这一设计至今仍是默认调度器的基础。

二、CFS 完全公平调度器：红黑树与虚拟运行时间

2.1 核心设计理念

CFS 的设计哲学可以用一句话概括：让所有可运行任务获得等量的 CPU 时间。为了实现这一目标，CFS 引入了 虚拟运行时间（vruntime） 的概念。每个进程维护一个 vruntime 值，每次调度时，CFS 选择 vruntime 最小的进程运行，从而实现"公平"。

虚拟运行时间的计算公式如下：

// kernel/sched/fair.c
static void update_curr(struct cfs_rq *cfs_rq)
{
    struct sched_entity *curr = cfs_rq->curr;
    u64 now = rq_clock_task(rq_of(cfs_rq));
    u64 delta_exec;
    
    if (unlikely(!curr))
        return;
    
    delta_exec = now - curr->exec_start;  // 计算本次运行的物理时间
    if (unlikely((s64)delta_exec <= 0))
        return;
    
    curr->exec_start = now;  // 更新上次开始时间
    
    curr->sum_exec_runtime += delta_exec;  // 累加总运行时间
    
    // 关键公式：vruntime += delta_exec * NICE_0_LOAD / weight
    curr->vruntime += calc_delta_fair(delta_exec, curr);
    
    update_min_vruntime(cfs_rq);  // 更新队列中最小 vruntime
}

其中权重计算考虑了进程的 nice 值（优先级）。nice 为 0 的进程权重为 1024，nice 值每减 1（优先级提高），权重增加约 25%；每加 1，减少约 10%。这意味着高优先级进程的 vruntime 增长更慢，获得更多 CPU 时间。

2.2 红黑树数据结构

CFS 使用红黑树来管理所有可运行的红黑树，以 vruntime 作为键值。每次调度只需从树的左侧取出最左侧的节点（最小 vruntime），时间复杂度为 O(log N)。当进程用完时间片或被抢占时被重新放回红黑树中，取最小值和重新插入都是 O(log N) 操作。

// 选择下一个要运行的进程
static struct pick_next_task_fair(struct rq *rq)
{
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct sched_entity *se;
    
    if (!cfs_rq->nr_running)
        return NULL;
    
    // 取出 vruntime 最小的调度实体
    se = pick_next_entity(cfs_rq);
    set_next_entity(cfs_rq, se);
    
    return task_of(se);
}

2.3 调度延迟与粒度

CFS 中有两个关键参数：

• sched_latency：调度周期（默认 24ms），在此周期内所有可运行任务至少运行一次
• min_granularity：最小时间片（默认 3ms），避免进程数过多时每个时间片太小导致频繁切换

每个进程的时间片 = sched_latency / nr_running，但不得小于 min_granularity。当进程数 N 大于 sched_latency / min_granularity 时，周期会自动扩展以保证每个进程至少运行 min_granularity。

2.4 CFS 存在的问题

尽管 CFS 设计优良，但在长期使用中暴露出一些核心问题：

• 新进程惩罚不公平：新进程的 vruntime 初始化为当前 min_vruntime，但如果此时有大量进程等待，新进程会因为 vruntime 过小而"爆发"性抢占，导致老进程饥饿
• 睡眠进程补偿：长时间睡眠后醒来，vruntime 远小于其他进程，可能会导致短时间内的不公平分配
• 交互性延迟：桌面场景下的交互进程可能被延迟唤醒，导致"卡帧"现象
• Wakeup Preemption（唤醒抢占）不足：被唤醒的进程不一定能及时抢占正在运行的低优先级进程

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

3.1 设计动机

2023 年，Linux 内核社区引入了一个可选的调度器 EEVDF（Earliest Eligible Virtual Deadline First），它由 Peter Zijstra 提出，旨在解决 CFS 长期存在的公平性与延迟问题。自 Linux 6.6 开始，EEVDF 作为 CONFIG_SCHEDEEVDD 配置项可使用；Linux 6.9 之后成为默认调度器。

EEVDF 的理论基础来自实时调度领域中的 EDF（Earliest Deadline First）算法，但将其扩展到了通用调度场景。核心思想是：每个任务不仅有自己的虚拟运行时间，还有一个明确的合法截止时间（eligible deadline），调度器选择截止时间最早的任务运行。

3.2 核心概念

EEVDF 引入了三个关键属性来管理每个任务：

• vRuntime（虚拟运行时间）：与 CFS 相同的权重计算方式，任务已经消耗的虚拟时间量
• vElapsed（虚拟流逝时间）：系统范围内单调递增的虚拟时间
• eligibility（合格时间）：任务的 vruntime 达到其应分配的"份额"时的虚拟时间点，即 deadline

任务在 EEVDF 中被放置在两个数据结构中：

• 时间轴（Timeline）：以 deadline 为键的红黑树，调度器选择最左侧（最早 deadline）的任务
• rq→ tree：以 vruntime 为键的红黑树，用于在 deadline 相同时决定顺序

3.3 调度决策过程

EEVDF 的调度决策可概括为以下算法：

// 简化版 EEVDF 选择逻辑
struct sched_entity *pick_next_ee_vdf(struct cfs_rq *cfs_rq)
{
    // 1. 检查最左侧节点是否已过 eligible time
    //    如果未过，即使它 deadline 最早也不能运行
    //    必须选择一个"laciest eligible"的任务
    
    // 2. 在 timeline 上选择 deadline 最早且已 eligible 的候选人
    struct rb_node *leftmost = rb_first_cached(&cfs_rq->timeline);
    struct sched_entity *se = rb_entry(leftmost, struct sched_entity, run_node);
    
    // 3. 检查是否 eligible（vruntime 达到了其份额的起点）
    //    eligible = base + lag_positive - w * offset
    //    其中 lag 保证公平性
    
    // 4. 如果没有 eligible 的任务，选择 lag 最大（最不公平的）任务运行
    if (!se_enough_elapsed(se)) {
        se = pick_next_find(cfs_rq);  // 在 lag 中找最大 lag 的候选人
    }
    
    return se;
}

3.4 公平性保证：Lag 机制

EEVDF 确保公平的核心机制是 lag。lag 定义为任务「已获得的真实 CPU 比例」与其「应得比例」之差：

• lag > 0：任务获得 CPU 不足，需要补偿
• lag = 0：任务正在"公平线"上
• lag < 0：任务获得 CPU 过多，需要让出

EEVDF 通过 lag 来确保在任意时间窗口 T 内，任务获得的 CPU 时间近似等于其权重比例 × T，即实现了长期公平性。同时不像 CFS 那样需要全局 "sched_latency" 参数，而是直接在每个任务级别管理公平性。

3.5 唤醒抢占改进

EEVDF 最大的改进之一是对唤醒抢占的处理。在 CFS 中，唤醒抢占（wakeup preemption）只是一个 heuristic 参数控制的软优化，而 EEVDF 基于 deadline 进行抢占判断：

• 被唤醒的任务如果 deadline 早于当前运行任务，且已合格（eligible），则可以被抢占
• 不需要 sysctl_sched_wakeup_granularity_us 这类"猜测性参数"
• 一致性更好，桌面场景的交互延迟显著降低

四、性能对比与实际效果

4.1 桌面交互延迟

在 Phoronix 的测试中，EEVDF 相对于 CFS 的主要改进包括：

• Firefox 编译期间的桌面响应延迟降低约 30%
• 桌面合成器（Kwin/Mutter）的卡帧频率明显减少
• 在重度负载（如并行编译）切换应用程序的时间更稳定

4.2 吞吐量和服务器场景

在服务器工作负载下，EEVDF 与 CFS 的吞吐量差异并不大，但因为更有可预测性，延时敏感型服务（如 Redis、Memcached）的尾延迟有所改善。EEVDF 的 lag 机制确保了当某个任务暂时释放 CPU 后再次需要时，能更快获得补偿，减少了所谓的"调度器延迟抖动"。

4.3 内核编译测试数据

测试场景	CFS (ms)	EEVDF (ms)	改善
桌面交互延迟 (编译负载)	45	32	~29%
Redis P99 延迟 (负载下)	1.8	1.5	~17%
内核编译 (make -j64)	145s	144s	~持平
桌面帧率稳定性 (Kwin)	92%	98%	明显改善

五、实践：如何在系统中使用和调优 EEVDF

5.1 检查当前调度器

# 查看内核版本
uname -r

# 查看当前调度器（需要较新的内核）
cat /sys/kernel/debug/sched/deadline_mode
# 输出 1 表示 EEVDF 已激活

# 查看所有调度器参数
ls /proc/sys/kernel/sched*

5.2 EEVDF 可调参数

# sched_min_granularity_ns: 最小运行粒度（默认 1ms EEVDF vs 3ms CFS）
sysctl kernel.sched_min_granularity_ns

# sched_base_slice_ns: 基础时间片（默认 3ms）
sysctl kernel.sched_base_slice_ns

# sched_child_runs_first: 子进程是否优先运行（仍为 CFS 时代参数）
sysctl kernel.sched_child_runs_first

# sched_energy_aware: 是否针对异构核（big.LITTLE）做能耗感知调度
sysctl kernel.sched_energy_aware

5.3 chrt 与 nice 仍然有效

在支持 EEVDF 的系统中，nice 值和 SCHED_FIFO/SCHED_RR 实时调度依然生效。EEVDF 主要影响 SCHED_NORMAL/SCHED_OTHER（CFS 队列）的行为，对实时策略（FIFO/RR）的优先级顺序不变，始终高于普通调度类。

5.4 对 cgroups 资源控制的影响

EEVDD 与 cgroups v2 的 cpu.max（类似 CFS bandwidth control）配合更好。在延迟敏感的工作负载中（如 kubelet 管理的关键服务），EEVDF 的确定性可以减少 CPU throttling 造成的尾部延迟毛刺。

六、总结与展望

EEVDF 并非对 CFS 的一揽子否定，而是在 CFS 运行良好的基础上，通过引入 deadline-based 的调度决策和 lag-based 的公平性保证，解决了 CFS 在交互延迟和公平边界上的遗留问题。对于大多数服务器场景，CFS 差异不大；对于桌面交互、实时音视频处理、游戏直播等场景，EEVDF 带来的改善是切实可感知的。

Linux 调度器的演进没有停止，未来我们可以看到更多工作：

• 针对异构大小核架构的感知调度优化
• NUMA 感知的负载均衡改进
• 与 SCHED_EXT（基于 BPF 的用户态可扩展调度器）的集成
• 能耗感知调度的进一步智能化

操作系统的心脏——调度器，永远在公平与效率之间寻找最优平衡点。