Linux CFS 调度器深度解析：红黑树、vruntime 与 NUMA 负载均衡

引言：调度器的演进之路

Linux 内核的进程调度器经历了从 O(n) 到 O(1)，再到 CFS（完全公平调度器）的三次重大演进。CFS 由 Ingo Molnar 在 2007 年引入 2.6.23 内核，其核心思想是用红黑树取代传统运行队列，实现了真正意义上的"虚拟运行时间"追踪与公平分配。

1. CFS 核心数据结构

CFS 的关键数据结构是红黑树（rbtree），每个可调度实体（sched_entity）都有一个 vruntime（虚拟运行时间）字段。调度器始终选择 vruntime 最小的进程执行，从而保证长期的 CPU 时间公平性。

struct sched_entity {
    struct load_weight  load;       /* 用于负载均衡 */
    struct rb_node      run_node;   /* 红黑树节点 */
    u64                 vruntime;   /* 虚拟运行时间 */
    u64                 exec_start; /* 当前周期的开始时间 */
    u64                 sum_exec_runtime; /* 总运行时间 */
};

2. 红黑树与进程选择

红黑树的操作复杂度为 O(log n)，当系统中存在大量进程时，这一设计显著优于传统 O(n) 遍历。__pick_next_entity() 函数通过 rb_leftmost 指针直接获取最左侧节点（最小 vruntime），实现了 O(1) 的进程选择。

3. 权重与优先级映射

nice 值每变化 1 级，CPU 权重变化约 10%。CFS 使用预计算的 prio_to_weight 表将 [-20, 19] 的 nice 值映射到 [88761, 15] 的权重区间，高权重进程获得更大的实际时间片。

const int sched_prio_to_weight[40] = {
    /* -20 */ 88761, 71755, 56483, 46273, 36291,
    /* -15 */ 29154, 23254, 18705, 14949, 11916,
    /* -10 */ 9548,  7620,  6100,  4904,  3906,
    /*  -5 */ 3121,  2501,  1991,  1586,  1277,
    /*   0 */ 1024,  820,   655,   526,   423,
    /*   5 */ 335,   272,   215,   172,   137,
    /*  10 */ 110,   87,    70,    56,    45,
    /*  15 */ 36,    29,    23,    18,    15,
};

4. 调度延迟与粒度控制

通过 sched_latency_ns（默认 24ms）和 sysctl_sched_min_granularity（默认 3ms）两个参数，CFS 在公平性和上下文切换开销间取得平衡。当运行进程数超过 4 个时，实际时间片按 min_granularity 计算，避免过度切换。

5. NUMA 感知与负载均衡

现代多核系统中，CFS 的负载均衡器在 NUMA 节点内和跨节点间工作，通过 periodic load balance 和 idle balance 两种策略将任务迁移至空闲核心，同时考虑迁移成本（cache affinity）。

6. EDL 调度与实时性扩展

Linux 5.x 引入的 EDF（最早截止时间）调度类 SCHED_DEADLINE 使用 GEDF（全局最早截止时间第一）算法，为硬实时任务提供了基于带宽预留的强保障，在自动驾驶和工业控制领域得到广泛应用。

结语

CFS 的设计哲学是"用数据结构取代复杂算法"——一个红黑树加 vruntime 追踪，便解决了困扰操作系统数十年的公平调度问题。理解 CFS 不仅有助于系统性能调优，更是学习 Linux 内核设计的绝佳入口。