第3部分 处理机调度与死锁——知识点总结
依据老师课堂 PPT《第3部分 处理机调度与死锁》整理。
目标：把 PPT 中的概念、公式、算法、易考点和算法题思路压缩成便于复习的知识笔记。
一、章节结构
- 处理机调度概述
- 调度算法
- 实时调度
- 产生死锁的原因和必要条件
- 预防死锁和避免死锁
- 死锁的检测与解除
1. 处理机调度概述
1.1 什么是调度
当任务很多，但处理机等资源有限，无法同时处理所有任务，就需要按照一定规则决定任务的处理顺序。
处理机调度：
从就绪队列中按照某种调度算法选择一个进程，并把处理机分配给它运行。
核心目的：合理安排进程执行，实现并发执行，并兼顾系统性能与用户体验。
1.2 处理机调度的三个层次
| 层次 | 别名 | 核心作用 | 主要发生位置 |
|---|---|---|---|
| 高级调度 | 长程调度、作业调度 | 从外存后备队列选择作业，调入内存并建立进程 | 外存 → 内存 |
| 中级调度 | 中程调度、内存调度 | 决定哪些挂起进程重新调入内存 | 外存 ↔ 内存 |
| 低级调度 | 短程调度、进程调度、处理机调度 | 从就绪队列选择进程，把 CPU 分给它 | 就绪队列 → CPU |
高级调度
- 又称作业调度、长程调度。
- 从外存的作业后备队列中选择作业。
- 将作业调入内存并创建进程。
- 每个作业一般只调入一次、调出一次。
- 调入时建立 PCB，调出时撤销 PCB。
- 主要用于多道批处理系统。
**大白话：**很多程序排队等着启动，到底先把哪个装进内存？
中级调度
- 又称内存调度、中程调度。
- 内存不足时，可以把部分进程的数据调出到外存。
- 被调出的进程处于挂起状态。
- 挂起进程的 PCB 会组织成挂起队列。
- 内存空闲后，再决定哪些挂起进程重新调入。
- 一个进程可能多次调入、调出，因此频率高于高级调度。
低级调度
- 又称进程调度、处理机调度。
- 从就绪队列中选择进程。
- 给被选进程分配 CPU。
- 操作系统中最基本的调度。
- 调度频率很高，PPT 中给出的典型量级为几十毫秒一次。
- 多道批处理、分时、实时操作系统都需要。
2. 进程调度
2.1 进程调度的任务
主要有三个：
- 保存处理机现场信息
- 按某种调度算法选择进程
- 把处理机分配给被选中的进程
2.2 调度程序的组成
调度程序主要包括：
- 排队器：把就绪进程插入相应就绪队列。
- 分派器：把选中的进程移出就绪队列。
- 上下文切换器：完成新旧进程之间的上下文切换。
2.3 进程调度与进程切换
狭义进程调度
从就绪队列中选中一个要运行的进程。
进程切换
一个进程让出 CPU，由另一个进程占用 CPU。
主要完成：
- 保存原进程的处理机现场。
- 恢复新进程的处理机现场。
例如：
- 程序计数器 PC
- 程序状态字
- 各种数据寄存器
- 其他处理机现场信息
这些信息通常保存在 PCB 中。
广义进程调度
可以理解为：
选择进程 + 进程切换
重要
进程切换有系统开销。
如果调度、切换过于频繁，CPU 会花大量时间保存/恢复上下文，真正用于执行进程的时间反而减少。
3. 调度算法的评价指标
3.1 CPU 利用率
CPU 利用率：
CPU 忙碌时间 / 总时间
公式：
textCPU利用率 = CPU忙碌时间 / 总时间 × 100%
3.2 系统吞吐量
系统吞吐量：
单位时间内完成的作业数量。
公式：
text系统吞吐量 = 完成作业数 / 总时间
例如：
10 道作业共耗时 100 秒：
text10 / 100 = 0.1 道/秒
3.3 周转时间
周转时间：
从作业提交给系统开始，到作业完成为止的时间。
公式：
text周转时间 = 完成时间 - 到达/提交时间
周转时间包含：
- 外存后备队列等待作业调度的时间
- 就绪队列等待进程调度的时间
- CPU 执行时间
- 等待 I/O 的时间
操作系统通常还关注：
text平均周转时间 = 所有作业周转时间之和 / 作业数
3.4 等待时间
等待时间：
作业/进程处于等待处理机状态的时间总和。
对于进程：
text等待时间 = 周转时间 - CPU运行时间
如果进程同时存在 CPU 和 I/O：
text等待时间 = 周转时间 - CPU运行时间 - I/O操作时间
对于作业，还需要考虑建立进程前在外存后备队列中的等待时间。
3.5 带权周转时间
text带权周转时间 = 周转时间 / 运行时间
带权周转时间越大，说明相对于实际运行时间，等待等额外时间越多。
3.6 响应时间
响应时间：
从用户提交请求，到系统首次产生响应所需要的时间。
它是交互式系统非常重要的指标。
4. 调度算法总览
学习每一种调度算法，建议固定从 6 个方面记：
- 算法思想
- 算法规则
- 作业调度还是进程调度
- 抢占式还是非抢占式
- 优点和缺点
- 是否可能产生饥饿
5. 先来先服务 FCFS
5.1 核心思想
FCFS = First Come First Serve
谁先到，谁先执行。
类似排队买东西。
5.2 规则
按照到达顺序服务：
- 作业调度：比较进入后备队列的先后。
- 进程调度：比较进入就绪队列的先后。
非抢占式。
5.3 特点
优点：
- 公平
- 实现简单
缺点：
- 长作业排在前面时，会让后面的短作业等待很久。
- 对短作业不友好。
- 可能造成较大的带权周转时间。
5.4 是否饥饿
PPT 对 FCFS 的重点是公平性，一般不会因为大量短作业持续到达而让某个已经排队的进程永远得不到服务。
6. 短作业优先 SJF / SPF
6.1 核心思想
SJF = Shortest Job First
每次选择要求服务时间最短的作业。
用于进程调度时称：
SPF = Shortest Process First
6.2 规则
每次调度：
从当前已经到达的作业/进程中，选择运行时间最短的。
SJF / SPF：
- 非抢占式版本
- 也有抢占式版本：SRTN
6.3 最短剩余时间优先 SRTN
SRTN = Shortest Remaining Time Next
核心：
每当就绪队列发生变化，如果新到达进程的剩余运行时间比当前进程剩余时间更短，就抢占当前进程。
需要关注两个时机：
- 新进程到达
- 当前进程完成
6.4 SJF 的优缺点
优点：
- 平均等待时间较低
- 平均周转时间较低
- 平均带权周转时间较低
缺点：
- 不公平
- 对长作业不利
- 可能产生饥饿
- 运行时间通常由用户提供，不一定真实
为什么会饥饿？
如果源源不断地有短作业到达，长作业可能一直被短作业插队。
如果长期得不到服务，就可能出现：
饥饿 / 饿死
7. 高响应比优先 HRRN
HRRN = Highest Response Ratio Next
7.1 核心思想
同时考虑：
- 等待时间
- 要求服务时间
7.2 响应比公式
text响应比 = (等待时间 + 要求服务时间) / 要求服务时间
也可以写成：
text响应比 = 1 + 等待时间 / 要求服务时间
因此：
text响应比 ≥ 1
7.3 调度规则
每次调度：
- 计算所有就绪作业/进程的响应比。
- 选择响应比最高者。
特点：
- 可用于作业调度
- 可用于进程调度
- 非抢占式
7.4 为什么能兼顾 FCFS 和 SJF？
当等待时间相同时：
要求服务时间短的响应比更高 → 体现 SJF 特点。
当要求服务时间相同时：
等待时间长的响应比更高 → 体现 FCFS 特点。
长作业等待越久，响应比越大，因此 PPT 强调其可以避免长作业饥饿。
8. 时间片轮转 RR
RR = Round Robin
8.1 核心思想
公平地、轮流给各进程分配 CPU 时间片。
8.2 规则
按照就绪队列顺序：
textP1 → P2 → P3 → P4 → ...
每个进程运行一个时间片。
如果时间片用完仍未完成：
text当前进程被抢占↓重新进入就绪队列队尾↓下一个进程运行
RR 用于进程调度。
属于：
抢占式调度
通常由时钟中断通知 CPU 时间片结束。
8.3 优点
- 公平
- 响应快
- 适用于分时操作系统
8.4 缺点
- 进程切换频繁
- 有上下文切换开销
- 不区分任务紧急程度
8.5 时间片大小非常重要
时间片太大
如果一个进程基本都能在一个时间片内完成：
textRR → 逐渐退化为 FCFS
而且会增加响应时间。
时间片太小
会导致：
text进程切换次数过多↓上下文切换开销增加↓CPU 真正执行进程的时间减少
PPT 给出的设计原则：
进程切换开销占比一般不超过 1%。
9. 优先级调度算法
9.1 核心思想
每个作业/进程具有优先级：
每次选择优先级最高的进程。
可以用于：
- 作业调度
- 进程调度
- I/O 调度
9.2 抢占式 / 非抢占式
非抢占式
只有当前进程主动放弃 CPU 时才调度。
抢占式
除了当前进程主动放弃 CPU：
就绪队列发生变化时，还要检查是否应该发生抢占。
9.3 优先级类型
静态优先级
创建进程时确定，之后基本不改变。
动态优先级
创建时有初始优先级，之后根据运行情况动态调整。
9.4 优先级设置思路
PPT 给出的典型原则：
- 系统进程通常高于用户进程
- 前台进程通常高于后台进程
- 操作系统偏好 I/O 型进程
原因：
I/O 设备和 CPU 可以并行工作。
优先让 I/O 繁忙型进程运行，有利于让 I/O 设备尽早工作，从而提高资源利用率和系统吞吐量。
9.5 动态调整优先级
例如：
- 等待时间很长 → 提高优先级
- 占用 CPU 很久 → 适当降低优先级
- 频繁进行 I/O → 可以适当提高优先级
9.6 缺点
如果源源不断地有高优先级进程到达：
低优先级进程可能长期得不到服务 → 饥饿。
10. 多级反馈队列调度
这是 PPT 中用于综合权衡其他调度算法的重要算法。
10.1 核心规则
设置多个就绪队列：
text第1级：优先级最高，时间片最小第2级：优先级较低，时间片较大第3级：优先级更低，时间片更大...
规则一
新进程：
先进入第 1 级队列。
规则二
第 k 级队列的进程：
- 时间片用完且未完成
- → 降到第 k+1 级队列队尾
如果已经是最低级：
- → 重新放回最低级队尾
规则三
只有第 k 级队列为空时：
才调度第 k+1 级队列。
规则四
如果低级队列正在运行，而更高级队列出现新进程：
高级队列中的新进程抢占 CPU。
被抢占的进程：
放回原来的队列队尾。
10.2 特点
- 用于进程调度
- 抢占式
- 新进程能够较快得到响应
- 短进程更容易快速完成
- 不需要预先知道进程运行时间
- 可以灵活调整不同类型进程的优先级
PPT 将其视为对 FCFS、RR、SPF 等思路的综合权衡。
11. 多级队列调度
与多级反馈队列不同：
多级队列中的进程通常固定属于某一个队列。
11.1 基本思想
按照进程类型设置多个队列。
例如：
- 系统进程队列
- 交互式进程队列
- 批处理进程队列
11.2 队列之间的调度
可以采用：
固定优先级
高优先级队列为空后，低优先级队列才能运行。
时间片划分
例如：
text队列1：50%队列2：40%队列3：10%
11.3 每个队列可以使用不同算法
例如：
text系统进程 → 优先级调度交互式进程 → RR批处理进程 → FCFS
12. 各调度算法速记表
| 算法 | 核心思想 | 抢占 | 主要特点 | 饥饿 |
|---|---|---|---|---|
| FCFS | 先到先服务 | 否 | 公平、简单 | PPT重点不是此问题 |
| SJF/SPF | 最短作业优先 | 通常否 | 平均等待/周转时间较低 | 会 |
| SRTN | 最短剩余时间优先 | 是 | SJF 抢占式版本 | 会 |
| HRRN | 最高响应比优先 | 否 | 综合等待时间和运行时间 | PPT强调可避免长作业饥饿 |
| RR | 时间片轮流执行 | 是 | 公平、响应快 | 通常不突出 |
| 优先级 | 优先级最高者先运行 | 可抢占/不可抢占 | 可区分紧急程度 | 会 |
| 多级反馈队列 | 多级队列 + 动态降级 | 是 | 综合多种算法特点 | PPT未单独强调 |
13. 实时调度
13.1 什么是实时调度
实时调度：
针对实时任务进行调度。
实时任务通常都有一个：
截止时间（Deadline）
13.2 两类实时任务
硬实时 HRT
必须满足截止时间。
错过截止时间可能导致严重后果。
软实时 SRT
允许偶尔错过截止时间，但通常希望尽快完成。
14. 实时调度的基本条件
条件一：提供必要信息
调度程序需要知道：
- 就绪时间
- 开始截止时间 / 完成截止时间
- 处理时间
- 资源要求
- 优先级
条件二：系统处理能力强
PPT 给出的单处理机可调度条件：
textΣ(Ci / Pi) ≤ 1
其中：
Ci：任务处理时间Pi：任务周期时间
含义：
所有周期性硬实时任务的 CPU 利用率总和不能超过 1。
例子
6 个硬实时任务：
textC = 10msP = 50ms
则：
text(10/50) × 6 = 1.2 > 1
所以系统不可调度。
另一个例子：
text50/100 + 30/200 + 100/500= 0.85 ≤ 1
因此满足 PPT 给出的条件。
系统不可调度怎么办？
PPT 给出两种思路：
- 增强单处理机处理能力，减少每个任务的处理时间。
- 使用多处理机系统。
15. 实时系统为什么强调抢占？
硬实时系统中：
当更高优先级任务到达时，可以暂时挂起当前任务，让高优先级任务立即运行。
这样有利于满足截止时间要求。
但抢占机制实现更加复杂。
16. 实时系统的快速切换机制
需要：
① 快速响应外部中断
- 快速硬件中断机构
- 尽量缩短禁止中断的时间
② 快速任务分派
调度完成后快速完成任务切换。
17. 实时调度算法分类
按任务性质
- 硬实时调度
- 软实时调度
按调度方式
- 非抢占式调度
- 抢占式调度
18. EDF 最早截止时间优先
EDF = Earliest Deadline First
核心思想
截止时间越早，优先级越高。
既可以：
- 抢占式
- 非抢占式
PPT 中：
- 非抢占式：用于非周期实时任务
- 抢占式：用于周期实时任务
调度方法
维护实时任务就绪队列：
按截止时间从早到晚排序。
每次选择截止时间最早的任务运行。
19. LLF 最低松弛度优先
LLF = Least Laxity First
主要用于：
抢占式调度。
松弛度公式
text松弛度 = 必须完成时间 - 本身运行时间 - 当前时间
也就是：
textL = D - C - t
其中：
D：截止时间C：剩余需要运行的时间t：当前时间
调度规则
松弛度越低，任务越紧急，优先级越高。
20. 优先级倒置
使用优先级调度 + 抢占时，可能出现：
高优先级进程反而被低优先级进程延迟或阻塞。
PPT 给出的主要原因：
共享临界资源。
21. 死锁
21.1 什么是死锁
在并发环境中：
各进程因为竞争资源而互相等待对方手里的资源，导致各进程都阻塞、无法继续推进。
经典例子：
哲学家进餐问题
5 个哲学家同时拿起左边筷子：
textP1 等右边筷子P2 等右边筷子P3 等右边筷子P4 等右边筷子P5 等右边筷子
所有人都在等待，谁也无法继续。
这就是死锁。
22. 死锁、饥饿、死循环的区别
| 概念 | 含义 |
|---|---|
| 死锁 | 多个进程互相等待资源，全部阻塞 |
| 饥饿 | 某进程长期得不到所需资源，无法推进 |
| 死循环 | 程序一直执行某个循环，无法跳出 |
关键区别：
死锁强调“互相等待资源”；饥饿强调“长期得不到服务”；死循环强调“程序控制流无法退出循环”。
23. 死锁产生的四个必要条件
死锁必须同时满足以下四个条件：
- 互斥条件
- 不剥夺条件
- 请求和保持条件
- 循环等待条件
只要破坏其中任意一个：
死锁就不会发生。
23.1 互斥条件
某资源只能被一个进程使用。
例如：
- 打印机
- 某些独占设备
可以共享使用的资源通常不会因为互斥而导致这种死锁。
23.2 不剥夺条件
进程已经获得的资源：
在使用完之前，不能被其他进程强行夺走，只能由进程主动释放。
23.3 请求和保持条件
进程：
- 已经保持至少一个资源；
- 又请求新的资源；
- 新资源被其他进程占有；
- 自己已有资源仍然保持不放。
23.4 循环等待条件
存在一个进程—资源循环等待链：
textP1 等 P2 的资源P2 等 P3 的资源P3 等 P1 的资源
形成循环等待。
非常重要
死锁发生时一定存在循环等待。
但是：
循环等待不一定导致死锁。
当每类资源只有一个实例时，循环等待可作为死锁的充分必要条件；如果同类资源有多个实例，则有循环等待也未必死锁。
24. 死锁产生的原因
PPT 总结了三类典型原因：
① 对系统资源的竞争
不可剥夺资源的竞争可能导致死锁。
例如：
- 打印机
CPU 是可剥夺资源，对 CPU 的竞争不会导致这种资源死锁。
② 进程推进顺序非法
例如：
textP1 占有 R1，等待 R2P2 占有 R2，等待 R1
双方都无法继续。
③ 信号量使用不当
例如生产者—消费者问题中：
互斥 P 操作与同步 P 操作顺序使用不当，也可能产生死锁。
25. 死锁处理策略
主要有三种：
text预防死锁↓破坏四个必要条件中的一个或几个避免死锁↓防止系统进入不安全状态↓银行家算法检测和解除↓允许死锁发生↓检测到死锁后解除
26. 死锁预防
核心思想：
破坏死锁产生的四个必要条件中的一个或几个。
26.1 破坏互斥条件
方法：
把只能互斥使用的资源改造成允许共享使用。
典型技术：
SPOOLing
例如：
使用 SPOOLing 技术在逻辑上把独占设备打印机改造成共享设备。
缺点：
- 并非所有资源都能共享
- 某些资源为了系统安全必须保持互斥
26.2 破坏不剥夺条件
方法一
当进程申请新资源失败：
立即释放自己已经保持的全部资源，以后重新申请。
方法二
操作系统强制剥夺其他进程占有的资源。
缺点：
- 实现复杂
- 可能导致前面工作失效
- 反复申请、释放会增加系统开销
- 降低吞吐量
- 可能造成饥饿
这种方法通常更适合：
容易保存和恢复状态的资源，例如 CPU。
26.3 破坏请求和保持条件
采用：
静态资源分配方法
进程运行前：
一次申请它需要的全部资源。
只有全部资源满足后才允许运行。
缺点：
- 资源利用率低
- 有些资源可能很短时间才需要
- 可能导致饥饿
26.4 破坏循环等待条件
采用：
顺序资源分配法
给系统资源编号：
textR1 < R2 < R3 < ... < Rn
规定：
每个进程必须按照编号递增顺序申请资源。
这样可以避免出现：
text持有大编号资源 → 再反向申请小编号资源
从而破坏循环等待。
缺点：
- 增加设备时可能需要重新编号
- 实际资源使用顺序可能与编号顺序不同
- 编程不方便
- 可能造成资源浪费
27. 死锁避免
核心思想：
不破坏死锁必要条件，而是在资源分配时避免系统进入不安全状态。
经典算法：
银行家算法
28. 安全状态与安全序列
28.1 安全序列
安全序列：
如果系统按照某种顺序分配资源，可以让所有进程都顺利完成，那么这个进程顺序就是安全序列。
只要存在一个安全序列：
系统处于安全状态。
注意：
安全序列可能不止一个。
28.2 不安全状态
如果找不到任何安全序列：
系统处于不安全状态。
PPT 特别强调：
text不安全状态 ≠ 一定已经死锁
但：
text死锁 → 一定处于不安全状态
以及：
text安全状态 → 一定不会死锁
29. 银行家算法
假设：
- n 个进程
- m 种资源
29.1 四个核心数据结构
Available
textAvailable[j]
表示系统当前剩余的第 j 类可用资源数量。
Max
textMax[i][j]
表示进程 Pi 对资源 Rj 的最大需求。
Allocation
textAllocation[i][j]
表示已经给 Pi 分配了多少 Rj。
Need
textNeed = Max - Allocation
表示 Pi 还最多需要多少资源。
Request
textRequest[i][j]
表示 Pi 此次申请的资源数量。
30. 银行家算法步骤
进程 Pi 请求资源：
第一步
检查：
textRequest ≤ Need
如果超过之前声明的最大需求：
请求非法。
第二步
检查：
textRequest ≤ Available
如果当前没有足够的可用资源：
暂时不能分配，进程等待。
第三步
尝试分配资源。
临时修改：
textAvailableAllocationNeed
第四步
运行安全性算法：
检查分配后是否仍存在安全序列。
如果存在：
正式分配。
如果不存在：
撤销试探分配，让进程等待。
31. 银行家算法安全性检查
基本思路：
textWork = Available
寻找某个进程，使：
textNeed[i] ≤ Work
如果找到：
textWork = Work + Allocation[i]
说明假设 Pi 可以完成并释放资源。
然后继续找下一个进程。
最终：
- 所有进程都能加入 → 存在安全序列 → 安全
- 有进程始终无法满足 → 找不到安全序列 → 不安全
32. 死锁检测
如果系统既不预防，也不避免死锁：
就需要允许死锁发生，然后检测并解除。
需要：
- 数据结构记录资源请求和分配信息。
- 死锁检测算法。
33. 资源分配图检测死锁
PPT 给出的检测思路：
第一步
寻找一个：
既不阻塞、又不是孤点的进程 Pi。
如果该进程请求的每种资源数量都能由当前空闲资源满足：
假设它可以继续执行到结束。
第二步
消除它的：
- 请求边
- 分配边
并将它占有的资源释放。
释放出的资源可能使其他阻塞进程变为可运行。
第三步
不断重复。
如果：
所有边最终都能消除
则资源分配图：
可完全简化 → 没有死锁
如果：
最终无法继续消除所有边
则：
不可完全简化 → 系统发生死锁
最终仍连接着边的进程：
就是处于死锁状态的进程。
34. 死锁解除
检测到死锁后，需要解除。
PPT 给出三种主要方法。
34.1 资源剥夺法
- 挂起部分死锁进程
- 抢占其资源
- 把资源分配给其他死锁进程
注意：
防止被挂起进程长期得不到资源而产生饥饿。
34.2 撤销进程法
也称：
终止进程法。
强制撤销：
- 部分死锁进程
- 或全部死锁进程
并回收资源。
优点：
- 实现简单
缺点：
如果进程已经运行很长时间，终止它可能造成很大的工作损失。
34.3 进程回退法
让一个或多个死锁进程：
回退到足以解除死锁的历史状态。
要求系统：
- 保存历史信息
- 设置还原点
35. 最重要的公式
调度指标
textCPU利用率 = CPU忙碌时间 / 总时间 × 100%系统吞吐量 = 完成作业数 / 总时间周转时间 = 完成时间 - 到达时间带权周转时间 = 周转时间 / 运行时间等待时间 = 周转时间 - 运行时间
若存在 I/O：
text等待时间 = 周转时间 - CPU运行时间 - I/O时间
HRRN
text响应比 = (等待时间 + 要求服务时间) / 要求服务时间 = 1 + 等待时间 / 要求服务时间
实时调度
textCPU利用率 = Σ(Ci / Pi)
PPT 给出的单处理机可调度条件：
textΣ(Ci / Pi) ≤ 1
LLF
text松弛度 = 必须完成时间 - 本身运行时间 - 当前时间
银行家算法
textNeed = Max - Allocation
36. 考试重点：调度算法怎么判断
遇到题目，先看关键词：
“先到先服务”
→ FCFS
“运行时间最短”
→ SJF / SPF
“剩余运行时间最短”
→ SRTN
“等待时间 + 服务时间 / 服务时间”
→ HRRN
“时间片”
→ RR
“优先级最高”
→ 优先级调度
“多级队列、用完时间片降级”
→ 多级反馈队列
“截止时间最早”
→ EDF
“松弛度最低”
→ LLF
“银行家、Max、Allocation、Need、Available”
→ 银行家算法
“资源分配图、消边、能否完全简化”
→ 死锁检测
37. 抢占式 vs 非抢占式
非抢占式
当前进程：
一旦获得 CPU，通常一直运行到主动放弃 CPU。
典型：
- FCFS
- SJF
- HRRN
- 非抢占式优先级调度
抢占式
操作系统可以：
强制让当前进程让出 CPU。
典型：
- RR
- SRTN
- 抢占式优先级调度
- 多级反馈队列
38. 死锁三大处理方式
记忆：
text预防 → 破坏条件避免 → 银行家检测 → 发现后解除
39. 死锁预防的四个破坏点
| 必要条件 | 预防方法 |
|---|---|
| 互斥 | 尽可能改为共享资源，如 SPOOLing |
| 不剥夺 | 允许资源被剥夺 / 失败时释放已有资源 |
| 请求和保持 | 一次性申请全部资源 |
| 循环等待 | 按固定资源编号递增申请 |
记忆口诀：
互、不、请、环 → 共享、剥夺、一次申请、按序申请
40. 安全状态与死锁关系
最容易混淆：
text安全状态↓一定不会死锁不安全状态↓不一定已经死锁↓但可能进一步发展成死锁死锁状态↓一定是不安全状态
41. 一页速记版
处理机调度
text高级：作业调入内存中级：挂起进程 ↔ 内存低级：就绪进程 → CPU
调度指标
text利用率：CPU忙不忙吞吐量：单位时间完成多少周转时间：提交 → 完成等待时间：等CPU多久响应时间：提交 → 第一次响应带权周转：周转时间 / 运行时间
调度算法
textFCFS → 先来SJF → 最短SRTN → 剩余最短HRRN → 响应比最高RR → 时间片轮转Priority → 优先级最高MLFQ → 多级反馈EDF → 截止时间最早LLF → 松弛度最低
死锁
text四条件：互斥不剥夺请求和保持循环等待预防：破坏条件避免：银行家算法检测：资源分配图解除：资源剥夺撤销进程进程回退
42. 复习建议
本章建议重点掌握以下内容：
第一重点：调度算法
必须能够区分：
textFCFSSJF / SPFSRTNHRRNRR优先级调度多级反馈队列
尤其要会判断：
- 调度顺序
- 是否抢占
- 是否可能饥饿
- 适合什么场景
- 等待时间
- 周转时间
- 带权周转时间
第二重点：实时调度
重点记：
textHRT / SRTEDFLLFΣ(Ci/Pi) ≤ 1优先级倒置
第三重点：死锁
必须熟练：
text四个必要条件↓预防死锁↓银行家算法↓安全序列↓死锁检测↓死锁解除
结论
本章的核心逻辑可以压缩成：
text处理机调度 ↓如何决定“谁先运行” ↓FCFS / SJF / HRRN / RR / 优先级 / 多级反馈队列 ↓实时任务怎么办？ ↓EDF / LLF / 实时优先级调度 ↓多个进程争抢资源 ↓可能发生死锁 ↓四个必要条件 ↓预防 / 避免 / 检测与解除
一句话记忆：
调度解决“CPU先给谁”；
实时调度解决“任务必须什么时候完成”；
死锁解决“进程互相等资源，谁都走不了怎么办”。
