Linux CFS 完全公平调度器深度工程实战：从红黑树到 vruntime 与组调度全链路

一、为什么需要理解 CFS

进程调度是操作系统的核心职责，决定了哪个进程在何时获得 CPU 时间。Linux 内核自 2.6.23 版本起引入 CFS（Completely Fair Scheduler，完全公平调度器），取代了之前 O(1) 调度器。CFS 的核心哲学极其优雅：每个进程应该获得等比例的 CPU 时间份额。

理解 CFS 不仅有助于理解操作系统原理，更是系统调优、性能瓶颈排查、实时性优化的基础。大公司股票交易延迟的微秒级竞争、数据库的 CPU 争用、容器编排的 QoS 保障——背后都绕不开 CFS。

本文将从工程实战角度，逐层拆解 CFS 的设计哲学、数据结构、算法流程、组调度扩展、NUMA 负载均衡以及与实时调度的交互。

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

2.1 问题建模

假设有两个进程 A 和 B 同时在运行，理想情况下每个进程应获得 50% 的 CPU 时间。如果我们记录每个进程实际已运行的时间（exec_time），公平调度就等价于：选择 exec_time 最小的那个下一个执行。

但这个过程忽略了一个关键因素——进程的优先级（nice 值）。高优先级进程应该获得更多的 CPU 时间。引入权重（weight）的概念后，vruntime 的定义为：

vruntime = (实际运行时间 × NICE_0_LOAD) / 进程权重

NICE_0_LOAD 是 nice=0 时的基准权重（通常 1024），而进程权重由 nice 值通过 sched_prio_to_weight 数组映射。nice 值越小（优先级越高），权重越大，vruntime 增长越慢。

2.2 权重表与 nice 值

Linux 内核中 nice 值从 -20 到 +19，对应的权重范围从 88761 到 15。这意味着 nice=+19 的进程获得 CPU 时间的比例约为 nice=-20 进程的 1/5895。每一级 nice 值之间的比例约为 1.25（即高优先级进程每级多获得 25% 的相对 CPU）。

2.3 红黑树：选择下一个进程

CFS 选择下一个要运行的进程时，需要找到 vruntime 最小的那个。如果对所有进程做线性扫描，时间复杂度 O(n)，在成千上万个进程时不可接受。CFS 使用 红黑树（Red-Black Tree） 来组织可运行进程，键值为 vruntime。

红黑树的特点：

• 插入/删除/查找操作 O(log n)，适合高频调度场景
• 树的最左叶子节点始终是 vruntime 最小的进程，即下一个要调度的进程
• 内核通过 rb_leftmost 指针以 O(1) 快速获得最左节点

三、CFS 核心数据结构

3.1 sched_entity

每个进程（task_struct）内部嵌入了 sched_entity 结构体，这是 CFS 调度的基本单元。关键字段：

struct sched_entity {
    struct load_weight  load;       // 权重
    struct rb_node      run_node;   // 红黑树节点
    u64                 vruntime;   // 虚拟运行时间
    u64                 exec_start; // 本次开始执行的时间
    u64                 sum_exec_runtime; // 累计实际运行时间
};

3.2 cfs_rq（CFS 运行队列）

每个 CPU 都有一个 cfs_rq，代表该 CPU 上的 CFS 调度队列。核心字段：

struct cfs_rq {
    struct load_weight  load;       // 队列总权重
    unsigned long       nr_running; // 可运行进程数
    u64                 min_vruntime; // 队列最小 vruntime（用于新进程初始化）
    struct rb_root_cached tasks_timeline; // 红黑树根
    struct sched_entity *curr;      // 当前运行实体
};

3.3 调度周期与目标延迟

CFS 的调度周期（sched_latency）是指所有可运行进程至少运行一轮的时间。默认在 6ms ~ 24ms 之间动态调整：

调度周期 = max(6ms, 可运行进程数 × 0.75ms)
每个进程的时间片 = 调度周期 × 进程权重 / 队列总权重

四、核心算法流程

4.1 进程被唤醒：enqueue_entity

当进程从睡眠状态被唤醒时，需要插入到红黑树中：

1. 计算新进程的 vruntime（初始值为 cfs_rq->min_vruntime，避免饥饿）
2. 将 sched_entity 的红黑树节点插入正确位置
3. 更新队列的 nr_running 和 load

4.2 进程被阻塞：dequeue_entity

当进程放弃 CPU（等待 I/O、定时器到期等）：

1. 从红黑树中删除节点
2. 更新 sum_exec_runtime 和 vruntime
3. 如果该进程是当前进程，设置 cfs_rq->curr = NULL

4.3 调度选择：pick_next_task_fair

struct sched_entity *se = pick_next_entity(cfs_rq);
set_next_entity(cfs_rq, se);
context_switch(prev, next);

pick_next_entity 从红黑树最左叶子选出下一个进程，set_next_entity 更新当前进程并计算下次调度时间。

4.4 周期性调度：task_tick_fair

每个 tick 时钟中断时调用：

if (cfs_rq->curr->vruntime > se->vruntime + sched_slice)
    resched_curr(rq);  // 触发抢占

五、组调度（Group Scheduling）

5.1 动机

当系统中有大量用户时，仅按进程级公平会在用户间产生不公平。例如：用户 A 有 1 个进程，用户 B 有 100 个进程——B 获得 100 倍的 CPU 时间。组调度确保用户间的公平。

5.2 cgroup 与 cpu 子系统

通过 cpu cgroup 子系统，可以将进程分组到不同层级，每组有自己的权重和时间限制。顶部使用 CFS，底部也是 CFS——形成层级调度。

/sys/fs/cgroup/cpu/
├── user.slice          (用户级组，权重 100)
│   ├── user-1000.slice (单用户组)
│   │   ├── session-X.scope
│   │   └── app.service
│   └── user-1001.slice
├── system.slice        (系统服务组，权重 100)
└── machine.slice       (虚拟机/容器组)

5.3 带宽控制（Bandwidth Control）

cgroup 通过 cpu.cfs_quota_us 和 cpu.cfs_period_us 实现硬限流：

# 限制一组进程每 100ms 内最多使用 30ms CPU（即 0.3 核）
echo 30000 > /sys/fs/cgroup/myapp/cpu.cfs_quota_us
echo 100000 > /sys/fs/cgroup/myapp/cpu.cfs_period_us

六、NUMA 负载均衡

在 NUMA 架构中，进程在不同节点间迁移需要考虑：

• 内存局部性：迁移进程可能导致大量远程内存访问
• 调度域层级：DIE → MC → NODE，逐层均衡
• Idle 优先：优先将进程迁移到 idle CPU，避免中断运行中的进程

关键参数 sched_balundering 控制跨 NUMA 节点迁移的阈值。负载均衡器通过 find_busiest_group() 和 active_load_balance_cpu_stop() 在不同层级间做均衡决策。

七、实时调度类与优先级

Linux 调度器存在优先级链：

SCHED_FIFO / SCHED_RT (优先级 0-99, 高于 CFS)
    ↓
SCHED_NORMAL / SCHED_OTHER (CFS 管理)
    ↓
SCHED_BATCH (降低交互性，允许更长延迟)
    ↓
SCHED_IDLE (优先级最低，只在系统空闲时运行)

实时进程（RT）始终优先于 CFS 进程。内核通过 for_each_class 从高到低选择调度类。SCHED_IDLE 的进程不会主动抢占普通进程，但 wk_time 极低（仅 ~15）。

八、eBPF 可观测与调优

8.1 调度延迟追踪

通过 eBPF 的 runqlat、runqlen 工具可以观测运行队列长度和调度延迟：

# 统计运行队列延迟分布（单位微秒）
$ bpftrace -e tracepoint:sched:sched_switch { @delay = nsecs - args->prev->exec_start; }'

8.2 使用 sched_ext 在用户空间编写调度器

Linux 6.12+ 引入了 sched_ext（Scheduler Extending），允许用户态通过 eBPF 代码实现自定义调度策略而无需修改内核源码。调度器以 "scx_" 为前缀命名。

8.3 关键调优参数

# 调度器粒度（越小越精细，越多 overhead）
/proc/sys/kernel/sched_min_granularity_ns   # 默认 3ms
/proc/sys/kernel/sched_wakeup_granularity_ns  # 默认 4ms
/proc/sys/kernel/sched_migration_cost_ns     # 默认 500us
/proc/sys/kernel/sched_cfs_bandwidth_slice_us # 默认 5ms

九、容器调度实践

在 Kubernetes/Docker 中，CFS 直接限制容器可用时间：

# Docker --cpu-quota 原理：每 period 最多使用 quota 的 CPU 时间
docker run --cpu-quota=50000 --cpu-period=100000 myapp  # 0.5 核

# Kubernetes resources.requests.cpu 对应 cpu.shares（权重比）
# Kubernetes resources.limits.cpu 对应 cfs_quota_us / cfs_period_us

重要陷阱：vCPU 过载（overcommit）时，即使 limits 设为 1 核，由于 CFS 配额限制，单线程应用也可能出现调度延迟峰值（多达 period 长度）。

十、总结与展望

CFS 的设计优雅地将复杂的调度决策转化为一个简单的不变量：所有可运行进程的 vruntime 应该是单调递增的。红黑树、组调度、NUMA 负载均衡、带宽控制都是在这个核心之上构建的工程扩展。

未来 Linux 调度的演进方向：

• LATENCY_NICE：允许进程声明自己对延迟的敏感度（不改变实际优先级），调度器在第二层决策时考虑
• sched_ext：用户态调度器框架，让应用针对性地优化自身调度行为
• 硬件调度：Intel Thread Director / AMD CPPC 配合调度器的异构 CPU 感知

深入理解 CFS 不仅有助于编写高性能程序，更是通往系统级优化的必经之路。