目录

3.5  死 锁 概 述

3.5.1  资源问题

3.5.2  计算机系统中的死锁

3.5.3  死锁的定义、必要条件和处理方法

3.6  预 防 死 锁

3.6.1  破坏“请求和保持”条件 

3.6.2  破坏“不可抢占”条件 

 3.6.3  破坏“循环等待”条件     

3.7  避 免 死 锁

3.7.1　系统安全状态

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

---

3.5  死 锁 概 述

3.5.1  资源问题

　　在系统中有许多不同类型的资源，其中可以引起死锁的主要是，需要采用互斥访问方法的、不可以被抢占的资源，即在前面介绍的临界资源。系统中这类资源有很多，如打印机、数据文件、队列、信号量等。

1. 可重用性资源和消耗性资源
　　1) 可重用性资源
　　可重用性资源是一种可供用户重复使用多次的资源，它具有如下性质：
　　(1) 每一个可重用性资源中的单元只能分配给一个进程使用，不允许多个进程共享。
　　(2) 进程在使用可重用性资源时，须按照这样的顺序：① 请求资源。如果请求资源失败，请求进程将会被阻塞或循环等待。② 使用资源。进程对资源进行操作，如用打印机进行打印；③ 释放资源。当进程使用完后自己释放资源。
　　(3) 系统中每一类可重用性资源中的单元数目是相对固定的，进程在运行期间既不能创建也不能删除它。

2) 可消耗性资源
　　可消耗性资源又称为临时性资源，它是在进程运行期间，由进程动态地创建和消耗的，它具有如下性质：① 每一类可消耗性资源的单元数目在进程运行期间是可以不断变化的，有时它可以有许多，有时可能为0；② 进程在运行过程中，可以不断地创造可消耗性资源的单元，将它们放入该资源类的缓冲区中，以增加该资源类的单元数目。③ 进程在运行过程中，可以请求若干个可消耗性资源单元，用于进程自己的消耗，不再将它们返回给该资源类中。

2. 可抢占性资源和不可抢占性资源
　　1) 可抢占性资源
　　可把系统中的资源分成两类，一类是可抢占性资源，是指某进程在获得这类资源后，该资源可以再被其它进程或系统抢占。
　　2) 不可抢占性资源
　　另一类资源是不可抢占性资源，即一旦系统把某资源分配给该进程后，就不能将它强行收回，只能在进程用完后自行释放。

3.5.2  计算机系统中的死锁

　　1. 竞争不可抢占性资源引起死锁
　　通常系统中所拥有的不可抢占性资源其数量不足以满足多个进程运行的需要，使得进程在运行过程中，会因争夺资源而陷入僵局。

我们可将上面的问题利用资源分配图进行描述，用方块代表可重用的资源(文件)，用圆圈代表进程，见图3-12所示。

 2. 竞争可消耗资源引起死锁
　　现在进一步介绍竞争可消耗资源所引起的死锁。图3-13示出了在三个进程之间，在利用消息通信机制进行通信时所形成的死锁情况。

 3. 进程推进顺序不当引起死锁
　　除了系统中多个进程对资源的竞争会引发死锁外，进程在运行过程中，对资源进行申请和释放的顺序是否合法，也是在系统中是否会产生死锁的一个重要因素。

1) 进程推进顺序合法
　　在进程P1和P2并发执行时，如果按图3-14中的曲线①所示的顺序推进：P1：Request(R1)→P1：Request(R2)→P1：Releast(R1)→P1：Release(R2)→P2：Request(R2)→P2：Request(R1)→P2：Release(R2)→P2：Release(R1)，两个进程可顺利完成。类似地，若按图中曲线②和③所示的顺序推进，两进程也可以顺利完成。我们称这种不会引起进程死锁的推进顺序是合法的。

2) 进程推进顺序非法
　　若并发进程P1和P2按图3-14中曲线④所示的顺序推进，它们将进入不安全区D内。此时P1保持了资源R1，P2保持了资源R2，系统处于不安全状态。此刻，如果两个进程继续向前推进，就可能发生死锁。例如，当P1运行到P1：Request(R2)时，将因R2已被P2占用而阻塞；当P2运行到P2：Request(R1)时，也将因R1已被P1占用而阻塞，于是发生了进程死锁，这样的进程推进顺序就是非法的。

3.5.3  死锁的定义、必要条件和处理方法

    
　　1. 死锁的定义
　　在一组进程发生死锁的情况下，这组死锁进程中的每一个进程，都在等待另一个死锁进程所占有的资源。

2. 产生死锁的必要条件
　　虽然进程在运行过程中可能会发生死锁，但产生进程死锁是必须具备一定条件的。综上所述不难看出，产生死锁必须同时具备下面四个必要条件，只要其中任一个条件不成立，死锁就不会发生：
　　(1) 互斥条件。
　　(2) 请求和保持条件。
　　(3) 不可抢占条件。
　　(4) 循环等待条件。

3. 处理死锁的方法
　　目前处理死锁的方法可归结为四种：
　　(1) 预防死锁。
　　(2) 避免死锁。
　　(3) 检测死锁。
　　(4) 解除死锁。

3.6  预 防 死 锁

　　预防死锁的方法是通过破坏产生死锁的四个必要条件中的一个或几个，以避免发生死锁。由于互斥条件是非共享设备所必须的，不仅不能改变，还应加以保证，因此主要是破坏产生死锁的后三个条件。

3.6.1  破坏“请求和保持”条件 

　　为了能破坏“请求和保持”条件，系统必须保证做到：当一个进程在请求资源时，它不能持有不可抢占资源。该保证可通过如下两个不同的协议实现：
　　1. 第一种协议
　　该协议规定，所有进程在开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源。

2. 第二种协议
　　该协议是对第一种协议的改进，它允许一个进程只获得运行初期所需的资源后，便开始运行。

3.6.2  破坏“不可抢占”条件 

　　为了能破坏“不可抢占”条件，协议中规定，当一个已经保持了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。这意味着进程已占有的资源会被暂时地释放，或者说是被抢占了，从而破坏了“不可抢占”条件。 

 3.6.3  破坏“循环等待”条件     

　　一个能保证“循环等待”条件不成立的方法是，对系统所有资源类型进行线性排序，并赋予不同的序号。

3.7  避 免 死 锁

　　避免死锁同样是属于事先预防的策略，但并不是事先采取某种限制措施，破坏产生死锁的必要条件，而是在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。这种方法所施加的限制条件较弱，可能获得较好的系统性能，目前常用此方法来避免发生死锁。

3.7.1　系统安全状态

　　在死锁避免方法中，把系统的状态分为安全状态和不安全状态。当系统处于安全状态时，可避免发生死锁。反之，当系统处于不安全状态时，则可能进入到死锁状态。
　　1. 安全状态
　　在该方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。

2. 安全状态之例
　　假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：

 　　3. 由安全状态向不安全状态的转换
　　如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。

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

　　最有代表性的避免死锁的算法是Dijkstra的银行家算法。起这样的名字是由于该算法原本是为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。在OS中也可用它来实现避免死锁。

1. 银行家算法中的数据结构
　　为了实现银行家算法，在系统中必须设置这样四个数据结构，分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配，以及所有进程还需要多少资源的情况。
　　(1) 可利用资源向量Available。
　　(2) 最大需求矩阵Max。
　　(3) 分配矩阵Allocation。
　　(4) 需求矩阵Need。

2. 银行家算法
　　设Requesti是进程Pi的请求向量，如果Request i[j]=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：
　　(1) 如果Request i[j]≤Need[i, j]，便转向步骤(2)； 否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
　　(2) 如果Request i[j]≤Available[j]，便转向步骤(3)； 否则，表示尚无足够资源，Pi须等待。

 (3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：
      　Available[j] = Available[j] - Request i[j];
　  　Allocation[i, j] = Allocation[i, j] + Request i[j];
  　　Need[i, j] = Need[i, j] - Request i[j];
　　(4) 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

3. 安全性算法
　　系统所执行的安全性算法可描述如下：
　　(1) 设置两个向量：① 工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work := Available；② Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i] := false；当有足够资源分配给进程时，再令Finish[i] := true。

(2) 从进程集合中找到一个能满足下述条件的进程：
　　① Finish[i]=false;
　　② Need[i, j]≤Work[j];
　　若找到，执行步骤(3)，否则，执行步骤(4)。
　　(3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
　　　　Work[j] = Work[j]+Allocation[i, j];
　　　　Finish[i] =true;
　　　　go to step 2;
　　(4) 如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

4. 银行家算法之例
　　假定系统中有五个进程{P0, P1, P2, P3, P4}和三类资源{A, B, C}，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图3-15所示。

 (1)  T0时刻的安全性：利用安全性算法对T0时刻的资源分配情况进行分析(如图3-16所示)可知，在T0时刻存在着一个安全序列{P1, P3, P4, P2, P0}，故系统是安全的。

 (2)  P1请求资源：P1发出请求向量Request1(1, 0, 2)，系统按银行家算法进行检查：
　　① Request1(1, 0, 2)≤Need1(1, 2, 2)；
　　② Request1(1, 0, 2)≤Available1(3, 3, 2)；
　　③ 系统先假定可为P1分配资源，并修改Available，Allocation1和Need1向量，由此形成的资源变化情况如图3-15中的圆括号所示；
　　④ 再利用安全性算法检查此时系统是否安全，如图3-17所示。

 (3)  P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查：
　　① Request4(3，3，0)≤Need4(4，3，1)；
　　② Request4(3，3，0)＞Available(2，3，0)，让P4等待。
　　(4)  P0请求资源：P0发出请求向量Request0(0，2，0)，系统按银行家算法进行检查：
　　① Request0(0，2，0)≤Need0(7，4，3)；
　　② Request0(0，2，0)≤Available(2，3，0)；
　　③ 系统暂时先假定可为P0分配资源，并修改有关数据，如图3-18所示。

 ④ 进行安全性检查：可用资源Available(2，1，0)已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。