目录

3.8  死锁的检测与解除

3.8.1  死锁的检测

3.8.2  死锁的解除

3.8  死锁的检测与解除

　　如果在系统中，既不采取死锁预防措施，也未配有死锁避免算法，系统很可能会发生死锁。在这种情况下，系统应当提供两个算法：
　　① 死锁检测算法。该方法用于检测系统状态，以确定系统中是否发生了死锁。
　　② 死锁解除算法。当认定系统中已发生了死锁，利用该算法可将系统从死锁状态中解脱出来。

3.8.1  死锁的检测

　　为了能对系统中是否已发生了死锁进行检测，在系统中必须：① 保存有关资源的请求和分配信息；② 提供一种算法，它利用这些信息来检测系统是否已进入死锁状态。
1. 资源分配图(Resource Allocation Graph)
　　系统死锁，可利用资源分配图来描述。

该图是由一组结点N和一组边E所组成的一个对偶G = (N, E)，它具有下述形式的定义和限制：
　　(1) 把N分为两个互斥的子集，即一组进程结点P={P1, P2, …, Pn}和一组资源结点R={R1, R2, …, Rn}，N = P∪R。在图3-19所示的例子中，P = {P1, P2}，R = {R1, R2}，N = {R1, R2}∪{P1, P2}。
　　(2) 凡属于E中的一个边e∈E，都连接着P中的一个结点和R中的一个结点，e = {Pi, Rj}是资源请求边，由进程Pi指向资源Rj，它表示进程Pi请求一个单位的Rj资源。E = {Rj, Pi}是资源分配边，由资源Rj指向进程Pi，它表示把一个单位的资源Rj分配给进程Pi。图3-19中示出了两个请求边和两个分配边，即E = {(P1, R2), (R2, P2), (P2, R1), (R1, P1)}。

 2．死锁定理
　　我们可以利用把资源分配图加以简化的方法(图3-19)，来检测当系统处于S状态时，是否为死锁状态。简化方法如下：
　　(1) 在资源分配图中，找出一个既不阻塞又非独立的进程结点Pi。在顺利的情况下，Pi可获得所需资源而继续运行，直至运行完毕，再释放其所占有的全部资源，这相当于消去Pi的请求边和分配边，使之成为孤立的结点。在图3-20(a)中，将P1的两个分配边和一个请求边消去，便形成图(b)所示的情况。

 (2)  P1释放资源后，便可使P2获得资源而继续运行，直至P2完成后又释放出它所占有的全部资源，形成图(c)所示的情况，即将P2的两条请求边和一条分配边消去。
　　(3) 在进行一系列的简化后，若能消去图中所有的边，使所有的进程结点都成为孤立结点，则称该图是可完全简化的；若不能通过任何过程使该图完全简化，则称该图是不可完全简化的。

3．死锁检测中的数据结构
　　死锁检测中的数据结构类似于银行家算法中的数据结构：
　　(1) 可利用资源向量Available，它表示了m类资源中每一类资源的可用数目。
　　(2) 把不占用资源的进程(向量Allocation=0)记入L表中，即Li∪L。
　　(3) 从进程集合中找到一个Requesti≤Work的进程，做如下处理：① 将其资源分配图简化，释放出资源，增加工作向量Work =Work + Allocation i。② 将它记入L表中。
　　(4) 若不能把所有进程都记入L表中，便表明系统状态S的资源分配图是不可完全简化的。因此，该系统状态将发生死锁。

3.8.2  死锁的解除

1. 终止进程的方法
　　1) 终止所有死锁进程
　　这是一种最简单的方法，即是终止所有的死锁进程，死锁自然也就解除了，但所付出的代价可能会很大。因为其中有些进程可能已经运行了很长时间，已接近结束，一旦被终止真可谓“功亏一篑”，以后还得从头再来。还可能会有其它方面的代价，在此不再一一列举。

        2) 逐个终止进程
　　稍微温和的方法是，按照某种顺序，逐个地终止进程，直至有足够的资源，以打破循环等待，把系统从死锁状态解脱出来为止。但该方法所付出的代价也可能很大。因为每终止一个进程，都需要用死锁检测算法确定系统死锁是否已经被解除，若未解除还需再终止另一个进程。另外，在采取逐个终止进程策略时，还涉及到应采用什么策略选择一个要终止的进程。选择策略最主要的依据是，为死锁解除所付出的“代价最小”。但怎么样才算是“代价最小”，很难有一个精确的度量。

2. 付出代价最小的死锁解除算法
　　一种付出代价最小的死锁解除算法如图3-21所示。