《产生死锁的原因和必要条件教案》由会员分享，可在线阅读，更多相关《产生死锁的原因和必要条件教案（64页珍藏版）》请在金锄头文库上搜索。
1、产生死锁的原因和必要条件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life, there is hope。有生命必有希望。有生命必有希望3.8 3.8 死锁问题死锁问题在在多多道道程程序序系系统统中中，多多个个进进程程并并发发运运行行，共共享享资资源源，从从而而提提高高了了资资源源的的利利用用率率。但但是是若若对对资资源源的的管管理理和和使使用用不不当当，在在一一定定条条件件下下会会导导致致系系统统发发生生一一种种随随机机性性故故障障死死锁锁。在在一一些些系系统统中中，比比如如实实时时控控制制系系统统，系系统统一一旦旦发发生
2、生死死锁锁将将导导致致灾难性的后果。灾难性的后果。23.8.1 死锁的基本概念死锁的基本概念资源死锁的定义产生死锁的原因产生死锁的必要条件处理死锁的基本方法3资源的概念OS是计算机系统中资源的管理者，而进是计算机系统中资源的管理者，而进程是竞争资源的基本单位，故对系统中程是竞争资源的基本单位，故对系统中所有进程的资源分配工作，都由所有进程的资源分配工作，都由OS完成。完成。研究资源分配时，我们必须搞清该资源研究资源分配时，我们必须搞清该资源是可以被几个进程同时使用，还是只能是可以被几个进程同时使用，还是只能为一个进程使用，资源的不同使用性质为一个进程使用，资源的不同使用性质正是引起系统死锁的原
3、因。正是引起系统死锁的原因。4根据资源性质：可剥夺（抢占）和不可剥夺根据资源性质：可剥夺（抢占）和不可剥夺（抢占）资源。（抢占）资源。可抢占资源可抢占资源指资源占有进程虽然需要使用该指资源占有进程虽然需要使用该资源，但另一个进程却强行把资源从占有者进资源，但另一个进程却强行把资源从占有者进程处抢来。程处抢来。不可抢占资源不可抢占资源指只有占用者进程不再需要使指只有占用者进程不再需要使用该资源而主动释放资源外，其它进程不得在用该资源而主动释放资源外，其它进程不得在占有者进程使用资源过程中强行抢占。占有者进程使用资源过程中强行抢占。资源的分类5 根据使用方式：共享资源和独享资源。根据使用方式：共享
4、资源和独享资源。根据使用期限；根据使用期限；永久资源永久资源和和临时性资源临时性资源。资源资源CPU、主存、硬盘，该类资源可为几个进程、主存、硬盘，该类资源可为几个进程共同使用（可抢占）共同使用（可抢占）打印机，读卡机，磁带驱动器，可为某个进打印机，读卡机，磁带驱动器，可为某个进程独享（不可抢占）程独享（不可抢占）可顺序重复使用的资源由一个进程产生，被另外一个进程使用短暂时间之后便无用的资源6死锁的定义死锁死锁Deadlock：是计算机系统中多道程序并发：是计算机系统中多道程序并发执行时，两个或两个以上的进程由于竞争资源执行时，两个或两个以上的进程由于竞争资源而造成的一种互相等待的现象（僵局）
5、，如无而造成的一种互相等待的现象（僵局），如无外力作用，这些进程将永远不能再向前推进。外力作用，这些进程将永远不能再向前推进。陷入死锁状态的进程称为陷入死锁状态的进程称为死锁进程死锁进程，所占用的，所占用的资源或者需要它们进行某种合作的其它进程就资源或者需要它们进行某种合作的其它进程就会相继陷入死锁，最终可能导致整个系统处于会相继陷入死锁，最终可能导致整个系统处于瘫痪状态。瘫痪状态。7产生死锁的原因1 竞争资源竞争资源。当系统中供多个进程所共享的资。当系统中供多个进程所共享的资源，不足以同时满足它们的需要时，引起它们源，不足以同时满足它们的需要时，引起它们对资源的竞争而产生死锁；对资源的竞争而
6、产生死锁；2 进程推进的顺序不当进程推进的顺序不当 。进程在运行过程中，。进程在运行过程中，请求和释放资源的顺序不当，导致进程的死锁。请求和释放资源的顺序不当，导致进程的死锁。8竞争资源1竞争非剥夺性资源：2竞争临时性资源打印机R1磁带机R2P1P29P1S1S3P2P3S2P1：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
7、)可能发生死锁S1、S2、S3是临时资源10 若干死锁的例子(1) 例进程推进顺序不当产生死锁 设系统有打印机、读卡机各一台，被进程和共享。两个进程并发执行，按下列次序请求和释放资源： 进程 进程 请求读卡机 请求打印机 请求打印机 请求读卡机 释放读卡机 释放读卡机 释放打印机 释放打印机11P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1) P1Rel(R2)进程P1、P2并发执行。资源R1、R2曲线4将进入不安全区域（进程推进顺序非法）12死锁模型死锁模型R1R2P1P2申请r2已分配给p2申请r1已分配给P1R
8、2已经分配给P1、R1已经分配给P213产生死锁的四个必要条件互互斥斥条条件件: :进进程程访访问问的的是是临临界界资资源源，那那个个资资源源一次只能被一个进程所使用。一次只能被一个进程所使用。不不剥剥夺夺条条件件: :一一个个资资源源仅仅能能被被占占有有它它的的进进程程所所释放，而不能被其他进程剥夺。释放，而不能被其他进程剥夺。部部分分分分配配: :（请请求求和和保保持持条条件件）一一个个进进程程在在请请求新的资源的同时，保持对某些资源的占有。求新的资源的同时，保持对某些资源的占有。环环路路等等待待条条件件: :存存在在一一个个进进程程的的环环路路链链，链链中中每每一一个个进进程程占占用用有
9、有着着某某个个或或某某些些资资源源，又又在在等等待链中的另一个进程占有的资源待链中的另一个进程占有的资源。14若干死锁的例子(2)例 PV操作使用不当产生死锁 进程Q1 进程Q2 P(S1); P(s2); P(s2); P(s1); 使用r1和r2; 使用r1和r2 V(S1); V(s2); V(S2); V(S1); 15若干死锁的例子(3)例 资源分配不当引起死锁 若系统中有m个资源被n个进程共享，每个进程都要求个资源，而m nK时，即资源数小于进程所要求的总数时，如果分配不得当就可能引起死锁。16若干死锁的例子(4)例对临时性资源使用不加限制引起死锁进程通信使用的信件是一种临时性资源
10、，如果对信件的发送和接收不加限制，可能引起死锁。进程P1等待进程P3的信件S3来到后再向进程P2发送信件S1；P2又要等待P1的信件S1来到后再向P3发送信件S2；而P3也要等待P2的信件S2来到后才能发出信件S3。这种情况下形成了循环等待，产生死锁。 173.6预防死锁的方法破坏第一个条件破坏第一个条件使资源可同时访问而不是互斥使用，是个简单的办法，磁盘可用这种办法管理,但有许多资源往往是不能同时访问，所以这种做法许多场合行不通。18死锁防止破坏第二个条件或第四个条件破坏第二个条件或第四个条件种种死锁防止办法施加于资源的限制条件太严格,会造成资源利用率和吞吐率低。两种比较实用的死锁防止方法，
11、它们能破坏第二个条件或第四个条件。19死锁防止1.摒弃”请求和保持”静态分配策略（破坏条件2） 静静态态分分配配是是指指一一个个进进程程必必须须在在执执行行前前就就申申请请它它所所要要的的全全部部资资源源，并并且且直直到到它它所所要要的的资资源源都得到满足后才开始执行。都得到满足后才开始执行。 20死锁防止2.摒弃”不剥夺”条件破坏第三个条件采用剥夺式调度方法可破坏第三个条件，但只适用于对主存资源和处理器资源的分配，当进程在申请资源未获准许的情况下,如主动释放资源(一种剥夺式),然后才去等待，以后再一起向系统提出申请,也能防止死锁。 21死锁的防止3.摒弃”环路等待”条件层次分配策略（破坏条件
12、2和4）资源被分成多个层次资源被分成多个层次当当进进程程得得到到某某一一层层的的一一个个资资源源后后，它它只能再申请较高层次的资源只能再申请较高层次的资源当当进进程程要要释释放放某某层层的的一一个个资资源源时时，必必须先释放占有的较高层次的资源须先释放占有的较高层次的资源当当进进程程得得到到某某一一层层的的一一个个资资源源后后，它它想想申申请请该该层层的的另另一一个个资资源源时时，必必须须先先释放该层中的已占资源释放该层中的已占资源22死锁防止层次层次策略的变种按序分配策略把系统的所有资源排一个顺序，例如，系统若共有n个进程,共有m个资源，用ri表示第i个资源，于是这m个资源是：r1,r2,r
13、m规定如果进程不得在占用资源ri(1im)后再申请rj(ji)。不难证明，按这种策略分配资源时系统不会发生死锁。 23 2 2 预防死锁预防死锁根根据据生生产产死死锁锁的的四四个个必必要要条条件件，只只要要使使用用其其中中之之一一不不能能成成立立，死死锁锁就就不不会会出出现现。但但必必要要条条件件是是由由设设备备的的固固有有特特性性所所决决定定的的，不不仅仅不不能能改改变变，相反还应加以保证，因此实际上只相反还应加以保证，因此实际上只有三种方法。有三种方法。 预防死锁是一种较易实现的方法，已被广泛预防死锁是一种较易实现的方法，已被广泛使用，但由于所施加的限制条件往往太严格，使用，但由于所施加的
14、限制条件往往太严格，可能导致系统资源利用率和系统吞吐量降低。可能导致系统资源利用率和系统吞吐量降低。1互斥条件2请求和保持条件3不剥夺条件4环路等待条件241:1:防止部分分配（摒弃请求和保持条件）防止部分分配（摒弃请求和保持条件） 系系统统要要求求任任一一进进程程必必须须预预先先申申请请它它所所需需的的全全部部资资源源，而而且且仅仅当当该该进进程程的的全全部部资资源源要要求求能能得得到到满满足足时时，系系统统才才能能给给予予一一次次性性分分配配，然然后后启启动动该该进进程程运运行行，但但是是在在分分配配时时只只要要由由一一种种资资源源不不满满足足，系系统统就就不不会会给给进进程程分分配配资资
15、源源。进进程程运运行行期期间间，不不会会再再请请求求新新的的资资源源，所所以以，再再分分配配就就不不会会发发生生（摒弃了部分分配）。（摒弃了部分分配）。特点：资源严重浪费特点：资源严重浪费 进程延迟进行进程延迟进行253 3 防止防止“不剥夺不剥夺”条件的出现条件的出现采用的策略：一个已经保持了某些资源的进程，采用的策略：一个已经保持了某些资源的进程，当它再提出新的资源要求而不能立即得到满足当它再提出新的资源要求而不能立即得到满足时，必须释放它已经保持的所有资源，待以后时，必须释放它已经保持的所有资源，待以后需要时再重新申请。需要时再重新申请。实现比较复杂，且要付出很大代价；此外，还实现比较复
16、杂，且要付出很大代价；此外，还因为反复地申请和释放资源，而使进程的执行因为反复地申请和释放资源，而使进程的执行无限地推迟，延长了周转时间，增加了系统的无限地推迟，延长了周转时间，增加了系统的开销，降低了系统吞吐量。（例如打印机打印开销，降低了系统吞吐量。（例如打印机打印的结果不连续）的结果不连续）262.2.防止防止“环路等待环路等待”条件的出现。条件的出现。 采采用用资资源源顺顺序序使使用用法法，基基本本思思想想是是：把把系系统统中中所所有有资资源源类类型型线线性性排排队队，并并按按递递增增规规则则赋赋予予每每类类资资源源以以唯唯一一的的编编号号。例例如如输输入入机机1 1，打打印印机机2
17、2，磁磁带带机机3 3，磁磁盘盘4 4等等等等。进进程程申申请请资资源源时时，必必须须严严格格按按资资源源编编号号的的递增顺序进行，否则系统不予分配。递增顺序进行，否则系统不予分配。优点：资源利用率和系统吞吐量与另两种方法相比有较优点：资源利用率和系统吞吐量与另两种方法相比有较明显的改善。明显的改善。缺点：缺点： 1 为系统中各种类型的资源所分配的序号必须相对稳为系统中各种类型的资源所分配的序号必须相对稳定，这就限制了新设备类型的增加定，这就限制了新设备类型的增加 2 作业实际使用资源的顺序与系统规定的顺序不同而作业实际使用资源的顺序与系统规定的顺序不同而造成资源的浪费；造成资源的浪费； 27
18、3 3 死锁避免死锁避免避避免免死死锁锁与与预预防防死死锁锁的的区区别别在在于于，预预防防死死锁锁是是设设法法至至少少破破坏坏产产生生死死锁锁的的必必要要条条件件之之一一，严严格格地地防止死锁的出现。防止死锁的出现。 避避免免死死锁锁，它它是是在在进进程程请请求求分分配配资资源源时时，采采用用银银行行家家算算法法等等防防止止系系统统进进入入不不安全状态。安全状态。28在资源的动态分配的过程中，使用某种方法去防止系统进入不安全状态，从而避免死锁的发生。系统状态：安全状态：指系统能按照某种顺序如(称为序列为安全序列)，为每个进程分配所需的资源，直至最大需求，使得每个进程都能顺利完成。非安全状态：即
19、在某个时刻系统中不存在一个安全序列，则称系统处于不安全状态或非安全状态。29虽然并非所有不安全状态都是死锁状态，但当系统进入不安全状态后，便有可能进入死锁状态；反之只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质是如何使系统不进入不安全状态。30安全状态的例子例：假定系统有三个进程P1、P2、P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和九台。设在T0时刻，进程P1、P2和P3已经获得5台、2台和2台，还有3台空闲没有分配。进程最大需求已分配可用P11053P2P34229T0时刻系统时安全的。这时存在一个安全序列31安全状态的例子例：假定系
20、统有三个进程P1、P2、P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和九台。设在T0时刻，进程P1、P2和P3已经获得5台、2台和2台，还有3台空闲没有分配。进程最大需求已分配可用P11053P2P34229T0时刻系统时安全的。这时存在一个安全序列32虽然并非所有不安全状态都是死锁状态，但当系统进入不安全状态后，便有可能进入死锁状态；反之只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质是如何使系统不进入不安全状态。系统的状态可能通过下述来描述：系统的状态可能通过下述来描述： 进程剩余申请数最大申请数占有数。进程剩余申请数最大申请数占有数。
21、可分配资源数总数占有数之和。可分配资源数总数占有数之和。333.6.3利用银行家算法避免死锁银行家算法银行家算法银行家拥有一笔周转资金银行家拥有一笔周转资金客客户户要要求求分分期期贷贷款款，如如果果客客户户能能够够得得到到各各期期贷贷款款，就就一一定定能能够够归归还还贷贷款款，否否则则就就一一定不能归还贷款定不能归还贷款银行家应谨慎的贷款，防止出现坏帐银行家应谨慎的贷款，防止出现坏帐用银行家算法避免死锁用银行家算法避免死锁操作系统（银行家）操作系统（银行家）操作系统管理的资源操作系统管理的资源( (周转资金周转资金) )进程（要求贷款的客户）进程（要求贷款的客户） 34银行家算法银行家算法银行
22、家算法是最有代表性的避免死锁算法，是Dijkstra提出的银行家算法。这是由于该算法能用于银行系统现金贷款的发放而得名。为实现银行家算法，系统中必须设置若干数据结构。35一、银行家算法中的数据结构1可利用资源向量Available是一个含有m个元素，其中的每一个元素代表一类可利用的资源数目，其初值是系统中所配 置 的 该 类 全 部 可 用 资 源 数 目 。 如 果Availablej=k，表示系统中现有Rj类资源k个。2最大需求矩阵Max是一个含有nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max(i,j)=k，表示进程i需要Rj类资源的最大数目为k。Avai
23、lable=354283861363分配矩阵Allocation是一个含有nm的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation(i,j)=k，表示进程i当前已分得Rj类资源k个。4需求矩阵Need是一个含有nm的矩阵，用以表示每一个进程尚需的各类资源数。如果Need(i,j)=k，表示进程i还需要Rj类资源k个，方能完成其任务。Need(i,j)=Max(i,j)-Allocation(i,j)37二、银行家算法设Requesti是进程Pi的请求向量，如果进程Pi需要K个Rj类资源，当Pi发出资源请求后，系统按下述步骤进行检查：1如果RequestiNee
24、di,则转向步骤2；否则认为出错。（因为它所需要的资源数已超过它所宣布的最大值。2如果RequestiAvailable,则转向步骤3；否则，表示系统中尚无足够的资源，Pi必须等待3系统试探把要求的资源分配给进程Pi，并修改下面数据结构中的数值：Available:=Available-Requesti;Allocation:=Allocation+Requesti;Needi:=Needi-Requesti;4系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，正式将资源分配给进程Pi，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。38三、安
25、全性算法系统所执行的安全性算法可描述如下：1设置两个向量工作向量Work.它表示系统可提供给进程继续运行所需要的各类资源 的 数 目 ， 它 含 有 m个 元 素 ， 执 行 安 全 算 法 开 始 时 ，Work:=Available。Finish.它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi:=false；当有足够的资源分配给进程时，令Finishi:=true.2 从 进 程 集 合 中 找 到 一 个 能 满 足 下 述 条 件 的 进 程 ：Finishi=false; NeediWork. 如找到，执行步骤3；否则执行步骤4。3 当进程Pi获得资源后
26、，可顺利执行，直至完成，并释放出分配给它的资源，故执行：Work:=Work+Allocation;Finishi:=true;Goto step2;4 如果所有进程的Finishi=true，则表示系统处于安全状态；否则，系统处于不安全状态。39要记住的一些变量的名称1Available（可利用资源向量）某类可利用的资源数目，其初值是系统中所配置的该类全部可用资源数目。2Max最大需求矩阵某个进程对某类资源的最大需求数3Allocation分配矩阵某类资源当前非配给某进程的资源数。4Need需求矩阵某个进程还需要的各类资源数。Need=Max-Allocation系统把进程请求的资源分配给它
27、以后要修改的变量Available:=Available-Request;Allocation:=Allocation+Request;Need:=Need-Request;40银行家算法之例假定系统中有五个进程P0、P1、P2、P3、P4和三种类型的资源A，B，C，每一种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图资源情况进程AllocationABCMaxABCNeedABCAvailableABCP0P1P2P3P4010322902222433200(302)302211002743122(020)600011431332(230)413 3 21 2 22 0 0资源情
28、况资源情况进程进程AllocationA B CMaxA B CNeedA B CAvailableA B CP0P1P2P3P40 1 03 2 29 0 22 2 24 3 32 0 0( 3 0 2 )3 0 22 1 10 0 27 4 31 2 2( 0 2 0 )6 0 00 1 14 3 13 3 2( 2 3 0 )7 5 3资源情况资源情况进程进程NeedA B CworkA B CWorkAllocationA B CAllocationA B CP1P3P4P2P0finish5 3 2truetruetruetruetrue0 1 12 1 15 3 27 4 37 4
29、 34 3 10 0 27 4 57 4 56 0 03 0 210 4 710 4 77 4 30 1 010 5 7最大值已分配还需要可用若P1发出请求向量Request（1，0，2）工作向量Work.它表示系统可提供给进程继续运行所需要的各类资源的数目10,5742思考和练习假定系统中有五个进程P0、P1、P2、P3、P4和三种类型的资源A，B，C，每一种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图请找出该表中T0时刻以后存在的安全序列（至少2种）资源情况资源情况进程进程AllocationA B CMaxA B CNeedA B CAvailableA B CP0P1P2
30、P3P40 1 03 2 29 0 22 2 24 3 32 0 03 0 22 1 10 0 27 4 31 2 26 0 00 1 14 3 13 3 27 5 343 3 3 死锁的检测和恢复死锁的检测和恢复 死锁的检测和恢复技术是指定期启动死锁的检测和恢复技术是指定期启动一个软件检测系统的状态，若发现有死一个软件检测系统的状态，若发现有死锁存在，则采取措施恢复之。锁存在，则采取措施恢复之。 (1) (1)死锁的检测死锁的检测 检查死锁的办法就是由软件检查系统检查死锁的办法就是由软件检查系统中由进程和资源构成的有向图是否构成中由进程和资源构成的有向图是否构成一个或多个环路，若是，则存在死
31、锁，一个或多个环路，若是，则存在死锁，否则不存在。否则不存在。44死锁的检测：实质是确定是否存在环路等待现象，一旦发现这种环路便认定死锁存在，并识别出该环路所涉及的有关进程，以供系统采取适当的措施来解除死锁。最常用的是一种基于资源分配图RAG和死锁定理的检测死锁算法。45资源分配图（RAG）系统死锁可用资源分配图来描述，该图是由一组结点N和一组边E所组成的一对偶G=(N,E)。（用圆圈代表一个进程，用方框代表一类资源，由于一种类型的资源可能有多个，可用方框中的一个点代表一类资源中的一个资源）几个概念：请求边，分配边P1P2r1r2请求r2资源分配图46封锁进程：是指某个进程由于请求了超过了系统
32、中现有的未分配资源数目的资源，而被系统封锁的进程。非封锁进程：即没有被系统封锁的进程资源分配图的化简方法：假设某个RAG中存在一个进程Pi，此刻Pi是非封锁进程，那么可以进行如下化简：当Pi有请求边时，首先将其请求边变成分配边(即满足Pi的资源请求)，而一旦Pi的所有资源请求都得到满足，Pi就能在有限的时间内运行结束，并释放其所占用的全部资源，此时Pi只有分配边，删去这些分配边（实际上相当于消去了Pi的所有请求边和分配边），使Pi成为孤立结点。（反复进行）。47死锁定理：系统中某个时刻S为死锁状态的充要条件是S时刻系统的资源分配图是不可完全简化的。在经过一系列的简化后，若能消去图中的所有边，使
33、所有的进程都成为孤立结点，则称该图是可完全简化的；反之的是不可完全简化的。P1P2r1r2P1P2r1r2P1P2r1r248死锁的恢复。是与检测死锁相配套的一种措施，用于将进程从死锁状态下解脱出来。常用的方法有：1撤消进程；最简单撤消进程的方法是使全部死锁的进程夭折掉；另一方法是按照某种顺序逐个地撤消进程，直至有足够的资源可用，死锁状态消除为止2挂起进程（剥夺资源）。使用挂起/激活机构挂起一些进程，剥夺它们的资源以解除死锁，待条件满足时，再激活进程。目前挂起法比较受到重视。491（北大95）一个OS有20个进程，竞争使用65个同类资源，申请方式是逐个进行的，一旦某个进程获得它所需要的全部资源
34、，则立即归还所有资源。每个进程最多使用三个资源。若仅考虑这类资源，该系统有无可能产生死锁，为什么？2死锁和饥饿的主要差别是什么？例题例题501答：不可能。因为死锁产生的原因有两点：系统资源不足或推进顺序不当，在本题中，进程所需的最大资源数为60，而系统共有该类资源65个，其资源数已足够系统内各进程使用。2答：简言之，死锁是某进程等待一个不会发生的事件的一种现象；而饥饿现象是某进程正等待这样一个事件，它发生了但总是受到其它进程的影响，以至轮不到（或很难轮到）该进程。51银行家算法的基本思想(1)系统中的所有进程进入进程集合,在安全状态下系统收到进程的资源请求后,先把资源试探性分配给它。系统用剩下
35、的可用资源和进程集合中其他进程还要的资源数作比较，在进程集合中找到剩余资源能满足最大需求量的进程,从而,保证这个进程运行完毕并归还全部资源。52银行家算法的基本思想(2)把这个进程从集合中去掉, 系统的剩余资源更多了,反复执行上述步骤。最后,检查进程集合,若为空表明本次申请可行,系统处于安全状态,可实施本次分配;否则,有进程执行不完，系统处于不安全状态,本次资源分配暂不实施,让申请进程等待。 533.7 死锁的检测与解除1 资源分配图和死锁定理2 借助于死锁的安全性测试算法的死锁检测3 warshall传递闭包算法的死锁检测 54简化进程-资源分配图检测系统是否处于死锁状态(1)(1)如果进程
36、-资源分配图中无环路，则此时系统没有发生死锁。(2)如果进程-资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生了死锁，此时，环路是系统发生死锁的充要条件，环路中的进程便为死锁进程。55简化进程-资源分配图检测系统是否处于死锁状态(2) (3)如果进程-资源分配图中有环路，且涉及的资源类中有多个资源，则环路的存在只是产生死锁的必要条件而不是充分条件。56简化进程-资源分配图检测系统是否处于死锁状态(3)如果能在进程-资源分配图中消去此进程的所有请求边和分配边，成为孤立结点。经一系列简化，使所有进程成为孤立结点，则该图是可完全简化的；否则则称该图是不可完全简化的。57简化进程-资源分配
37、图检测系统是否处于死锁状态(4)系统为死锁状态的充分条件是：当且仅当该状态的进程-资源分配图是不可完全简化的。该充分条件称为死锁定理。58死锁的具体检测和解除方法(1) 借助于死锁的安全性测试算法来实现。今定义布尔型向量possiblek，k=1,.,n。检测死锁算法如下： （1）currentavail:=available；（2）在rest中查每一个进程Pk,如果claimk,*-allock,*=0，则possiblek:=true；否则possiblek:=false；这里k=1,.,n。59死锁的具体检测和解除方法(2)（3）在rest中找一个进程Pk，需满足条件：possiblek
38、=false&(request*currentavail)找到这样的Pk便转（4）；否则转（5）；（4）currentavail:=currentavail+allocation；possiblek:=true；然后转（3）； (5) 如果对k=1,.,n若possiblek=true不成立，那么，系统出现了死锁，并且possiblek=false的Pk为死锁进程。60死锁的具体检测和解除方法(3) 死锁检测算法与死锁避免算法是类似的，不同在于前者考虑了检查每个进程还需要的所有资源能否满足要求；而后者则仅要根据进程的当前申请资源量来判断系统是否进入了不安全状态。613.7.2死锁的解除(1)立即结束所有进程的执行，并重新启动操作系统。方法简单,但以前工作全部作废,损失可能很大。撤销陷于死锁的所有进程,解除死锁继续运行。62死锁的解除(2)逐个撤销陷于死锁的进程,回收其资源,直至死锁解除。剥夺陷于死锁的进程占用的资源，但并不撤销它, 直至死锁解除。63死锁的解除(3) 根据系统保存的checkpoint,让所有进程回退,直到解除死锁。 当检测到死锁时，如果存在某些未卷入死锁的进程，而这些进程随着建立一些新的抑制进程能执行到结束，则它们可能释放足够的资源来解除死锁。64
