主题
第三章 CPU 调度：谁先运行
1. 调度问题从哪里来
上一章建立了进程的概念：就绪队列里随时躺着一堆"万事俱备只差 CPU"的进程。CPU 却只有那么几个。从就绪队列里挑谁上场、让它跑多久，就是调度问题。
先破一个误区：调度没有"标准答案"。让短任务先跑，长任务就吃亏；追求总吞吐量，交互程序就可能卡顿。每个调度算法都是对某种目标的偏心，所以学习调度的正确姿势不是背算法步骤，而是问三个问题：这个算法偏心谁？亏待谁？为此付出什么代价？
2. 调度的三个层次
教材里"调度"一词其实覆盖三件发生频率完全不同的事：
| 层次 | 别名 | 决定什么 | 发生频率 |
|---|---|---|---|
| 高级调度 | 作业调度 | 哪个作业从外存调入内存、建立进程 | 最低，分钟级 |
| 中级调度 | 内存调度 | 哪个进程暂时换出到外存、何时换回 | 中等 |
| 低级调度 | 进程调度 | 就绪队列中哪个进程获得 CPU | 最高，毫秒级 |
记忆抓手：高级管"进门"，中级管"暂住外面"，低级管"上场"。频率越高的调度，算法必须越快——进程调度每秒发生成百上千次，不能用复杂算法慢慢算。本章后面讲的经典算法都属于低级调度（进程调度）。
3. 评价指标：每个指标在关心什么
设一个作业"到达时间"为它进入系统的时刻，"服务时间"为它实际需要的 CPU 时间，则：
| 指标 | 定义 | 白话解读 |
|---|---|---|
| 周转时间 | 完成时间 − 到达时间 | 用户从提交到拿到结果，总共等了多久 |
| 带权周转时间 | 周转时间 ÷ 服务时间 | 等待相对于干活的"冤枉倍数"，短任务对它最敏感 |
| 等待时间 | 周转时间 − 服务时间 | 纯排队没干活的时间 |
| 响应时间 | 从提交到第一次获得响应的时间 | 交互用户关心的是"有没有反应"，不是"做没做完" |
| 吞吐量 | 单位时间完成的作业数 | 系统角度：一天能干多少活 |
| CPU 利用率 | CPU 忙碌时间占比 | 资源不空转 |
| 公平性 | 各进程都能得到合理份额 | 没有谁被永远晾着 |
关键理解：这些指标互相冲突。比如让短作业插队能降低平均周转时间，但牺牲了长作业的公平；把时间片切小能改善响应时间，但切换开销上升、吞吐量下降。批处理系统重吞吐量和周转时间，分时系统重响应时间，实时系统重截止时间——题目问"某系统最应关注什么指标"时按此对号入座。
4. 抢占与非抢占
- 非抢占式：进程一旦上了 CPU，除非它自己完成或主动阻塞，否则谁也拿不走。实现简单，但紧急任务插不了队。
- 抢占式：内核可以依据时钟中断、优先级等强行把 CPU 收回。响应好，代价是切换更频繁、实现更复杂。
这不是两个独立算法，而是一个"开关"：同一思想（如短作业优先、优先级）都有非抢占版和抢占版，下面逐个算法时会看到。
5. FCFS：先来先服务
规则：按到达顺序排队，非抢占，先到先跑到底。
例题：三个进程，到达时间与服务时间如下（单位统一为时间单位）：
| 进程 | 到达时间 | 服务时间 |
|---|---|---|
| P1 | 0 | 24 |
| P2 | 1 | 3 |
| P3 | 2 | 3 |
执行顺序 P1 → P2 → P3。逐个手算：
| 进程 | 开始 | 完成 | 周转时间 = 完成 − 到达 | 带权周转 = 周转 ÷ 服务 |
|---|---|---|---|---|
| P1 | 0 | 24 | 24 − 0 = 24 | 1.00 |
| P2 | 24 | 27 | 27 − 1 = 26 | 8.67 |
| P3 | 27 | 30 | 30 − 2 = 28 | 9.33 |
平均周转时间 =（24 + 26 + 28）÷ 3 = 26。
点评：P2 只需要 3 个单位的活，却等了 23 个单位——这叫护航效应：一个长进程像慢船堵在航道口，后面一串短进程干等。FCFS 公平（先来先得）、无饥饿，但对短作业极不友好，平均周转时间往往很差。
6. SJF 与 SRTF：短作业优先
SJF 规则（非抢占）：每次从就绪队列中挑服务时间最短的进程运行。
用同一组数据：0 时刻只有 P1 到达，只能先跑 P1（0～24）；24 时刻 P2、P3 都已到达且都需 3 个单位，按到达序先 P2（24～27）再 P3（27～30）——本例结果恰与 FCFS 相同，因为长进程先到已开跑。换一组更能体现差别的数据：
| 进程 | 到达时间 | 服务时间 |
|---|---|---|
| P1 | 0 | 7 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 5 | 4 |
SJF（非抢占）：P1 先跑完（0～7）；7 时刻 P2、P3、P4 都已到齐，按最短挑 P3（7～8），再 P2（8～12），再 P4（12～16）。
| 进程 | 完成 | 周转时间 |
|---|---|---|
| P1 | 7 | 7 |
| P2 | 12 | 10 |
| P3 | 8 | 4 |
| P4 | 16 | 11 |
平均周转时间 =（7 + 10 + 4 + 11）÷ 4 = 8。
SRTF（最短剩余时间优先）是 SJF 的抢占版：新进程到达时，若其服务时间比当前进程的剩余时间还短，立刻抢占。同一组数据手算：P1 跑到 2 时 P2 到达（P2 需 4 < P1 剩 5，抢占）；P2 跑到 4 时 P3 到达（P3 需 1 < P2 剩 2，抢占）；P3 跑完（4～5）；P2 继续（5～7）；然后 P4（7～11）；最后 P1（11～16）。平均周转时间 =（16 + 5 + 1 + 6）÷ 4 = 7，比非抢占更优。
点评：可以证明 SJF/SRTF 让平均周转时间最短，这是它的王牌。但两大硬伤：其一，服务时间事先无法准确知道，只能估计；其二，短作业源源不断时，长作业可能饥饿（永远轮不上）。
7. 优先级调度：饥饿与老化
规则：每个进程带一个优先级，每次挑优先级最高者运行；同样分抢占和非抢占两版。优先级可以是静态的（创建时定死，简单但僵化）或动态的（随运行情况调整）。
例题：四个进程同时（0 时刻）到达，数字越小优先级越高：
| 进程 | 服务时间 | 优先级 |
|---|---|---|
| P1 | 10 | 3 |
| P2 | 1 | 1 |
| P3 | 2 | 4 |
| P4 | 5 | 2 |
执行顺序：P2（0～1）→ P4（1～6）→ P1（6～16）→ P3（16～18）。平均周转时间 =（16 + 1 + 18 + 6）÷ 4 = 10.25。
致命问题——饥饿：如果高优先级进程持续到来，低优先级进程可能永远得不到 CPU。传说 MIT 曾在关机时发现一个等了多年的低优先级进程。
解药——老化（aging）：进程每等待一段时间就自动提升一点优先级。等得越久优先级越高，最终一定能熬出头。一句话点透：老化就是把"资历"折算成"优先级"，用时间换公平。
8. 时间片轮转：分时系统的招牌
规则：就绪进程排成一圈，每人最多跑一个固定的时间片（如 20 毫秒），时间片用完就被时钟中断强制换下，排到队尾。天生是抢占式的。
例题：P1、P2、P3 于 0 时刻到达，服务时间分别为 3、4、3，时间片 = 1：
执行序列：P1 P2 P3 P1 P2 P3 P1 P2 P3 P2（第 10 个时间片 P2 收尾）。
| 进程 | 完成时间 | 周转时间 |
|---|---|---|
| P1 | 7 | 7 |
| P2 | 10 | 10 |
| P3 | 9 | 9 |
平均周转时间 =（7 + 10 + 9）÷ 3 ≈ 8.67。若用 FCFS 则为（3 + 7 + 10）÷ 3 ≈ 6.67——轮转的平均周转时间反而更差，但每个进程都在 3 个单位内得到了第一次响应。这正是轮转的定位：不求总账好看，只求人人及时有反应。
时间片大小的权衡是核心考点：
| 时间片 | 后果 |
|---|---|
| 太大 | 退化成 FCFS，交互响应变差 |
| 太小 | 切换过于频繁，上下文切换的纯开销吃掉大量 CPU |
经验法则：时间片应远大于一次上下文切换的开销（比如切换占时间片的 1% 以下），同时小到能保证响应。时间片轮转不会导致饥饿——每人每圈都有份。
9. 多级反馈队列：集大成者
前面的算法各有偏科：SJF 照顾短任务但要预知未来，轮转响应好但周转差，优先级灵活但会饥饿。多级反馈队列（MLFQ）把它们的优点缝合在一起，不需要预知服务时间，却能近似 SJF 的效果。
规则：
- 设多个就绪队列，优先级从高到低，队列越低时间片越长。
- 新进程进入最高级队列。
- 高级队列非空时，绝不运行低级队列的进程（高级可抢占低级）。
- 进程用满时间片仍没完成，就降到下一级队列；若在时间片内主动阻塞（如等 I/O），通常留在原级。
- 最低一级队列内部按时间片轮转。
为什么说它是集大成者：它用"是否用完时间片"来自动探测进程的长短——短任务、交互任务在高级队列里就完成了，享受 SJF 般的待遇；长任务逐级下沉，用大时间片安稳地跑，减少切换开销。不用预知服务时间，历史行为就是最好的预言。为防长任务饥饿，实际系统还会周期性把所有进程升回最高队列（这也是一种老化）。
10. 算法总对比与实时调度一瞥
| 算法 | 抢占性 | 偏心谁 | 会饥饿吗 | 最大短板 |
|---|---|---|---|---|
| FCFS | 非抢占 | 先到者、长作业 | 不会 | 护航效应，短作业遭殃 |
| SJF / SRTF | 两版都有 | 短作业 | 长作业会 | 需预知服务时间 |
| 优先级 | 两版都有 | 高优先级 | 低优先级会，需老化 | 饥饿 |
| 时间片轮转 | 抢占 | 公平对待所有人 | 不会 | 平均周转时间不优，切换开销 |
| 多级反馈队列 | 抢占 | 短任务和交互任务 | 底层可能，需定期提升 | 实现复杂 |
实时调度一句话概念：任务带截止时间，调度目标从"平均性能好"变成"每个任务都赶得上截止时间"，代表算法有最早截止时间优先 EDF 和速率单调 RM，考试一般只考概念定位。
11. 本章要点回顾
| 主题 | 必须记住的结论 |
|---|---|
| 三级调度 | 高级管作业进内存，中级管挂起换出，低级管 CPU 分配且频率最高 |
| 周转时间 | 完成 − 到达；带权周转 = 周转 ÷ 服务；平均值是手算题的标准问法 |
| 指标取舍 | 批处理重吞吐与周转，分时重响应，实时重截止时间 |
| FCFS | 简单公平无饥饿，护航效应害惨短作业 |
| SJF/SRTF | 平均周转时间最优，但要预知时间且长作业饥饿 |
| 优先级 | 饥饿的标准案例，老化是标准解药 |
| 时间片轮转 | 响应好、无饥饿；时间片过大变 FCFS，过小切换开销爆炸 |
| MLFQ | 用降级机制自动区分长短任务，不需预知服务时间 |
12. 做题提醒
- 手算题先画时间轴（甘特图），再套公式：周转 = 完成 − 到达，别把"开始时间"当"到达时间"。
- SJF 非抢占版：只在进程完成的时刻挑下一个，且只能从已到达的进程里挑，别让还没到的短进程穿越插队。
- "时间片轮转的时间片越小越好"是错的——切换开销会失控；"越大越好"也错——退化为 FCFS。
- 会导致饥饿的算法：SJF、SRTF、优先级（不带老化）、MLFQ（不带提升）；不会饥饿的：FCFS、时间片轮转。
- "SJF 的平均周转时间一定最短"要加限定条件：在同批作业、非抢占且不考虑到达时间差异等理想前提下成立，抢占版 SRTF 在有到达时间时更优。
- 响应时间考查"第一次被服务"的时刻，别和周转时间（完成时刻）混为一谈。