1. 课程导论
1.1 研究调度器演进的驱动力
操作系统调度器是内核中最核心的子系统之一，它直接决定了多任务环境下CPU资源的分配效率与公平性。研究调度器从O1到CFS的演进，本质上是理解操作系统如何应对硬件架构变革与负载模型复杂化的过程。
核心驱动力： 从单核到多核、从交互式桌面到服务器/云原生、从固定时间片到完全公平的调度哲学转变。
调度器演进的主要驱动因素可归纳为以下四个方面：
- 硬件架构变革： SMP（对称多处理）普及、NUMA（非统一内存访问）架构出现、CPU核心数从个位数增长到数百个。
- 负载模型多样化： 交互式桌面应用（低延迟需求）、批处理任务（高吞吐需求）、实时任务（硬截止时间需求）共存。
- 公平性需求提升： 用户期望每个进程获得与其优先级/权重成比例的CPU时间，而非简单的优先级抢占。
- 可维护性与扩展性： O1调度器的复杂启发式逻辑难以维护和调优，需要更简洁、数学上可证明的调度模型。
1.2 O1调度器与CFS调度器的历史地位
| 维度 | O1调度器 | CFS调度器 |
|---|---|---|
| 引入内核版本 | Linux 2.6.0 (2003年) | Linux 2.6.23 (2007年) |
| 核心数据结构 | 多级优先级队列（140个运行队列） | 红黑树（按虚拟运行时间排序） |
| 时间复杂度 | O(1) 调度决策（常数时间） | O(log N) 调度决策（N为可运行进程数） |
| 调度单位 | 固定时间片（优先级决定时间片长度） | 虚拟运行时间（vruntime，按权重加权） |
| 交互式优化 | 启发式“交互性”检测（复杂且易出错） | 基于睡眠延迟的唤醒抢占（简洁可预测） |
| 历史地位 | 解决了2.4内核调度器O(N)的可扩展性问题 | 确立了完全公平的调度范式，影响后续所有调度器 |
关键认知： O1调度器是“可扩展性”的里程碑，CFS调度器是“公平性”的里程碑。两者分别解决了不同时代最突出的调度矛盾。
1.3 设计哲学对比：启发式 vs. 数学模型
O1与CFS最根本的差异在于设计哲学：O1依赖经验启发式，而CFS依赖数学模型。
O1调度器的设计哲学
- 优先级驱动： 静态优先级（nice值）和动态优先级（交互性奖励/惩罚）共同决定调度顺序。
- 时间片固定： 高优先级进程获得更长的时间片，低优先级进程获得更短的时间片。
- 交互性启发式： 通过“平均睡眠时间”等指标猜测进程是否为交互式，并给予动态优先级提升。
- 问题： 启发式规则存在大量边界情况，导致调度行为不可预测，且在多核环境下负载均衡复杂。
CFS调度器的设计哲学
- 公平性驱动： 所有进程按权重比例获得CPU时间，目标是让每个进程的虚拟运行时间（vruntime）尽可能相等。
- 时间片动态： 不预设固定时间片，每次调度选择vruntime最小的进程运行，运行时间由调度周期和权重动态计算。
- 数学模型： 使用红黑树维护vruntime排序，调度决策完全由数学公式决定，无启发式猜测。
- 优势： 行为可预测、调优简单（仅需调整nice值权重映射表）、多核负载均衡基于vruntime迁移。
设计哲学警示： O1的启发式逻辑在负载复杂化后成为维护噩梦，CFS的数学模型虽然增加了调度决策的时间复杂度（从O(1)到O(log N)），但换来了可证明的公平性和极低的可维护成本。这是“可扩展性”与“可维护性”之间的经典权衡。
1.4 调度器演进核心架构对比图
下图展示了O1调度器与CFS调度器在核心架构上的关键差异，包括数据结构、调度决策流程和负载均衡机制。
1.5 从O1到CFS：演进的核心矛盾
调度器演进并非简单的版本升级，而是对以下核心矛盾的重新平衡：
- 可扩展性 vs. 公平性： O1追求O(1)调度决策，但牺牲了公平性；CFS接受O(log N)复杂度，但实现了可证明的公平。
- 启发式 vs. 确定性： O1依赖经验规则处理交互式负载，CFS用数学模型统一所有负载类型。
- 静态优先级 vs. 动态权重： O1的优先级是调度核心，CFS的nice值仅作为权重因子影响vruntime推进速度。
- 时间片固定 vs. 时间片动态： O1的时间片是预设的，CFS的时间片由调度周期和权重动态计算，更适应负载变化。
演进本质： 从“如何快速选择下一个进程”转变为“如何公平地分配CPU时间”。O1解决了“慢”的问题，CFS解决了“不公平”的问题。现代调度器（如EEVDF）在CFS基础上进一步优化了延迟边界。
1.6 本章小结
O1调度器与CFS调度器的对比，本质上是操作系统设计哲学从“经验主义”向“理性主义”的转变。O1通过精巧的数据结构实现了O(1)调度，但其复杂的启发式逻辑成为后续维护的负担；CFS通过红黑树和虚拟运行时间模型，用数学上的简洁性换取了可证明的公平性和可维护性。理解这一演进过程，是深入分析现代调度器（如EEVDF、BFS、MuQSS）的基础。