产生死锁的原因和必要条件

1、1会计学产生死锁的原因和必要条件产生死锁的原因和必要条件一、竞争资源引起死锁一、竞争资源引起死锁1 1、可将系统中的资源分为两类：、可将系统中的资源分为两类：可剥夺性资可剥夺性资源和非剥夺性资源源和非剥夺性资源。 可剥夺性资源是指：某进程在获得这类资可剥夺性资源是指：某进程在获得这类资源后，该资源可被其他进程抢占。源后，该资源可被其他进程抢占。 如处理机、内存。优先权高的进程可以剥如处理机、内存。优先权高的进程可以剥夺优先权低的进程的处理机；内存区可由内存夺优先权低的进程的处理机；内存区可由内存管理程序把一个进程从一个存储区移到另一个管理程序把一个进程从一个存储区移到另一个存储区，即剥夺了该进

2、程原来占有的存储区。存储区，即剥夺了该进程原来占有的存储区。第2页/共63页 非剥夺性资源是指：进程一旦占有该资源非剥夺性资源是指：进程一旦占有该资源，就不可抢占，不管其它进程的优先权是否高，就不可抢占，不管其它进程的优先权是否高于当前进程，只能在该进程用完后自行释放。于当前进程，只能在该进程用完后自行释放。 如打印机、磁带机等。如打印机、磁带机等。 大多数情况下，我们所讲引起的死锁的资大多数情况下，我们所讲引起的死锁的资源竞争，是指对于非剥夺性资源的竞争。源竞争，是指对于非剥夺性资源的竞争。第3页/共63页2、竞争非剥夺性资源、竞争非剥夺性资源 若系统中只有一台打印机若系统中只有一台打印机R

3、1R1和一台磁带机和一台磁带机R2R2，可供进程，可供进程P1P1和和P2P2共享。假定共享。假定P1P1已占用了打已占用了打印机印机R1R1，P2P2占用了磁带机占用了磁带机R2R2。此时，若。此时，若P2P2继续继续要求打印机，要求打印机，P2P2将阻塞；将阻塞；P1P1若又要求磁带机，若又要求磁带机，P1P1也将阻塞。也将阻塞。 于是，于是，P1P1与与P2P2之间便形成了僵局，两个进之间便形成了僵局，两个进程都在等待对方释放出自己所需的资源，但它程都在等待对方释放出自己所需的资源，但它们又都因不能获得所需的资源而不能继续推进，们又都因不能获得所需的资源而不能继续推进，从而也不释放自己已

4、占用的资源，就进入了死从而也不释放自己已占用的资源，就进入了死锁状态。锁状态。第4页/共63页I/O设备共享时的死锁情况设备共享时的死锁情况P2P1R1R2 方块代表资源方块代表资源 圆圈代表进程圆圈代表进程 箭头从进程指向资箭头从进程指向资源，表示进程请求该源，表示进程请求该资源资源 箭头从资源指向进箭头从资源指向进程，表示该资源已分程，表示该资源已分配给进程配给进程第5页/共63页3、竞争临时性资源、竞争临时性资源 临时性资源，也称为消耗性资源，是指由临时性资源，也称为消耗性资源，是指由一个进程产生，被另一进程使用一短暂时间后一个进程产生，被另一进程使用一短暂时间后便无用的资源，如消息等。

5、便无用的资源，如消息等。 竞争临时性资源也可能引起死锁。竞争临时性资源也可能引起死锁。第6页/共63页例：例：S1、S2、S3是临时性资源，进程是临时性资源，进程P1产生消产生消息息S1，又要求接收，又要求接收S3；P3产生消息产生消息S3，又要求，又要求接收接收S2；P2产生消息产生消息S2，又要求接收，又要求接收S1。若消。若消息通信按以下顺序进行：息通信按以下顺序进行：P1:Release(S1);Request(S3);P2:Release(S2);Request(S1);P3:Release(S3);Request(S1);并不可能发生死锁。并不可能发生死锁。第7页/共63页若按以下

6、运行顺序：若按以下运行顺序：P1:Request(S3);Release(S1);P2:Request(S1);Release(S2);P3:Request(S2);Release(S3);则可能发生死锁则可能发生死锁P3P1S2S2P2S1进程通信时的死锁进程通信时的死锁第8页/共63页二、进程推进顺序不当引起死锁二、进程推进顺序不当引起死锁1、进程推进顺序合法、进程推进顺序合法例：在进程例：在进程P1和和P2并发执行时，如果按以下顺并发执行时，如果按以下顺序推进：序推进：P1 Request(R1); P1 Request(R2); P1 Release(R1); P1 Release(R

7、2);P2 Request(R2); P2 Request(R1); P2 Release(R2); P2 Release(R1); 则两个进程可顺利完成。如下图则两个进程可顺利完成。如下图4-16中的曲中的曲线线1 所示。所示。第9页/共63页第10页/共63页第11页/共63页第12页/共63页2、进程推进顺序非法、进程推进顺序非法 若并发进程若并发进程P1P1和和P2P2按曲线条所示的顺序推按曲线条所示的顺序推进，进，P1P1保持了资源保持了资源R1R1，P2P2保持了资源保持了资源R2R2，系统，系统处于不安全状态。处于不安全状态。 当当P1P1运行到运行到P1 Request(R2)

8、 P1 Request(R2) 时，将因时，将因R2R2已被已被P2P2占用而阻塞；当占用而阻塞；当P2P2运行到运行到P2 P2 Request(R1)Request(R1)时，又因时，又因R1R1已被已被P1P1占用而阻塞，占用而阻塞，于是发生了进程死锁。于是发生了进程死锁。第13页/共63页第14页/共63页系统中如果死锁发生，则一定同时存在下列系统中如果死锁发生，则一定同时存在下列四个条件，即死锁的必要条件：四个条件，即死锁的必要条件：（1 1）互斥条件）互斥条件（2 2）占有且申请条件）占有且申请条件（3 3）不可抢占条件）不可抢占条件（4 4）环路条件）环路条件第15页/共63页（

9、1 1）互斥条件）互斥条件 对于一个排它性资源，某一时刻最多只能对于一个排它性资源，某一时刻最多只能由一个进程占有，不能同时分配给两个以上的由一个进程占有，不能同时分配给两个以上的进程。如果此时还有其它进程要求该资源，要进程。如果此时还有其它进程要求该资源，要求者只能阻塞，直到占有该资源的进程放弃该求者只能阻塞，直到占有该资源的进程放弃该资源后，其它进程才能占有该资源。资源后，其它进程才能占有该资源。 如打印机是临界资源，各进程必须互斥地如打印机是临界资源，各进程必须互斥地使用。使用。第16页/共63页（2 2）请求和保持条件）请求和保持条件 进程已经保持了至少一个资源，但又申请进程已经保持了

10、至少一个资源，但又申请新的资源；而该资源已被另外进程占有，此时新的资源；而该资源已被另外进程占有，此时该进程阻塞；但是，它在等待新资源时，仍不该进程阻塞；但是，它在等待新资源时，仍不释放已保持的资源。释放已保持的资源。（3 3）不剥夺条件）不剥夺条件 进程所获得的资源，在未使用完毕之前，进程所获得的资源，在未使用完毕之前，不能被强行剥夺该资源；只能在该进程释放已不能被强行剥夺该资源；只能在该进程释放已获得的资源后，其它进程才可以使用。获得的资源后，其它进程才可以使用。第17页/共63页（4 4）环路等待条件）环路等待条件 如果死锁产生，则一定存在一个如果死锁产生，则一定存在一个“进程进程- -

11、资资源源”的环形链。即进程集合的环形链。即进程集合P0,P1,PnP0,P1,Pn，其，其中中P0P0等待等待P1 P1 所占有的资源，所占有的资源，P1P1等待等待P2P2所需的所需的资源，资源，Pn-1 Pn-1 等待等待Pn Pn 所占有的资源，所占有的资源，PnPn等等待待P0 P0 所占有的资源。所占有的资源。 以上四个条件是在死锁发生时同时出现的以上四个条件是在死锁发生时同时出现的，我们可以利用它的逆否命题，即：，我们可以利用它的逆否命题，即：四个条四个条件中只要有一个不满足，则死锁不会发生件中只要有一个不满足，则死锁不会发生。这正是我们预防死锁所需考虑的方法。这正是我们预防死锁所

12、需考虑的方法。第18页/共63页为保证系统的正常运行，应事先采取措施，为保证系统的正常运行，应事先采取措施，预防或避免死锁的发生。在系统已出现死锁后，预防或避免死锁的发生。在系统已出现死锁后，要及时检测到死锁并解除死锁。要及时检测到死锁并解除死锁。目前用于处理死锁问题的方法有以下几种：目前用于处理死锁问题的方法有以下几种： 1 1死锁的预防死锁的预防 2 2死锁的避免死锁的避免 3 3死锁的检测死锁的检测 4 4死锁的解除死锁的解除第19页/共63页3.6 3.6 预防死锁的方法预防死锁的方法3.6.1 3.6.1 预防死锁预防死锁一、摒弃一、摒弃“请求和保持请求和保持”条件条件1 1、实现方

13、法、实现方法 要求进程一次性申请整个运行进程中的全部要求进程一次性申请整个运行进程中的全部资源，只有申请到全部资源后，方可投入运行；资源，只有申请到全部资源后，方可投入运行；这样进程运行期间不会再提出资源要求。这样进程运行期间不会再提出资源要求。 只要有一种资源要求不能满足，则全部其它只要有一种资源要求不能满足，则全部其它资源都不分配给进程，而让该进程等待；这样，资源都不分配给进程，而让该进程等待；这样，进程等待期间未占有任何资源。进程等待期间未占有任何资源。第20页/共63页一、摒弃一、摒弃“请求和保持请求和保持”条件条件优点：优点：简单，易于实现，安全。简单，易于实现，安全。缺点：缺点：资

14、源严重浪费，进程延迟运行。资源严重浪费，进程延迟运行。第21页/共63页二、摒弃二、摒弃“不剥夺不剥夺”条件条件1 1、实现方法：、实现方法： 一个已保持了某些资源的进程，当它在提出一个已保持了某些资源的进程，当它在提出新的资源要求而不能得到立即满足时，必须释新的资源要求而不能得到立即满足时，必须释放它已经保持的所有资源，待以后需要时再重放它已经保持的所有资源，待以后需要时再重新申请。新申请。2 2、缺点：、缺点：实现复杂、代价高。实现复杂、代价高。第22页/共63页三、摒弃三、摒弃“环路等待环路等待”条件条件1 1、实现方法：、实现方法： 将所有的资源按类型进行线性排队，并赋将所有的资源按类

15、型进行线性排队，并赋予不同的序号；并规定进程的资源请求必须予不同的序号；并规定进程的资源请求必须按资源序号递增的次序提出。按资源序号递增的次序提出。 这样在所形成的资源分配图中，不可能再这样在所形成的资源分配图中，不可能再出现环路；在采用这种策略时，总有一个进出现环路；在采用这种策略时，总有一个进程占据了较高序号的资源，它继续请求的资程占据了较高序号的资源，它继续请求的资源必然是空闲的，因而进程可以一直向前推源必然是空闲的，因而进程可以一直向前推进。进。第23页/共63页优点：优点：资源利用率和系统吞吐量得到了提高。资源利用率和系统吞吐量得到了提高。缺点：缺点：、限制了新设备的增加。、限制了新

16、设备的增加。、系统为资源分配的序号与进程实际、系统为资源分配的序号与进程实际使用资源的顺序不同而造成资源浪费。使用资源的顺序不同而造成资源浪费。 、给用户编程带来了麻烦。、给用户编程带来了麻烦。第24页/共63页3.6.2 3.6.2 系统的安全状态系统的安全状态 预防死锁的方法都是施加了较强的限制条件预防死锁的方法都是施加了较强的限制条件而使实现简单，但损害了系统的性能。在避免而使实现简单，但损害了系统的性能。在避免死锁的方法中，所施加的限制条件较弱，有可死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。能获得令人满意的系统性能。 在避免死锁的方法中，把系统的状态分为安在避免

17、死锁的方法中，把系统的状态分为安全状态和不安全状态，只要能使系统始终处于全状态和不安全状态，只要能使系统始终处于安全状态，就可避免发生死锁。安全状态，就可避免发生死锁。第25页/共63页一、安全状态一、安全状态 在避免死锁的方法中，允许进程动态地申请在避免死锁的方法中，允许进程动态地申请资源，系统在进行资源分配之前，先计算资源资源，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会导致系统进入分配的安全性。若此次分配不会导致系统进入不安全状态，便将资源分配给进程；否则，进不安全状态，便将资源分配给进程；否则，进程等待。程等待。 所谓所谓“安全状态安全状态”，是指系统能按某种顺序，是

18、指系统能按某种顺序如如序列，来为每个进程分配其序列，来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺所需资源，直至最大需求，使每个进程都可顺序完成。序完成。 若系统不存在这样的安全序列，则称系统处若系统不存在这样的安全序列，则称系统处于不安全状态。于不安全状态。第26页/共63页 虽然并非所有不安全状态都是死锁状态，虽然并非所有不安全状态都是死锁状态，但当系统进入不安全状态时，便可能进而进但当系统进入不安全状态时，便可能进而进入死锁状态；反之，只要系统处于安全状态，入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态。系统便可避免进入死锁状态。 因此，避免死锁的实质在于：

19、因此，避免死锁的实质在于：如何使系统如何使系统不进入不安全状态不进入不安全状态。第27页/共63页二、安全状态举例二、安全状态举例 假定系统有三个进程假定系统有三个进程P1,P2,P3P1,P2,P3，共有，共有12 12 台磁台磁带机。进程带机。进程P1P1总共要求总共要求1010台磁带机，台磁带机，P2P2和和P3P3分别要分别要求求4 4台和台和9 9台。设在台。设在T T0 0时刻，进程时刻，进程P1P1、P2P2和和P3P3已分别已分别获得获得5 5台、台、2 2台和台和2 2台，如下表所示：台，如下表所示：进程进程最大需求最大需求已分配已分配可用可用P1P110105 53 3P2

20、P24 42 2P3P39 92 2第28页/共63页 经分析可以发现，在经分析可以发现，在T T0 0时刻，系统是安全时刻，系统是安全的。因为的。因为T T0 0时刻存在一个安全序列时刻存在一个安全序列 P2,P1,P3 P2,P1,P3 ，即只要系统按此序列分配，即只要系统按此序列分配资源，每个进程都可以顺利完成。资源，每个进程都可以顺利完成。第29页/共63页三、由安全状态向不安全状态的转换三、由安全状态向不安全状态的转换 当系统不按照安全序列分配资源时，则系统可能当系统不按照安全序列分配资源时，则系统可能由安全状态进入不安全状态。由安全状态进入不安全状态。进程进程最大需求最大需求 已分

21、配已分配可用可用P1P110105 53 3P2P24 42 2P3P39 92 2进程进程最大需求最大需求 已分配已分配 可用可用P1P110105 52 2P2P24 42 2P3P39 93 3T T0 0时刻安全状态时刻安全状态T T1 1时刻不安全状态时刻不安全状态第30页/共63页3.6.3 3.6.3 利用银行家算法避免死锁利用银行家算法避免死锁 最具有代表性的避免死锁的算法，是最具有代表性的避免死锁的算法，是DijkstraDijkstra的银行家算法。这是由于该算法可的银行家算法。这是由于该算法可能用于银行现金贷款而得名的。一个银行家能用于银行现金贷款而得名的。一个银行家把他

22、的固定资金贷给若干顾客。只要不出现把他的固定资金贷给若干顾客。只要不出现一个顾客借走所有资金后还不够，银行家的一个顾客借走所有资金后还不够，银行家的资金应是安全的。银行家需一个算法保证借资金应是安全的。银行家需一个算法保证借出去的资金在有限时间内可收回。出去的资金在有限时间内可收回。 第31页/共63页一、银行家算法中的数据结构一、银行家算法中的数据结构1 1可利用资源向量可利用资源向量AvailableAvailable 也称为空闲向量。这是一个含有也称为空闲向量。这是一个含有mm个元素的个元素的数组。其中的每一个元素，代表一类可利用的数组。其中的每一个元素，代表一类可利用的资源数目，其初始

23、值是系统中所配置的该类全资源数目，其初始值是系统中所配置的该类全部可用资源的数目。其数值随该类资源的分配部可用资源的数目。其数值随该类资源的分配和回收而动态地改变。和回收而动态地改变。 如果如果Availablej=KAvailablej=K，则表示系统中现有，则表示系统中现有 Rj Rj 类资源类资源 K K 个。个。 第32页/共63页2 2最大需求矩阵最大需求矩阵MaxMax 这是一个这是一个n nmm的矩阵，它定义了系统中的矩阵，它定义了系统中n n个个进程中的每一个进程对进程中的每一个进程对mm类资源的最大需求。类资源的最大需求。 如果如果Maxi,j=KMaxi,j=K，则表示第，

24、则表示第i i个进程需要个进程需要RjRj类类资源的最大数目为资源的最大数目为K K。3 3分配矩阵分配矩阵AllocationAllocation 也叫做占有矩阵。这也是一个也叫做占有矩阵。这也是一个n nmm的矩阵，的矩阵，它定义了系统中每一进程已占有的每一类资源数它定义了系统中每一进程已占有的每一类资源数。 如果如果Allocationi,j=KAllocationi,j=K，则表示第，则表示第i i个进程当个进程当前已分得前已分得R Rj j类资源的数目为类资源的数目为K K。第33页/共63页4 4需求矩阵需求矩阵NeedNeed 也叫做申请矩阵。这也是一个也叫做申请矩阵。这也是一个

25、n nmm的矩阵的矩阵，用以表示每一个进程尚需的各类资源数。，用以表示每一个进程尚需的各类资源数。 如果如果Needi,j=Needi,j=K K，则表示第，则表示第i i个进程还需要个进程还需要RjRj类资源类资源K K个，才能完成其任务。个，才能完成其任务。显然，以上三个矩阵之间存在如下关系：显然，以上三个矩阵之间存在如下关系：Needi,j = Maxi,j - Allocationi,j Needi,j = Maxi,j - Allocationi,j 第34页/共63页二、银行家算法二、银行家算法 设设RequestiRequesti是进程是进程PiPi的请求向量，如果的请求向量，如

26、果Requestij=KRequestij=K，表示进程，表示进程PiPi需要需要RjRj类型的资源的个类型的资源的个数为数为K K。这里要提及的是，。这里要提及的是，RequestiRequesti与与NeediNeedi的关的关系可能为以下三种情况：系可能为以下三种情况：（1 1）RequestiNeediRequestiNeedi：表示该进程的资源需求表示该进程的资源需求已超过它所宣布的最大值，因此认为出错。已超过它所宣布的最大值，因此认为出错。（2 2）Requesti=NeediRequesti=Needi：表示该进程现在对它所表示该进程现在对它所还需的全部资源一次申请完成。还需的全

27、部资源一次申请完成。（3 3）RequestiNeediRequestiNeedi：表示该进程现在对它所表示该进程现在对它所需资源再进行部分的申请，剩余的资源以后可再次需资源再进行部分的申请，剩余的资源以后可再次申请。申请。第35页/共63页 当进程当进程PiPi发出资源请求后，系统按下述步骤发出资源请求后，系统按下述步骤进行检查：进行检查：（1 1）如果）如果RequestiNeediRequestiNeedi，转向步骤，转向步骤(2)(2)；否则认为出错，因为它所需要的资源数已超过否则认为出错，因为它所需要的资源数已超过它所事先要求的最大值。它所事先要求的最大值。（2 2）如果）如果Req

28、uestiAvailableRequestiAvailable，转向步骤，转向步骤3 3；否则，表示尚无足够资源，；否则，表示尚无足够资源，PiPi须等待。须等待。第36页/共63页（3 3）假设系统将资源分配给）假设系统将资源分配给PiPi，则需修改如下，则需修改如下数据结构的值：数据结构的值：Available:= Available -Requesti;Available:= Available -Requesti;Allocationi:=Allocationi+Requesti;Allocationi:=Allocationi+Requesti;Needi:=Needi-Reques

29、ti;Needi:=Needi-Requesti;（4 4）系统执行安全性算法，检查若此次资源分）系统执行安全性算法，检查若此次资源分配后，系统是否处于安全状态。如果是安全的，配后，系统是否处于安全状态。如果是安全的，则将资源真正地分配给进程则将资源真正地分配给进程PiPi，否则，将本进程，否则，将本进程的试探分配作废，恢复原来的资源分配状态，进的试探分配作废，恢复原来的资源分配状态，进程程PiPi等待。等待。第37页/共63页三、安全性算法三、安全性算法 系统所执行的安全性算法可描述如下：系统所执行的安全性算法可描述如下：（1 1）设置两个向量：）设置两个向量： 工作向量工作向量WorkWo

30、rk。 它表示在算法执行过程它表示在算法执行过程中，系统可提供给进程继续运行所需的各类中，系统可提供给进程继续运行所需的各类资源数目，它含有资源数目，它含有mm个元素，在执行安全算个元素，在执行安全算法开始时，初始置法开始时，初始置Work:=AvailableWork:=Available。 完成向量完成向量FinishFinish。 它表示系统能否运行它表示系统能否运行完成。它有完成。它有n n个分量，分别表示系统是否有个分量，分别表示系统是否有足够的资源分配给进程，使之运行完毕。足够的资源分配给进程，使之运行完毕。 开始时，开始时，Finishi:=falseFinishi:=false

31、；当有足够资源；当有足够资源分配给进程时，令分配给进程时，令Finishi:=trueFinishi:=true。第38页/共63页（2 2）从进程集合中找到一个能满足下述条件）从进程集合中找到一个能满足下述条件的进程的进程i i：Finishi=false; Finishi=false; NeediWork NeediWork； 若找到这样的进程，执行步骤（若找到这样的进程，执行步骤（3 3）；）； 若找不到这样的进程，则转步骤（若找不到这样的进程，则转步骤（4 4）。）。（3 3）当进程）当进程PiPi获得资源后，可顺序执行，直获得资源后，可顺序执行，直至完成，并释放出分配给它的资源，即执

32、行：至完成，并释放出分配给它的资源，即执行：Work:= Work+AllocationiWork:= Work+Allocationi；Finishi:= trueFinishi:= true；Go to Go to 步骤（步骤（2 2）；）； 第39页/共63页（4 4）若所有进程的）若所有进程的Finishi=trueFinishi=true，则表示，则表示系统处于安全状态，正式将资源分配给进程系统处于安全状态，正式将资源分配给进程PiPi；否则，系统处于不安全状态，系统不能；否则，系统处于不安全状态，系统不能进行这次试探性分配，恢复原来的资源分配进行这次试探性分配，恢复原来的资源分配状

33、态，让进程状态，让进程PiPi等待。等待。第40页/共63页四、银行家算法举例四、银行家算法举例 假定系统中有五个进程假定系统中有五个进程P0, P1, P2, P3, P4P0, P1, P2, P3, P4和三类资源和三类资源A, B, CA, B, C，各种资源的数量分别为，各种资源的数量分别为1010、5 5、7 7，在，在T T0 0时刻的资源分配情况如下图所示。时刻的资源分配情况如下图所示。第41页/共63页(1)(1)T T0 0时刻的安全性：时刻的安全性： 在在T T0 0时刻存在安全序列时刻存在安全序列P1P1，P3P3，P4P4，P2P2，P0 ,P0 ,因此系统是目前处于

34、安全状态。因此系统是目前处于安全状态。第42页/共63页第43页/共63页图 3-18 P1申请资源时的安全性检查 由所进行的安全性检查得知，可以找到一由所进行的安全性检查得知，可以找到一个安全序列个安全序列 P P ，P P ，P P ，P P ，P P 。因此，系统。因此，系统是安全的，可以立即将是安全的，可以立即将P1P1所申请的资源分配给所申请的资源分配给它。它。第44页/共63页第45页/共63页第46页/共63页图图 3-19 为为P0分配资源后的有关资源数据分配资源后的有关资源数据 第47页/共63页请思考：请思考： 在银行家算法中，把在银行家算法中，把P P0 0发出的请求向发

35、出的请求向量改为量改为RequstRequst0 0(0(0，1 1，0)0)，系统是否能，系统是否能将资源分配给它？将资源分配给它？第48页/共63页3.7 3.7 死锁的检测与解除死锁的检测与解除 3.7.1 3.7.1 死锁的检测死锁的检测 1.1.资源分配图资源分配图(Resource Allocation Graph) (Resource Allocation Graph) 系统死锁可利用资源分配图来描述。系统死锁可利用资源分配图来描述。 该图由一组结点该图由一组结点N N和一组边和一组边E E所组成的一对所组成的一对偶偶G=G=（N N，E E）。）。 第49页/共63页（1 1）

36、N N是顶点的集合，它被分为两个互斥的子集：是顶点的集合，它被分为两个互斥的子集：进程结点进程结点P=P1P=P1，P2P2，PnPn；资源结点；资源结点R=r1R=r1，r2r2，rn rn 。(2) E(2) E是有向边的集合。凡属于是有向边的集合。凡属于E E中的一个边中的一个边eEeE，都连接着都连接着P P中的一个结点和中的一个结点和R R中的一个结点。中的一个结点。 e=pi, rje=pi, rj是资源请求边，由进程是资源请求边，由进程pipi指向资源指向资源rj rj， 表示进程表示进程pipi请求一个单位的请求一个单位的rj rj资源。资源。 e=rj, pie=rj, pi

37、是资源分配边，由资源是资源分配边，由资源rj rj指向进程指向进程pi, pi, 它表示把一个单位的资源它表示把一个单位的资源rj rj分配给进程分配给进程pipi。 第50页/共63页图图3-20 3-20 每类资源有多个时的情况每类资源有多个时的情况 P1P2r1r2P= P1,P2P= P1,P2R= r1,r2R= r1,r2N= P1,P2U r1,r2N= P1,P2U r1,r2E= (p1,r2),(p2,r1)E= (p1,r2),(p2,r1)， (r1,p1),(r1,p2)(r1,p1),(r1,p2)， (r2,p2)(r2,p2) 第51页/共63页资源分配图的化简

38、方法：资源分配图的化简方法：假设某个资源分配图中存在一个进程假设某个资源分配图中存在一个进程PiPi，此刻此刻PiPi是非封锁进程，对非封锁进程是非封锁进程，对非封锁进程PiPi的化简的化简即删除资源分配图中与即删除资源分配图中与PiPi连结的所有有向边，连结的所有有向边，使使PiPi变成孤立结点，重复上述过程直到不能化变成孤立结点，重复上述过程直到不能化简为止。简为止。二、二、 死锁定理死锁定理 第52页/共63页 首先，在图首先，在图3-21(a)3-21(a)中找到一个非封锁进中找到一个非封锁进程程P1P1，删去其所有的有向边，使之成为孤立结，删去其所有的有向边，使之成为孤立结点。点。

39、即让即让P1P1获得所需的资源而继续执行，直到获得所需的资源而继续执行，直到运行完毕，再释放期所占有的全部资源；得到运行完毕，再释放期所占有的全部资源；得到如图如图3-21(b)3-21(b)所示。所示。(b)P1P2(a)P1P2第53页/共63页(c)P1P2(b)P1P2 由于由于P1P1进程释放了进程释放了R1R1资源从而唤醒资源从而唤醒P2P2进进程，使程，使P2P2也变成了非封锁进程，然后我们继也变成了非封锁进程，然后我们继续化简续化简P2P2，删去，删去P2P2的所有有向边，使的所有有向边，使P2P2也成也成了孤立结点，如图了孤立结点，如图3-21(c)3-21(c)所示。所示。

40、 第54页/共63页 在进行一系统的简化后，若能消去图中所在进行一系统的简化后，若能消去图中所有的边，使所有进程都成为孤立结点，则称该有的边，使所有进程都成为孤立结点，则称该图是可完全简化的；若不能通过任何过程使该图是可完全简化的；若不能通过任何过程使该图完全简化，则称该图是不可完全简化的。图完全简化，则称该图是不可完全简化的。不可简化的资源分配图不可简化的资源分配图第55页/共63页通过资源分配图，我们就可以很直观地看通过资源分配图，我们就可以很直观地看出系统中的进程使用资源的情况。很显然，如出系统中的进程使用资源的情况。很显然，如果图中不出现封闭的环路，则系统中不会存在果图中不出现封闭的环

41、路，则系统中不会存在死锁。死锁。 但如果系统出现由各有向边组成的环路，但如果系统出现由各有向边组成的环路，则是否产生死锁，还需进一步分析：如果环路则是否产生死锁，还需进一步分析：如果环路可以通过化简的方式取消，则系统一定不产生可以通过化简的方式取消，则系统一定不产生死锁；如果环路通过化简的方式仍不能取消，死锁；如果环路通过化简的方式仍不能取消，即不能再进行简化，则系统一定会产生死锁。即不能再进行简化，则系统一定会产生死锁。这就是著名的死锁定理。这就是著名的死锁定理。第56页/共63页三、三、 死锁检测中的数据结构死锁检测中的数据结构 (1) (1) 可利用资源向量可利用资源向量Availabl

42、eAvailable，它表示了，它表示了mm类资类资源中每一类资源的可用数目。源中每一类资源的可用数目。(2) (2) 把不占用资源的进程把不占用资源的进程( (向量向量Allocation=0)Allocation=0)记入记入L L表中，表中， 即即L Li iLL。(3) (3) 从进程集合中找到一个从进程集合中找到一个RequestRequesti iWorkWork的的进程，做如下处理：进程，做如下处理： 将其资源分配图简化，释放出资源，增加工将其资源分配图简化，释放出资源，增加工作向量作向量Work=Work+AllocationWork=Work+Allocationi i。 将

43、它记入将它记入L L表中。表中。 第57页/共63页(4) (4) 若不能把所有进程都记入若不能把所有进程都记入L L表中，表中， 便表明系便表明系统状态统状态S S的资源分配图是不可完全简化的。的资源分配图是不可完全简化的。 因因此，该系统状态将发生死锁。此，该系统状态将发生死锁。 第58页/共63页Work =Available; L =Li|Allocationi=0Requesti=0 for all Li L do begin for all RequestiWork do begin Work =Work+Allocationi; LiL; end end deadlock = (

44、L=p1, p2, , pn); 第59页/共63页3.7.2 3.7.2 死锁的解除死锁的解除 当发现有进程死锁时，便应立即把它们从死当发现有进程死锁时，便应立即把它们从死锁状态中解脱出来，常用的两种方法是：锁状态中解脱出来，常用的两种方法是：（1 1）剥夺资源。）剥夺资源。 从其它进程剥夺足够数量的资源给死锁进程，从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态。以解除死锁状态。（2 2）撤消进程。）撤消进程。 最简单的方法是：使全部死锁进程都夭折；最简单的方法是：使全部死锁进程都夭折； 另一种方法是：按照某种顺序逐个地撤消进程，另一种方法是：按照某种顺序逐个地撤消进程，直到有足够的

45、资源可用，死锁状态消除为止。直到有足够的资源可用，死锁状态消除为止。第60页/共63页 在出现死锁时，可采用各种策略来撤消进在出现死锁时，可采用各种策略来撤消进程。如撤消进程所付出的代价最小。为把系统程。如撤消进程所付出的代价最小。为把系统从死锁状态中解脱出来，所花费的代价可表示从死锁状态中解脱出来，所花费的代价可表示为：为： R(S)R(S)minmin=minC=minCuiui+minC+minCujuj+minC+minCukuk+ + 一个付出最小代价的方法如图一个付出最小代价的方法如图4-234-23所示。所示。第61页/共63页图图3-22 付出代价最小的死锁解除方法付出代价最小

46、的死锁解除方法 U1V12V13V1kW132W134W13kP2P3P2P4PkPkU2V21V22V2kW231W234W23kP1P4PkUkVk1Vk2VkkWk21Wk22Wk2kPkSP1(cu1)P1(cuk)P1(cud)第62页/共63页第63页/共63页第10页/共63页3.6 3.6 预防死锁的方法预防死锁的方法3.6.1 3.6.1 预防死锁预防死锁一、摒弃一、摒弃“请求和保持请求和保持”条件条件1 1、实现方法、实现方法 要求进程一次性申请整个运行进程中的全部要求进程一次性申请整个运行进程中的全部资源，只有申请到全部资源后，方可投入运行；资源，只有申请到全部资源后，方可投入运行；这样进程运行期间不会再提出资源要求。这样进程运行期间不会再提出资源要求。 只要有一种资源要求不能满足，则全部其它只要