Linux 内核 CFS 调度器：完全公平调度算法深度解析与实战

一、调度器概述

进程调度是操作系统内核最核心的组成部分之一。它负责决定哪个进程在何时获得 CPU 时间片，直接影响系统的吞吐量、响应时间和公平性。Linux 内核从 2.6.23 版本开始引入 完全公平调度器（Completely Fair Scheduler, CFS），取代了早期的 O(1) 调度器，成为普通进程的默认调度策略。

CFS 的核心设计理念是：让每个进程获得「完全公平」的 CPU 时间份额。它不使用传统的固定时间片，而是通过跟踪每个进程的虚拟运行时间（vruntime）来动态分配 CPU 资源。

二、CFS 核心数据结构

2.1 调度实体 struct sched_entity

在 CFS 中，每个进程或进程组都对应一个调度实体（sched_entity），它包含了调度的核心数据：

struct sched_entity {
    u64 exec_start;          // 本次执行开始时间
    u64 sum_exec_runtime;    // 总实际运行时间
    u64 vruntime;            // 虚拟运行时间（核心字段）
    u64 prev_sum_exec_runtime; // 上次切换前的总运行时间
    u64 nr_migrations;       // 迁移次数
    struct load_weight load; // 进程权重（与 nice 值相关）
    struct rb_node run_node; // 红黑树节点
    // ... 更多字段
};

其中 vruntime 是 CFS 的灵魂字段——它记录了进程的虚拟运行时间，在所有可运行进程中选择 vruntime 最小的进程来运行。

2.2 红黑树（Red-Black Tree）

CFS 使用红黑树来组织所有可运行进程，按 vruntime 排序：

• 最左侧节点：vruntime 最小的进程，即最「亏欠」CPU 时间的进程，下一个被调度
• 最右侧节点：vruntime 最大的进程，即获得 CPU 最多的进程
• 树操作复杂度：O(log n)，即使进程数量极大，调度开销也很小

// 选择下一个要运行的进程（简化逻辑）
struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq) {
    struct sched_entity *se = __pick_first_entity(cfs_rq);
    return se;
}

三、vruntime 的计算与积累

3.1 核心计算公式

vruntime 的增长速度取决于进程的权重。权重越高（nice 值越低），vruntime 增长越慢，意味着该进程可以获得更多的 CPU 时间：

// 简化的 vruntime 更新逻辑
delta_vruntime = physical_delta_exec * (NICE_0_LOAD / curr->load.weight)

例如：

• nice=0（默认）：权重 1024，vruntime 增长速率 = 实际物理时间速率
• nice=5：权重约 335，vruntime 增长速率 ≈ 3×物理时间速率
• nice=-5：权重约 3121，vruntime 增长速率 ≈ 0.33×物理时间速率

因此，nice=-5 的进程在较长时间内 vruntime 可能仍最小，会持续获得优先调度。

3.2 时间记账流程

在每次时钟 tick 或上下文切换时，CFS 执行以下步骤：

1. 更新当前进程的 sum_exec_runtime
2. 根据权重计算 vruntime 增量
3. 将新 vruntime 加入红黑树
4. 检查是否需要抢占当前进程（新加入进程的 vruntime 是否小于当前进程）
5. 选择 vruntime 最小的进程进行调度

四、调度策略与抢占机制

4.1 调度策略分类

CFS 主要处理 SCHED_NORMAL 和 SCHED_BATCH 策略的普通进程。内核中还存在独立的实时调度器，负责处理 SCHED_FIFO 和 SCHED_RR 策略的实时进程。

4.2 抢占机制

CFS 支持以下几种抢占场景：

• 周期性抢占：每 tick 检查当前进程的 vruntime 是否超过红黑树最左节点一个阈值
• 唤醒抢占：新进程唤醒时，如果 vruntime 远小于当前进程（wakeup_granularity），立即抢占
• 新进程初始 vruntime：新创建的继承父进程的 vruntime（可能被重置为 cfs_rq 的最小值），避免新进程饥饿老旧进程

五、CFS 调度延迟与带宽控制

5.1 目标延迟（sched_latency）

CFS 需要在「目标延迟」内让所有可运行进程都至少运行一次：

#define sysctl_sched_latency   (6 * NSEC_PER_MSEC)  // 默认 6ms
# define sysctl_sched_min_granularity  (0.75 * NSEC_PER_MSEC) // 最小粒度 0.75ms

当可运行进程数增加时，每个进程的最小时间片会相应减小，但不能低于 min_granularity。当进程数过多时，总延迟会超过 sched_latency。

5.2 CPU 带宽控制（CFS Bandwidth Control）

CFS 支持通过 cfs_period_us 和 cfs_quota_us 来实现 CPU 带宽限制，这是 cgroup v1 中 cpu 子系统的核心参数：

# 限制进程组每 100ms 周期内最多使用 50ms CPU 时间（即 0.5 个 CPU core）
echo 50000 > /sys/fs/cgroup/cpu/mygroup/cpu.cfs_quota_us
echo 100000 > /sys/fs/cgroup/cpu/mygroup/cpu.cfs_period_us

# 启动时设置 nice 值
nice -n -5 ./my_realtime_app  // 更高优先级（需要 root）
nice -n 10 ./batch_job        // 更低优先级

// 运行时修改
renice -n -10 -p 12345

// 将进程改为 SCHED_FIFO 实时策略
struct sched_param param;
param.sched_priority = 50;
sched_setscheduler(pid, SCHED_FIFO, ¶m);

// 切换回 CFS
sched_setscheduler(pid, SCHED_NORMAL, ¶m);

# 创建 cgroup 并限制 CPU 使用率
mkdir /sys/fs/cgroup/cpu/limited
echo 50000 > /sys/fs/cgroup/cpu/limited/cpu.cfs_quota_us
echo 100000 > /sys/fs/cgroup/cpu/limited/cpu.cfs_period_us
echo $PID > /sys/fs/cgroup/cpu/limited/cgroup.procs

# 查看当前调度参数
sysctl kernel.sched_latency_ns
sysctl kernel.sched_min_granularity_ns
sysctl kernel.sched_wakeup_granularity_ns

# 实时调整
sysctl -w kernel.sched_latency_ns=10000000  # 增大到 10ms，改善吞吐
sysctl -w kernel.sched_wakeup_granularity_ns=1500000  # 减少唤醒抢占

# 查看进程的调度统计
cat /proc/$PID/sched
# 关键字段: se.vruntime, nr_switches, nr_voluntary_switches, nr_involuntary_switches

# 查看 CFS 运行队列
cat /proc/sched_debug | grep cfs_rq

# perf 分析调度延迟
perf sched record -a sleep 10
perf sched latency

# ftrace 跟踪调度事件
echo 1 > /sys/kernel/debug/tracing/events/sched/enable
cat /sys/kernel/debug/tracing/trace_pipe