4. Linux 调度器演进史：从 O(n) 到 O(1) 再到 CFS
Linux 内核调度器在过去三十年间经历了三次重大架构重构：从早期简单粗暴的 O(n) 调度器，到追求确定性的 O(1) 调度器，再到如今兼顾公平与交互的 CFS（完全公平调度器）。每一次变迁都对应着硬件环境与负载模型的根本性变化。
演进主线： 调度器的发展始终围绕三个核心矛盾展开——吞吐量 vs 响应延迟、公平性 vs 优先级、多核扩展性 vs 调度开销。
4.1 早期 O(n) 调度器（Linux 2.4 及之前）
在 Linux 2.4 内核时代，调度器采用最简单的 循环遍历 + 时间片轮转 模型。每次调度时，调度器必须遍历整个就绪队列，计算所有进程的“好度（goodness）”，选出得分最高的进程执行。
核心缺陷
- 时间复杂度 O(n)： 进程数越多，调度耗时越长。当系统运行 1000 个进程时，一次调度遍历可能消耗数百微秒。
- 多核扩展性差： 所有 CPU 共享一个全局就绪队列，需要大内核锁保护，导致 CPU 争抢严重。
- 交互响应迟钝： 没有显式的交互进程识别机制，桌面打字、鼠标移动等操作容易出现卡顿。
O(n) 调度器核心公式（简化版）：
goodness(p) = p->counter + p->nice + p->sleep_avg
// 遍历所有进程，选择 goodness 最大的进程执行每次调度都需要 O(n) 时间扫描整个链表，n 为系统进程总数。
4.2 O(1) 调度器（Linux 2.6.0 ~ 2.6.22）
2003 年，Ingo Molnár 在 Linux 2.6.0 中引入了 O(1) 调度器，彻底解决了 O(n) 的扩展性问题。其核心思想是：用空间换时间——通过多级优先级位图和双队列结构，将调度决策的时间复杂度降为常数级。
架构创新
- 每 CPU 独立就绪队列： 每个 CPU 维护自己的 active 和 expired 两个队列，彻底消除全局锁竞争。
- 优先级位图（bitmap）： 使用 140 级优先级（0~139），通过位图操作在 O(1) 时间内找到最高优先级非空队列。
- 时间片动态计算： 根据优先级和交互性动态分配时间片，交互进程获得更长时间片以降低响应延迟。
| 特性 | O(n) 调度器 | O(1) 调度器 |
|---|---|---|
| 时间复杂度 | O(n) | O(1) |
| 就绪队列结构 | 全局单链表 | 每 CPU 双队列 + 位图 |
| 多核扩展性 | 差（大内核锁） | 优秀（无锁 per-CPU） |
| 交互进程识别 | 无 | 基于睡眠时间启发式判断 |
| 调度公平性 | 粗糙（依赖 counter） | 较好（优先级 + 时间片） |
4.3 CFS 调度器（Linux 2.6.23 至今）
2007 年，Con Kolivas 的 RSDL（楼梯调度器） 和 Ingo Molnár 的 CFS（完全公平调度器） 先后进入内核主线。CFS 彻底抛弃了固定时间片和优先级位图，转而采用 红黑树 + 虚拟运行时间（vruntime） 模型，实现了真正的按权重比例分配 CPU 时间。
设计哲学
- 理想公平模型： 假设存在一个“完美多任务 CPU”，每个进程获得 1/n 的 CPU 时间。CFS 通过 vruntime 度量每个进程已获得的 CPU 时间，每次选择 vruntime 最小的进程执行。
- 红黑树（Red-Black Tree）： 就绪队列使用红黑树组织，插入、删除、查找操作均为 O(log n)，但实际调度决策（取最左节点）为 O(1)。
- 权重与优先级： nice 值不再直接决定时间片大小，而是转化为权重（weight），影响 vruntime 的增长速度。高优先级（低 nice 值）进程的 vruntime 增长更慢，从而获得更多 CPU 时间。
CFS 核心公式：
vruntime += delta_exec * NICE_0_LOAD / se->load.weight
// delta_exec：实际执行时间
// NICE_0_LOAD：nice=0 时的基准权重（1024）
// se->load.weight：当前进程的权重（由 nice 值映射）调度决策：始终选择红黑树中 vruntime 最小 的进程执行。
4.4 三代调度器核心对比
| 维度 | O(n)（2.4） | O(1)（2.6.0~2.6.22） | CFS（2.6.23+） |
|---|---|---|---|
| 数据结构 | 全局链表 | 每 CPU 双队列 + 位图 | 每 CPU 红黑树 |
| 调度复杂度 | O(n) | O(1) | O(log n)（取最左 O(1)） |
| 公平模型 | 时间片轮转 | 优先级 + 时间片 | vruntime 加权公平 |
| 交互优化 | 无 | 睡眠时间启发式 | 唤醒延迟 + 组调度 |
| 多核扩展 | 极差 | 优秀 | 优秀 + 负载均衡 |
| 内核版本 | ≤ 2.4 | 2.6.0 ~ 2.6.22 | 2.6.23 ~ 至今 |
演进启示： O(1) 调度器虽然解决了扩展性问题，但其交互性判断规则复杂且难以调优。CFS 通过数学化的 vruntime 模型，用更简洁的算法同时实现了公平性、交互响应和可扩展性，成为 Linux 调度器设计的里程碑。