Linux 内核进程调度器深度工程实战：从 CFS 到 EEVDF 的完整演进链路

前言

Linux 内核的进程调度器是整个操作系统的神经中枢，它决定了 CPU 时间片如何在数百个进程之间公平分配、如何在吞吐量和时延之间取得平衡、以及如何适配从嵌入式设备到超级计算机的各种硬件拓扑。本文将从调度器的历史演变出发，深入剖析 CFS（完全公平调度器）的 vruntime 理论和红黑树实现，再到 Linux 6.6 引入的 EEVDF（Earliest Eligible Virtual Deadline First）调度器，完整呈现调度器工程实现的每一个细节。

1. 调度器的演进脉络

Linux 调度器经历了四个主要阶段：

• O(n) 调度器（Linux 2.4）：遍历所有进程选择最优，复杂度 O(n)，在进程数增多时性能急剧下降
• O(1) 调度器（Linux 2.6 早期）：引入活跃/过期数组和优先级位图，选择进程 O(1)，但交互性启发式判断过于复杂且有缺陷
• CFS（Linux 2.6.23+）：Ingo Molnár 提出，用红黑树管理 vruntime，实现 NICE_0_LOAD 权重公平分配
• EEVDF（Linux 6.6+）：基于虚拟截止时间优先的调度器，用红黑树按 elapse+deadline 排序，替代 CFS 的时延敏感调度

2. CFS 核心原理：虚拟运行时间

CFS 的核心思想是维护每个进程的虚拟运行时间（vruntime），确保所有可运行进程的 vruntime 尽可能相等。计算公式：

delta_vruntime = (delta_exec * NICE_0_LOAD) / weight

其中权重由进程的 nice 值决定：

• nice=0 → weight=1024
• nice=-5 → weight=335（获得更多 CPU 份额）
• nice=+5 → weight=312（获得更少 CPU 份额）

优先级每差一级，CPU 份额差约 10%（即 weight 比值约 1.25）。

3. CFS 红黑树调度队列

CFS 使用红黑树作为运行队列（cfs_rq），以 vruntime 为 key：

struct cfs_rq {
    struct rq *rq;
    struct rb_root_cached tasks_timeline; // 红黑树根
    struct rb_node *rb_leftmost;          // 最左节点（最小vruntime）
    u64 min_vruntime;                     // 当前最小vruntime
    unsigned long nr_running;
    struct load_weight load;
};

调度器总是选择最左节点（rb_leftmost），即 vruntime 最小的进程运行。这样做的好处是选择下一个进程的复杂度仅为 O(1)。

4. 时间片与调度周期

CFS 不再使用固定时间片，而是动态计算 sched_slice：

// sched_slice: 当前进程在一个调度周期内可运行的时间
static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    u64 slice = __sched_period(cfs_rq->nr_running);
    slice *= se->load.weight;
    do_div(slice, cfs_rq->load.weight);
    return slice;
}

// __sched_period: 调度周期，最少 sysctl_sched_latency (6ms)
// 当进程数 > /sysctl_sched_latency/sysctl_sched_min_granularity 时
// 周期 = nr_running * sysctl_sched_min_granularity (0.75ms)
static u64 __sched_period(unsigned long nr_running)
{
    if (nr_running > sysctl_sched_latency / sysctl_sched_min_granularity)
        return nr_running * sysctl_sched_min_granularity;
    return sysctl_sched_latency;
}

5. 组调度与 cgroup v2

CFS 支持组调度（Group Scheduling），允许将 CPU 资源按 cgroup 层级分配：

• cpu.weight：控制 cgroup 间的 CPU 份额（默认 100，范围 1-10000）
• cpu.max：设置 cgroup 的 CPU 配额（如 "100000 100000" 表示每 100ms 周期最多使用 100ms CPU，即 1 核上限）
• cpu.max.burst：允许 cgroup 短时间超出 max 限制

在 cgroup v2 中，CPU 权重通过 sched_entity 的 weight 字段传达给 CFS，每个 cgroup 的调度实体独立进入红黑树。

6. NUMA 调度与负载均衡

在多核 NUMA 系统中，CFS 面临两大挑战：跨 NUMA 节点内存访问延迟不均衡，以及 CPU 间的负载不均衡。内核通过以下机制解决：

• 周期性负载均衡（load_balance）：tick 触发，将最繁忙运行队列的进程拉到空闲 CPU
• 空闲负载均衡（idle_balance）：CPU 进入空闲时，从邻居域拉取任务
• NUMA 平衡（numa_balancing）：扫描进程访问的页面，将页面迁移到访问最频繁的 NUMA 节点
• 调度域（sched_domain）：MCU → DIE → MC → NUMA 四层拓扑，下层域在上层域中做负载均衡

7. EEVDF：下一代调度器

Linux 6.6 引入 EEVDF（Earliest Eligible Virtual Deadline First）作为新调度类，专门为时延敏感任务设计。其核心概念：

• eligibility：进程必须满足 runtime ≤ lag + eligibility 条件才能获得 CPU
• virtual deadline：deadline = vruntime + latency_nice_based_slice
• lag 补偿：追踪进程的"债务"，防止饥饿

// EEVDF 调度实体关键结构
struct sched_entity {
    u64 vruntime;      // 虚拟运行时间
    u64 deadline;      // 虚拟截止时间（EEVDF 新增）
    u64 vlag;          // 虚拟延迟 = vruntime - 理想vruntime
    u64 slice_min;     // 最小时间片约束
};

8. EEVDF vs CFS 对比

9. 实际调优参数

生产环境中常用的调度器调优：

# 查看当前调度策略
chrt -p $$

# 设置实时优先级（SCHED_FIFO）
chrt -f -p 50 进程PID

# 调整调度器粒度
sysctl kernel.sched_min_granularity_ns = 1000000    # 1ms
sysctl kernel.sched_latency_ns = 8000000             # 8ms
sysctl kernel.sched_wakeup_granularity_ns = 1500000  # 唤醒抢占

# NUMA 自动平衡开关
sysctl kernel.numa_balancing = 1

# latency_nice（-20到19，越小越优先）
latency-nice 程序  
renice -n -5 -p PID  # 等效调整

10. 总结

Linux 调度器从 O(n) → O(1) → CFS → EEVDF 的演进，体现了内核在公平性和时延之间持续探索的过程。CFS 的 vruntime 模型极其优雅，但在时延敏感场景下依赖启发式调优。EEVDF 通过显式的 deadline 约束和 lag 补偿，提供了可证明的时延保证。理解 CFS 和 EEVDF 的原理，是深入 Linux 系统内核和性能优化的必经之路。