CPU 调度算法
这一节是第 2 章计算题的主战场。七个算法本身不难，难在手算时容易乱——时间轴一长，谁在什么时刻该被换下来、下一个该选谁，很容易记错。
所以本节先给出一套固定的手算流程，再逐个讲算法。流程比算法更值得先掌握。
机制
手算流程：五步法
疑问点：调度算法计算题的固定解法
这类题应当如何着手？时间轴怎么画？能否把流程固定下来，避免每次现想？
可以。任何调度计算题都可以套下面五步，不要跳步：
第一步：列表。 把题目数据抄成一张固定格式的表，四列——进程名、到达时间、运行时间、（若有）优先级。先抄再算，不要边看题边算。
第二步：判定算法性质。 问自己两个问题：
- 是抢占还是非抢占？这决定了”是否需要在每个新进程到达时重新决策”。
- 决策依据是什么？（到达时间 / 运行时间 / 剩余时间 / 响应比 / 优先级 / 时间片）
第三步：确定”决策点”。 这是全流程的核心。只在决策点上做选择，其余时间什么都不用想：
| 算法类型 | 决策点 |
|---|---|
| 非抢占 | 仅当前进程结束时 |
| 抢占（SRTN、抢占式优先级） | 当前进程结束时 + 每有新进程到达时 |
| 时间片轮转 | 当前进程结束时 + 时间片用完时 |
第四步：逐个决策点推进，画甘特图。 每到一个决策点，从”此刻已到达且未完成”的进程中按规则选一个，在时间轴上画一段。关键纪律：只看已经到达的进程。 手算出错最常见的原因就是把还没到达的进程也纳入了比较。
第五步：读出完成时间，套公式。
算完必查：带权周转时间是否都 ≥ 1？若有小于 1 的，一定算错了。
五步法示范
用一道典型题走一遍全流程。
- 有 5 个批处理作业 A、B、C、D、E 几乎同时到达，其预计运行时间分别为 10、6、2、4、8， 其优先级（由外部设定）分别为 3、5、2、1、4，这里 5 为最高优先级。 以下各种调度算法中，平均周转时间为 14 的是（ ）。 A. 时间片轮转（时间片为 1） B. 优先级调度 C. 先来先服务（按顺序 10, 6, 2, 4, 8） D. 短作业优先
第一步 列表：
| 作业 | A | B | C | D | E |
|---|---|---|---|---|---|
| 运行时间 | 10 | 6 | 2 | 4 | 8 |
| 优先级 | 3 | 5 | 2 | 1 | 4 |
注意：选项 C 的括号”按顺序 10, 6, 2, 4, 8”同时也确定了队列顺序为 A→B→C→D→E，这是后面算 RR 的必要条件。
第二步 判性质：全部作业同时到达，故所有非抢占算法都只需按各自规则排一个顺序。
第三步~第五步：因为同时到达，各作业的完成时间就是排在它之前（含自己）的运行时间之和，周转时间等于完成时间。
| 算法 | 执行顺序 | 各作业完成时间 | 总和 | 平均周转 |
|---|---|---|---|---|
| FCFS | A B C D E | 10, 16, 18, 22, 30 | 96 | 19.2 |
| SJF | C D B E A | 2, 6, 12, 20, 30 | 70 | 14 ✅ |
| 优先级 | B E A C D | 6, 14, 24, 26, 30 | 100 | 20 |
| RR (q=1) | 轮转 | C=8, D=17, B=23, E=28, A=30 | 106 | 21.2 |
答案：D 短作业优先。
这道题正好印证了 SJF 的最优性——在所有作业同时到达的前提下，SJF 的平均周转时间是四者中最小的，这与后面要证明的结论一致。
RR 的 21.2 是四者中最差的，原因也很直白：轮转让每个作业都被拖到很晚才完成，短作业 C 本来 2 个单位就能跑完，却因为要陪着别人轮转而拖到第 8 个单位。RR 牺牲平均周转时间换取的是响应时间。
甘特图怎么画
甘特图就是一条横向时间轴，把每段占用 CPU 的区间标出来。手写时用这个格式最不容易乱：
时刻 0 2 4 8 12 16
|----|----|---------|---------|---------|
P1 P2 P3 P1 P4
三条纪律：
- 只在决策点断开，不要随意切分。
- 每段下方标进程名，上方标时刻（标的是边界时刻，不是区间长度）。
- 抢占式算法中，同一进程会出现多段，读完成时间时要取它最后一段的右端点。
七个算法
FCFS 先来先服务
按到达的先后排队，非抢占。
它是最公平、实现最简单的算法，且绝不会导致饥饿——排在队里就一定轮得到。
但它对短作业极不友好。
疑问点：FCFS 为何对短作业不利
排在长作业后面的短作业，实质上是被迫等待长作业全部执行完毕。
这个现象有个专门的名字：护航效应（convoy effect）。一个长作业排在队首，后面所有短作业都得陪着它一起等，就像一队车被一辆慢车堵住。
后果直接体现在带权周转时间上：一个只需运行 1 单位的作业若等了 100 单位，其带权周转时间高达 101，用户体验极差；而那个长作业自己的带权周转时间可能才 1.01。FCFS 的平均带权周转时间通常很大，问题就出在这里。
SJF 短作业优先 / SPF 短进程优先
每次从就绪队列中选运行时间最短的，非抢占。
疑问点：SJF 平均周转时间最短能否被证明，这是否属于贪心
最短作业优先据称能使平均周转时间最短，该结论能否证明？它是否属于贪心算法？
是贪心算法，而且它的最优性可以严格证明。 证明用的正是贪心算法标准的交换论证（exchange argument）。
设所有作业同时到达，考虑任意一个调度顺序。若其中存在相邻的两个作业，前面那个运行时间为
交换只影响这两个作业各自的完成时间，对其余作业毫无影响（因为这两段占用的总时长
- 交换前：两者完成时刻为
与 ，两者之和 - 交换后：两者完成时刻为
与 ，两者之和
两式相减得
这说明：只要存在”长在前、短在后”的相邻对，就一定还能改进。 不断交换直到无法改进，得到的必然是按运行时间升序排列的顺序——这正是 SJF。故 SJF 最优。
范围限定（极其重要）：上述证明有两个前提，缺一不可：
- 所有作业同时到达（或至少在决策时都已到达）
- 非抢占
若作业到达时间不同，SJF 不再保证平均周转时间最短——此时最优的是它的抢占版本 SRTN。这是本节最常被抽掉限定条件的结论。
SJF 的代价是可能产生饥饿：只要短作业源源不断地到来，长作业就永远排不上。极端情况下长作业饿死（starvation）。
SRTN 最短剩余时间优先
SJF 的抢占版本。每当有新进程到达或当前进程完成时，比较所有已到达且未完成进程的剩余运行时间，选最短的。
它在”作业到达时间不同”的一般情形下，能取得最小的平均周转时间。代价是抢占带来的上下文切换开销，以及更严重的饥饿倾向。
手算时特别注意：决策点比 SJF 多了”新进程到达”这一类，非常容易漏。
HRRN 高响应比优先
非抢占。每次选择响应比最高的：
这个公式是 FCFS 和 SJF 的折中，设计得相当巧妙：
- 当等待时间相同时，要求服务时间越短，响应比越高 → 体现 SJF 的倾向
- 当要求服务时间相同时，等待时间越长，响应比越高 → 体现 FCFS 的倾向
- 对长作业而言，随着等待时间增长，响应比会不断上升，最终必然能被选中
最后一条是关键：HRRN 不会产生饥饿。这是它相对 SJF 的核心优势，也是最常见的考点。
RR 时间片轮转
按到达顺序排队，每个进程运行一个时间片，用完就被剥夺并排到队尾。抢占式。
它是分时系统的标配，因为它保证了响应时间的上界：n 个进程、时间片 q，则任一进程最多等待
时间片大小的选择是核心考点：
- 时间片过大：所有进程都能在一个时间片内跑完，RR 退化为 FCFS，响应时间变长。
- 时间片过小：进程切换过于频繁，上下文切换开销占比过高，CPU 真正用于计算的比例下降。
一般要求时间片略大于一次典型交互所需的时间，通常使切换开销不超过 1%。
疑问点：题目未给出队列顺序时，RR 能否计算
若多个作业几乎同时到达，时间片轮转的调度顺序如何确定？ 题目若未给出该顺序，是否根本无法计算？
这个顾虑是成立的：RR 的结果确实依赖初始队列顺序，顺序不同，各进程的完成时间不同。
但实际做题时通常不成问题，原因有二：
其一，题目往往已隐含给出顺序。例如某题的选项写作”先来先服务（按顺序 10, 6, 2, 4, 8）“，这个括号就已经确定了队列顺序为 A、B、C、D、E，RR 按同一顺序推演即可。
其二，若确实未给，约定按到达顺序；同时到达则按题目列出的顺序。
还有一个必须约定清楚的细节：当某进程时间片用完、而同一时刻又有新进程到达时，谁先入队？ 通行约定是新到达的进程先入队，被剥夺的进程后入队。这个约定会影响后续顺序，考试中若有歧义，按此处理并写明假设。
优先级调度
每次选择优先级最高的进程。分抢占式与非抢占式。
优先级又分两类：
- 静态优先级：创建时确定，之后不变。简单，但可能导致低优先级进程饥饿。
- 动态优先级：运行过程中根据情况调整。例如随等待时间增长而提升优先级，可有效缓解饥饿。
优先级设置的一般规律（选择题常考）：
- 系统进程 > 用户进程
- 交互型进程 > 非交互型（前台 > 后台）
- I/O 型进程 > 计算型进程
最后一条的理由值得想清楚：I/O 型进程占用 CPU 的时间很短，让它优先运行，它很快就会去做 I/O 而让出 CPU，这样 I/O 设备和 CPU 就能并行工作，整体资源利用率更高。 反之若让计算型进程长期霸占 CPU，I/O 设备就一直闲置。
多级队列与多级反馈队列
多级队列：系统中设置多个就绪队列，不同队列采用不同的调度算法，队列之间也有优先级。进程被固定分配到某个队列，不能移动。
多级反馈队列：多级队列的改进，进程可以在队列之间移动。规则是：
- 设置多级就绪队列，优先级从高到低，时间片从小到大。
- 新进程进入第 1 级（最高优先级）队列末尾，按 FCFS 等待。
- 若在该级时间片内未完成，则被剥夺并降入下一级队列末尾。已在最低级则留在原级。
- 只有当第
级队列全空时，才会调度第 级队列中的进程。 - 若正在运行时有更高级队列的进程到达，则立即抢占，被抢占者回到原队列队尾。
这个设计的精妙之处在于，它不需要预知作业长度，就自动实现了对短作业的偏好：
短作业在前几级队列里就跑完了，享受到了高优先级和快速响应；长作业会一级级往下沉，虽然优先级降低，但时间片越来越大，一旦轮到就能连续跑很久，减少了切换开销。
它是综合性能最好的算法，兼顾了各类进程，且对各类作业相对公平（FCFS 的优点）、能使短作业较快完成（SJF 的优点）、又有较好的响应时间（RR 的优点）。但仍可能产生饥饿——只要高优先级队列源源不断有进程到来。
流水式作业的通用解法
疑问点：输入—计算—输出型题目的通用做法
【2016 统考真题】某单 CPU 系统中有输入和输出设备各 1 台，现有 3 个并发执行的作业，每个作业的输入、计算和输出时间均分别为 2ms、3ms 和 4ms，且都按输入、计算和输出的顺序执行，则执行完 3 个作业需要的时间最少是（ ）。 A. 15ms B. 17ms C. 22ms D. 27ms
此类题目可用时间轴推演，但作业数增多时是否有通用公式？
答案是 B. 17ms。
这类题本质上是三级流水线：输入设备、CPU、输出设备是三个独立部件，可以并行工作，但每个部件同一时刻只能服务一个作业，且每个作业必须按 I→C→O 的顺序推进。
逐作业推演：
| 作业 | 输入(2) | 计算(3) | 输出(4) |
|---|---|---|---|
| 1 | 0–2 | 2–5 | 5–9 |
| 2 | 2–4 | 5–8 | 9–13 |
| 3 | 4–6 | 8–11 | 13–17 |
加粗处是被前一作业占用同一部件而推迟的时刻。例如作业 2 的输入在 4ms 就完成了，但 CPU 直到 5ms 才被作业 1 释放，所以它只能等到 5ms 才开始计算。总时长 17ms。
通用公式（相同作业、每级一台设备）：
公式的道理是瓶颈决定节拍：流水线充满之后，每隔一个”最慢那级的时长”就产出一个作业。本题输出级最慢（4ms），因此稳态下每 4ms 完成一个。
这个公式回答了”作业更多会不会更复杂”——不会。
范围限定：该公式要求各作业的各级时间相同、每级只有一台设备。若作业时间不一，或某级有多台设备，仍须退回逐作业推演。这一点务必留意，不要盲套。
边界
会不会饥饿
这是最高频的辨析点，必须逐个记准：
| 算法 | 是否可能饥饿 | 原因 |
|---|---|---|
| FCFS | 不会 | 排队就一定轮得到 |
| SJF / SPF | 会 | 短作业不断到来，长作业永远排不上 |
| SRTN | 会 | 同上，且更严重 |
| HRRN | 不会 | 等待越久响应比越高，最终必被选中 |
| RR | 不会 | 轮转保证每轮都有机会 |
| 优先级（静态） | 会 | 低优先级可能永远得不到 |
| 多级反馈队列 | 会 | 高优先级队列持续有进程则低级饿死 |
记忆抓手：只有 FCFS、HRRN、RR 三个不会饥饿。 它们的共同点是决策依据中包含”等待时间”或”轮转保证”，天然带有防饿机制。
SJF 的”最优”有前提
如前所述，SJF 平均周转时间最短这一结论仅在所有作业同时到达且非抢占时成立。到达时间不同时，最优者是 SRTN。考题常常给出不同到达时间却仍问”哪个算法平均周转时间最短”，此时答 SJF 就错了。
时间片过大退化为 FCFS
RR 中若时间片大到所有进程都能在一个时间片内完成，则每个进程一上 CPU 就跑到结束，与 FCFS 完全等价。这是常见的选择题设问方式。
多级队列 vs 多级反馈队列
一字之差，区别在于进程能否在队列间移动：
- 多级队列：进程被固定分配到某队列，终生不变。
- 多级反馈队列：进程会因时间片用完而降级，实现了动态调整。
对照速查
| 算法 | 抢占 | 决策依据 | 对短作业 | 对长作业 | 饥饿 | 适用 |
|---|---|---|---|---|---|---|
| FCFS | 否 | 到达时间 | 不利 | 有利 | 否 | 批处理 |
| SJF | 否 | 运行时间 | 有利 | 不利 | 会 | 批处理 |
| SRTN | 是 | 剩余时间 | 有利 | 不利 | 会 | 批处理 |
| HRRN | 否 | 响应比 | 较有利 | 较有利 | 否 | 批处理 |
| RR | 是 | 时间片 | 中性 | 中性 | 否 | 分时 |
| 优先级 | 均可 | 优先级 | 看设置 | 看设置 | 会 | 实时 |
| 多级反馈队列 | 是 | 队列级别 | 有利 | 尚可 | 会 | 通用，综合最好 |
| 手算五步 | 内容 |
|---|---|
| ① 列表 | 进程、到达、运行、优先级 |
| ② 判性质 | 抢占否；决策依据是什么 |
| ③ 定决策点 | 非抢占=结束时；抢占=结束时+新到达；RR=结束时+时间片到 |
| ④ 画甘特图 | 只在已到达的进程中选 |
| ⑤ 套公式 | 周转、带权周转；查带权 ≥ 1 |
考点
- 五步手算流程与甘特图纪律（只看已到达的进程）
- 哪些算法会饥饿：只有 FCFS、HRRN、RR 不会
- SJF 最优的两个前提：同时到达 + 非抢占
- HRRN 响应比公式，及其”不会饥饿”的原因
- RR 时间片过大退化为 FCFS
- 多级反馈队列的五条规则，及其与多级队列的区别
- 流水式作业公式：
链接
- 🏠 返回总览：操作系统第 2 章：进程与线程总览
- ⬅️ 上一节：2.2.4 进程切换
- ➡️ 下一节：2.2.6 多处理机调度
- 🔗 指标公式见 2.2.3 调度的目标
- 📖 名词库：第 2 章名词库