1. 课程导论：进程调度的重要性、O(1)与CFS的历史背景、课程目标与学习路径
1.1 为什么进程调度是操作系统的核心
进程调度器是操作系统内核中最关键的子系统之一。它决定了在任意时刻，哪个进程能够获得CPU的使用权。一个优秀的调度器需要在多个目标之间取得平衡：
- 公平性：确保每个进程都能获得合理的CPU时间份额
- 吞吐量：最大化单位时间内完成的进程数量
- 响应时间：交互式进程需要快速响应用户输入
- CPU利用率：避免CPU空闲等待
- 功耗效率：在移动设备上尤为重要
核心认知： 调度器是操作系统对"谁该运行"这一问题的最终裁决者。一个设计糟糕的调度器会导致系统响应迟钝、吞吐量低下，甚至引发进程饥饿问题。
1.2 O(1)调度器的历史背景
O(1)调度器由Ingo Molnar开发，于Linux内核2.6.0-rc1（2003年）中引入，取代了早期的O(n)调度器。其名称来源于调度算法的时间复杂度为O(1)，即无论系统中运行多少个进程，调度决策的时间都是恒定的。
| 特性 | O(1)调度器 |
|---|---|
| 引入时间 | Linux 2.6.0 (2003年) |
| 开发者 | Ingo Molnar |
| 时间复杂度 | O(1) — 常数时间 |
| 核心数据结构 | 140个优先级的位图 + 双链表数组 |
| 调度策略 | 基于优先级的抢占式调度 |
| 主要优势 | 大规模系统下性能可预测，SMP扩展性好 |
| 主要缺陷 | 交互式进程识别启发式复杂，公平性不足 |
O(1)的局限性： 虽然O(1)调度器在性能上取得了巨大进步，但其基于"优先级+时间片"的模型存在根本性问题——高优先级进程可能长时间占用CPU，导致低优先级进程饥饿；交互式进程的识别依赖复杂的启发式规则，容易误判。
1.3 CFS调度器的诞生与设计哲学
完全公平调度器（Completely Fair Scheduler, CFS）由Con Kolivas的"楼梯调度器"和"RSDL"启发，由Ingo Molnar重新实现，于Linux内核2.6.23（2007年）中正式取代O(1)调度器。
CFS的核心设计哲学是：模拟"理想的多任务处理器"——如果存在一个能够同时运行所有进程的完美CPU，每个进程将获得1/N的CPU时间。CFS通过虚拟运行时间（vruntime）来逼近这一理想模型。
| 特性 | CFS调度器 |
|---|---|
| 引入时间 | Linux 2.6.23 (2007年) |
| 开发者 | Ingo Molnar（基于Con Kolivas的工作） |
| 时间复杂度 | O(log N) — 红黑树操作 |
| 核心数据结构 | 红黑树（按vruntime排序） |
| 调度策略 | 基于vruntime的加权公平调度 |
| 主要优势 | 公平性极佳，交互式体验好，无需复杂启发式 |
| 主要缺陷 | 大规模进程下红黑树操作开销略高于O(1) |
1.4 O(1)与CFS的核心差异概览
在深入细节之前，我们先从宏观上把握两种调度器的本质区别：
| 对比维度 | O(1)调度器 | CFS调度器 |
|---|---|---|
| 调度模型 | 固定优先级 + 时间片轮转 | 加权公平队列（WFQ） |
| 核心数据结构 | 优先级位图 + 140个链表 | 红黑树（按vruntime排序） |
| 选择下一个进程 | 查找位图中最高优先级非空链表 | 取红黑树最左节点（vruntime最小） |
| 时间复杂度 | O(1) | O(log N) |
| 公平性 | 较差（优先级高的进程占优） | 极好（所有进程按权重公平分配） |
| 交互式响应 | 依赖启发式规则，不稳定 | 天然支持（睡眠进程vruntime不增长） |
| 负载均衡 | 基于优先级迁移 | 基于负载统计迁移 |
学习提示： 理解O(1)和CFS的关键在于把握它们对"公平"的不同定义。O(1)认为"高优先级进程应该获得更多CPU"，而CFS认为"所有进程应该按权重比例公平分享CPU"。这两种哲学导致了完全不同的实现路径。
1.5 课程目标与学习路径
本课程旨在帮助你从原理到实践，全面掌握两种经典调度器的设计思想与实现细节。课程分为四个阶段：
- 基础篇（第1-8章）：调度器基础概念、进程状态模型、调度策略分类、上下文切换机制
- O(1)深度篇（第9-16章）：优先级位图实现、时间片计算、交互式进程识别、SMP负载均衡
- CFS深度篇（第17-26章）：vruntime计算、红黑树操作、调度组与cgroup、组调度、NUMA感知
- 实战篇（第27-30章）：调度器参数调优、性能分析工具、调度器选型决策、未来趋势（EEVDF）
1.6 预备知识要求
为了获得最佳学习效果，建议你具备以下基础：
- 操作系统基础：理解进程、线程、上下文切换等基本概念
- C语言基础：能够阅读内核源码中的数据结构定义和函数实现
- 数据结构基础：熟悉链表、位图、红黑树、哈希表等基本结构
- Linux基础：了解内核编译、模块加载、系统调用等基本操作
课程承诺： 本课程将从最基础的调度概念讲起，逐步深入到O(1)和CFS的源码级实现。即使你目前对调度器只有初步了解，通过30章的系统学习，也能成为调度器领域的专家。