2. CFS调度器基础：完全公平调度算法原理、红黑树数据结构、虚拟运行时间(vruntime)计算
2.1 完全公平调度算法原理
完全公平调度（Completely Fair Scheduler, CFS）是 Linux 内核自 2.6.23 版本引入的默认调度器，其设计哲学颠覆了传统基于时间片轮转的调度模型。CFS 的核心思想是：为每个可运行进程分配 CPU 时间的“公平份额”，而非固定时间片。它通过一个理想化的“精确多任务 CPU”模型，模拟所有进程同时以无限小的时间粒度并行运行。
CFS 调度周期（也称为“调度延迟”）是一个关键参数，它决定了所有可运行进程至少被调度一次的时间间隔。默认值为 6ms，但会根据可运行进程数量动态调整，以确保调度延迟不会过长。
| 传统调度器（O(1)） | CFS 调度器 |
|---|---|
| 基于固定时间片 | 基于虚拟运行时间（vruntime） |
| 优先级通过时间片长度体现 | 优先级通过 vruntime 增长速率体现 |
| 使用多级反馈队列 | 使用红黑树（rbtree） |
| 调度复杂度 O(1) | 调度复杂度 O(log N) |
| 需要处理时间片耗尽、重新计算 | 无需时间片概念，持续运行直到被抢占 |
2.2 红黑树数据结构
CFS 使用红黑树（Red-Black Tree）作为可运行进程队列的核心数据结构。红黑树是一种自平衡二叉查找树，其关键特性保证了 CFS 的调度效率：
- 自平衡性： 插入和删除操作后，树的高度始终保持在 O(log N)，确保调度延迟可控。
- 有序性： 所有节点按照 vruntime 值排序，最左侧节点始终是 vruntime 最小的进程。
- O(log N) 复杂度： 每次调度决策（选择下一个运行进程）只需取最左节点，复杂度为 O(1)；插入和删除操作复杂度为 O(log N)。
红黑树在 CFS 中的具体实现位于 kernel/sched/fair.c 文件中，核心数据结构为 struct cfs_rq，其中包含红黑树的根节点 rb_root 和缓存的最左节点指针 rb_leftmost。
/* kernel/sched/fair.c - CFS 运行队列结构 */
struct cfs_rq {
struct load_weight load; /* 运行队列的总负载 */
unsigned int nr_running; /* 可运行进程数量 */
unsigned int h_nr_running; /* 包括子 cgroup 的进程数 */
u64 min_vruntime; /* 队列最小虚拟运行时间 */
struct rb_root_cached tasks_timeline; /* 红黑树根节点 + 最左节点缓存 */
struct sched_entity *curr; /* 当前正在运行的调度实体 */
struct sched_entity *next; /* 下一个要运行的调度实体 */
struct sched_entity *last; /* 上一个运行的调度实体 */
/* ... 其他字段 */
};2.3 虚拟运行时间（vruntime）计算
虚拟运行时间（vruntime）是 CFS 调度器的核心度量指标。它不是一个真实的物理时间，而是经过进程优先级（nice 值）加权后的“标准化运行时间”。CFS 通过 vruntime 实现了“权重感知”的公平调度。
2.3.1 vruntime 计算公式
vruntime 的更新发生在每次时钟中断（tick）和进程状态切换时。其核心计算公式如下：
/* vruntime 增量计算 */
delta_exec = 当前进程实际运行的物理时间（ns）
vruntime += delta_exec * (NICE_0_LOAD / se->load.weight)
其中：
- NICE_0_LOAD = 1024（nice 值为 0 时的权重）
- se->load.weight = 进程的实际权重（由 nice 值映射而来）从公式可以看出：
- 高优先级进程（nice 值小，权重大）： 分母大，vruntime 增长慢，因此更容易被调度器选中。
- 低优先级进程（nice 值大，权重小）： 分母小，vruntime 增长快，因此运行时间更短。
| nice 值 | 权重（weight） | vruntime 增长速率（相对 nice=0） | 典型应用场景 |
|---|---|---|---|
| -20 | 88761 | 0.0115x（极慢） | 实时音频处理 |
| -10 | 11051 | 0.0927x（慢） | 交互式应用 |
| 0 | 1024 | 1.0x（基准） | 普通进程 |
| 10 | 304 | 3.368x（快） | 后台批处理 |
| 19 | 15 | 68.267x（极快） | 空闲任务 |
2.3.2 min_vruntime 与虚拟时间归一化
CFS 运行队列维护一个 min_vruntime 字段，它表示队列中所有进程 vruntime 的最小值。当新进程加入或进程被唤醒时，其初始 vruntime 会被设置为 min_vruntime，以防止新进程获得不公平的 CPU 时间优势。
min_vruntime。如果直接恢复运行，该进程会“饿死”其他进程。CFS 通过 place_entity() 函数对唤醒进程的 vruntime 进行补偿，将其设置为 min_vruntime - 调度延迟/2 左右，既保证其获得一定补偿，又不至于过度抢占。
2.3.3 vruntime 更新路径
vruntime 的更新发生在以下关键路径中：
- 周期性调度（scheduler_tick）： 每次时钟中断（通常 1ms 或 4ms）触发，更新当前进程的 vruntime。
- 进程唤醒（try_to_wake_up）： 进程从睡眠状态被唤醒时，重新计算其 vruntime。
- 进程创建（wake_up_new_task）： 新创建的进程首次加入运行队列时。
- 上下文切换（context_switch）： 进程切换时，更新被切换出去进程的 vruntime。
/* kernel/sched/fair.c - 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;
if (unlikely(!curr))
return;
/* 计算自上次更新以来的实际运行时间 */
delta_exec = now - curr->exec_start;
if (unlikely((s64)delta_exec <= 0))
return;
curr->exec_start = now;
/* 核心：根据权重缩放 vruntime */
curr->vruntime += calc_delta_fair(delta_exec, curr);
/* 更新 min_vruntime */
update_min_vruntime(cfs_rq);
}
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;
}2.4 调度延迟与 vruntime 的交互
调度延迟（sched_latency）是 CFS 中一个关键的系统参数，它直接影响了 vruntime 的更新和进程的抢占行为。CFS 通过以下机制将调度延迟与 vruntime 关联起来：
- 目标延迟（targeted_latency）： 默认值为 6ms，表示所有可运行进程在一个调度周期内至少被调度一次的时间目标。
- 最小粒度（min_granularity）： 默认值为 0.75ms，防止进程切换过于频繁导致上下文切换开销过大。
- 抢占阈值： 当当前进程的 vruntime 与红黑树最左节点的 vruntime 差值超过
thresh（通常为调度延迟/2）时，触发抢占。