Linux 内核进程调度器 CFS 深度实战：从红黑树到虚拟运行时间的完全公平

引言

进程调度是操作系统的核心职责之一，它决定了哪个进程在何时获得 CPU 时间。Linux 内核的调度器经历了多次重大演进，其中最具里程碑意义的是 2.6.23 内核引入的 CFS（Completely Fair Scheduler，完全公平调度器），它彻底取代了之前的 O(1) 调度器，成为 Linux 调度器的里程碑式设计。

CFS 的核心设计理念简单而优雅：让每个进程获得"完全公平"的 CPU 时间份额。本文将深入剖析 CFS 的实现原理、核心数据结构、调度算法细节，以及生产环境中的调优实践。

一、CFS 的设计哲学

1.1 从 O(1) 到 CFS 的演进

在 CFS 之前，Linux 使用的是 O(1) 调度器（2.6.0 - 2.6.22）。O(1) 调度器使用运行队列数组和过期队列数组来实现 O(1) 时间复杂度的调度决策，但它存在以下问题：

• 交互式进程识别困难：通过睡眠时间等启发式规则判断进程是否为交互式进程，误判率高
• 公平性不足：优先级粒度粗，难以保证严格的公平性
• 扩展性差：活跃/过期数组的设计在大规模场景下表现不佳

CFS 的设计者 Ingo Molnár 提出了一个革命性的想法：不使用传统的时间片概念，而是基于"虚拟运行时间"来实现公平调度。

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

CFS 的核心创新是引入 vruntime（virtual runtime，虚拟运行时间） 概念：

vruntime += delta_exec * (NICE_0_LOAD / weight)

其中：

• delta_exec：进程实际执行的物理时间
• NICE_0_LOAD：nice 值为 0 时的负载权重（常量 1024）
• weight：进程的权重（由 nice 值决定）

关键洞察：优先级高的进程（nice 值小，权重大），vruntime 增长更慢，因此能更频繁地被调度。当所有进程的 vruntime 相同时，系统就达到了"完全公平"。

二、核心数据结构

2.1 调度实体（sched_entity）

在 CFS 中，每个进程的调度信息通过 sched_entity 结构表示（嵌入在 task_struct 中）：

struct sched_entity {
    struct load_weight  load;       // 权重
    struct rb_node      run_node;   // 红黑树节点
    unsigned int        on_rq;      // 是否在运行队列
    
    u64                 exec_start; // 本次执行开始时间
    u64                 sum_exec_runtime; // 总执行时间
    u64                 vruntime;   // 虚拟运行时间
    u64                 prev_sum_exec_runtime; // 上次切换时的总执行时间
};

关键字段说明：

• load：进程的调度权重，决定 vruntime 的增长速率
• run_node：红黑树节点，用于将调度实体插入 CFS 运行队列
• vruntime：虚拟运行时间，CFS 调度的唯一排序依据

2.2 CFS 运行队列（cfs_rq）

每个 CPU 维护一个 CFS 运行队列：

struct cfs_rq {
    struct load_weight  load;           // 队列总权重
    unsigned long       nr_running;     // 可运行进程数
    
    u64                 min_vruntime;   // 队列中最小的 vruntime（单调递增）
    struct rb_root      tasks_timeline; // 红黑树根节点（按 vruntime 排序）
    struct rb_node      *rb_leftmost;   // 最左侧节点（vruntime 最小的进程）
    
    struct sched_entity *curr;          // 当前正在运行的实体
    struct sched_entity *next;          // 下一个要运行的实体
    struct sched_entity *last;          // 上次运行的实体
};

CFS 使用红黑树（Red-Black Tree）来组织所有可运行进程，以 vruntime 作为排序键：

• 最左侧节点（rb_leftmost）始终指向 vruntime 最小的进程，即最应该被调度的进程
• 插入和查找操作时间复杂度为 O(log N)，非常高效
• min_vruntime 用于保证新进程不会因 vruntime 过小而长期占用 CPU

2.3 进程权重与 nice 值的映射

Linux 内核通过 sched_prio_to_weight 数组将 nice 值映射到权重：

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

重要规律：nice 值每降低 1（优先级提高），权重增加约 1.25 倍。这意味着：

• nice -20 的进程获得的 CPU 时间约为 nice 19 的 88761/15 ≈ 5900 倍
• nice 值每差 1，CPU 时间差约 25%

三、CFS 调度算法详解

3.1 入队操作（enqueue_entity）

当进程变为可运行状态时，调用 enqueue_entity() 将其加入 CFS 运行队列：

static void enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
    bool renorm = !(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATED);
    bool curr = cfs_rq->curr == se;
    
    // 1. 如果是被唤醒的进程且未迁移，需要修正 vruntime
    if (renorm && curr)
        se->vruntime += cfs_rq->min_vruntime;
    
    // 2. 更新 sched_entity 的统计信息
    update_curr(cfs_rq);
    
    // 3. 累加 Account 被挂起的时间
    if (renorm && !curr)
        se->vruntime += cfs_rq->min_vruntime;
    
    // 4. 将新节点插入红黑树
    enqueue_entity_load_avg(cfs_rq, se);
    account_entity_enqueue(cfs_rq, se);
    if (flags & ENQUEUE_WAKEUP)
        place_entity(cfs_rq, se, 0);
    
    // 5. 检查是否需要抢占
    if (sched_feat(START_DEBIT) || ...)
        check_preempt_tick(cfs_rq, se);
    
    // 6. 插入红黑树
    __enqueue_entity(cfs_rq, se);
    
    // 7. 更新负载
    update_cfs_group(se);
    add_nr_running(cfs_rq, 1);
}

关键点：place_entity() 函数负责设置新唤醒进程的 vruntime，防止新进程或睡眠后唤醒的进程"作弊"。

3.2 出队操作（dequeue_entity）

当进程阻塞或被抢占时，调用 dequeue_entity() 将其从红黑树中移除：

static void dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
    // 1. 更新当前进程的统计信息
    update_curr(cfs_rq);
    
    // 2. 处理 dequeue 操作
    dequeue_entity_load_avg(cfs_rq, se);
    account_entity_dequeue(cfs_rq, se);
    
    // 3. 更新最小 vruntime
    if (!(flags & DEQUEUE_SLEEP))
        se->vruntime -= cfs_rq->min_vruntime;
    
    // 4. 从红黑树中移除
    __dequeue_entity(cfs_rq, se);
    
    // 5. 更新负载
    update_cfs_group(se);
    sub_nr_running(cfs_rq, 1);
}

注意：当进程睡眠时，vruntime 会减去 min_vruntime，这样进程被唤醒时其 vruntime 保持相对较小，能较快获得调度。

3.3 核心调度函数：pick_next_entity

CFS 选择下一个运行进程的逻辑非常简单——总是选择 vruntime 最小的进程：

static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
{
    // 直接从红黑树最左侧节点获取
    struct sched_entity *se = pick_first_entity(cfs_rq);
    
    // 使用缓存的左侧指针优化
    struct sched_entity *left = cfs_rq->rb_leftmost;
    
    // 为什么使用 left 而不是 se？考虑以下场景：
    // 如果 left 为 NULL，说明没有可运行进程
    // 如果有多个相同 vruntime 的情况，需要特殊处理
    if (left) {
        se = __pick_first_entity(&cfs_rq->tasks_timeline);
        cfs_rq->rb_leftmost = NULL;
    }
    
    return se;
}

红黑树的最左侧节点总是 vruntime 最小的节点，因此 pick_next_entity() 的时间复杂度为 O(1)（使用缓存的 rb_leftmost 指针）。

3.4 检查抢占：check_preempt_tick

CFS 不是严格意义上的"时间片"调度器，但它仍然有一个最小调度粒度（sysctl_sched_min_granularity，默认 0.75ms）和目标延迟（sysctl_sched_latency，默认 6ms）：

static void check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
    unsigned long ideal_runtime, delta_exec;
    struct sched_entity *se;
    s64 delta;
    
    // 1. 计算当前进程应获得的理想运行时间
    ideal_runtime = sched_slice(cfs_rq, curr);
    
    // 2. 获取实际运行时间
    delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
    
    // 3. 如果实际运行时间超过理想运行时间，标记为需要重新调度
    if (delta_exec > ideal_runtime) {
        resched_curr(rq_of(cfs_rq));
        return;
    }
    
    // 4. 检查是否低于最小粒度
    if (delta_exec < sysctl_sched_min_granularity)
        return;
    
    // 5. 比较当前进程和最优进程的 vruntime
    se = pick_next_entity(cfs_rq);
    delta = curr->vruntime - se->vruntime;
    
    // 6. 如果当前进程的 vruntime 不是最小的，标记抢占
    if (delta > 0)
        resched_curr(rq_of(cfs_rq));
}

                CPU 调度器 (CFS)
                      |
            +---------+---------+
            |                   |
        CGroup A            CGroup B
     +----+----+         +----+----+
     |         |         |         |
   proc1    proc2     proc3    proc4

# Docker/K8s 资源限制示例
echo 50000 > /sys/fs/cgroup/cpu/docker/xxx/cpu.cfs_quota_us  # 0.5 个 CPU
echo 100000 > /sys/fs/cgroup/cpu/docker/xxx/cpu.cfs_period_us # 100ms 周期

# 桌面/交互式场景优化
echo 4000000 > /proc/sys/kernel/sched_wakeup_granularity_ns
echo 1500000 > /proc/sys/kernel/sched_min_granularity_ns

# 高吞吐服务器优化
echo 10000000 > /proc/sys/kernel/sched_min_granularity_ns
echo 8000000 > /proc/sys/kernel/sched_latency_ns

# 将进程绑定到 CPU 2-3
taskset -c 2,3 ./my_latency_sensitive_app

# 查看进程的 CPU 亲和性
taskset -p <pid>

# 设置为 SCHED_FIFO，优先级 90（最高 99）
chrt -f 90 ./realtime_app

# 使用 SCHED_RR（时间片轮转）
chrt -r 50 ./round_robin_app

# 注意：实时优先级高于所有普通 CFS 调度进程

# 查看进程的 vruntime
cat /proc/<pid>/sched | grep vruntime

# 查看 CFS 运行队列信息
cat /proc/sched_debug | grep -A 10 "cfs_rq"

# 查看调度器统计
cat /proc/<pid>/schedstat

# 记录调度事件
perf record -e sched:sched_switch -a sleep 5

# 分析上下文切换
perf report --sort=comm

# 查看 CFS 相关的 BPF 程序
bpftool prog list | grep cfs

# 跟踪 enqueue/dequeue 操作
bpftool trace