死锁

死锁

死锁：指多个进程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都讲无法向前推进。

如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的（Deadlock)。

计算机系统中的死锁

• 竞争不可抢占性资源引发死锁
• 竞争可消耗资源引起死锁
• 进程推进顺序不当引起死锁

产生死锁的必要条件

• 互斥条件。即在一段时间内，某资源只能被一个进程占用。
• 请求和保持条件。进程已经保持了至少一个资源，但又提出了新的资源请求，该资源已被其它进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。
• 不可抢占条件。
• 循环等待条件。在发生死锁时，必然存在一个进程-资源的循环链，即进程集合{p0,p1,…,pn}中的p0正在等待一个p1占用的资源，p1正在等待p2占用的资源，…pn正在等待已被p0占用的资源。

处理死锁的方法

目前处理死锁的方法可归结为四种。

预防死锁 ：实现预防方法，该方法通过设置某些限制条件，去破坏产生死锁四个必要条件中的一个或几个来预防产生死锁。

• 避免死锁：同样属于事先预防策略，在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而可以避免发生死锁。
• 检测死锁：允许运行过程中发生死锁。但可通过检测机构及时的检测出死锁的发生，然后采取适当的措施，把进程从死锁中解脱出来。
• 解除死锁：当检测到系统中已发生死锁时，就采取相应措施，将进程从死锁状态中解脱出来。常用的方法是撤销一些进程，回收它们的资源，将它们分配给已处于阻塞状态的进程，使其能继续运行。

预防死锁

由于互斥条件是非共享设备所必须的，不仅不能改变，还应加以保证，因此主要是破坏产生死锁的后三个条件。

• 破坏请求和保持

第一种协议：一次性申请其在整个运行过程中的全部资源。

第二种协议：允许一个进程只获得运行初期所需的资源后，便开始运行，进程运行过程中再逐步释放已分配给自己的、且已用毕的全部资源，然后再请求新的所需资源。

• 破坏不可抢占条件

当一个已经保持了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。

• 破坏循环等待条件

一个能保证“循环等待”条件不成立的方法是，对系统的所有资源类型进行线性排序，并赋予不同的序号，这样不可能再出现环路，因而破坏了“循环等待”条件。

避免死锁 （银行家算法）

避免死锁的基本思想： 确保系统始终处于安全状态，一个系统开始是处于安全状态的。当有进程请求一个可用资源时，系统需对该进程的请求进行计算，若将资源分配给进程后系统仍处于安全状态，才将该资源分配给进程。

利用银行家算法来避免死锁

当前序列是安全的，即当前状态不会发生死锁。此时如果某个进程请求资源，当前资源如果小于等于它需要的值，执行下一步，否则，返回异常；

继续判断需求的资源值是否小于等于系统中尚有的可用资源数，如果大于，则需等待其它进程释放资源，否则，系统试探性的将资源分配给该进程，并修改相应的资源数

接着系统调用安全判定算法，如果安全，也就是存在一个安全系列，资源分配成功；如果不安全，恢复原来的资源分配状态，让该进程继续等待。

银行家算法：

我们将第i个进程请求的资源数记为Requests[i]。

1.如果Requests[i]<=Need[i]，则转到第二步。否则，返回异常。这一步是控制进程申请的资源不得大于需要的资源。

2.如果Requests[i]<=Available，则转到第三步，否则表示尚无足够资源，pi需等待。

3.如果满足前两步，那么做如下操作：

系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：

Available = Available -Requests[i]   
Allocation = Allocation[i]+Requests[i]
Need[i]=Need[i]-Requests[i]

4.调用安全判定算法，检查是否安全

if(安全)
{
    申请成功，资源分配
}
else
{
    申请失败，资源撤回。第三步前几个操作进行逆操作
}

参考链接：银行家算法学习笔记

死锁的检测与解除

如果在系统中，既不采取死锁预防措施，也未配有死锁避免算法，系统很可能会发生死锁。在这种情况下，系统应当提供两个算法：
​

• 死锁检测算法。该方法用于检测系统状态，以确定系统中是否发生了死锁。
• 死锁解除算法。当认定系统中已发生了死锁，利用该算法可将系统从死锁状态中解脱出来。

检测死锁

系统死锁，可利用资源分配图来描述。如图所示，用圆圈代表一个进程，用框代表一类资源。由于一种类型的资源可能有多个，用框中的一个点代表一类资源中的一个资源。从进程到资源的有向边叫请求边，表示该进程申请一个单位的该类资源；从资源到进程的边叫分配边，表示该类资源已经有一个资源被分配给了该进程。

所示的资源分配图中，进程P1已经分得了两个R1资源，并又请求一个R2资源；进程P2分得了一个R1和一个R2资源，并又请求一个R1资源。

死锁定理
可以通过将资源分配图简化的方法来检测系统状态S是否为死锁状态。简化方法如下：

1) 在资源分配图中，找出既不阻塞又不是孤点的进程Pi（即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。若所有的连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源）。消去它所有的请求边和分配边，使之成为孤立的结点。在图2-18(a)中，P1是满足这一条件的进程结点，将P1的所有边消去，便得到图248(b)所示的情况。

2) 进程Pi所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。在图2-17中，进程P2就满足这样的条件。根据第1)条中的方法进行一系列简化后,若能消去图中所有的边，则称该图是可完全简化的，如图2-18(c)所示。

S为死锁的条件是当且仅当S状态的资源分配图是不可完全简化的,该条件为死锁定理。

死锁的解除

常采用解除死锁的两种方法：

• 抢占资源。从一个或多个进程中抢占足够数量的资源，分配给死锁进程，以解除死锁状态。
• 终止（或撤销）进程。终止（或撤销）系统中的一个或多个死锁进程，直到打破循环环路，使系统从死锁状态解脱出来。

1. 终止进程的方法

• 终止所有死锁进程
• 逐个终止进程