第3章：处理机调度与死锁
处理机调度（CPU Scheduling）是操作系统资源管理的核心功能之一。本章系统介绍三级调度体系、调度算法、实时调度以及死锁的产生条件和解决方法。
3.1 调度的基本概念
3.1.1 三级调度体系 ⭐
作业进入系统│▼┌───────────────┐│ 高级调度 │ ← 作业调度：外存 → 内存│ (作业调度) │ 频次最低，每作业一次└───────┬───────┘▼┌───────────────┐│ 中级调度 │ ← 挂起调度：换出/换入内存│ (内存调度) │ 频次中等，调节内存负载└───────┬───────┘▼┌───────────────┐│ 低级调度 │ ← 进程调度：就绪 → 执行│ (进程调度) │ 频次最高，ms级└───────────────┘
| 调度层次 |
别名 |
功能 |
频率 |
是否必有 |
| 高级调度 |
作业调度/长程调度 |
从外存后备队列选作业进内存 |
最低（分钟级） |
分时/实时OS可无 |
| 中级调度 |
内存调度/中程调度 |
进程换入换出内存（挂起/激活） |
中等 |
分时OS有 |
| 低级调度 |
进程调度/短程调度 |
从就绪队列选进程分配CPU |
最高（ms级） |
必有 |
3.1.2 调度队列模型
新作业 ──→ 后备队列 ──→ [高级调度] ──→ 就绪队列 ──→ [低级调度] ──→ CPU ──→ 完成↑┌────── 阻塞队列 ──────┐│ (等待I/O等事件) │└───────────────────────┘
3.1.3 CPU调度时机
| 情形 |
是否为抢占 |
说明 |
| 进程终止 |
非抢占 |
必须切换 |
| 进程阻塞（等待I/O） |
非抢占 |
必须切换 |
| 新进程到达 |
可选抢占 |
新进程优先级极端高时 |
| I/O中断 |
可选抢占 |
唤醒更高优先级进程时 |
| 时钟中断 |
可选抢占 |
时间片轮转中必然发生 |
3.2 调度算法评价指标
| 指标 |
含义 |
追求方向 |
| CPU利用率 |
CPU忙时间 / 总时间 |
越高越好 |
| 系统吞吐量 |
单位时间内完成的作业数 |
越高越好 |
| 周转时间 |
作业完成时间 - 提交时间 |
越短越好 |
| 带权周转时间 |
周转时间 / 实际运行时间 |
越小越好 |
| 等待时间 |
进程在就绪队列中等待时间的总和 |
越短越好 |
| 响应时间 |
从提交到首次响应的时间 |
越短越好（交互系统） |
周转时间 = 完成时间 - 提交时间= 等待时间 + 运行时间（若仅计算系统内阶段）带权周转时间 = 周转时间 / 运行时间≥ 1（越小越好，=1最理想）
3.3 经典调度算法 ⭐⭐⭐
3.3.1 先来先服务（FCFS）
| 特征 |
说明 |
| 原则 |
按作业/进程到达先后顺序调度 |
| 类型 |
非抢占 |
| 优点 |
简单、公平 |
| 缺点 |
短作业可能排在长作业后，平均周转时间长 |
| 适用 |
批处理系统 |
例：P1(24ms), P2(3ms), P3(3ms) 依次到达FCFS:
|────── P1 ──────|─P2─|─P3─|
0 24 27 30平均等待时间 = (0 + 24 + 27)/3 = 17ms若运行顺序改为 P2→P3→P1：
平均等待时间 = (0 + 3 + 6)/3 = 3ms
→ 短作业优先能显著降低平均等待时间
3.3.2 短作业优先（SJF / SPF）⭐
| 特征 |
说明 |
| 原则 |
每次调度选运行时间最短的作业/进程 |
| 类型 |
可抢占（SRTF）或非抢占 |
| 优点 |
平均等待时间最小（可证明最优） |
| 缺点 |
长作业可能饥饿、需预知运行时间 |
| 适用 |
批处理系统 |
⭐ SJF最优性证明：SJF能给出最小的平均等待时间（对于一组同时到达的作业）。
短作业优先（SPF）vs 最短剩余时间优先（SRTF）SPF（非抢占）：
P1(7), P2(4), P3(1), P4(4) 假设时间0全部就绪
|P3|─P2─|───P4───|────P1─────|
0 1 5 9 16SRTF（抢占式）：
P1在0时刻运行1ms后，P2到达(剩余4 < P1剩余6)，抢占！
|P1|P2|P3|──P2──|───P4───|────P1─────|
0 1 2 3 7 11 16
3.3.3 优先级调度
| 特征 |
说明 |
| 原则 |
优先级最高的进程先运行 |
| 类型 |
可抢占或非抢占 |
| 优先级确定 |
静态（固定）或动态（随等待时间变化） |
优先级的设定：- 系统进程 > 用户进程- I/O型进程 > 计算型进程（让I/O先行，减少CPU空闲）- 前台进程 > 后台进程
⚠️ 饥饿（Starvation）：高优先级进程不断到来，低优先级进程永远得不到CPU。解决方法：老化（Aging）——随等待时间增加而逐渐提高优先级。
3.3.4 高响应比优先（HRRN）⭐
响应比 $R_p = \frac{等待时间 + 要求服务时间}{要求服务时间} = 1 + \frac{等待时间}{要求服务时间}$
| 特征 |
说明 |
| 公式 |
$R_p = \frac{T_{等待}+T_{服务}}{T_{服务}}$ |
| 含义 |
等待时间越长 + 服务时间越短 → 响应比越高 |
| 优点 |
既照顾短作业，又不会让长作业无限等待 |
| 缺点 |
每次调度需计算响应比 |
当服务时间相同时：响应比由等待时间决定 → FCFS
当等待时间相同时：响应比由服务时间决定 → SJF
长作业等待足够久后，响应比会足够大 → 不会饥饿
3.3.5 时间片轮转（RR）⭐
| 特征 |
说明 |
| 原则 |
每个进程轮流获得一个时间片的CPU |
| 类型 |
抢占式 |
| 适用 |
分时系统 |
| 关键参数 |
时间片大小 q |
时间片选择原则：q 太大 → 退化为FCFS，响应时间变长q 太小 → 上下文切换频繁，系统开销增大经验法则：q 应该大于上下文切换时间，且保证80%的CPU突发能在q内完成
3.3.6 多级队列调度
就绪进程：│├──→ 队列1（前台交互式进程，RR调度，优先级最高）│├──→ 队列2（后台批处理进程，FCFS调度，优先级次之）│└──→ 队列3（系统进程，优先级最低但必不可少）
不同队列采用不同调度算法，队列间也可设定优先级。
3.3.7 多级反馈队列调度 ⭐⭐
现代操作系统（Linux、Windows）广泛采用的调度策略，综合了多种算法的优点。
┌──────────────┐新进程 → │ 队列0: q=8ms │ (RR, 最高优先级)└──┬──┬──┬────┘│ │ └──→ 时间片用完，降到下一级▼ ▼┌──────────────┐│ 队列1: q=16ms │ (RR, 次高优先级)└──┬──┬──┬────┘│ │ └──→ 时间片用完，降到下一级▼ ▼┌──────────────┐│ 队列2: FCFS │ (最低优先级)└──────────────┘
| 特征 |
说明 |
| 多个队列 |
不同优先级，时间片递增 |
| 动态调整 |
I/O密集型进程优先（I/O完成后回到高优先级队列） |
| 老化机制 |
低优先级队列等待过久可提升优先级 |
| 优点 |
兼顾响应时间和吞吐量，灵活 |
3.3.8 调度算法总结对比
| 算法 |
抢占 |
饥饿 |
平均等待 |
复杂度 |
适用场景 |
| FCFS |
否 |
不会 |
较高 |
O(1) |
批处理 |
| SJF |
均可 |
长作业 |
最优 |
O(n log n) |
批处理 |
| 优先级 |
均可 |
低优先级 |
取决于策略 |
O(n) |
通用 |
| HRRN |
否 |
不会 |
较好 |
O(n) |
批处理 |
| RR |
是 |
不会 |
取决于q |
O(1) |
分时 |
| 多级反馈队列 |
是 |
防止 |
很好 |
O(1) |
通用 |
3.4 实时调度
3.4.1 实时调度的必要条件
| 条件 |
说明 |
| 系统处理能力 |
周期任务的总利用率 ≤ 1 |
| 提供必要信息 |
就绪时间、开始/完成截止时间、处理时间、资源需求、优先级 |
| 可抢占 |
硬实时系统必须支持抢占 |
3.4.2 常用实时调度算法
| 算法 |
全称 |
策略 |
特点 |
| EDF |
Earliest Deadline First |
截止时间最早的优先 |
可证明最优（动态优先级） |
| RMS |
Rate Monotonic Scheduling |
周期越短（速率越高）优先级越高 |
静态优先级，$U ≤ n(2^{1/n}-1)$ 可调度 |
| LLF |
Least Laxity First |
松弛度最低的优先 |
松弛度 = 截止时间 - 当前时间 - 剩余处理时间 |
3.5 死锁 ⭐⭐⭐
3.5.1 死锁的定义
死锁（Deadlock）：多个进程因竞争资源而造成的一种僵局，若无外力，这些进程将永远无法向前推进。
3.5.2 产生死锁的四个必要条件 ⭐
死锁四条件：
┌──────────────────────────────────────┐
│ ① 互斥条件 │
│ 资源排他性使用，一次一个进程 │
├──────────────────────────────────────┤
│ ② 请求和保持条件 │
│ 已拥有资源的进程又请求新资源， │
│ 且不释放已有资源 │
├──────────────────────────────────────┤
│ ③ 不可抢占条件 │
│ 已分配给进程的资源，不能被强制拿走 │
├──────────────────────────────────────┤
│ ④ 循环等待条件 │
│ 存在进程-资源的循环等待链 │
│ P0 → R0 → P1 → R1 → ... → P0 │
└──────────────────────────────────────┘
⭐ 四个条件必须同时满足才会死锁。破坏任一条件即可预防死锁。
3.5.3 资源分配图与死锁检测
资源分配图示例（存在死锁）：P1 ←──┐ P2 ←──┐│ │ │ │▼ │ ▼ │R1 │ R2 ││ │ │ │▼ │ ▼ │P2 ───┘ P3 ───┘若存在环，且每种资源只有一个实例 → 必定死锁
若存在环，但资源有多个实例 → 可能死锁（需进一步判断）
3.5.4 死锁的处理策略
死锁处理 ──┬── 预防（Prevention） ← 破坏四条件之一，静态策略├── 避免（Avoidance） ← 银行家算法，动态策略├── 检测（Detection） ← 检测并恢复└── 忽略（Ignore） ← 鸵鸟算法（Ostrich Algorithm）
3.6 死锁预防 ⭐
3.6.1 破坏四个条件的方法
| 破坏的条件 |
方法 |
问题 |
| 破坏互斥 |
让资源可共享（如SPOOLing） |
不是所有资源都能共享 |
| 破坏请求保持 |
一次性分配所有资源（静态分配） |
资源利用率低，可能饥饿 |
| 破坏不可抢占 |
请求被拒时释放已有资源 |
实现复杂，状态难保存 |
| 破坏循环等待 |
资源有序分配（按编号升序申请） |
编号难定，增加编程负担 |
资源有序分配法：将所有资源编号：R1, R2, ..., Rm
规定：进程只能按编号递增顺序申请资源例：P1 先申请 R2，再申请 R5 ✅P1 先申请 R5，再申请 R2 ❌此方法破坏了循环等待条件，因为不可能形成环。
3.7 死锁避免 ⭐⭐⭐
3.7.1 安全状态
安全状态：系统能按某种进程推进顺序（安全序列），为每个进程分配其所需资源，直到所有进程都能顺利完成。
安全序列：<P1, P3, P4, P0, P2>
系统按此顺序可满足所有进程需求 → 系统处于安全状态不安全状态 ≠ 死锁，但不安全状态可能导致死锁
3.7.2 银行家算法 ⭐⭐⭐
数据结构：Available[m] // 每种资源的可用数量Max[n][m] // 各进程对各资源的最大需求Allocation[n][m] // 已分配Need[n][m] // 还需要 = Max - Allocation算法步骤（安全性检查）：① 设 Work = Available，Finish[i] = false② 找满足 Finish[i]=false 且 Need[i] ≤ Work 的进程 i③ 设 Work = Work + Allocation[i], Finish[i] = true④ 重复 ②③ 直至所有 Finish[i]=true（安全）或找不到（不安全）
3.7.3 银行家算法的两个子算法
| 算法 |
调用时机 |
功能 |
| 安全性算法 |
资源分配前 |
判断系统是否处于安全状态 |
| 资源请求算法 |
进程申请资源时 |
判断请求是否可满足（Need/Request/Available检查） |
// 资源请求算法伪代码
Request_i[j] // 进程Pi请求资源Rj的k个实例// Step 1: 请求是否超过声明需求？
if (Request_i > Need_i) → 错误// Step 2: 系统是否有足够资源？
if (Request_i > Available) → 等待// Step 3: 试探性分配
Available -= Request_i
Allocation_i += Request_i
Need_i -= Request_i// Step 4: 执行安全性算法
if (安全) → 正式分配
else → 回滚，Pi等待
⚠️ 银行家算法的问题：很少在实用OS中使用（进程最大需求难以预知、算法开销大）。
3.8 死锁检测与解除
3.8.1 死锁检测
对资源分配图进行化简，检测是否存在无法化简的环路。
资源分配图化简：① 找既不阻塞也不孤立的进程节点② 去除其所有分配边和请求边（该进程可完成）③ 重复直至无进程可化简④ 若仍有边残留 → 存在死锁
3.8.2 死锁解除
| 方法 |
说明 |
代价 |
| 进程终止 |
终止所有死锁进程（或逐个终止） |
损失已完成工作 |
| 资源抢占 |
从进程中抢占资源 |
需要回滚机制 |
挑选"牺牲"进程的原则：优先级低、已完成工作量少、剩余时间短、资源使用少、批处理型（非交互型）。
3.9 鸵鸟算法
鸵鸟算法（Ostrich Algorithm）：对死锁视而不见，假装系统中不存在死锁问题。
| 系统 |
策略 |
| UNIX/Linux |
一般不考虑死锁（应对用户程序引发的死锁能力有限） |
| Windows |
忽略死锁（依赖程序自身解决） |
理由：死锁发生的概率极低，而死锁处理的开销太大，从性价比考虑，"忽略"是合理的。
⭐ 本章小结
| 知识点 |
核心内容 |
| 三级调度 |
高级（作业）→ 中级（内存）→ 低级（进程） |
| 评价指标 |
周转时间、带权周转时间、等待时间、响应时间 |
| 调度算法 |
FCFS、SJF、优先级、HRRN、RR、多级反馈队列 |
| 死锁四条件 |
互斥、请求保持、不可抢占、循环等待 |
| 死锁预防 |
破坏四条件之一（静态策略） |
| 死锁避免 |
银行家算法——确保每次分配后系统仍处于安全状态 |
| 死锁检测 |
资源分配图化简法 |
| 鸵鸟算法 |
忽略死锁，实际OS的常见做法 |
📖 参考资料
| 教材 |
作者 |
相关章节 |
| 《计算机操作系统》（第4版） |
汤小丹 |
第3章 处理机调度与死锁 |
| 《操作系统概念》 |
Silberschatz |
CPU调度 & 死锁 |
| 《现代操作系统》 |
Tanenbaum |
调度 & 死锁 |
