死锁的产生以及解决死锁的办法

前言：继续学习操作系统相关知识，做一个关于 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 周期性地执行死锁检测例程,检测系统中是否出现“环路等待”

如果出现「环路等待」就说明出现了死锁，解决死锁的办法就是

• 重启系统（最简单）
• 撤销进程、剥夺资源（有多种策略：比如按进程占用资源的大小，撤掉占用最少的）
• 进程回退策略（不现实）