Linux CFS 完全公平调度器：从红黑树到vruntime的深度解析

一、引言：为什么需要 CFS

在 Linux 2.6.23 内核之前，O(1) 调度器主导着进程调度。然而随着服务器负载日益复杂，O(1) 调度器在交互式进程响应时间上的不合理性日益突出。2007 年，Ingo Molnár 提出了 Completely Fair Scheduler（CFS），以"完全公平"的理念彻底重构了 Linux 的进程调度机制。

CFS 的核心思想极其简洁：让每个进程的虚拟运行时间（vruntime）保持同步增长，谁落后了就给谁更多 CPU 时间。这一理念通过红黑树数据结构实现了 O(log n) 的高效调度。

二、核心概念：虚拟运行时间（vruntime）

vruntime（virtual runtime）是 CFS 调度的基石。每个进程维护一个累计值，表示该进程在虚拟时钟下的运行时间：

vruntime += delta_exec * (NICE_0_LOAD / weight)

其中关键参数的含义：

• delta_exec：实际执行的物理时间
• NICE_0_LOAD：nice 值为 0 时的权重基准（1024）
• weight：进程权重，由 nice 值决定

这意味着：高权重进程的 vruntime 增长更慢，更倾向于被调度器选中。nice 值每降低 1（优先级提高），获得 CPU 时间约增加 10%。

三、红黑树：CFS 的调度数据结构

CFS 使用红黑树（Red-Black Tree）来组织所有可运行进程，树键为 vruntime。最左侧节点即 vruntime 最小的进程，就是下一个被调度的候选者。

// 内核源码：kernel/sched/fair.c\nstruct cfs_rq {\n    struct rb_root_cached tasks_timeline;  // 红黑树根\n    struct rb_node *rb_leftmost;           // 缓存最左节点\n    u64 min_vruntime;                      // 最小 vruntime\n    unsigned long runnable_weight;\n    struct load_weight load;\n    // ...\n};

红黑树的选择出于以下考虑：

• 插入/删除 O(log n)，适合频繁的进程切换
• 查找最小值 O(1)（通过 rb_leftmost 缓存）
• 自平衡，避免退化

四、调度流程详解

4.1 进程入队与出队

// 进程唤醒/创建时入队\nstatic void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)\n{\n    struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node;\n    struct rb_node *parent = NULL;\n    struct sched_entity *entry;\n    bool leftmost = true;\n\n    while (*link) {\n        parent = *link;\n        entry = rb_entry(parent, struct sched_entity, run_node);\n        if (entity_before(se, entry)) {\n            link = &parent->rb_left;\n        } else {\n            link = &parent->rb_right;\n            leftmost = false;\n        }\n    }\n\n    rb_link_node(&se->run_node, parent, link);\n    rb_insert_color_cached(&se->run_node, &cfs_rq->tasks_timeline, leftmost);\n}\n\n// 取下一个进程（最左侧节点）\nstatic struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)\n{\n    struct rb_node *left = rb_first_cached(&cfs_rq->tasks_timeline);\n    if (\!left)\n        return NULL;\n    return rb_entry(left, struct sched_entity, run_node);\n}

4.2 主调度器逻辑

当 CPU 需要选出下一个进程运行时，CFS 调度类的 pick_next_task_fair 被调用：

static struct task_struct *pick_next_task_fair(struct rq *rq)\n{\n    struct cfs_rq *cfs_rq = &rq->cfs;\n    struct sched_entity *se;\n\n    if (\!cfs_rq->nr_running)\n        return NULL;\n\n    do {\n        se = pick_next_entity(cfs_rq);    // 取出最左进程\n        set_next_entity(cfs_rq, se);       // 更新 min_vruntime\n        cfs_rq = group_cfs_rq(se);         // 处理组调度\n    } while (cfs_rq);\n\n    return task_of(se);\n}

五、时间片与抢占机制

CFS 没有传统意义上的固定时间片。取而代之的是 targeted latency（目标延迟） 和 minimum granularity（最小粒度） 两个参数：

进程的理想运行时间计算：

ideal_runtime = sched_latency_ns / nr_running

当运行进程数过多时（nr_running * min_granularity > latency），使用最小粒度替代。

六、组调度（Group Scheduling / cgroups）

CFS 原生支持进程组调度，与 cgroups 深度集成。系统中的调度实体可以嵌套，形成树状结构：

struct sched_entity {\n    struct load_weight load;      // 权重\n    struct run_node   run_node;   // 红黑树节点\n    struct cfs_rq      *cfs_rq;    // 所属 cfs_rq\n    struct cfs_rq      *my_q;      // 子 cfs_rq（组调度时非空）    u64                vruntime;\n    // ...\n};

使用 cpu.shares 可以控制一个 cgroup 获得的 CPU 时间占比。例如：

/sys/fs/cgroup/cpu/A/cpu.shares = 1024   # 50% CPU\n/sys/fs/cgroup/cpu/B/cpu.shares = 1024   # 50% CPU\n/sys/fs/cgroup/cpu/C/cpu.shares = 2048   # 66.7%（相对 B）

七、NUMA 感知调度

现代多核/多路服务器中，NUMA（Non-Uniform Memory Access）架构对调度性能影响巨大。CFS 通过以下机制实现 NUMA 感知：

1. 负载均衡：周期性在 CPU 间平衡负载，优先在同一 NUMA 节点内迁移
2. NUMA Balancing：自动检测远程访问的页面，决策是否迁移进程或页面
3. Idle Balance：当 CPU 空闲时主动去其他运行队列"偷取"任务

八、实战调优指南

8.1 交互式应用加速

# 提高优先级（减小 nice 值）\nnice -n -5 ./interactive_app\n\n# 或运行时调整\nrenice -n -10 -p $(pgrep app_name)\n\n# 使用 chrt 设置实时优先级（谨慎！）\nchrt -f 50 ./realtime_task

8.2 限制 CPU 占用

# 使用 cgroups v2 限制\nmkdir /sys/fs/cgroup/cpu/limited_group\necho "200000 1000000" > /sys/fs/cgroup/cpu/limited_group/cpu.max\necho $PID > /sys/fs/cgroup/cpu/limited_group/cgroup.procs\n# 结果：每 1 秒周期内最多使用 0.2 秒 CPU（即 20%）

8.3 性能监控

# 查看进程调度统计\ncat /proc/$(pidof nginx)/sched\n\n# 关键输出：\n# nr_switches      : 总上下文切换次数（自愿 + 非自愿）\n# nr_voluntary_switches : 自愿切换（等待 IO 等）\n# nr_involuntary_switches : 非自愿切换（时间片用完被抢占）\n# se.sum_exec_runtime : 总实际运行时间\n# se.vruntime      : 当前虚拟运行时间\n\n# 使用 perf 分析调度延迟\nperf sched record -a sleep 10\nperf sched latency --sort max\nperf sched map    # 可视化 CPU 调度热点

九、内核参数速查

十、与 EEVDF 的演进关系

从 Linux 6.6 内核开始，CFS 逐渐被 EEVDF（Earliest Eligible Virtual Deadline First） 调度器替代。EEVDF 通过引入 deadline 概念，解决了 CFS 在高负载下的延迟尾部分布问题，同时保留了 vruntime 公平性的核心思想。

EEVDF 的关键改进：

• 为每个任务设定明确的 deadline = vruntime + 调度延迟/进程数
• 选择 earliest deadline 的任务运行，行为更接近理论上的理想调度
• 消除了 CFS 中复杂的 "granularity" 和 "latency" 权衡参数

十一、总结

CFS 作为 Linux 调度器发展史上的里程碑，其设计哲学影响深远：

• 用红黑树替代了传统的优先级数组，实现 O(log n) 高效调度
• 用vruntime代替固定时间片，实现真正的按比例公平分配
• 引入组调度原语，为容器化和资源隔离奠定基础
• 其理念延续到 EEVDF，持续推动 Linux 调度器向更精确、更低延迟演进

理解 CFS 不仅有助于系统性能调优，更是深入 Linux 内核的一把钥匙。