3. 完全公平调度器(CFS)核心原理：红黑树、虚拟运行时间(vruntime)、权重与优先级
完全公平调度器（Completely Fair Scheduler, CFS）是 Linux 内核自 2.6.23 版本引入的默认调度器，旨在为每个进程提供“完全公平”的 CPU 时间分配。CFS 摒弃了传统的时间片轮转模型，转而采用基于虚拟运行时间（vruntime）的数学模型，通过红黑树数据结构高效管理就绪队列，并利用权重机制将进程优先级映射为实际的时间分配比例。
3.1 虚拟运行时间（vruntime）
vruntime 是 CFS 调度器的核心度量指标。它表示一个进程在理想、完全公平的多任务系统下应该已经运行的时间。实际运行时间通过进程的权重进行加权，从而得到 vruntime。
vruntime 的计算公式：
vruntime = 实际运行时间 × (NICE_0_LOAD / 进程权重)其中 NICE_0_LOAD 是 nice 值为 0 时的标准权重（1024）。权重越大的进程（优先级越高），其 vruntime 增长越慢；权重越小的进程（优先级越低），其 vruntime 增长越快。CFS 总是选择 vruntime 最小的进程来运行，从而保证所有进程的 vruntime 尽可能接近。
- 单调递增：vruntime 随时间单调递增，不会回退。
- 权重敏感：高优先级进程的 vruntime 增长慢，因此更容易被选中。
- 睡眠补偿：进程睡眠时 vruntime 保持不变，唤醒后其 vruntime 相对较小，从而获得优先运行权（交互式进程优化）。
3.2 红黑树：就绪队列的数据结构
CFS 使用红黑树来组织所有可运行进程（就绪队列）。红黑树是一种自平衡二叉查找树，其查找、插入、删除操作的时间复杂度均为 O(log n)，非常适合调度器频繁选择最小 vruntime 进程的场景。
红黑树在 CFS 中的角色：
- 键值：每个节点的键值是进程的
vruntime。 - 最左节点：树中最左侧的节点（vruntime 最小）即为下一个要运行的进程。
- 缓存指针：内核缓存了最左节点的指针，避免每次调度都遍历整棵树。
- 进程数量：树中节点数等于当前可运行进程的数量。
3.3 权重与优先级映射
Linux 内核使用 nice 值作为用户可见的优先级接口，范围从 -20（最高优先级）到 +19（最低优先级）。CFS 内部将 nice 值映射为权重（weight），权重决定了进程的 vruntime 增长速率。
nice 值与权重的映射表（部分）：
| nice 值 | 权重 | 相对比例（相对于 nice=0） | 典型场景 |
|---|---|---|---|
| -20 | 88761 | 86.7 倍 | 实时音频处理 |
| -10 | 11051 | 10.8 倍 | 高优先级用户进程 |
| 0 | 1024 | 1.0 倍（基准） | 普通进程 |
| 10 | 304 | 0.3 倍 | 后台批处理任务 |
| 19 | 15 | 0.015 倍 | 低优先级空闲任务 |
sched_prio_to_weight[40]，将 nice 值 [-20, 19] 映射到对应的权重值。权重值的设计使得每降低一个 nice 值（优先级提高），CPU 时间分配增加约 10%。
3.4 CFS 调度决策流程
CFS 的调度决策是一个持续循环的过程，核心步骤包括：
- 选择下一个进程：从红黑树中获取 vruntime 最小的节点（最左节点）。
- 上下文切换：保存当前进程的状态，恢复目标进程的状态。
- 运行进程：允许进程在 CPU 上执行。
- 时钟中断触发：每次时钟中断（通常为 1ms 或 4ms）更新当前进程的 vruntime。
- 检查是否需要抢占：如果当前进程的 vruntime 超过了红黑树中最左节点的 vruntime，则设置重新调度标志。
- 重新插入红黑树：当进程时间片用完或被抢占时，将其重新插入红黑树，并回到步骤 1。
3.5 CFS 与实时调度器的对比
| 特性 | CFS (SCHED_NORMAL/SCHED_BATCH) | 实时调度器 (SCHED_FIFO/SCHED_RR) |
|---|---|---|
| 调度依据 | vruntime（虚拟运行时间） | 静态优先级（0-99） |
| 数据结构 | 红黑树（按 vruntime 排序） | 位图 + 链表（按优先级队列） |
| 公平性 | 完全公平（按权重比例分配） | 严格优先级（高优先级先运行） |
| 抢占点 | 时钟中断、进程唤醒、yield | 更高优先级进程就绪时立即抢占 |
| 适用场景 | 普通用户进程、批处理、交互式 | 实时系统、音频/视频、工业控制 |
3.6 内核代码关键路径
CFS 的核心实现在 kernel/sched/fair.c 文件中。以下是一些关键函数及其作用：
// 选择下一个要运行的进程（红黑树最左节点）
static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
{
struct sched_entity *se = __pick_first_entity(cfs_rq);
// ... 缓存优化逻辑
return se;
}
// 更新进程的 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 = now - curr->exec_start;
curr->vruntime += calc_delta_fair(delta_exec, curr);
curr->exec_start = now;
}
// 将进程插入红黑树
static void enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
update_curr(cfs_rq);
// ... 更新统计信息
__enqueue_entity(cfs_rq, se); // 实际插入红黑树
se->on_rq = 1;
}
// 权重计算：nice 值 -> 权重
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,
};