1. 课程导论：为什么需要进程调度？调度算法的评价指标
在现代操作系统中，进程（或线程）的数量通常远多于 CPU 核心数。操作系统必须决定在任意时刻，哪个进程获得 CPU 的使用权，以及它能运行多久。这个决策过程就是 进程调度。没有调度，多个进程将无法有序共享 CPU，系统会陷入混乱，甚至死锁。
核心问题： 给定一组就绪进程，调度器如何选择下一个运行的进程，并分配多长时间片，以最大化系统整体性能并满足用户期望？
1.1 为什么需要进程调度？
进程调度的必要性源于以下几个关键需求：
- 多任务并发： 让多个进程看起来在同时运行，提高 CPU 利用率。
- 资源公平分配： 防止某个进程长期霸占 CPU，导致其他进程“饥饿”。
- 响应及时性： 对于交互式应用（如编辑器、浏览器），调度需要保证低延迟，避免用户感到卡顿。
- 系统吞吐量最大化： 在单位时间内完成尽可能多的任务。
- 满足实时性约束： 对于多媒体或工业控制系统，调度必须在规定时间内完成特定任务。
1.2 调度算法的评价指标
设计或选择调度算法时，需要从不同维度衡量其优劣。没有一种算法能在所有指标上同时达到最优，因此需要根据系统目标（如批处理、交互式、实时）进行权衡。以下是五个核心指标：
| 指标 | 英文 | 定义 | 优化方向 | 典型场景 |
|---|---|---|---|---|
| 吞吐量 | Throughput | 单位时间内完成的进程数量 | 最大化 | 批处理系统、服务器 |
| 周转时间 | Turnaround Time | 从进程提交到完成的总时间（包含等待、运行、I/O） | 最小化 | 批处理作业 |
| 响应时间 | Response Time | 从进程提交到第一次产生输出（或用户感知到响应）的时间 | 最小化 | 交互式系统（桌面、手机） |
| 等待时间 | Waiting Time | 进程在就绪队列中等待 CPU 的总时间 | 最小化 | 所有系统 |
| 公平性 | Fairness | 每个进程获得 CPU 时间的比例是否合理，避免饥饿 | 保证公平 | 分时系统、通用 OS |
关键权衡： 响应时间与吞吐量往往相互冲突。例如，频繁切换进程（时间片短）能提升响应速度，但会因上下文切换开销降低吞吐量。CFS 算法试图在两者间取得更好的平衡。
1.3 指标间的内在矛盾
理解指标间的矛盾是掌握调度算法的前提。以下通过一个简单例子说明：
- 场景： 两个进程，P1 需要运行 10 秒，P2 需要运行 1 秒。
- FCFS（先来先服务）： 若 P1 先到，P2 等待 10 秒。P2 的响应时间极差（10 秒），但吞吐量可能较高（因为切换少）。
- RR（时间片轮转）： 若时间片为 1 秒，P2 在 1 秒后即可获得 CPU，响应时间优秀（1 秒），但总周转时间可能变长（因为切换开销）。
1.4 公平性：一个复杂的目标
公平性并非简单的“每个进程运行相同时间”。它涉及：
- 时间公平： 每个进程获得等量的 CPU 时间。
- 进度公平： 每个进程按相同比例推进（如 CFS 的“虚拟运行时间”概念）。
- 优先级公平： 高优先级进程获得更多时间，但低优先级进程不应被无限期推迟（避免饥饿）。
注意： 绝对的公平（如严格轮转）可能导致性能下降。例如，I/O 密集型进程需要快速响应以释放资源，如果与 CPU 密集型进程完全平等对待，会降低整体系统效率。现代调度器（如 CFS）通过动态权重和睡眠补偿机制来平衡公平性与性能。
1.5 调度算法分类概览
在进入具体算法之前，先了解调度算法的宏观分类，这有助于理解 O1 和 CFS 所处的技术背景：
| 分类 | 典型算法 | 核心特点 | 适用场景 |
|---|---|---|---|
| 非抢占式 | FCFS, SJF (非抢占) | 进程一直运行到主动阻塞或结束 | 早期批处理系统 |
| 抢占式 | RR, SRTF, 优先级调度 | 时间片用完或更高优先级进程到达时强制切换 | 分时系统、通用 OS |
| 公平共享 | CFS, Lottery Scheduling | 基于权重或概率分配 CPU 时间，强调公平性 | 现代通用 OS (Linux) |
| 实时调度 | Rate Monotonic, EDF | 满足任务的截止时间，可预测性强 | 嵌入式、工业控制 |
本课程将重点聚焦于 Linux 内核中两个里程碑式的调度器：O(1) 调度器（Linux 2.6.0~2.6.22）和 CFS 调度器（Linux 2.6.23 至今）。O1 调度器以其常数时间复杂度和对 SMP（对称多处理）的良好支持著称，而 CFS 则通过红黑树和虚拟运行时间模型，实现了更优的公平性和交互响应。
1.6 小结
进程调度是操作系统的核心功能，它直接决定了系统的响应速度、吞吐量和用户体验。评价调度算法需要从吞吐量、周转时间、响应时间、等待时间和公平性等多个维度综合考量。这些指标之间存在内在矛盾，调度算法的设计就是在这些矛盾中寻找最佳平衡点。从 O1 到 CFS 的演进，正是 Linux 内核在追求更高公平性、更低延迟和更好交互体验过程中的重要里程碑。接下来的章节，我们将深入剖析 O1 调度器的设计与实现。