📚 课程目录第3章 CFS调度器核心原理

3. CFS调度器核心原理：虚拟运行时间、红黑树、nice值权重映射

完全公平调度器（CFS，Completely Fair Scheduler）是Linux内核中用于普通任务（SCHED_NORMAL/SCHED_OTHER）的默认调度器。其设计哲学是：在理想的多处理器系统中，每个任务应获得相等的CPU时间片。CFS通过虚拟运行时间（vruntime）、红黑树（Red-Black Tree）和nice值权重映射三个核心机制，在O(log n)时间复杂度内实现精确的公平调度。

3.1 虚拟运行时间（vruntime）

vruntime是CFS调度器的核心度量指标，它表示一个任务在理想公平CPU下应获得的运行时间。实际运行时间越短的任务，其vruntime增长越慢，在红黑树中的位置越靠左，越容易被调度器选中。

  关键公式：

  vruntime += (实际运行时间 × NICE_0_LOAD) / 任务的权重(weight)

其中NICE_0_LOAD是nice值为0时的基准权重（1024）。当任务实际运行了t个时钟周期后，其vruntime增加量为：

delta_exec = 实际运行时间（单位：ns）
delta_vruntime = (delta_exec * NICE_0_LOAD) / se->load.weight

这意味着：

高优先级任务（nice值小，权重大）：分母大，vruntime增长慢，在红黑树中偏左，更容易被调度。
低优先级任务（nice值大，权重小）：分母小，vruntime增长快，在红黑树中偏右，不容易被调度。

理解要点：vruntime不是物理时间，而是经过权重调整后的“虚拟时间”。CFS总是选择vruntime最小的任务运行，从而保证所有任务在虚拟时间维度上“公平”。

3.2 红黑树：CFS的就绪队列结构

CFS使用红黑树（rbtree）来组织所有可运行（runnable）的普通任务。红黑树是一种自平衡二叉搜索树，其核心特性保证了调度操作的高效性：

红黑树特性	对CFS的意义
自平衡（O(log n)插入/删除）	任务创建、唤醒、睡眠时快速更新就绪队列
中序遍历有序	最左节点即为vruntime最小的任务，O(1)获取
节点颜色约束（红/黑）	保证树高不超过2log(n+1)，避免退化
键值为vruntime	直接按虚拟运行时间排序，天然公平

在Linux内核中，每个CPU都有一个独立的CFS运行队列（struct cfs_rq），其中包含红黑树的根节点tasks_timeline：

// 内核源码：kernel/sched/sched.h
struct cfs_rq {
    struct load_weight  load;           // 该队列的总权重
    unsigned long       nr_running;     // 可运行任务数
    u64                 min_vruntime;   // 队列最小vruntime
    struct rb_root_cached tasks_timeline; // 红黑树根节点（含缓存）
    struct sched_entity *curr;          // 当前正在运行的任务
    struct sched_entity *next;          // 下一个被选中的任务（缓存）
    // ... 其他字段
};

性能关键点：CFS使用rb_root_cached结构，它缓存了红黑树的最左节点。这样，调度器在每次需要选择下一个任务时，不需要遍历整棵树，而是直接获取缓存的最左节点，时间复杂度为O(1)。只有在缓存失效（如最左节点被删除）时才需要O(log n)重新查找。

3.3 nice值权重映射表

nice值范围是[-20, 19]，共40个优先级。CFS将每个nice值映射到一个权重（weight），权重决定了任务在CPU时间分配中的比例。权重映射表定义在kernel/sched/core.c中：

// 内核源码：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,
};

权重映射的核心规律：

nice值每增加1，任务获得的CPU时间减少约10%（精确值为1.25的倒数）。
nice值相差10（如nice=0 vs nice=10），权重比约为1024:110 ≈ 9.3:1，即高优先级任务可获得近10倍的CPU时间。
nice值相差20（如nice=-20 vs nice=19），权重比约为88761:15 ≈ 5917:1，极端情况下优先级差距巨大。

nice值	权重	相对nice=0的CPU占比	典型场景
-20	88761	约86.7倍	系统关键守护进程
-10	9548	约9.3倍	音频/低延迟应用
-5	3121	约3.0倍	交互式应用
0	1024	1.0倍（基准）	普通用户进程
5	335	约0.33倍	后台批处理任务
10	110	约0.11倍	低优先级后台任务
19	15	约0.015倍	空闲任务（idle）

  权重映射的数学原理：CFS使用近似公式 weight = 1024 / (1.25 ^ nice) 来计算权重。当nice=0时，weight=1024；nice每增加1，权重除以1.25（约0.8倍）；nice每减少1，权重乘以1.25。这种指数映射保证了nice值在数值上线性变化时，CPU分配比例呈几何级数变化，使得调度策略在宽优先级范围内保持平滑。

3.4 调度决策流程：三者如何协作

CFS的调度决策是一个连续循环过程，虚拟运行时间、红黑树和nice值权重映射三者紧密协作：

任务创建/唤醒：根据任务的nice值查表获得权重，初始化vruntime（通常设置为当前队列的min_vruntime），插入红黑树。
调度点触发：时钟中断、任务睡眠、任务唤醒、系统调用返回等场景触发调度。
选择下一个任务：从红黑树缓存中获取最左节点（vruntime最小），设为next任务。
上下文切换：保存当前任务状态，恢复next任务状态，开始运行。
运行时更新：每次时钟中断（通常1ms或4ms）更新当前任务的vruntime：vruntime += delta_exec * NICE_0_LOAD / weight。
重新入队：如果当前任务vruntime增长后不再是树中最左节点，将其从红黑树中删除，更新vruntime后重新插入（保持树平衡）。
循环：回到步骤2，等待下一个调度点。

3.5 关键数据结构关系

CFS调度器的核心数据结构层次关系如下：

数据结构	作用	关键字段
`struct task_struct`	进程描述符（每个任务一个）	`se` (sched_entity), `prio`, `static_prio`, `normal_prio`
`struct sched_entity`	调度实体（嵌入task_struct）	`vruntime`, `load.weight`, `run_node` (rb_node), `on_rq`
`struct cfs_rq`	CFS运行队列（每CPU一个）	`tasks_timeline` (rb_root_cached), `min_vruntime`, `nr_running`, `load`
`struct rb_root_cached`	红黑树根（含最左缓存）	`rb_root`, `rb_leftmost`
`struct load_weight`	权重信息	`weight` (实际权重值), `inv_weight` (用于快速除法)

性能优化技巧：内核在load_weight中保存了inv_weight（权重的倒数，以定点数表示），这样在计算vruntime时可以将除法转换为乘法，避免昂贵的除法指令。公式变为：delta_vruntime = (delta_exec * NICE_0_LOAD * inv_weight) >> shift。

3.6 总结：CFS核心机制一览

机制	核心思想	时间复杂度	关键代码路径
虚拟运行时间	将物理时间按权重缩放，实现公平度量	O(1)更新	`update_curr()`
红黑树	按vruntime排序，自平衡二叉搜索树	O(log n)插入/删除，O(1)取最左	`enqueue_task_fair()`, `dequeue_task_fair()`
nice值权重映射	nice值→权重→CPU分配比例	O(1)查表	`sched_prio_to_weight[]`
调度决策	选择vruntime最小的任务运行	O(1)（缓存命中）	`pick_next_task_fair()`

CFS通过这三个核心机制的协同工作，在O(log n)时间内完成了从任务创建到调度决策的全流程，同时保证了调度的公平性和实时性。理解vruntime、红黑树和权重映射是掌握CFS调度器的关键，也是后续学习CFS与RT调度协作的基础。