操作系统2002--死锁

1、 死锁的定义死锁的定义 死锁的描述死锁的描述 死锁的预防和避免死锁的预防和避免 死锁的检测死锁的检测 死锁的解除死锁的解除一、死锁定义一、死锁定义死锁定义：死锁定义： 多个进程由于竞争资源（或者等待对多个进程由于竞争资源（或者等待对方消息）而造成的彼此无休止的互相等待，方消息）而造成的彼此无休止的互相等待，在无外力作用下，永远不能向前推进，这在无外力作用下，永远不能向前推进，这种僵持局面称为死锁。种僵持局面称为死锁。（也可以叙述为：一组进程处于死锁状态，（也可以叙述为：一组进程处于死锁状态，仅当这组中的每一进程都在等待一个事件，仅当这组中的每一进程都在等待一个事件，且这个事件仅被同组中的另一进

2、程所引发）且这个事件仅被同组中的另一进程所引发）例子：设有进程例子：设有进程P1P1、P2P2和和I/OI/O设备设备D DI I、D DO O P1 P2 P1 P2申请一台输入设备申请一台输入设备D DI I 申请一台输出设备申请一台输出设备D DO O 使用之使用之 释放输入设备释放输入设备D DI I 释放输出设备释放输出设备D DO O 申请一台输出设备申请一台输出设备D DO O申请一台输入设备申请一台输入设备D DI I使用之使用之释放输出设备释放输出设备D DO O释放输入设备释放输入设备D DI I例子：哲学家用餐问题例子：哲学家用餐问题定义信号量定义信号量 fork5: s

3、emaphorefork5: semaphore，初值均为，初值均为1 1。PROCESS Pibegin L1: 思考思考; P(fork i ); P(fork ( i +1 ) mod 5 ; 用餐用餐; V(fork i ); V(fork ( i +1 ) mod 5 ; goto L1;end;例子：生产者例子：生产者 消费者问题消费者问题（多缓冲区）（多缓冲区）定义：整型变量：定义：整型变量：k = 0, t = 0k = 0, t = 0 整型数组：整型数组：B0n-1B0n-1 信号量：信号量：SP = n, SG = 0 SP = n, SG = 0 PROCESS Pro

4、ducerbegin L1: produce a product; P(SP); Bk := product; k := (k + 1) mod n; V(SG); goto L1endPROCESS Consumerbegin L2: P(SG); Take a product form Bt; t := (t + 1) mod n V(SP); consumer; goto L2end能否这样改写：能否这样改写：定义：信号量：定义：信号量：mutex=1, empty=n full=0;mutex=1, empty=n full=0; PROCESS Producerbegin L1: p

5、roduce a product; P(mutex); P(empty); 送一个产品到有界缓冲区送一个产品到有界缓冲区; k := (k + 1) mod n; V(mutex); V(full); goto L1endPROCESS Producerbegin L1: produce a product; P(mutex); P(empty); 送一个产品到有界缓冲区送一个产品到有界缓冲区; k := (k + 1) mod n; V(mutex); V(full); goto L1end当缓冲区满时，生产者仍可顺利执行p(mutex)操作，于是它对缓冲区有控制权，然后，当它执行p(emp

6、ty)时，由于没有空缓冲区被挂起。能将这个生产者释放的是有一个消费者从缓冲区中取走一个产品，并执行v(empty)操作，但由于缓冲区已被生产者占用，出现了死锁。出现了死锁。死锁的必要条件：死锁的必要条件：互斥：资源是独占的且排它使用（至少有一个资源处互斥：资源是独占的且排它使用（至少有一个资源处于非共享方式）；于非共享方式）；占用并等待：已获得资源未获释放，又有新的申请请占用并等待：已获得资源未获释放，又有新的申请请求（至少存在一个进程，它至少占用一个以上的资源并求（至少存在一个进程，它至少占用一个以上的资源并等待得到另外的被其它进程占用的资源）；等待得到另外的被其它进程占用的资源）；非抢占：

7、进程已获得的资源只能由它自己释放，不允非抢占：进程已获得的资源只能由它自己释放，不允许剥夺（资源不可抢占）；许剥夺（资源不可抢占）；循环等待：在发生死锁时，必然存在一个进程资循环等待：在发生死锁时，必然存在一个进程资源的环形链，即前一个进程保持后一个进程所申请的资源的环形链，即前一个进程保持后一个进程所申请的资源（存在一组等待进程源（存在一组等待进程PP0 0，P P1 1，P Pn n ，其中，其中P P0 0要等要等待待P P1 1占用的资源，占用的资源，P P1 1等待等待P P2 2占用的资源，占用的资源，P Pn n等待等待P P0 0占占用的资源）。用的资源）。二、死锁的描述（资源

8、分配图方法）二、死锁的描述（资源分配图方法）死锁的一种描述方法资源分配图：死锁的一种描述方法资源分配图：资源分配图定义为资源分配图定义为G G（V V，E E），其中），其中V V是顶点集，是顶点集，E E是边集。是边集。顶点集分两类：集合顶点集分两类：集合SpSpPP1 1,P,P2 2,P,Pn n 包括系统中所有进包括系统中所有进程，集合程，集合SrSrRR1 1,R,R1 1,R,Rm m 包括系统中的所有资源。边集包括系统中的所有资源。边集E E中的每个元素均为有序对（中的每个元素均为有序对（P Pi i,R,Rj j）或（）或（R Rj j,P,Pi i）。若（）。若（P Pi i

9、,R,Rj j）EE说明进程说明进程P Pi i正等待系统分配资源正等待系统分配资源R Rj j，此边称作请求边；，此边称作请求边；若（若（R Rj j,P,Pi i）EE说明资源说明资源R Rj j的一个示例已分配给了进程的一个示例已分配给了进程P Pi i，此边称作分配边。此边称作分配边。R R1 1R R2 2P P1 1P P2 2R R1 1R R3 3R R2 2P P3 3P P2 2P P1 1p2p1p3r4r2r3r1有死锁的资源分配图有死锁的资源分配图p2p1p3r4r2r3r1p1 r1 p2 r3 p3 r2 p1有环路但没有死锁的资源分配图有环路但没有死锁的资源分配

10、图 P1P3P2r2死锁产生的原因：死锁产生的原因：竞争资源引起死锁竞争资源引起死锁可剥夺和非剥夺性资源可剥夺和非剥夺性资源竞争非剥夺性资源竞争非剥夺性资源竞争临时性资源竞争临时性资源P1P2r1r2P1：; Release(S1); Request(S3); P2：; Release(S2); Request(S1); P3：; Release(S3); Request(S2); 不会发生死锁不会发生死锁P1：; Request(S3); Release(S1); P2：; Request(S1); Release(S2); P3：; Request(S2); Release(S3); 则可

11、能发生死锁则可能发生死锁P1P2s1s2P3s3进程推进顺序不当死锁进程推进顺序不当死锁进程推进顺序合法进程推进顺序合法进程推进顺序非法进程推进顺序非法 P1: P1req(R1) P1req(R2) P1rel(R1) P1rel(R2)P1: P2req(R2) P2req(R1) P2rel(R2) P2rel(R1)P1req(R1)P1req(R2)P1rel(R1)P1rel(R2)P2req(R2)P2req(R1)P2rel(R2)P2rel(R1)P1req(R1)P1req(R2)P1rel(R1)P1rel(R2)P2req(R2)P2req(R1)P2rel(R2)P2

12、rel(R1)P1req(R1) P1req(R2) P1rel(R1) P1rel(R2) P2req(R2) P2req(R1) P2rel(R2) P2rel(R1) 进程推进顺序不当进程推进顺序不当P1req(R1) P2req(R2) P1req(R2) P2req(R1) 用资源分配图讨论死锁问题，可得到如用资源分配图讨论死锁问题，可得到如下结论：下结论： 如果资源分配图中无环路，则系统中没如果资源分配图中无环路，则系统中没 有死锁发生有死锁发生 如果资源分配图有环路，且每个资源类如果资源分配图有环路，且每个资源类 中只有一个资源，则环路的存在就意味着中只有一个资源，则环路的存在就

13、意味着 死锁死锁 如果资源分配图有无环路，但涉及到的资如果资源分配图有无环路，但涉及到的资 源类中有多个资源，则环路的存在未必就源类中有多个资源，则环路的存在未必就 有死锁形成。有死锁形成。 例题例题： 考虑下列资源分配策略：对资源的申请和释放可考虑下列资源分配策略：对资源的申请和释放可以在任何时刻进行。如果一进程的资源得不到满足，则以在任何时刻进行。如果一进程的资源得不到满足，则检查所有由于等待资源而被阻塞的进程。如果它们有申检查所有由于等待资源而被阻塞的进程。如果它们有申请进程所需要资源，则将这些资源取出分配给申请进程。请进程所需要资源，则将这些资源取出分配给申请进程。例如，考虑一个有三类

14、资源的系统，系统所有可用资源例如，考虑一个有三类资源的系统，系统所有可用资源为（为（4 4，2 2，2 2），进程），进程A A申请（申请（2 2，2 2，1 1），可满足，进），可满足，进程程B B申请（申请（1 1，0 0，1 1），也可满足，若），也可满足，若A A再请求（再请求（0 0，0 0，1 1），则被阻塞。此时，若），则被阻塞。此时，若C C请求（请求（2 2，0 0，0 0），它可以），它可以分到剩余资源（分到剩余资源（1 1，0 0，0 0），并从），并从A A已分到的资源中获得已分到的资源中获得一个资源，于是，进程一个资源，于是，进程A A的分配向量变为（的分配向量变为（

15、1 1，2 2，1 1），），而需求向量变成（而需求向量变成（1 1，0 0，1 1）。）。 这种分配方式会导致死锁吗？如果会，请举一个例这种分配方式会导致死锁吗？如果会，请举一个例子；如果不会，请说明死锁的那一个必要条件不成立？子；如果不会，请说明死锁的那一个必要条件不成立？ 这种分配方式会导致某些进程的无限等待吗？这种分配方式会导致某些进程的无限等待吗？ 解答解答： 本方法不会产生死锁，因为它破坏了死锁的本方法不会产生死锁，因为它破坏了死锁的 不可抢夺条件。不可抢夺条件。 这种方法会导致某些进程无限期的等待。这种方法会导致某些进程无限期的等待。 例题例题： 一个操作系统有一个操作系统有20

16、20个进程，竞争使个进程，竞争使用用6565个同类资源，申请方式是逐个进行的，个同类资源，申请方式是逐个进行的，一旦某进程获得它所需要的全部资源，立即一旦某进程获得它所需要的全部资源，立即归还所有资源。每个进程最多使用三个资源。归还所有资源。每个进程最多使用三个资源。若仅考虑这类资源，该系统有无可能全部死若仅考虑这类资源，该系统有无可能全部死锁，为什么？锁，为什么？ 解答解答：不会产生死锁：不会产生死锁 例题例题：一个计算机有：一个计算机有8 8台磁带机，它们由台磁带机，它们由N N个个进程竞争使用，每个进程可能需要三台磁带进程竞争使用，每个进程可能需要三台磁带机，请问机，请问N N为多少时，

17、系统没有死锁的危险？为多少时，系统没有死锁的危险？ 解答解答：当：当N N为为3 3或更少时，系统没有死锁的危或更少时，系统没有死锁的危险。险。解决死锁的基本方法解决死锁的基本方法A A、预防死锁预防死锁 破坏四个必要条件之一，防止发破坏四个必要条件之一，防止发生死锁（但可能导致资源利用率降低）。生死锁（但可能导致资源利用率降低）。B B、避免死锁避免死锁 在资源的动态分配过程中，采用在资源的动态分配过程中，采用某种方法防止系统进入不安全状态，比如银行某种方法防止系统进入不安全状态，比如银行家算法。家算法。C C、检测死锁检测死锁 允许死锁发生，但通过某种检测允许死锁发生，但通过某种检测机构及

18、时检测出死锁的发生，并精确的确定与机构及时检测出死锁的发生，并精确的确定与死锁有关的进程和资源，然后采取适当措施解死锁有关的进程和资源，然后采取适当措施解除死锁。除死锁。D D、解除死锁解除死锁 一般采用资源剥夺和资源抢占方一般采用资源剥夺和资源抢占方式。解除死锁需付出代价，原则上以代价越小式。解除死锁需付出代价，原则上以代价越小越好。越好。 三、死锁的预防和避免三、死锁的预防和避免 1 1、死锁的预防、死锁的预防思路是破坏四个必要条件之一（死锁的条件思路是破坏四个必要条件之一（死锁的条件1 1是固有的，是固有的，一般不能改变），或者在分配临界资源分之前，检查系一般不能改变），或者在分配临界资

19、源分之前，检查系统的状态，如是安全的，则分配之。统的状态，如是安全的，则分配之。破坏破坏“占用并等待占用并等待”条件条件 资源作为一个整体，一次性分配。优点是简单、安全、资源作为一个整体，一次性分配。优点是简单、安全、 易于实现，缺点是资源浪费严重，进程延迟运行。易于实现，缺点是资源浪费严重，进程延迟运行。 可制定相应的规则，例如，当一个进程（程序）申请可制定相应的规则，例如，当一个进程（程序）申请 某资源被拒绝，则必须释放已占用的资源，如需要再某资源被拒绝，则必须释放已占用的资源，如需要再 与其它所需资源一起申请。对与其它所需资源一起申请。对CPUCPU还可进行可剥夺分配还可进行可剥夺分配。

20、破坏破坏“非抢占非抢占”条件条件进程已经占有的资源，运行时可以暂时释放，以后进程已经占有的资源，运行时可以暂时释放，以后再次申请。问题：实现复杂，且要付出代价。由于再次申请。问题：实现复杂，且要付出代价。由于可能反复的释放和申请资源，因而可能极大的延迟可能反复的释放和申请资源，因而可能极大的延迟进程的完成时间。进程的完成时间。 破坏破坏“循环等待循环等待”条件条件进程有序的申请资源。与前两种方法相比，资源的进程有序的申请资源。与前两种方法相比，资源的使用效率和系统性能都有较明显地改善。问题：限使用效率和系统性能都有较明显地改善。问题：限制了新设备的增加；用户需求与系统规定有冲突；制了新设备的增

21、加；用户需求与系统规定有冲突；对用户不方便。对用户不方便。系统的安全状态系统的安全状态安全状态安全状态一般地，称系统处于安全状态，仅当存在一个安全（进一般地，称系统处于安全状态，仅当存在一个安全（进程）序列程）序列PP1 1,P,P2 2,P,Pn n ，其中任一进程，其中任一进程P Pi i所可能请求的所可能请求的最大资源数可被当前可用资源加上所有最大资源数可被当前可用资源加上所有P Pj j（j ij i）已）已占用的资源所满足。占用的资源所满足。例子：三个进程，共有例子：三个进程，共有1212台设备台设备进程进程最大需求最大需求t0时分配时分配可用可用P1 11053P2 242P3 3

22、92不安全状态不安全状态当不存在上述的安全序列时，系统状态称之为不安全的。当不存在上述的安全序列时，系统状态称之为不安全的。注意：不安全状态不等于死锁，不安全状态仅仅意味着注意：不安全状态不等于死锁，不安全状态仅仅意味着系统将可能进入死锁状态。系统将可能进入死锁状态。 由安全状态向不安全状态的转换由安全状态向不安全状态的转换如果在如果在t t1 1时刻时刻P P3 3又申请又申请1 1台设备，若系统满足台设备，若系统满足P P3 3的要求，的要求，分配给分配给P P3 3一台设备，则系统将进入不安全状态。一台设备，则系统将进入不安全状态。 此时存在安全序列此时存在安全序列 P P2 2,P,P

23、1 1,P,P3 3 进程进程最大需求最大需求t0时分配时分配t1时分配时分配可用可用P1 110552P2 2422P3 3923因此，避免死锁就是找出安全状态和不安全状态的临因此，避免死锁就是找出安全状态和不安全状态的临界点，以确定能否分配资源界点，以确定能否分配资源。银行家算法银行家算法银行家算法的数据结构：银行家算法的数据结构：可利用资源向量可利用资源向量AvailableAvailable：m m个元素的数组，其中个元素的数组，其中每个元素代表一类可利用的资源数目，其数值随该类每个元素代表一类可利用的资源数目，其数值随该类资源的分配和回收而动态的改变，初值为系统中可利资源的分配和回收

24、而动态的改变，初值为系统中可利用的该类全部资源的数目。如用的该类全部资源的数目。如AvailablejAvailablejk k，表示，表示R Rj j类资源全部有类资源全部有k k个。个。 最大需求矩阵最大需求矩阵MaxMax：n nm m矩阵，定义了系统中矩阵，定义了系统中n n个进个进程中每个进程对程中每个进程对m m类资源的最大需求。如类资源的最大需求。如Max(i,j)Max(i,j)k k，表示进程表示进程i i需要需要R Rj j类资源的最大数为类资源的最大数为k k个。个。分配矩阵分配矩阵AllocationAllocation：n nm m矩阵，定义了系统中每矩阵，定义了系统

25、中每一类资源当前已分配给每个进程的资源数。如果一类资源当前已分配给每个进程的资源数。如果Allocationi,jAllocationi,jk k，表示进程，表示进程i i当前已分得当前已分得R Rj j类资源类资源的数目为的数目为k k个。个。需求矩阵需求矩阵NeedNeed：n nm m矩阵，表示每个进程尚需的各矩阵，表示每个进程尚需的各类资源数。如果类资源数。如果Needi,jNeedi,jk k，表示进程，表示进程i i还需要还需要R Rj j类类资源资源k k个方能完成任务。个方能完成任务。 上述矩阵存在如下关系：上述矩阵存在如下关系： Needi,jNeedi,jMaxi,jMax

26、i,jAllocationi,jAllocationi,j银行家算法银行家算法：设设RequestRequesti i是进程是进程P Pi i的请求向量。如果的请求向量。如果RequestRequesti ijjk k，表示进程，表示进程P Pi i需要需要k k个个R Rj j类的资源。当类的资源。当P Pi i发出资源发出资源申请申请RequestRequesti i后，系统按下述步骤检查：后，系统按下述步骤检查：如果如果RequestRequesti i NeedNeedi i，则转步骤，则转步骤，否则认，否则认为出错（所需资源已超过宣布的最大值）。为出错（所需资源已超过宣布的最大值）。

27、如果如果RequestRequesti i AvailableAvailablei i，则转向步骤，则转向步骤，否则表示尚无足够资源，否则表示尚无足够资源，PiPi必须等待。必须等待。系统试探把资源分配给进程系统试探把资源分配给进程P Pi i，并修改下面数据，并修改下面数据结构中的数值：结构中的数值：AvailableAvailable RequestiAllocationAllocation RequestiNeedNeedi iNeedNeedi i RequestRequesti i系统执行安全性算法，检查资源分配后，系统执行安全性算法，检查资源分配后，系统是否处于安全状态。如安全，则

28、正式分系统是否处于安全状态。如安全，则正式分配，否则上述试探作废，恢复原来的资源分配，否则上述试探作废，恢复原来的资源分配状态，让进程配状态，让进程P Pi i等待。等待。 安全性算法：安全性算法：设初值：设初值：工作向量工作向量Work(Work(长度长度m) m) 表示系统可提供的资源数表示系统可提供的资源数目。目。WorkWork的初值为的初值为AllocationAllocation。向量向量Finish (Finish (长度长度n)n) 表示系统是否有足够的资源表示系统是否有足够的资源分配给进程，使之运行完成。初始的分配给进程，使之运行完成。初始的FinishiFinishifal

29、sefalse，当有足够的资源分配给当有足够的资源分配给P Pi i时，令时，令FinishiFinishiTrueTrue。从进程集合中找一个能满足下述条件的进程：从进程集合中找一个能满足下述条件的进程：FinishiFinishifalsefalseNeedNeedi i WorkWork如找到，执行步骤如找到，执行步骤，否则执行步骤，否则执行步骤。当进程当进程P Pi i获得资源后，顺利执行，直至完成并获得资源后，顺利执行，直至完成并释放出分配给它的资源，故应执行释放出分配给它的资源，故应执行 WorkWorkWorkWorkAllocationAllocationi i Finishi

30、 Finishitruetrue 转步骤转步骤。如果所有进程的如果所有进程的FinishiFinishitruetrue，则表示系统，则表示系统处于安全状态，否则系统处于不安全状态。处于安全状态，否则系统处于不安全状态。 MAXA B CAllocationA B CNeedA B CAvailableA B CP0 07 5 30 1 07 4 33 3 2P1 13 2 22 0 01 2 2P2 29 0 23 0 26 0 0P3 32 2 22 1 10 1 1P4 44 3 30 0 24 3 1例子：现有五个进程例子：现有五个进程 P P0 0，P P1 1，P P2 2，P P

31、3 3，P P4 4 和和资源资源 A,B,C = 10 A,B,C = 10，5 5，7 7 。T T0 0时刻的资时刻的资源分配表为：源分配表为： T T0 0时刻的安全性时刻的安全性T T0 0时刻可找出安全序列时刻可找出安全序列 P P1 1，P P3 3，P P4 4，P P2 2，P P0 0 ，故，故此时系统是安全的。此时系统是安全的。 WorkA B CNeedA B CAllocationA B CWook+AllocationA B C FinishP1 13 3 21 2 22 0 05 3 2TrueP3 35 3 20 1 12 1 17 4 3TrueP4 47 4

32、 34 3 10 0 27 4 5TrueP2 27 4 56 0 03 0 210 4 7TrueP0 010 4 77 4 30 1 110 5 7TrueP P1 1请求请求RequestRequest1 1(1,0,2)(1,0,2)，系统按银行家算法检查：，系统按银行家算法检查： RequestRequest1 1(1,0,2) = Need(1,0,2) = Need1 1(1,2,2)(1,2,2) Request Request1 1(1,0,2) = Available(3,3,2)(1,0,2) = Available(3,3,2)假定可分配，修改假定可分配，修改Avail

33、ableAvailable，AllocationAllocation和和NeedNeed向量，向量，由此形成资源变化：由此形成资源变化： MAXA B CAllocationA B CNeedA B CAvailableA B CP0 07 5 30 1 07 4 32 3 0P1 13 2 23 0 20 2 0P2 29 0 23 0 26 0 0P3 32 2 22 1 10 1 1P4 44 3 30 0 24 3 1经安全性检查，可以找出一个安全序列经安全性检查，可以找出一个安全序列 P P1 1,P,P3 3,P,P4 4,P,P0 0,P,P2 2 。系统是安全的，可以实施分配。

34、系统是安全的，可以实施分配。 WorkA B CNeedA B CAllocationA B CWook+AllocationA B C FinishP1 12 3 00 2 03 0 25 3 2TrueP3 35 3 20 1 12 1 17 4 3TrueP4 47 4 34 3 10 0 27 4 5TrueP0 07 4 57 4 30 1 07 5 5TrueP2 27 5 56 0 03 0 010 5 7TrueP P4 4请求请求RequestRequest4 4(3,3,0)(3,3,0)，系统按银行家算法检查：，系统按银行家算法检查： RequestRequest4 4(

35、3,3,0) = Need(3,3,0) = Need4 4(4,3,1)(4,3,1) Request Request4 4(3,3,0) != Available(2,3,0)(3,3,0) != Available(2,3,0)P P4 4必须等待。必须等待。 P P0 0请求请求RequestRequest0 0(0,2,0)(0,2,0)，系统按银行家算法检查：，系统按银行家算法检查： RequestRequest0 0(0,2,0) = Need(0,2,0) = Need0 0(7,4,3)(7,4,3) Request Request0 0(0,2,0) = Available

36、(2,3,0)(0,2,0) 0 0。 对每一进程对每一进程P Pi i，1 = max1 = maxi i = m P - P3232 P P1212PP2323 - P - P1313P P3131PP1313 - P - P3333 直观的解释：资源分配图中如有环路直观的解释：资源分配图中如有环路存在，则发生死锁，环路上的进程都卷入存在，则发生死锁，环路上的进程都卷入死锁中死锁中. .P1 1P2 2P3 3P1 1011 P2 2001P3 311 1 2 2、资源类中含有若干个资源、资源类中含有若干个资源 可以利用把资源分配图加以简化的方法来检测系统可以利用把资源分配图加以简化的方法

37、来检测系统在某状态下是否处于死锁。在某状态下是否处于死锁。在资源分配图中，方框表示在资源分配图中，方框表示资源的类，方框中的点的个数表示资源的数量。我们可资源的类，方框中的点的个数表示资源的数量。我们可以通过对资源分配图的化简来判断系统是否处于死锁状以通过对资源分配图的化简来判断系统是否处于死锁状态，具体方法如下：态，具体方法如下： 在资源分配图中找出一个既不阻塞又非独立的进程在资源分配图中找出一个既不阻塞又非独立的进程结点结点P P，在顺利情况下，结点，在顺利情况下，结点P P可获得所需资源而继续执可获得所需资源而继续执行，直至运行完毕，在释放其占有的所有资源，这相当行，直至运行完毕，在释放

38、其占有的所有资源，这相当于消取于消取P P所有的请求边和分配边，使之称为孤立结点。所有的请求边和分配边，使之称为孤立结点。P P释放资源后，继续寻找下一个既不阻塞又非独立的结点，释放资源后，继续寻找下一个既不阻塞又非独立的结点，使它获得资源而继续执行，直至该结点完成后又释放出使它获得资源而继续执行，直至该结点完成后又释放出它所占用的全部资源。它所占用的全部资源。 在进行了一系列的简化后，若能消取图中所有的边，在进行了一系列的简化后，若能消取图中所有的边，使所有进程都成为孤立结点，则称该图为可完全简化的，使所有进程都成为孤立结点，则称该图为可完全简化的，否则该图使不可完全简化的。否则该图使不可完

39、全简化的。 第一步第一步 在资源分配图中找出一个既非阻塞又不孤立在资源分配图中找出一个既非阻塞又不孤立且它的资源申请数量可以得到系统满足的任何一个结且它的资源申请数量可以得到系统满足的任何一个结点点P Pi i，如果不存在这样的，如果不存在这样的P Pi i，则系统已经处于不安全，则系统已经处于不安全或死锁状态，检测结束。或死锁状态，检测结束。第二步第二步 去掉去掉P Pi i的所有请求边和分配边，使之成为孤的所有请求边和分配边，使之成为孤立结点，并在立结点，并在P Pi i所归还的资源的类方框中添加与归还所归还的资源的类方框中添加与归还资源数量相对应的圆点，然后转第一步。资源数量相对应的圆点

40、，然后转第一步。 如果所有结点都成为孤立结点，则称资源分配图如果所有结点都成为孤立结点，则称资源分配图可完全简化，否则为不可完全简化。可完全简化，否则为不可完全简化。 资源分配图的化简过程（或者说得到的进程化简资源分配图的化简过程（或者说得到的进程化简序列）可以不同，但可以证明，它们都将得到相同的序列）可以不同，但可以证明，它们都将得到相同的不可简化图。同样可以证明，系统的资源分配图不可不可简化图。同样可以证明，系统的资源分配图不可完全简化是死锁的充分条件。完全简化是死锁的充分条件。例子例子 P1 1P2 2r1 1r2 2P1 1P2 2r1 1r2 2a 结点结点P1 1既不阻塞也不孤既不

41、阻塞也不孤立立b 给给P1 1分配资源变请求边为分配资源变请求边为分配边分配边P1 1P2 2r1 1r2 2c P1 1释放资源成为孤立结点释放资源成为孤立结点P1 1P2 2r1 1r2 2d 给给P2 2分配资源变请求边为分配边分配资源变请求边为分配边P1 1P2 2r1 1r2 2e P2 2释放资源成为孤立结点释放资源成为孤立结点例子例子 P1 1P2 2r1 1r2 2a 初始态初始态P3 3r3 3P1 1P2 2r1 1r2 2b 变变P1 1的申请边为分配边的申请边为分配边P3 3r3 3P1 1P2 2r1 1r2 2c P1 1释放资源成为孤立结点释放资源成为孤立结点P3

42、 3r3r3P1 1P2 2r1 1r2 2d 无法继续化简无法继续化简P3 3r3 3对上述方法进行形式化，可分为三步来进行：对上述方法进行形式化，可分为三步来进行：第一步第一步 找出资源已经满足的进程，将它们所占找出资源已经满足的进程，将它们所占用的资源和系统中还剩余的资源加在一起作为用的资源和系统中还剩余的资源加在一起作为“可分配的资源可分配的资源”，对这些处理过的进程加上标，对这些处理过的进程加上标志；志；第二步第二步 在新的在新的“可分配资源可分配资源”的约束下，继续的约束下，继续从未加上标志的进程中查找资源可以满足的进程，从未加上标志的进程中查找资源可以满足的进程，如果有这样的进程

43、，转第一步，否则转下一步；如果有这样的进程，转第一步，否则转下一步；第三步第三步 如系统中所有进程均有标志，表明系统如系统中所有进程均有标志，表明系统没有死锁，否则说明系统处于死锁状态，没有标没有死锁，否则说明系统处于死锁状态，没有标志的那一组进程就是死锁进程。志的那一组进程就是死锁进程。 死锁检测中的数据结构：死锁检测中的数据结构： 可利用资源向量可利用资源向量AvailableAvailable：表示了：表示了m m类资源中的类资源中的 每一类资源的可用数目。每一类资源的可用数目。 请求矩阵请求矩阵RequestRequest：一个：一个n nm m矩阵，用以表示进矩阵，用以表示进 程当前

44、对各类资源的请求数目。程当前对各类资源的请求数目。 分配矩阵分配矩阵AllocationAllocation：一个：一个n nm m矩阵，用以表示矩阵，用以表示 某一时刻的资源分配情况。某一时刻的资源分配情况。 工作向量工作向量WorkWork：表示系统可提供给进程继续运行：表示系统可提供给进程继续运行 的各类资源数目。的各类资源数目。 进程向量进程向量FinishFinish：记录进程当前是否还占有资源。：记录进程当前是否还占有资源。死锁检测算法死锁检测算法 work := available; L := Pi | allocationi = 0 requesti = 0 for all Pi !L do begin