前言：继续学习操作系统相关知识，做一个关于 Deadlock 的总结
死锁是什么
用通俗的话说：死锁就是一组 进程/线程 都进行不下去了，都要等待自己这一组其他的 进程/线程 执行下去的局面
死锁产生的条件
想要解决死锁，我们得知道死锁产生的条件
-
互斥
如果相同的资源都不用互斥，也就不会产生死锁了，进程/线程 A 直接把进程 B 的资源拿走
-
保持并等待或资源保留
进程/线程 当前持有至少一个资源并请求其他进程持有的其他资源
-
没有释放
资源只能由持有它的进程自愿释放
-
循环等待
每个 进程/线程 必须等待另一个进程持有的资源，而该进程又等待第一个进程释放资源
其中最后一个条件是死锁产生的充分条件，如果产生了循环等待就一定会产生死锁
死锁的预防
我们从这个图就可以看出来，一旦死锁发生，除了强行剥夺某个 进程/线程 的资源，否则死锁是很难解决的。
但是一旦剥夺某个 进程/线程 的资源，实质上上让一个 进程/线程 之前的操作白白执行了
所以我们尽可能避免死锁产生，因此引入一个很经典的算法：银行家算法
下面详细介绍这个算法
银行家算法
银行家算法本质上是去如何如何给进程分配资源，从而避免死锁
首先我们得知道三个东西（括号里面的内容会在后面展示出来）：
- 每个进程可能请求的每个资源有多少（Claim Matrix）
- 每个进程当前持有多少资源（Allocation Matrix）
- 系统当前有多少资源可用（Available Vector）
银行家算法能从上面的必要条件按某种顺序如 <P1,P2,...,Pn> (称 <P1,P2,...,Pn> 为安全序列)，来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺序完成，则称系统处于 safe state。若系统不存在这样一个安全序列，则称系统处于 unsafe state。
算法举例
P 代表进程，R 代表资源
我举个例子告诉你这张图是什么意思：
从 Claim Matrix 中可以看到（仅仅是举例）：
-
P1 分别需要 3 个 R1 资源、2 个 R2 资源、3 个 R3 资源（Claim Matrix）
-
已经给 P1 分配了 1 个 R1 资源、0 个 R2 资源、0 个 R3 资源
-
系统还剩下 1 个 R1 资源、1 个 R2 资源、2 个 R3 资源
现在开始我们来银行家算法（真的不难）：
首先计算出需求矩阵（C - A）
| 2 | 2 | 2 |
| 1 | 0 | 2 |
| 1 | 0 | 3 |
| 4 | 2 | 0 |
还剩下的资源：
| 1 | 1 | 2 |
只能给 P2，P2 运行完并释放资源：
还需要的资源：
| 2 | 2 | 2 |
| 0 | 0 | 0 |
| 1 | 0 | 3 |
| 4 | 2 | 0 |
还剩下的资源：
| 2 | 0 | 4 |
可以给 P1 P3，我们假设给 P1
P1 执行完
还需要的资源：
| 0 | 0 | 0 |
| 0 | 0 | 0 |
| 1 | 0 | 3 |
| 4 | 2 | 0 |
还剩下的资源：
| 4 | 2 | 4 |
一直这样执行，直到能找到一个序列，能使这些 进程/线程 能够不出现死锁
这就是银行家算法，也有可能一开始在计算的过程中一开始能够分配，到后来就不能分配了，这个就像递归调用，如果这个不行，就回退，直到找到，
如果找不到，就是不安全的状态，如果找得到，就是安全状态
死锁的检测与解决
- 检测死锁不同于预防死锁，不限制资源访问方式和资源申请
- OS 周期性地执行死锁检测例程,检测系统中是否出现“环路等待”
如果出现「环路等待」就说明出现了死锁，解决死锁的办法就是
- 重启系统（最简单）
- 撤销进程、剥夺资源（有多种策略：比如按进程占用资源的大小，撤掉占用最少的）
- 进程回退策略（不现实）
网友评论