1. CFS 调度器概述

完全公平调度器（Completely Fair Scheduler, CFS）自 Linux 2.6.23 引入以来，一直是 Linux 内核默认的 CPU 调度器。CFS 的核心目标是在所有可运行进程之间公平地分配 CPU 时间，同时保持极低的调度延迟和良好的交互性。与传统的基于时间片轮转的调度器不同，CFS 采用基于虚拟运行时间的红黑树模型，实现了 O(log n) 的调度复杂度。

1.1 设计哲学：从时间片到虚拟时间

CFS 的设计哲学可以概括为“理想的多任务处理器”模型：假设存在一个完全理想的 CPU，能够同时运行所有进程，每个进程获得 1/n 的 CPU 算力。CFS 通过虚拟运行时间（vruntime）来逼近这一理想状态。

1.2 核心数据结构：三层调度实体

CFS 的调度数据组织为三层结构，从全局到进程粒度逐层细化：

• rq（runqueue）：每个 CPU 一个，是调度器的顶级结构。包含当前运行的进程、CFS 就绪队列、实时就绪队列、停止调度器队列等。
• cfs_rq（CFS runqueue）：每个 CPU 的 CFS 就绪队列，内嵌在 rq 中。维护红黑树根节点、最小 vruntime、运行中的进程计数等。
• sched_entity（调度实体）：可被调度的基本单元。每个进程（task_struct）内嵌一个 sched_entity，记录 vruntime、权重、负载贡献等。

1.3 虚拟时钟（vruntime）概念

vruntime 是 CFS 调度器的核心度量指标，它衡量一个进程在理想 CPU 上应该获得的运行时间。实际运行时间越短的进程，其 vruntime 越小，越容易被调度器选中。

vruntime 的计算

/* kernel/sched/fair.c */
static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
    if (unlikely(se->load.weight != NICE_0_LOAD))
        delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
    return delta;
}

/* 每次时钟 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;

    delta_exec = now - curr->exec_start;
    curr->vruntime += calc_delta_fair(delta_exec, curr);
    curr->exec_start = now;
    /* 更新 min_vruntime */
    update_min_vruntime(cfs_rq);
}

vruntime 的关键特性

权重与 nice 值的映射

CFS 使用 prio_to_weight[] 数组将用户空间的 nice 值（-20 ~ 19）映射为调度权重。权重越大，vruntime 增长越慢，获得的 CPU 时间比例越高。

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

1.4 调度流程与抢占点

CFS 的调度决策发生在以下关键点：

1. 周期性调度（schedule_tick）：每个时钟中断触发，检查当前进程是否应该被抢占。
2. 进程唤醒（try_to_wake_up）：唤醒进程时检查是否可抢占当前进程。
3. 自愿调度（cond_resched）：内核抢占点，进程主动让出 CPU。
4. 新进程创建（wake_up_new_task）：新进程加入就绪队列时触发调度。

1.5 关键内核参数预览

以下 sysctl 参数直接控制 CFS 的调度行为，后续章节将逐一深入调优：