死锁的产生条件及解决办法_死锁的条件和解决方案

一、死锁产生的条件

死锁需要同时满足以下四个条件才会发生：

• 互斥条件
• 持有并等待条件
• 不可剥夺条件
• 环路条件

互斥：
指的是共享资源的互斥。
主要是因为多个线程都想访问同一个共享资源，但是该共享资源在某个时刻只能由一个进程访问。
持有并等待：
某进程持有一些资源并等待另外一些资源，在这一过程中，该进程并不会放弃自己已经持有的资源。
不可剥夺：
某线程持有的资源在其使用完之前不能被其他线程获取，只能由其自己使用完后释放。
环路等待：
两个或多个进程互相持有某些资源，并希望得到对方的资源，也可以说线程获取资源的顺序构成了环形链。

二、死锁解决的方法

• 死锁防止
• 死锁避免
• 死锁检测和恢复

1.死锁防止

防止是指在程序运行前就采取措施。
死锁防止主要策略是至少要破坏死锁产生的四个必要条件中的一个。

1.1 破坏互斥条件

使资源可以同时访问而不是互斥访问。
但是这种方法只适合只读资源，不能在独占性资源上采取。

1.2 破坏持有和等待条件

采用静态分配的方式，即进程必须在执行前申请所需的全部资源，否则不执行。
但是这种方式会严重降低资源的利用率，因为有些资源时在运行前期使用，而有些是在运行后期才使用的。

1.3 破坏不可剥夺条件

方法一：占有资源的进程若要申请新资源，必须主动释放已占有的资源。
方法二：资源分配管理程序为进程分配新资源时，若有则分配；否则将剥夺此进程已占有的全部资源，并让进程进入等待资源状态，资源充足后再唤醒它重新申请所有所需资源。

1.4 破坏等待循环条件

给系统所有资源编号，规定进程请求资源需按资源编号顺序进行。

2.死锁避免

避免是指在程序运行时采取的措施。
安全状态

图 a 的第二列 Has 表示已拥有的资源数，第三列 Max 表示总共需要的资源数，Free 表示还有可以使用的资源数。从图 a 开始出发，先让 B 拥有所需的所有资源（图 b），运行结束后释放 B，此时 Free 变为 5（图 c）；接着以同样的方式运行 C 和 A，使得所有进程都能成功运行，因此可以称图 a 所示的状态时安全的。

定义：如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。

安全状态的检测与死锁的检测类似，因为安全状态必须要求不能发生死锁。下面的银行家算法与死锁检测算法非常类似，可以结合着做参考对比。

单个资源的银行家算法
一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，算法要做的是判断对请求的满足是否会进入不安全状态，如果是，就拒绝请求；否则予以分配。

上图 c 为不安全状态，因此算法会拒绝之前的请求，从而避免进入图 c 中的状态。

多个资源的银行家算法

上图中有五个进程，四个资源。左边的图表示已经分配的资源，右边的图表示还需要分配的资源。最右边的 E、P 以及 A 分别表示：总资源、已分配资源以及可用资源，注意这三个为向量，而不是具体数值，例如 A=(1020)，表示 4 个资源分别还剩下 1/0/2/0。

检查一个状态是否安全的算法如下：

• 查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行，那么系统将会发生死锁，状态是不安全的。
• 假若找到这样一行，将该进程标记为终止，并将其已分配资源加到 A 中。
• 重复以上两步，直到所有进程都标记为终止，则状态是安全的。

如果一个状态不是安全的，需要拒绝进入这个状态。

3.死锁检测

不试图阻止死锁，而是检测到死锁发生时，采取措施进行恢复。
这里采用进程-资源分配图进行检测
进程资源分配图如果有环路，则有两类情况：

• 每种资源类中仅有一个资源，则系统发生了死锁。此时，环路是系统发生死锁的充分必要条件，环路中的进程就是死锁进程。
• 每种资源类中有多个资源，则环路的存在只是产生死锁的必要不充分条件，系统未必会发生死锁。

每种资源类只有一个资源的死锁检测：

上图为资源分配图，其中方框表示资源，圆圈表示进程。资源指向进程表示该资源已经分配给该进程，进程指向资源表示进程请求获取该资源。

图 a 可以抽取出环，如图 b，它满足了环路等待条件，因此会发生死锁。

比如：进程D需要的资源是U、T；进程G需要的资源是V、U；进程E需要的资源是T、V
此时进程D占有资源U，进程E占有资源T，进程G占有资源V
所以此时导致进程D、E、G所申请的资源不能得到全部满足，陷入死锁。

死锁检测：
每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。

每个资源类中有多种资源的情况：

每个资源类用一个方框表示，方框中的原点表示此资源类中的各个资源；

每个进程用一个圆圈来表示，用有向边表示进程申请资源和资源分配情况。

约定方框→圆圈表示资源分配，圆圈→方框表示申请资源。

这种情况下，图3-6 发生了死锁，而图3-7没有发生死锁。

我们可以看到上边的进程-资源分配图其实是可以进行简化的，也就是说可以在图中找到一个既不阻塞又不与其他进程因请求资源而关联的进程，可以认为该进程会获得所需全部资源而执行，并且在执行结束后释放其拥有的资源，这相当于消去与之相关的请求边和分配边，成为孤立点。而其他进程也因为得到了其释放的资源而得以运行去消去边成为孤立点，最后如果能消去图中所有的边，使所有进程成为孤立点，则进程是可以完全简化的。

系统处于死锁状态的充分条件是：当且仅当此状态的进程-资源分配图是不可完全简化的，这一充分条件成为死锁定理。

死锁检测算法

上图中，有三个进程四个资源，每个数据代表的含义如下：

• E 向量：资源总量
• A 向量：资源剩余量
• C 矩阵：每个进程所拥有的资源数量，每一行都代表一个进程拥有资源的数量
• R矩阵：每个进程请求的资源数量

进程 P1 和 P2 所请求的资源都得不到满足，只有进程 P3 可以，让 P3 执行，之后释放 P3 拥有的资源，此时 A = (2 2 2 0)。P2 可以执行，执行后释放 P2 拥有的资源，A = (4 2 2 1) 。P1 也可以执行。所有进程都可以顺利执行，没有死锁。

算法总结如下：

每个进程最开始时都不被标记，执行过程有可能被标记。当算法结束时，任何没有被标记的进程都是死锁进程。

1. 寻找一个没有标记的进程 Pi，它所请求的资源小于等于 A。
2. 如果找到了这样一个进程，那么将 C 矩阵的第 i 行向量加到 A中，标记该进程，并转回 1。
3. 如果没有这样一个进程，算法终止。

4.死锁恢复

• 资源剥夺法
• 进程回退法
• 进程撤销法
• 系统重启法

参考链接：
​死锁的产生、防止、避免、检测和解除