3. CFS设计哲学：完全公平调度的核心思想

完全公平调度器（CFS，Completely Fair Scheduler）是Linux内核自2.6.23版本引入的默认调度类，其设计哲学彻底颠覆了传统基于时间片和优先级队列的调度模型。CFS的核心目标是在真实硬件（有限CPU核心）上，为每个可运行进程模拟出“理想、精确的多任务处理器”——即每个进程都能获得完全相等的CPU时间份额。

3.1 从“时间片”到“权重比例”的范式转变

传统O(1)调度器为每个优先级分配固定时间片，进程在时间片耗尽后被迫让出CPU。CFS摒弃了这种刚性分配，转而采用基于权重（weight）的比例分配模型。每个进程的优先级（nice值）被映射为一个权重值，权重越高，进程在单位时间内获得的CPU运行比例越大。

3.2 虚拟运行时间（vruntime）概念

vruntime是CFS调度器的核心度量指标，它记录了进程在理想多任务处理器上应该获得的运行时间。每次时钟中断或进程状态切换时，内核会更新当前运行进程的vruntime。vruntime的计算公式如下：

/* 简化后的vruntime更新逻辑 */
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->vruntime += calc_delta_fair(delta_exec, curr);
    curr->exec_start = now;
}

/* 虚拟运行时间增量计算 */
static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se) {
    /* NICE_0_LOAD 是nice=0时的权重（1024） */
    if (unlikely(se->load.weight != NICE_0_LOAD))
        /* vruntime增量 = 实际时间 * (NICE_0_LOAD / se->load.weight) */
        delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
    return delta;
}

从公式可以看出：

• nice=0的进程：权重为1024（NICE_0_LOAD），vruntime增量等于实际运行时间。
• 高优先级进程（nice=-20）：权重高达88761，vruntime增量仅为实际时间的约1.15%（1024/88761），增长极慢。
• 低优先级进程（nice=19）：权重仅为15，vruntime增量是实际时间的约68倍（1024/15），增长极快。

3.3 nice值与权重映射表

Linux内核维护了一个全局的权重数组，将每个nice值（-20到19）映射到一个具体的权重值。这个映射关系是CFS实现优先级差异的基础。

内核源码中对应的权重数组定义如下：

/* kernel/sched/core.c */
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,
};

3.4 红黑树数据结构：高效查找最小vruntime

CFS使用红黑树（Red-Black Tree）来组织同一调度实体组（cfs_rq）中的所有可运行进程。红黑树是一种自平衡二叉查找树，其核心特性保证了调度操作的高效性：

• 查找最小节点：红黑树的最左叶子节点即为vruntime最小的进程，时间复杂度为O(log N)。
• 插入新进程：进程被唤醒或创建时，按vruntime值插入红黑树，时间复杂度O(log N)。
• 删除进程：进程进入睡眠或退出时，从红黑树中删除，时间复杂度O(log N)。
• 自平衡：红黑树通过旋转和着色操作保持近似平衡，避免退化为链表。

3.5 CFS调度周期的完整流程

一个完整的CFS调度周期包含以下关键步骤，这些步骤在每个调度点（时钟中断、进程主动让出CPU、唤醒等）都会被执行：

1. 更新当前进程vruntime：调用update_curr()，根据当前进程的实际运行时间和权重，计算并累加vruntime。
2. 检查是否需要抢占：如果当前进程的vruntime超过了红黑树中最左叶子节点的vruntime，则设置TIF_NEED_RESCHED标志。
3. 选择下一个进程：在调度点（如时钟中断返回时），调用pick_next_task_fair()，从红黑树中取出vruntime最小的进程。
4. 上下文切换：保存当前进程的寄存器状态，恢复新进程的寄存器状态，完成CPU执行流的切换。
5. 新进程开始运行：新进程从上次被切换出去的位置继续执行，同时内核开始记录其exec_start时间戳。

3.6 调度延迟与最小粒度

CFS引入了两个关键参数来控制调度行为，防止进程切换过于频繁或过于稀疏：

当可运行进程数量增多时，CFS会动态调整每个进程的时间片：

/* 计算每个进程的时间片 */
static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se) {
    u64 slice = __sched_period(cfs_rq->nr_running);
    /* 时间片 = 调度延迟 * (进程权重 / 总权重) */
    do_div(slice, cfs_rq->load.weight);
    return slice * se->load.weight;
}

/* 调度周期 = max(调度延迟, 最小粒度 * 进程数) */
static u64 __sched_period(unsigned long nr_running) {
    if (unlikely(nr_running > sched_nr_latency))
        return nr_running * sysctl_sched_min_granularity;
    else
        return sysctl_sched_latency;
}

3.7 CFS调度器的整体架构

下图展示了CFS调度器在内核中的整体架构和核心组件之间的关系：