Linux CFS 调度器：从红黑树到虚拟时钟的公平调度艺术

前言：调度器——操作系统的"交通指挥官"

当我们在一台 Linux 服务器上同时运行数百个进程时，CPU 时间如何公平、高效地分配给每一个任务？答案藏在 Linux 内核最核心的子系统之一——进程调度器中。自 2.6.23 内核以来，CFS（Completely Fair Scheduler，完全公平调度器）取代了传统的 O(1) 调度器，以一套优雅的数学模型实现了"完全公平"的 CPU 时间分配。本文将深入 CFS 的源码级实现，解析红黑树、虚拟运行时间（vruntime）和最小粒度等核心概念的工程实践。

1. 核心思想："虚拟运行时间"取代真实时间

CFS 的革命性创新在于引入虚拟运行时间（virtual runtime, vruntime）作为调度决策的唯一依据。每个进程维护一个 vruntime 值，表示该进程在"公平世界"中已经获得的 CPU 时间。调度器每次选择 vruntime 最小的进程运行，从而保证所有可运行进程的 vruntime 最终趋于一致。

vruntime 的计算公式为：

vruntime += (实际运行时间) * (NICE_0_LOAD / 当前进程权重)

其中 NICE_0_LOAD 是 nice 值 0 对应的权重基准（通常为 1024），进程权重由 nice 值查表获得。这意味着：高权重进程（低 nice 值）的 vruntime 增长更慢，从而获得更多的实际 CPU 时间。这种设计让优先级差异被平滑地转化为时间分配比例，而非传统调度器的"硬抢占"。

2. 红黑树：O(log n) 的高效选择

为了快速找到 vruntime 最小的进程，CFS 使用红黑树（Red-Black Tree）作为可运行队列的数据结构（struct cfs_rq 中的 tasks_timeline 字段）。红黑树以进程的 vruntime 作为排序键，最左侧节点始终是下一个被调度的进程。

关键操作复杂度：

• 插入/删除节点：O(log n)，发生在进程唤醒或阻塞时
• 选择最左节点：均摊 O(1)，维护 rb_leftmost 指针缓存
• 树再平衡：最多 2 次旋转（红黑树性质）

相比 O(1) 调度器的 140 个优先级队列，CFS 的红黑树在动态进程数场景下表现更加稳定，且没有"时间片过期"带来的行为突变。

3. 时间片与最小粒度：防止过度抢占的"刹车"

CFS 不给进程分配固定时间片，而是通过两个参数控制调度的最小占用时间：

// kernel/sched/fair.c (简化逻辑)
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;
}

// 最小粒度 (sysctl_sched_min_granularity, 默认 0.75ms)
if (delta_exec > sysctl_sched_min_granularity)
    resched_curr(rq);

__sched_period 根据可运行进程数动态计算调度周期：当进程数 ≤ sched_latency / min_granularity 时，周期等于 sched_latency（默认 6ms）；否则周期 = 进程数 × min_granularity。这确保上下文切换的开销不超过总 CPU 时间的 ~1%。

4. 组调度与层级调度实体

CFS 通过 struct sched_entity 实现了调度实体的层级嵌套，支持组调度（CGroup CPU 子系统）：

struct sched_entity {
    struct load_weight  load;       // 权重
    struct rb_node      run_node;   // 红黑树节点
    u64                  vruntime;   // 虚拟运行时间
    u64                  exec_start; // 本次开始执行时间
    u64                  sum_exec_runtime; // 累计实际运行时间
    // ... 层级指针
    struct cfs_rq        *cfs_rq;   // 所属 CFS 运行队列
    struct cfs_rq        *my_q;     // 子 CFS 队列（组调度时）
};

层级调度让 CFS 实现了"组间公平、组内公平"的两级分配：首先在用户组间按 cpu.shares 分配时间，然后在组内再按进程权重分配。这是容器化场景下 CPU 资源隔离的基石。

5. 新进程的 vruntime 初始化：避免"饥饿攻击"

一个新创建的进程如果从 0 开始计算 vruntime，会立刻抢占 CPU（因为所有老进程的 vruntime 都更大）。为了防止这种"fork 炸弹式"的公平性破坏，CFS 使用min_vruntime 继承：

static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
    u64 vruntime = cfs_rq->min_vrquntime;
    if (initial)  // 新进程初始化
        vruntime += sched_vslice(cfs_rq, se);  // 放置到当前周期位置
    se->vruntime = max_vruntime(se->vruntime, vruntime);
}

新进程被插入到当前红黑树的中间位置，而不是最左端，从而让老进程继续运行一个周期才被抢占。

6. NUMA 感知与负载均衡

现代服务器多为 NUMA 架构，跨节点访存延迟可达本地节点的 2-3 倍。CFS 通过以下机制优化 NUMA 场景：

• NUMA Balancing：周期性地将进程迁移到其内存所在的 NUMA 节点
• 调度域（Sched Domain）：从 MC → DIE → NUMA 多级负载均衡，优先在核间、封装间迁移，最后才跨 NUMA
• Idle Balance：当 CPU 空闲时主动拉取其他节点的任务，减少唤醒延迟

7. 调优实战：如何为你的工作负载选参数

8. 总结：CFS 给我们的工程启示

CFS 的设计哲学——"不追求绝对公平的每个时间片，而追求长期累积的公平"——对分布式调度、资源配额系统都有深远启发：

1. 用抽象指标替代物理时间：vruntime 是对 CPU 使用的"公平度量"，类比分布式系统中的"虚拟时间戳"
2. 数据结构的效率决定系统规模上限：红黑树 O(log n) 让 CFS 在数千进程场景下仍保持稳定
3. 层级化设计解耦关注点：组调度通过实体嵌套同时支持单机公平和跨用户公平

下次当你在 Kubernetes 中设置 cpu limits 时，请记住这背后正是 CFS 通过 cfs_period_us 和 cfs_quota_us 在守护着容器的 CPU 公平。