Linux CFS 完全公平调度器深度剖析：从 vruntime 到 SMP 负载均衡的完整工程实践

一、调度器设计的核心矛盾

操作系统的进程调度器需要在多个相互矛盾的目标之间取得平衡：吞吐量（尽可能多地完成作业）、响应时间（用户交互的即时反应）、公平性（每个任务获得与其权重成比例的 CPU 份额）以及能效（减少不必要的唤醒和迁移）。在 Linux 2.6.23 之前，内核采用 O(1) 调度器，通过活跃/过期数组和二叉堆实现快速任务选择，但其交互式任务识别算法复杂且容易"C Pu饥饿"问题。

2007 年，Ingo Molnár 提出的 CFS（Completely Fair Scheduler）彻底摒弃了传统的时间片轮转模型，引入了一个革命性的概念：虚拟运行时间（virtual runtime，简称 vruntime）。CFS 并不给每个任务分配固定的时间片，而是追踪每个任务已经获得的 CPU 时间，并总是选择 vruntime 最小的任务来运行。这一设计方案使得调度公平性从"近似"变成了"数学意义上的精确"。

本文将从调度器数据结构、核心算法、实时调度支持、多核负载均衡、cgroup 集成内核参数调优以及生产级观测工具六个维度，完整剖析 CFS 的实现机制。

二、核心数据结构：红黑树与 vruntime

2.1 调度实体：struct sched_entity

CFS 调度的基本单位不是 task_struct（进程描述符），而是内嵌其中的 sched_entity。这意味着无论是单个线程、多线程组还是用户组（cgroup），都可以作为调度实体参与调度。

struct sched_entity {
    struct load_weight  load;           // 权重（nice 值映射）
    struct rb_node      run_node;       // 红黑树节点
    u64                 exec_start;     // 本次开始执行的时间
    u64                 sum_exec_runtime; // 累计运行时间
    u64                 vruntime;       // 虚拟运行时间
    u64                 prev_sum_exec;  // 上一次切换时 sum_exec_runtime
    
    /* 组调度相关 */
    struct sched_entity *parent;
    struct cfs_rq       *cfs_rq;        // 所属 CFS 运行队列
    
    /* ... 组调度/带宽控制字段 ... */
};

其中 load_weight 决定了任务在相同物理时间内 vruntime 的增长速度。优先级越高（nice 值越大）的任务，其权重越大，vruntime 增长越慢，因此获得更多的实际 CPU 时间。

2.2 权重与 nice 值的映射关系

Linux 内核使用如下增量权重表映射 nice 值到权重：

static const int 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,
};

相邻 nice 级之间的权重比值约为 1.25。这意味着 nice 0 与 nice 5 的任务相比，在相同物理时间内获得的 CPU 时间比约为 1024/335 ≈ 3.06 倍。CFS 使用这种"增量乘数"而非固定步长，使得高优先级任务的增量较少但增长率更低，从而实现更平滑的优先级区分。

2.3 红黑树：CFS 运行队列的引擎

CFS 使用红黑树（Red-Black Tree）组织所有可运行任务，以 vruntime 作为排序键。这一数据结构的选择至关重要：

数据结构	查找左most	插入	删除	适用场景
红黑树（CFS 选择）	O(1) ← 缓存 leftmost	O(log n)	O(log n)	任务数多、频繁增删
二叉堆（O(1)调度器）	O(1)	O(log n)	O(log n)	优先级数组+数组翻转（复杂）
链表/数组	O(1)	O(n)	O(n)	任务数极少

CFS 的核心操作 __pick_first_entity() 直接返回 cfs_rq->rb_leftmost 缓存的节点指针，时间复杂度 O(1)。树的根节点和 leftmost 节点缓存在 struct cfs_rq 中。

2.4 vruntime 增量计算

每次时钟中断（tick）触发时，entity_tick() 会更新当前任务的 vruntime：

static void __update_curr(struct cfs_rq *cfs_rq)
{
    struct sched_entity *curr = cfs_rq->curr;
    u64 now = rq_clock_task(rq_of(cfs_rq));
    u64 delta_exec = now - curr->exec_start;  // 实际执行时间
    
    curr->exec_start = now;                    // 重置开始时间
    curr->sum_exec_runtime += delta_exec;      // 累计运行时间
    
    // 核心：vruntime = 实际运行时间 / 权重 * NICE_0_LOAD
    curr->vruntime += calc_delta_fair(delta_exec, curr);
}

calc_delta_fair() 的本质是：vruntime += delta_exec * NICE_0_LOAD / curr->load.weight。这意味着：

• 权重为 1024（nice 0）的任务：vruntime 随物理时间线性增长（1× 速度）
• 权重为 820（nice -5）的任务：vruntime 增长更快（1.25× 速度），因此更快被抢占
• 权重为 335（nice 5）的任务：vruntime 增长更慢（0.33× 速度），因此获得更多实际 CPU 时间

三、调度周期与粒度控制

3.1 目标延迟与最小粒度

CFS 引入了两个关键参数控制调度行为：

• sysctl_sched_latency（默认 6ms）：所有可运行任务跑一遍的目标延迟。每个任务在此期间至少运行一次。
• sysctl_sched_min_granularity（默认 0.75ms）：任务切换的最小时间片。防止任务数过多时切换开销过大。

每个任务的理论时间片计算公式：

time_slice = latency / nr_running        (当 task数 ≤ latency/min_granularity)
time_slice = min_granularity             (当 task数 很大时)

例如当系统中有 8 个可运行任务时，每个任务的时间片 = 6ms / 8 = 0.75ms — 刚好等于最小粒度。当只有 4 个任务时，每个任务可获得 1.5ms 的时间片。

3.2 周期性调度器：scheduler_tick()

每次系统 tick（通常 1000Hz 或 250Hz）触发时，scheduler_tick() 会调用 entity_tick()：

static void entity_tick(struct cfs_rq *cfs_rq, struct curr, int queued)
{
    // 1. 更新 vruntime 和统计
    __update_curr(cfs_rq);
    
    // 2. 更新负载/权重（PELT）
    update_load_avg(cfs_rq, curr, UPDATE_TG);
    
    // 3. 检查是否需要抢占
    if (cfs_rq->nr_running > 1)
        check_preempt_tick(cfs_rq, curr);
}

static void check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
    u64 ideal_runtime = sched_slice(cfs_rq, curr); // 本次应运行的时间
    u64 delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
    
    if (delta_exec > ideal_runtime)
        resched_curr(rq_of(cfs_rq)); // 设置 TIF_NEED_RESCHED
    else if (delta_exec < sysctl_sched_min_granularity &&
             curr->vruntime != curr->min_vruntime)
        return; // 已运行不足最小时粒度，禁止抢占
}

注意第二个条件：即使当前任务的 vruntime 已被某些任务超越，但如果它实际运行时间不足 min_granularity，则不被抢占。这正是"最小时粒度"保护机制。

四、实时调度：FIFO 与 Round-Robin

CFS 并不孤立存在，它与实时调度器共同组成 Linux 的调度体系。每个调度器属于一个调度类（sched_class），优先级从高到低依次为：

stop_sched_class    ← 最高优先级（CPU 热插拔等）
dl_sched_class      ← SCHED_DEADLINE（EDF 算法）
rt_sched_class      ← SCHED_FIFO / SCHED_RR
fair_sched_class    ← SCHED_NORMAL / SCHED_BATCH / SCHED_IDLE（CFS）
idle_sched_class   ← SCHED_IDLE 的极端情况

4.1 SCHED_FIFO 的行为

SCHED_FIFO（First-In-First-Out）任务不受 vruntime 约束，它们始终保持在高优先级队列中。sched_class 的 pick_next_task() 会先检查 rt_sched_class，再检查 fair_sched_class。因此：

• FIFO 任务总是优先于 CFS（SCHED_NORMAL）任务运行
• FIFO 任务会一直运行直到它主动让出（阻塞、sched_yield() 或 preempted）
• 低优先级 FIFO 任务会被高优先级 FIFO 任务抢占

这带来了典型的"优先级反转"风险：如果一个高优先级 FIFO 任务陷入死循环，整个系统的 CFS 任务将被完全饿死。

4.2 SCHED_RR 的行为

SCHED_RR（Round-Robin）与 SCHED_FIFO 几乎相同，唯一区别是 RR 任务有固定的时间片（sched_rr_timeslice，默认 100ms），时间片耗尽后被移到同优先级队列的末尾，轮转调度。这保证了同级别 RR 任务之间的公平性。

4.3 实时带宽限制

为避免 SCHED_FIFO/SCHED_RR 任务饿死 CFS 任务，内核提供了 sched_rt_period_us（默认 1s）和 sched_rt_runtime_us（默认 0.95s）参数。后者限制实时任务在 period 内最多占用 runtime 微秒的 CPU 时间。超过后硬性抢占，即使只是 5% 的"逃逸"窗口也足以让 CFS 任务获得基本的 CPU 时间。

五、SMP 负载均衡：多核调度

5.1 调度域与调度组

在多核 NUMA 系统中，CFS 使用调度域（sched_domain）和调度组（sched_group）组织 CPU 层级结构：

NUMA 域（最外层）
  └─  LLC 域（共享三级缓存的 CPU）
       └─  MC 域（共享物理核心的逻辑 CPU，即 SMT）
            └─  DIE 域（物理核心内）

每个域包含多个调度组（通常对应一个物理 NUMA 节点或 LLC 域内的 CPU 子集）。load_balance() 从最繁忙的组中"拉"任务到空闲组。

5.2 负载均衡触发机制

CFS 负载均衡在以下四个时机触发：

1. 周期性均衡：每个 CPU 的调度器 ticks 触发 trigger_load_balance()，通过 IPI 将非空闲 CPU 的均衡工作与其同步。
2. 空闲均衡：CPU 进入空闲状态时立即尝试从其他 CPU "拉"任务。
3. 新任务均衡：wake_up_new_task()、try_to_wake_up() 后，可能选择空闲或负载较低的 CPU 唤醒。
4. NUMA 均衡：周期性迁移任务使其靠近其内存所在的 NUMA 节点。

5.3 唤醒抢占与空闲平衡

当一个任务被唤醒时（如从 I/O 返回），CFS 必须选择一个合适的 CPU 放置它：

// wakeup 路径中的 CPU 选择逻辑
int select_task_rq_fair(struct task_struct *p, int prev_cpu, int wake_flags)
{
    // 1. 唤醒亲和性：优先选择与 prev_cpu 共享 LLC 的 CPU（快速唤醒）
    // 2. 如果 prev_cpu 繁忙，在唤醒 ecore 域内寻找空闲 CPU
    // 3. 如果全部繁忙，选择负载最低的 CPU
    // 4. 在 NUMA 体系中，考虑内存亲和性
}

对于 wake_flags & WF_SYNC（同步唤醒），如果 prev_cpu 当前空闲或即将空闲，通常直接复用 prev_cpu，避免 Cache Line 迁移开销。对于 wake_flags & WF_TTWU（异步唤醒），则在整个调度域内选择负载最轻的 CPU。

5.4 负载度量：PELT 与 WALT

CFS 使用PELT（Per-Entity Load Tracking）算法追踪每个调度实体的负载贡献：

// PLT 衰减公式（32 个周期 ≈ 半衰期衰减）
load_avg = load_avg * y + load * (1 - y)    // y = 0.978572
util_avg = util_avg * y + running * (1 - y)

PELT 的设计兼顾短期峰值（running=1 时贡献即为 load）和长期趋势（指数衰减）。Android/GKI 内核中可选的 WALT（Windowed Assisted Load Tracking）更适合突发负载的响应，但它与 CFS 的公平性假设存在一定冲突。

六、cgroup 集成：cpu 控制器

6.1 cpu.shares：权重分配

cgroup v1 的 cpu.shares 直接影响该 cgroup 对应的 cfs_bandwidth->shares。当多个 cgroup 竞争 CPU 时，CFS 通过嵌套的 sched_entity 层级实现组间公平：

概念示例：
cgroup A (shares=1024) ← 包含 cgroups A1(share=1), A2(share=1)
cgroup B (shares=1024) ← 包含 cgroups B1(share=1), B2(share=1)

层级关系：
Root cgroup
 ├─ A (50% CPU)
 │   ├─ A1 (75% × 50% = 37.5%)
 │   └─ A2 (25% × 50% = 12.5%)
 └─ B (50% CPU)
     ├─ B1 (75% × 50% = 37.5%)
     └─ B2 (25% × 50% = 12.5%)

这种层级传播使得组内和组间的公平性都得到保证。

6.2 cpu.cfs_quota_us / cpu.cfs_period_us：带宽限制

对于带宽控制（hard cap），cgroup 提供 quota/period 比值限制每个周期内 cgroup 可使用的 CPU 总时间：

• period：默认 100ms
• quota：-1 表示无限制
• quota = 50000（50ms）→ 该 cgroup 最多使用 50% CPU（即使有空闲也不超）

跨周期的剩余时间不累积（与 CFQ I/O 调度器不同）。这保证了 cgroup 突发流量不会损害其他 cgroup 的公平性。

七、高效调度核心：SCHED_IDLE 与 SCHED_BATCH

7.1 SCHED_IDLE 的设计与实现

SCHED_IDLE 是 CFS 为实现极低优先级任务而引入的策略，其关键在于权重极小，而非独立队列：

// SCHED_IDLE 的权重 = 3（正常 NICE_0 为 1024 的极低比例）
static const int prio_to_wmult[41] = {
    /* nice +19（即 SCHED_IDLE 近似）的极端值 */
};

SCHED_IDLE 任务的 vruntime 增长速度极快（约为 NICE_0 的 341×）。因此它只在完全没有其他可运行任务时才会被选中。一旦有 NORMAL 任务加入，IDLE 任务立即被抢占。

这种设计比传统的 SCHED_BATCH 更严格——BATCH 任务只是"批量处理"倾向，而 IDLE 任务 essentially 会退让一切。

7.2 抢占延迟与 min_granularity_vsqlatency_ns

某些场景下（如桌面交互），即使目标延迟为 6ms，也需要确保交互式延迟的边界。sysctl_sched_wakeup_granularity（默认 1ms）控制唤醒抢占阈值：

// 是否允许刚唤醒的任务抢占当前任务？
static int wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
{
    u64 gran = sysctl_sched_wakeup_granularity;
    u64 vdiff = curr->vruntime - se->vruntime;
    
    if (vdiff <= gran)  // 差异不够大，不抢占
        return -1;
    
    return 1; // 允许抢占
}

这一机制防止了"过多抢占"问题——如果唤醒任务只比当前任务小一点点 vruntime 就抢占，会频繁切换，严重损害 Cache 局部性。wakeup_granularity 充当了"迟滞"参数。

八、生产级观测与调优

8.1 调度器统计文件

Linux 提供了丰富的 sched 相关 /proc 与 debugfs 文件：

文件路径	信息内容
/proc/<pid>/schedstat	vruntime、sum_exec_runtime、等待时间、调度次数
/proc/<pid>/stat	stime、utime、num_threads 等
/proc/sched_debug	每 CPU 运行队列详情、负载均衡状态
/sys/kernel/debug/sched/	PELT 负载图、能量模型、NUMA 均衡

8.2 perf sched 记录与分析

Linux perf 工具提供 perf sched record / perf sched latency / perf sched map / perf sched script 命令族，用于采集和分析调度事件：

# 采样调度器决策树
$ perf sched record -- sleep 10

# 输出每个任务的调度延迟分布
$ perf sched latency --sort max
  Task                  |   Runtime ms | Switches | Average delay ms | Maximum delay ms |
-----------------------------------------------------------------------------------------
  Xorg                  |     180.345 |     1234 |            3.214 |           45.678 |
  gnome-shell          |     234.567 |     2345 |            2.891 |           38.123 |
  chrome (1234)        |    1234.567 |     5678 |            1.234 |           25.456 |

# 可视化 CPU 时间轴
$ perf sched map

"Maximum delay ms" 追踪的是从任务变为可运行到实际获得 CPU 的时间，是衡量调度响应性的关键指标。

8.3 常见调优参数

内核参数	默认值	说明	调优建议
sched_latency_ns	6,000,000 ns	目标延迟	桌面交互场景可降至 3-4ms
sched_min_granularity_ns	750,000 ns	最小时间片	HPC 可增加到 4ms
sched_wakeup_granularity_ns	1,000,000 ns	唤醒抢占阈值	低延迟场景设为 0.5ms
sched_migration_cost_ns	500,000 ns	迁移成本判断	NUMA 场景增大使任务"粘"在本地
sched_dline_period_us	1,000,000 us	DEADLINE 周期	实时任务根据 Deadline 设置

九、调度器演进：EEVDF 与 CFS 的未来

Linux 6.6 引入了 EEVDF（Earliest Eligible Virtual Deadline First）调度器作为 CFS 的继任者候选。EEVDF 的核心改进在于：

• Lag 消除：传统 CFS 在任务睡眠后唤醒时，由于 vruntime 滞后过多，会导致"虚拟时间债务"EEVDF 引入 eligible 标志严格限制"补偿"范围。
• 平滑抢占：CFS 的 tick 抢占比较粗暴（超出时间片就 EEVDF 通过 deadline 字段提前预判下一次抢占点。
• 延迟边界确定性：EEVDF 给出数学上更紧密的最大延迟上界，更适合实时混合负载。

尽管 EEVDF 在理论上更优，但 CFS 凭借近 20 年的生产验证和极致的内核兼容性，短期内两者将长期共存。了解 CFS 的工程原理，仍是理解 Linux 调度的基石。

十、总结

CFS 的设计哲学——"模拟一个理想多核 CPU"——将复杂的调度公平性问题转化为简洁的 vruntime 比较问题。其关键架构决策包括：

1. 红黑树 + vruntime：O(1) 选择最应运行任务，O(log n) 增删，完美适配存在大量任务的生产环境
2. 权重驱动的时间分配：通过指数间隔的增量乘数，将 nice 值映射为精确的时间比例
3. 层级调度域：从单核到多核到 NUMA，通过递归的 load_balance() 跨级传递负载信息
4. PELT 负载追踪：指数衰减的滑动窗口均值，兼顾短期突发与长期趋势
5. cgroup 带宽控制：通过 quota/period 实现精确的资源隔离（如容器 CPU 限额）
6. 实时与公平的共存：sched_class 优先级分层，FIFO/RR 优先于 NORMAL，但受runtime_us 硬性约束

理解 CFS，不仅需要掌握其数据结构（sched_entity/cfs_rq/task_group），更需要理解其背后的设计哲学——公平性是调度器唯一需要维护的属性，其他一切（吞吐量、延迟、响应性）都是公平的推论。这也是 Ingo Molnár 留给 Linux 社区最深刻的洞察。