Linux 内核 CFS 完全公平调度器：从理论到实战

引言

进程调度是操作系统的核心职责之一，它决定了哪个进程在何时获得 CPU 时间。Linux 内核自 2.6.23 版本起引入了完全公平调度器（Completely Fair Scheduler, CFS），取代了之前的 O(1) 调度器。CFS 的设计理念堪称优雅：它不使用时间片，而是通过"虚拟运行时间"的概念，让所有任务公平地分享 CPU。

本文将深入剖析 CFS 的实现原理，包括红黑树数据结构、vruntime 计算、调度延迟控制，以及实际调优案例。

1. CFS 的设计哲学

1.1 "完全公平"的含义

CFS 的核心思想很简单：如果系统中有 N 个可运行进程，那么每个进程都应该获得 1/N 的 CPU 时间。CFS 不采用传统的时间片轮转方式，而是通过以下机制实现公平：

• 虚拟运行时间（vruntime）：每个进程维护一个虚拟运行时间计数器，表示该进程在"理想"多核系统上已经运行的时间。
• 红黑树（rbtree）：所有可运行进程按照 vruntime 值存储在红黑树中，vruntime 最小的进程位于最左侧，下次被调度。
• 无时间片：CFS 不再分配固定时间片，而是动态计算每个进程的运行时长。

1.2 理想多核模型

CFS 假设存在一个"理想多核处理器"：如果有 N 个进程，那么每个进程可以同时运行在单独的 CPU 上获得 100% 的 CPU 时间。现实的单核/多核系统无法做到这一点，所以 CFS 通过 vruntime 来近似模拟这个理想模型。

2. 核心数据结构

2.1 task_struct 中的调度相关字段

struct task_struct {
    ...
    struct sched_entity se;        // 调度实体（每个任务或每个CPU运行队列中的一个实体）
    struct sched_rt_entity rt;      // 实时调度实体
    const struct sched_class *sched_class;  // 调度类
    unsigned int policy;           // 调度策略（SCHED_NORMAL, SCHED_FIFO, SCHED_RR等）
    int prio, static_prio, normal_prio;  // 优先级相关
    unsigned int rt_priority;      // 实时优先级
    cpumask_t cpus_allowed;        // 允许运行的CPU掩码
    ...
};

2.2 sched_entity：调度实体

CFS 不直接操作 task_struct，而是通过 sched_entity 进行调度。这使得 CFS 可以调度"组"（cgroup）：

struct sched_entity {
    struct load_weight load;       // 权重（由优先级决定）
    struct run_node run_node;      // 红黑树节点
    struct cfs_rq *cfs_rq;         // 所属的CFS运行队列
    u64 exec_start;                // 本次开始执行的时间
    u64 vruntime;                  // 虚拟运行时间（核心字段）
    u64 sum_exec_runtime;          // 总实际运行时间
    u64 prev_sum_exec_runtime;     // 上一次的总运行时间（用于计算移出CPU时的时间差）
    ...
};

2.3 cfs_rq：CFS 运行队列

每个 CPU 都有一个 cfs_rq，维护该 CPU 上所有 CFS 调度的任务：

struct cfs_rq {
    struct load_weight load;       // 运行队列总权重
    unsigned long runnable_weight; // 可运行任务总权重
    unsigned int nr_running;       // 可运行任务数量
    
    u64 min_vruntime;             // 运行队列中最小的vruntime（用于归一化）
    u64 exec_clock;               // 执行时钟
    
    struct rb_root_cached tasks_timeline;  // 红黑树根节点（按vruntime排序）
    struct sched_entity *curr;     // 当前正在运行的调度实体
    struct sched_entity *next;     // 下一个要运行的（用于抢占优化）
    struct sched_entity *last;     // 上一个运行的（用于上下文切换优化）
    ...
};

3. vruntime 计算详解

3.1 核心公式

vruntime 的计算是 CFS 最核心的部分：

// 简化版 vruntime 计算
delta_exec = now - exec_start;           // 实际运行时间（纳秒）
delta_exec_weighted = delta_exec * NICE_0_LOAD / load->weight;  // 加权后的时间
se->vruntime  = delta_exec_weighted;     // 更新虚拟运行时间

其中：

• delta_exec：进程实际运行的时间
• NICE_0_LOAD：nice 0 的权重（1024）
• load->weight：当前进程的权重

3.2 优先级与权重的关系

Linux 中 nice 值范围是 -20 到 19，对应优先级 100 到 139。每个 nice 级别对应的权重存储在 sched_prio_to_weight 数组中：

// kernel/sched/core.c 中的权重表
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 值（增加优先级），CPU 时间增加约 10%。例如：

• nice 0（权重1024）与 nice 1（权重820）：nice 0 获得约 1024/(1024 820) ≈ 55.5% 的 CPU，nice 1 获得约 44.5%
• nice -1（权重1277）与 nice 0（权重1024）：nice -1 获得约 55.6%

3.3 新进程的 vruntime 处理

新创建的进程 vruntime 初始值为 0，如果直接放入红黑树，它将永远在树的最左侧，老进程会"饿死"。CFS 的解决方案是：

// 新进程的 vruntime 初始化为运行队列的 min_vruntime
// 这保证了新进程不会立即抢占老进程，而是获得"追赶"的机会
se->vruntime = cfs_rq->min_vruntime;但这也带来一个问题：如果进程休眠很久，它的 vruntime 可能远小于 min_vruntime，醒来后会获得大量 CPU 时间。CFS 对此的处理是：



// 当进程从睡眠中醒来，如果 vruntime 比 min_vruntime 小太多
// 可能会设置一个阈值限制
if (vruntime < (vruntime - sysctl_sched_latency)) {
    // 防止过度补偿
}

4. 调度时机与上下文切换

4.1 调度时机

CFS 在以下情况下触发调度：


主动调度：进程调用 schedule() 主动让出 CPU（阻塞在 I/O、互斥锁等）
抢占调度：时钟中断检查是否需要抢占（TICK_NSEC 间隔）
唤醒抢占：新进程唤醒时，如果 vruntime 远小于当前进程，可能立即抢占


4.2 __schedule() 核心流程


static void __sched notrace __schedule(bool preempt) {
    struct task_struct *prev, *next;
    struct rq *rq;
    
    // 1. 获取当前运行队列
    rq = cpu_rq(cpu);
    
    // 2. 更新当前运行进程的 vruntime
    update_curr(rq);
    
    // 3. 从红黑树中选择下一个要运行的进程（最左侧节点）
    next = pick_next_task(rq, prev, rf);
    
    // 4. 如果下一个进程与当前不同，执行上下文切换
    if (likely(prev != next)) {
        rq->nr_switches  ;
        rq->curr = next;
          *switch_count;
        
        // 执行上下文切换
        context_switch(rq, prev, next);
    }
}

5. 组调度（CGroup）支持

CFS 的一个重要特性是支持组调度（CONFIG_FAIR_GROUP_SCHED）。这使得我们可以按用户、按组或按容器分配 CPU 资源：

5.1 层级化调度

CFS 的调度实体可以"嵌套"：


struct cfs_rq {
    struct sched_entity *curr;      // 当前运行的调度实体
    ...
};

// 每个调度实体既可以代表一个进程，也可以代表一个组（cgroup）
struct sched_entity {
    struct cfs_rq *cfs_rq;         // 如果是组，指向组的运行队列
    struct cfs_rq *my_q;           // 如果是进程组，指向自己的运行队列
    ...
};

5.2 实际应用场景


容器资源限制：Docker/K8s 通过 cgroup 限制容器的 CPU 使用
多用户系统：按用户组分配 CPU 资源
服务质量（QoS）：不同服务级别保证不同的 CPU 份额


CFS 调优实践

1. 调度延迟参数


参数
默认值
说明
sched_latency
6ms
调度周期，所有可运行进程至少运行一次的时间
sched_min_granularity
0.75ms
最小运行时间粒度，防止过度切换
sched_wakeup_granularity
1ms
唤醒抢占的粒度控制



# 查看 / 修改调度参数
cat /proc/sys/kernel/sched_latency_ns
cat /proc/sys/kernel/sched_min_granularity_ns
cat /proc/sys/kernel/sched_wakeup_granularity_ns

# 修改示例
echo 10000000 > /proc/sys/kernel/sched_latency_ns  # 10ms

2. CPU 亲和性设置


// 设置进程 CPU 亲和性
cpu_set_t cpuset;
CPU_ZERO(