1. CFS 调度器概述
1.1 CFS 设计哲学：从“时间片”到“虚拟时间”
完全公平调度器（Completely Fair Scheduler, CFS）是 Linux 内核自 2.6.23 版本引入的默认调度类。其核心设计哲学可以用一句话概括：为每个任务提供“理想、精确的公平 CPU 时间分配”。
CFS 摒弃了传统调度器依赖固定时间片（Time Slice）和优先级动态计算的做法，转而引入 虚拟运行时间（vruntime） 作为公平性的唯一度量。CFS 不再问“这个任务的时间片还剩多少”，而是问“这个任务已经运行了多久（相对于其权重）”。
核心思想： 在一个无限小的粒度上，CFS 试图让所有可运行任务（runnable tasks）的 vruntime 保持相等。vruntime 最小的任务，就是“最受亏待”的任务，理应被优先调度。
1.2 公平调度核心概念
理解 CFS 必须掌握以下四个核心概念，它们构成了 CFS 公平性的基石：
- vruntime（虚拟运行时间）： 任务的“虚拟时钟”。实际运行时间会除以任务的权重（nice 值），权重越高的任务 vruntime 增长越慢，从而获得更多 CPU 时间。
- 红黑树（Red-Black Tree）： 用于组织所有可运行任务的数据结构。以 vruntime 为键值，最左侧节点（vruntime 最小）就是下一个被调度的任务。
- 调度延迟（sched_latency）： CFS 保证所有可运行任务在一个周期内至少被调度一次的目标时间间隔。
- 最小粒度（min_granularity）： 任务被调度后至少运行的时间，防止频繁上下文切换导致性能下降。
关键公式： vruntime += (实际运行时间 * NICE_0_LOAD) / 任务权重。其中 NICE_0_LOAD 是 nice 0 任务的权重基准值（1024）。
1.3 CFS 与 O(1) 调度器的核心区别
O(1) 调度器（Linux 2.6.0~2.6.22）虽然解决了调度算法的时间复杂度问题，但其公平性依赖于启发式算法和复杂的优先级升/降级机制。CFS 从根本上简化了模型。下表列出了两者的关键差异：
| 对比维度 | O(1) 调度器 | CFS 调度器 |
|---|---|---|
| 核心数据结构 | 140 个优先级链表（active/expired 数组） | 红黑树（以 vruntime 排序） |
| 公平性度量 | 时间片 + 动态优先级（交互性启发式） | vruntime（纯数学计算） |
| 时间复杂度 | O(1)（固定时间） | O(log N)（红黑树插入/删除） |
| 交互性判断 | 依赖睡眠/唤醒启发式算法（易出错） | 通过 vruntime 自然体现（I/O 密集型任务 vruntime 小） |
| 优先级映射 | nice 值 → 固定时间片（非线性） | nice 值 → 任务权重（vruntime 增长率） |
| 负载均衡 | 基于负载统计的拉取/推送 | 基于 vruntime 差的迁移（更平滑） |
1.4 CFS 调度流程架构图
下图展示了 CFS 从任务就绪到被调度执行的核心流程，以及 vruntime 在其中的作用：
1.5 为什么 CFS 更适合现代系统？
CFS 的设计带来了几个关键优势，使其成为现代 Linux 系统的默认选择：
- 公平性可预测： 不再依赖复杂的启发式算法，vruntime 的数学计算保证了公平性是可量化和可预测的。
- 交互性自然体现： I/O 密集型任务（如键盘输入）通常只运行很短时间就睡眠，其 vruntime 很小，一旦唤醒就能快速获得 CPU，无需特殊“交互性检测”。
- 调度延迟可控： 通过
sched_latency和min_granularity参数，系统管理员可以精确控制调度延迟和吞吐量的平衡。 - 代码简洁性： CFS 的核心代码量远小于 O(1) 调度器，减少了维护成本和潜在的 bug。
故障排查启示： 理解 CFS 的 vruntime 机制是排查“任务饥饿”问题的关键。当某个任务的 vruntime 异常增大（例如由于权重计算错误或时钟中断处理异常），该任务将被红黑树“遗忘”在右侧，导致长时间得不到调度，表现为任务饥饿。