1. 课程导论
1.1 调度器演进全景：从O(n)到CFS的三次跨越
Linux进程调度器在过去三十年中经历了三次重大重构，每一次都对应着硬件规模与负载模式的根本性变化。下表从核心算法、时间复杂度、关键缺陷三个维度对比三代调度器：
| 调度器版本 | 引入内核 | 核心算法 | 时间复杂度 | 主要缺陷 |
|---|---|---|---|---|
| O(n) 调度器 | Linux 0.01 ~ 2.4 | 全局优先级轮询 | O(n) — 随进程数线性增长 | 多核扩展差、交互响应迟钝 |
| O(1) 调度器 | Linux 2.6.0 ~ 2.6.22 | 双优先级位图 + 活跃/过期数组 | O(1) — 常数时间 | 交互进程判定启发式、公平性不足 |
| CFS 调度器 | Linux 2.6.23 至今 | 红黑树 + 虚拟运行时间 (vruntime) | O(log n) — 对数时间 | （无结构性缺陷，持续优化中） |
演进驱动力： 从单核到数百核、从批处理到交互/实时混合负载、从固定时间片到完全公平的权重分配——调度器必须同时满足 公平性、低延迟 和 高吞吐 三个矛盾目标。
1.2 O(n) 调度器：全局链表时代的困境
早期Linux调度器维护一个全局进程链表，每次调度时遍历所有就绪进程，计算“好度(goodness)”值并选出最大值。其核心流程如下：
O(n) 致命缺陷： 当系统进程数达到数百甚至上千时，每次调度都需要完整遍历链表，调度延迟与进程数成正比。在服务器场景下，调度器本身成为性能瓶颈，交互式应用（如SSH、编辑器）出现明显卡顿。
1.3 O(1) 调度器：常数时间的突破
Ingo Molnár 在 Linux 2.6.0 中引入了 O(1) 调度器，通过双优先级数组和位图查找将调度决策时间固定为常数。其核心架构如下：
O(1) 调度器的创新： 通过将140个优先级映射到位图的140个bit，调度器只需执行
__ffs() 指令即可在常数时间内找到最高优先级的非空队列。但交互进程的“启发式睡眠”判定（sleep_avg）在复杂负载下频繁误判，导致桌面体验仍然不够理想。
1.4 CFS 调度器：完全公平的设计哲学
2007年，Con Kolivas 的“楼梯调度器”和“RSDL”方案启发了 Ingo Molnár，最终在 Linux 2.6.23 中合入 CFS（Completely Fair Scheduler）。CFS 抛弃了传统的时间片和优先级数组，转而采用 虚拟运行时间 (vruntime) 作为核心度量。
CFS 的核心设计哲学可以概括为三个原则：
- 理想公平模型： 假设一个完美多任务处理器，所有可运行进程同时以1/n的速率执行。CFS 通过 vruntime 追踪每个进程实际获得的 CPU 时间，并始终选择 vruntime 最小的进程运行。
- 权重驱动分配： 进程的 nice 值被映射为权重（weight），权重越高，vruntime 增长越慢，从而获得更多 CPU 时间。nice 值每差1，CPU 时间分配比例差约10%。
- 红黑树索引： 所有可运行进程按 vruntime 组织在红黑树中，最左节点即 vruntime 最小的进程，调度器在 O(log n) 时间内完成选择。
1.5 公平调度理念的数学表达
CFS 的公平性可以用一个简洁的公式表达：
理想情况下，每个进程应获得的CPU时间 = 总CPU时间 × (进程权重 / 所有进程权重之和)
实际调度中，CFS 保证：|vruntime(A) - vruntime(B)| < 调度粒度（通常1~4ms）
这意味着在任何时刻，所有可运行进程的 vruntime 差值被严格限制在一个很小的范围内，从而实现“宏观公平、微观交错”的调度效果。
关键洞察： CFS 不直接分配时间片，而是通过 vruntime 的“速率控制”间接实现比例分配。这种设计天然支持 对称多处理（SMP） 和 负载均衡——每个CPU维护自己的红黑树，通过周期性的负载均衡算法在CPU之间迁移进程，使全局 vruntime 分布趋于均衡。