第二十一课：死锁预防与死锁避免

---

第一部分：先理解"银行家算法"

为什么叫：

银行家算法？

来看一个故事。

假设：

你是一家银行。

你：

现在：

有：

100万元

来了：

三个客户。

A：

最多：

需要：

60万

B：

最多：

需要：

40万

C：

最多：

需要：

50万

注意：

这里说的是：

最多需要。

不是：

现在就要。

---

例如：

今天。

A：

先借：

30万

银行：

还能：

借。

因为：

还有：

70万

但是。

如果：

A：

后来：

又借：

30万。

B：

借：

40万。

C：

借：

50万。

银行：

是不是：

一下：

没钱了？

如果：

大家：

都没完成。

没人：

还钱。

银行：

是不是：

可能：

崩？

所以。

银行：

每借一次钱。

都会：

先想：

借给你之后，我还有没有办法保证所有人最终都能完成？

如果：

可以。

借。

如果：

不可以。

拒绝。

这就是：

银行家算法。

---

第二部分：什么叫安全状态？

教材定义：

存在一个安全序列，使所有进程都能顺利完成。

这一句话：

第一次看。

几乎：

没人懂。

我们：

换成人话。

---

假设：

三个进程：

P1

P2

P3

资源：

还剩：

5

如果：

操作系统：

发现：

可以：

这样安排。

P2

↓

完成

↓

释放资源

↓

P1

↓

完成

↓

释放资源

↓

P3

最后：

三个：

都能：

结束。

那么：

现在：

就是：

安全状态（Safe State）

注意。

不是：

一起完成。

而是：

存在：

一种：

执行顺序。

---

第三部分：什么叫安全序列？

刚才：

那个顺序。

P2

↓

P1

↓

P3

就是：

安全序列（Safe Sequence）

所以：

教材：

一定：

会考。

区别：

名称	含义
安全状态	存在至少一个安全序列
安全序列	一个能够让所有进程完成的执行顺序

很多同学：

会：

混。

---

第四部分：危险状态（Unsafe State）

很多人：

最容易：

误解。

危险状态：

是不是：

已经：

死锁？

不是！

一定：

记住。

危险状态 ≠ 死锁

为什么？

来看。

假设：

现在：

资源：

越来越少。

已经：

找不到：

安全序列。

那么：

现在：

就是：

危险状态。

但是。

如果：

后面：

有进程：

提前：

释放：

资源。

还是：

可能：

恢复。

所以：

危险：

只是：

可能：

死锁。

不是：

一定。

口诀：

安全状态 → 一定不会死锁。

危险状态 → 可能死锁，但不一定已经死锁。

这是考试最爱出的判断题。

---

第五部分：死锁预防

上一课：

我们学过：

死锁：

发生：

必须：

满足：

四个条件。

那：

最简单：

怎么办？

破坏其中一个条件。

这就是：

死锁预防（Deadlock Prevention）。

---

方法一：破坏"请求并保持"

规定：

所有进程：

必须：

一次：

申请：

全部资源。

例如：

你要：

打印机。

扫描仪。

必须：

一起申请。

不能：

先拿：

打印机。

再：

申请：

扫描仪。

这样：

就不会：

拿着一个。

等另一个。

是不是：

破坏了：

请求并保持？

---

缺点：

资源：

利用率：

低。

因为：

很多资源：

可能：

一直：

空着。

---

方法二：破坏"不可剥夺"

规定：

如果：

申请：

失败。

已经：

拿到：

的资源。

全部：

还回去。

以后：

重新：

申请。

例如：

已经：

拿着：

打印机。

申请：

扫描仪。

失败。

操作系统：

直接：

收回：

打印机。

这样：

别人：

可以：

继续。

---

缺点：

有些资源：

不能：

随便：

抢。

例如：

打印机：

已经：

打印：

一半。

抢走：

是不是：

坏了？

所以：

不是：

所有资源：

都适合。

---

方法三：破坏"循环等待"

规定：

所有资源：

编号。

例如：

R1

R2

R3

R4

规定：

必须：

按：

编号：

申请。

例如：

可以：

R1

↓

R2

↓

R3

不能：

反过来。

于是：

等待：

永远：

不会：

形成：

一个圈。

---

教材：

这一种：

最喜欢：

考。

第六部分：死锁避免

预防：

比较：

严格。

资源：

利用率：

低。

于是：

提出：

避免。

思想：

不是：

禁止。

而是：

每次：

申请。

先：

试一试。

如果：

借出去。

还能：

保持：

安全状态。

批准。

否则：

拒绝。

这就是：

银行家算法。

---

第七部分：银行家算法流程（思想版）

假设：

P1：

申请：

2个资源。

操作系统：

不会：

马上：

给。

而是：

先：

模拟。

假装：

已经：

给了。

然后：

检查：

有没有：

安全序列。

如果：

有。

真正：

分配。

如果：

没有。

恢复。

拒绝。

整个过程：

像：

银行：

审批：

贷款。

---

第八部分：为什么叫"避免"？

因为：

它：

不是：

死锁：

以后：

解决。

而是：

在：

发生：

之前。

避免：

进入：

危险状态。

所以：

叫：

Deadlock Avoidance（死锁避免）

---

第九部分：预防 vs 避免（★★★★★）

这是考试最喜欢考的表格。

项目	死锁预防	死锁避免
思想	破坏四个必要条件	不进入危险状态
是否限制申请	很严格	较灵活
资源利用率	较低	较高
是否需要知道最大需求	不需要	需要

最后一行：

一定：

记住。

银行家算法：

必须：

知道：

每个进程：

最多：

需要：

多少资源。

否则：

怎么：

模拟？

---

第十部分：口诀（★★★★★）

预防：

破坏条件

避免：

进入危险

银行家：

先模拟

后分配

一句口诀：

预防靠破坏，避免靠判断；先试再分配，安全才批准。

---

第十一部分：本课重点

必须掌握

✅ 安全状态：存在安全序列。

✅ 安全序列：一种能让所有进程完成的执行顺序。

✅ 危险状态：可能死锁，不等于已经死锁。

---

必须会区分

状态	是否一定死锁
安全状态	❌ 一定不会死锁
危险状态	❌ 不一定死锁
死锁状态	✅ 已经死锁

---

必须知道

死锁预防：

破坏四个必要条件。

死锁避免：

银行家算法。

第二十二课：银行家算法（计算题）

---

一、先认识四张表

银行家算法一定会给你四组数据。

例如：

进程	Max	Allocation
P0	7	3
P1	5	2
P2	3	2

还有：

Available = 3

很多同学：

第一眼：

就懵了。

其实：

每一列：

都很好理解。

---

① Max（最大需求）

表示：

这个进程最多需要多少资源。

例如：

P0：

Max = 7

说明：

P0：

这一生：

最多：

需要：

7 个资源。

不是：

现在。

而是：

最多。

---

② Allocation（已分配）

表示：

操作系统已经给了多少资源。

例如：

Allocation = 3

说明：

P0：

手里：

已经：

有：

3 个资源。

---

③ Need（还需要）

考试：

不会：

直接：

给。

需要：

自己：

算。

公式：

Need = Max - Allocation

例如：

Max = 7

Allocation = 3

那么：

Need = 4

意思：

P0：

还需要：

4 个资源。

---

④ Available（剩余资源）

表示：

系统：

现在：

还有：

多少：

空闲资源。

例如：

Available = 3

说明：

系统：

还能：

借出去：

3 个资源。

---

二、第一步：计算 Need

来看完整例子。

进程	Max	Allocation
P0	7	3
P1	5	2
P2	3	2

Available：

3

先算：

Need。

进程	Need
P0	4
P1	3
P2	1

因为：

7-3=4

5-2=3

3-2=1

第一步：

结束。

---

三、第二步：找能完成的进程

规则：

Need ≤ Available

谁：

满足。

谁：

先执行。

现在：

Available = 3

看看：

P0：

Need = 4

够吗？

不够。

---

P1：

Need = 3

够。

可以：

完成。

---

P2：

Need = 1

也够。

也可以。

说明：

这里：

有：

两个：

选择。

例如：

我们：

先选：

P2。

---

四、第三步：释放资源

P2：

完成。

是不是：

应该：

把：

之前：

占有：

的资源：

还回来？

P2：

Allocation：

2

所以：

系统：

资源：

增加。

原来：

Available = 3

现在：

变成：

3 + 2 = 5

注意：

增加的是 Allocation ，不是 Need。

因为归还的是已经占有的资源。

---

五、继续找

现在：

Available = 5

看看：

P0：

Need = 4

可以。

P1：

Need = 3

也可以。

例如：

选：

P1。

完成。

释放：

Allocation = 2

于是：

Available = 7

---

最后：

P0：

Need：

4

系统：

有：

7

完成。

释放：

3。

结束。

---

于是：

安全序列：

就是：

P2

↓

P1

↓

P0

这就是：

安全序列（Safe Sequence）

---

六、考试完整步骤

拿到题目。

一定：

按下面：

四步。

---

第一步

算：

Need

公式：

Need = Max - Allocation

---

第二步

找：

Need ≤ Available

的进程。

---

第三步

执行：

释放：

Allocation

更新：

Available

---

第四步

重复。

直到：

全部：

完成。

或者：

找不到：

任何：

可执行：

进程。

---

七、什么时候是不安全状态？

假设：

Available：

只有：

1

看看：

Need。

P0 = 4

P1 = 3

P2 = 2

有没有：

一个：

满足：

Need ≤ 1

没有。

于是：

没有：

任何：

进程：

可以：

完成。

说明：

找不到：

安全序列。

于是：

进入：

危险状态。

注意：

这里：

还是：

危险。

不是：

已经：

死锁。

---

八、银行家算法真正干什么？

假设：

P1：

申请：

一个资源。

操作系统：

不会：

马上：

给。

而是：

先：

模拟：

给了之后

重新：

计算：

Available。

重新：

计算：

安全序列。

如果：

还能：

找到：

安全序列。

批准。

否则：

拒绝。

九、多资源怎么办？

刚才：

我们：

只有：

一种资源。

实际考试：

一般：

三个资源。

例如：

A

B

C

表格：

变成：

进程	Max(A,B,C)	Allocation(A,B,C)
P0	(7,5,3)	(0,1,0)

Need：

仍然：

公式：

Need = Max - Allocation

只是：

每一种：

资源：

分别：

计算。

例如：

Need

=

(7,5,3)

-

(0,1,0)

=

(7,4,3)

判断：

也是：

逐列：

比较。

例如：

Need

(2,1,3)

Available

(3,2,4)

比较：

2≤3

1≤2

3≤4

全部：

成立。

才能：

执行。

只要有一种资源不够，就不能执行。

十、一张流程图

开始

↓

计算Need

↓

Need≤Available？

↓

是

↓

执行

↓

释放Allocation

↓

更新Available

↓

继续

↓

全部完成？

↓

是

↓

安全状态

──────────

否

↓

危险状态

---

十一、口诀（★★★★★）

银行家：

四步：

口诀。

先算Need

↓

找能完成

↓

归还Allocation

↓

继续循环

一句话：

算 Need，找进程，还资源，再循环。

---

十二、本课重点（★★★★★）

必须会：

四个量：

名称	含义	公式
Max	最大需求	已知
Allocation	已分配	已知
Need	尚需资源	Max − Allocation
Available	剩余资源	已知/动态更新

---

必须知道：

安全序列：

就是：

能够：

让：

所有：

进程：

全部：

完成：

的顺序。

---

必须知道：

更新：

Available：

加的是：

Allocation

不是：

Need。