cpu-调度算法

2026-06-26

CPU 调度算法

核心定义

CPU 调度 是从就绪队列中按某种策略选取一个进程，把 CPU 分配给它运行。调度的根本目标是 提高 CPU 利用率、系统吞吐量、公平性，并降低平均周转时间与响应时间。

三级调度：高级调度（作业调度） 从外存的后备队列选作业调入内存，创建 PCB，发生频率低；中级调度（内存调度/交换） 决定哪些暂时不能运行的进程被换出到外存（挂起态），缓解内存压力；低级调度（进程调度） 从就绪队列选进程分配 CPU，发生频率最高，是 408 考试的核心。

七状态模型在五状态基础上增加 就绪挂起、阻塞挂起 两个挂起态；挂起的本质是进程被换出到外存。

调度的五大评价指标（单位均为时间）：

\text{周转时间} = \text{完成时间} - \text{到达时间}

\text{带权周转时间} = \dfrac{\text{周转时间}}{\text{要求服务时间}} \ge 1

\text{等待时间} = \text{周转时间} - \text{要求服务时间}\ (\text{不计 I/O 等待})

\text{响应时间} = \text{首次获得 CPU} - \text{到达时间}

平均周转时间 = $\dfrac{\sum \text{周转时间}}{n}$ ；CPU 利用率 = 忙碌时间 / 总时间；系统吞吐量 = 单位时间完成的进程数。

flowchart TD A["就绪队列"] --> B{"调度算法"} B -->|FCFS| C["先来先服务 非抢占"] B -->|SJF/SRTN| D["短作业/短剩余优先 SJF非抢占·SRTN抢占"] B -->|HRRN| E["高响应比优先 非抢占·不饿死"] B -->|优先级| F["静态/动态优先级 抢占或非抢占"] B -->|时间片轮转 RR| G["时间片到即抢占 适合分时"] B -->|多级反馈队列| H["综合型 现代 OS 常用"] C & D & E & F & G & H --> I["分配 CPU"]

考研常考 FCFS、SJF、SRTN、HRRN、时间片轮转、多级反馈队列 的特性比较与平均周转时间 / 平均等待时间的计算。

关键细节 / 操作步骤

第一步：先判断题目问的是 算法特性辨析 还是 性能计算。辨析题用特性表（是否抢占、是否会饿死、适合场景）；计算题画甘特图逐步推。
第二步：FCFS（先来先服务）——按到达时间顺序服务，非抢占。优点公平、实现简单；缺点护航效应（长作业后面跟一堆短作业都要久等），对短作业不利。
第三步：SJF（短作业优先）——选要求服务时间最短的，非抢占，平均等待时间最短（理论最优）。缺点可能饿死长作业。
第四步：SRTN（最短剩余时间优先）——SJF 的抢占版，每当新进程到达或当前进程运行一段后，比较剩余时间谁短就让谁运行。SRTN 的平均周转时间比 SJF 更优。
第五步：HRRN（高响应比优先）——非抢占，响应比公式：

$R = \dfrac{\text{等待时间} + \text{要求服务时间}}{\text{要求服务时间}} = 1 + \dfrac{\text{等待时间}}{\text{要求服务时间}}$

等待越久响应比越高，兼顾长短作业且不会饿死；每次调度时对所有就绪进程计算 R，选最大者。
第六步：优先级调度——分静态优先级（创建时确定不变）与动态优先级（运行中可变，如随等待时间增大而升高）。常遵循：系统进程 > 用户进程、I/O 型进程 > 计算型进程（让 I/O 与 CPU 并行）。分抢占式与非抢占式。
第七步：时间片轮转（RR）——就绪队列按 FCFS 排，每个进程每次最多运行一个时间片，时间片到则被抢占、排到队尾。时间片太大退化为 FCFS；太小切换开销过大。适合分时系统，响应快。
第八步：多级反馈队列调度（MLFQ）——设置多个优先级递减的队列，时间片随队列优先级降低而增大；新进程进最高优先级队列，未完成则降到下一级；高优先级队列非空时低优先级队列不执行。综合了响应快、短作业优先、可适应长作业，是现代 OS（如早期 Unix、Windows）的基础。
第九步：性能计算题三步法：①列各进程到达时间/服务时间 → ②按调度规则画甘特图确定各进程完成时间 → ③代入公式算周转/等待/响应，再取平均。
第十步：抢占式与非抢占式的触发时机——非抢占式只在进程运行结束或阻塞时调度；抢占式还会在新进程到达（SRTN）、时间片到（RR）、更高优先级进程到达时调度。

⚠️ 易错辨析

SJF 最小化的是”平均等待时间/平均周转时间”，不是响应时间；响应时间最优的是时间片轮转。

“SJF 不会饿死”是错的：SJF 长作业可能饿死；HRRN 和时间片轮转不会饿死。

时间片轮转的时间片大小不是越小越好——太小会因频繁切换使系统吞吐量下降（上下文切换开销占主导）。

带权周转时间 $\ge 1$ ，且服务时间越短的进程带权周转通常越大（短作业等比例吃亏更明显）。

“等待时间”在不同教材有两种口径：含 I/O 等待 vs 不含 I/O 等待；考研默认等待时间 = 周转时间 − 要求服务时间（不计 I/O 等待）。

FCFS 对长作业有利、对短作业不利（护航效应）；SJF 恰相反。

优先级调度的”动态优先级”常设规则：等待越久优先级越高，正是为了避免饿死。

多级反馈队列中时间片是”低优先级队列更长”，不是更短——因为长作业会沉到低优先级队列，给它们更长的时间片能减少切换开销。

💡 技巧与口诀

口诀：FCFS 公平护航长，SJF 最短饿长作业，SRTN 抢占更优，HRRN 响应比不饿死，RR 分时响应快，MLFQ 综合现代化。

计算题模板：列表 → 甘特图 → 完成时间 → 周转 = 完成 − 到达 → 等待 = 周转 − 服务 → 求平均。每一步都写清楚，避免跳步漏算。

应用场景：看到”平均等待时间最短”想到 SJF；看到”既照顾短作业又不饿死长作业”想到 HRRN；看到”分时系统/响应快”想到 RR；看到”现代操作系统/多队列”想到 MLFQ。

📝 真题闭环 题目：系统有 4 个进程，到达时间与服务时间如下表。分别用 FCFS、SJF（非抢占）、SRTN（抢占） 计算平均周转时间和平均等待时间。

进程到达时间服务时间
P1 0 8
P2 1 4
P3 2 1
P4 3 1

解题思路：

审题抓”三种调度算法 + 平均指标”，切入点是画甘特图定完成时间，再套周转/等待公式。

FCFS（按到达顺序，非抢占）：P1(0–8) → P2(8–12) → P3(12–13) → P4(13–14)。完成时间 P1=8,P2=12,P3=13,P4=14；周转 8/11/11/11；等待 0/7/10/10。平均周转 = (8+11+11+11)/4 = 10.25；平均等待 = (0+7+10+10)/4 = 6.75。

SJF（非抢占）：t=0 仅 P1 到达，先跑 P1(0–8)；t=8 时 P2/P3/P4 均就绪，选最短 → P3(8–9) → P4(9–10) → P2(10–14)。完成时间 P1=8,P3=9,P4=10,P2=14；周转 P1=8,P3=7,P4=7,P2=13；等待 0/6/6/9。平均周转 = (8+7+7+13)/4 = 8.75；平均等待 = (0+9+6+6)/4 = 5.25。

SRTN（抢占）：每次比较剩余时间最短者运行。 t=0 P1 跑；t=1 P2(剩4)<P1(剩7) 切 P2；t=2 P3(剩1)<P2(剩3) 切 P3；t=3 P3 完，P4(剩1)<P2(剩3) 切 P4；t=4 P4 完，P2 跑到 t=7 完；P1 跑到 t=14 完。完成时间 P3=3,P4=4,P2=7,P1=14；周转 P3=1,P4=1,P2=6,P1=14；等待 P3=0,P4=0,P2=2,P1=6。平均周转 = (14+6+1+1)/4 = 5.5；平均等待 = (6+2+0+0)/4 = 2。

答案：

FCFS：平均周转 10.25，平均等待 6.75。

SJF：平均周转 8.75，平均等待 5.25。

SRTN：平均周转 5.5，平均等待 2。

结论：本例 SRTN < SJF < FCFS（平均周转时间），印证”抢占式短作业优先类算法平均周转更优”，但 SJF/SRTN 都可能饿死长作业。

进程	到达时间	服务时间
P1	0	8
P2	1	4
P3	2	1
P4	3	1

cd ..