操作系统3-2死锁

CHAPTER3

DEADLOCK（死锁）3.5DeadlocksSystemModelDeadlockCharacterizationMethodsforHandlingDeadlocksDeadlockPreventionDeadlockAvoidanceDeadlockDetection

RecoveryfromDeadlockCombinedApproachtoDeadlockHandlingTheDeadlockProblemAsetofblockedprocesseseachholdingaresourceandwaitingtoacquirearesourceheldbyanotherprocessintheset.ExampleSystemhas2tapedrives.P1andP2eachhold1tapedriveandeachneedsanotherone.ExamplesemaphoresAandB,initializedto1

P0

P1wait(A); wait(B)wait(B); wait(A)BridgeCrossingExampleTrafficonlyinonedirection.Eachsectionofabridgecanbeviewedasaresource.Ifadeadlockoccurs,itcanberesolvedifonecarbacksup(preemptresourcesandrollback).Severalcarsmayhavetobebackedupifadeadlockoccurs.Starvationispossible.TrafficGridlock/Deadlock一个进程需要使用独占型资源必须有一定的次序：申请资源使用资源释放资源1968年Havender在评论OS/360操作系统时说：“原先多任务的概念是让多个任务不加限制的竞争资源，……但是随着系统的发展，很多任务被锁在系统中了。”1971年Lynch说：“1962年我们设计Exec2系统时并没有认识到死锁的问题，系统中也没有任何防范措施，结果现在一些程序中已被锁在系统中了。”死锁的产生操作系统的基本特征是并发与共享。系统允许多个进程并发执行，并且共享系统的软、硬件资源。为了最大限度的利用计算机系统的资源，操作系统应采用动态分配系统各种资源的策略。采用动态分配策略，当对某类资源的申请数目超过这类资源的可用数目时，若分配不当，可能出现进程之间相互等资源又都不能向前推进的情况，即造成进程相互封锁的危险。什么是死锁？死锁的定义：

一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而无限期地僵持下去的局面，这种现象称为进程死锁。这一组进程就称为死锁进程

死锁产生的原因1、进程推进顺序不当产生死锁。设系统有打印机、读卡机各一台，它们被进程P和Q共享。两个进程并发执行，它们按下列次序请求和释放资源：进程P进程Q

请求读卡机请求打印机请求打印机请求读卡机释放读卡机释放读卡机释放打印机释放打印机例2：R1和R2为可再用资源;进程Q1和Q2共享两个资源R1和R2。s1和s2分别代表资源R1和R2能否被使用的信号量，由于R1和R2是共享的，必须使用互斥。因而s1和s2的初值为1。假定两个进程都要求使用两个资源，它们的程序如下：进程Q1：P(s1)P(s2)使用R1和R2V(s1)V(s2)进程Q2：P(s2)P(s1)使用R1和R2V(s2)V(s1)死锁产生的原因2、PV操作使用不当产生死锁设S1=1，打印机可用。S2=1，读卡机可用。OS中的例子

操作系统中的例子（进程推进不合法）有二个进程P1、P2，两个设备打印机R1，读卡机R2

。

P(S1)；P(S2)；

P(S2)；P(S1)；

V(S1)；V(S2)；

V(S2)；V(S1)；

P1P2

P(S1)；P(S2)；

V(S1)；V(S2)；

P(S2)；P(S1)；

V(S2)；V(S1)；

P1P2P1P2P1P2？两种写法，谁可能造成死锁？申请R2S2：1-1=0占用R2申请R1S1：1-1=0占用R1申请R1，但R1被P1占用申请R2，但R2被P2占用等等死锁HoldandwaitA2B2C2D2申请r1申请r2释放r2释放r1A1B1C1D1申请r1申请r2释放r1释放r2两进程申请占用r1区域两进程申请占用r2区域xyP2进展P1进展0A死锁点路线1路线2ttt2t1A2B2C2D2申请r1申请r2释放r2释放r1A1B1C1D1申请r1申请r2释放r1释放r2两进程均占用r1两进程均占用r2xyP2进展P1进展0死锁点路线1路线2问题：那么为什么没有斜线的推进的进程顺序呢？tt死锁产生的原因3、同类资源分配不当引起死锁若系统中有m个资源被n个进程共享，当每个进程都要求k个资源。而m<n*k时，即资源数小于进程所需要的总数时，如果分配不得当就可能引起死锁。例3，m=5,n=5,k=2，采用的分配策略是为每个进程轮流分配。死锁产生的原因4、进程通讯引起死锁在进程通讯时使用的信件可以看作是一种临时性资源，如果对信件的发送和接收不加限制的话，则可能引起死锁例4：进程p1等待进程p3的信件s3来到后再向进程p2发送信件s1；p2又要等待p1信件来到后再向p3发送信件s2；而p3也要等待p2的信件s2来到后才能发出信件s3产生死锁的起因和条件（总结）起因：1）系统资源不足系统资源数目<进程需求结论与问题：死锁一定是系统资源不足的。那么系统资源不足是不是一定造成死锁呢（银行家告诉我们，那不一定！）2）联合推进路线非法（进程推进顺序不当）死锁产生的必要条件1971年Coffman总结出了对于可再使用资源，系统产生死锁必定同时保持四个必要条件：互斥条件（mutualexclusion）占有和等待条件（holdandwait）不剥夺条件（nopreemption）循环等待条件（circularwait）DeadlockCharacterizationDeadlockcanariseif4conditionsholdsimultaneously:Mutualexclusion:onlyoneprocessatatimecanusearesource.Holdandwait:

aprocessholdingatleastoneresourceiswaitingtoacquireadditionalresourcesheldbyotherprocesses.Nopreemption:

aresourcecanbereleasedonlyvoluntarilybyprocessholdingit,afterthatprocesscompleteditstask.Circularwait:

thereexistsaset{P0,P1,…,P0}ofwaitingprocessessuchthatP0iswaitingforaresourcethatisheldbyP1,P1iswaitingforaresourcethatisheldbyP2,…,Pn–1iswaitingforaresourcethatisheldby

Pn,andP0iswaitingforaresourcethatisheldbyP0.死锁产生的条件以上前三个条件互斥条件（mutualexclusion）占有和等待条件（holdandwait）不剥夺条件（nopreemption）是死锁存在的必要条件（necessarycondition），但不是充分条件。也就是说发生了死锁，必然具备互斥、占有和等待、不剥夺等条件。而具备互斥、占有和等待、不剥夺等条件却不一定产生死锁。死锁产生的条件第四个条件：

循环等待条件（circularwait） 是前三个条件同时存在时产生的结果，所以，这些条件并不完全独立。但单独考虑每个条件是有用的，只要能破坏这四个必要条件之一，死锁就可防止。死锁的解决策略归纳起来，可以采用以下策略之一来解决死锁问题：忽略该问题采用破坏4个必要条件来预防死锁采用有控分配方法（如银行家算法）来避免死锁当死锁发生时检测死锁，并设法修复鸵鸟算法TheostrichalgorithmUNIX潜在地受到了一些死锁的威协,但是这些死锁从来没有发生,甚至从来没有被检测到.处理死锁的UNIX办法是忽略它,由于大多数用户宁可在极偶然的情况下产生死锁,也不愿被限制只能创建一个进程,只能打开一个文件等等.象鸵鸟一样对死锁视而不见是最简单的方法.每个人对该方法的看法都不相同.数学家认为要彻底防止死锁的产生,不论代价有多大;工程师们想要了解死锁发生的频率,系统因各种原因崩溃的频率,以及死锁的严重程度.DeadlockPrevention(1)Restrainthewaysrequestcanbemade.MutualExclusion–notrequiredforsharableresources;mustholdfornonsharableresources.HoldandWait–mustguaranteethatwheneveraprocessrequestsaresource,itdoesnotholdanyotherresources.Requireprocesstorequestandbeallocatedallitsresourcesbeforeitbeginsexecution,orallowprocesstorequestresourcesonlywhentheprocesshasnone.Lowresourceutilization;starvationpossible.DeadlockPrevention(2)NoPreemption–Ifaprocessthatisholdingsomeresourcesrequestsanotherresourcethatcannotbeimmediatelyallocatedtoit,thenallresourcescurrentlybeingheldarereleased.Preemptedresourcesareaddedtothelistofresourcesforwhichtheprocessiswaiting.Processwillberestartedonlywhenitcanregainitsoldresources,aswellasthenewonesthatitisrequesting.CircularWait–imposeatotalorderingofallresourcetypes,andrequirethateachprocessrequestsresourcesinanincreasingorderofenumeration.解决死锁问题的策略---预防死锁

DeadlockPrevention一、解决死锁问题的几个策略1.DeadlockPrevention为了不发生死锁，必须设法破坏产生死锁的四个必要条件之一。条件1（互斥条件）：难以否定，但可采用相应的技术，如利用假脱机技术，即用可共享使用的设备模拟非共享的设备；解决死锁问题的策略---预防死锁条件2（占有和等待条件）：容易否定也容易实现，可制定相应的规则即可例如，当一个进程（程序）申请某资源被拒绝，则必须释放已占用的资源，如需要再与其它所需资源一起申请。在资源分配策略上可以采取静态资源分配的方式一次性的把所需资源全部分配到位，否则就不分配。Lowresourceutilization;starvationpossible死锁预防

对进程有关资源的活动加限制，所有进程遵循这种限制，即可保证没有死锁发生。优点：简单，系统不需要做什么。缺点：对进程的约束，违反约束仍可能死锁。预防方法：预先分配法；有序分配法。预先分配法进程：运行前申请所需全部资源；系统：能够满足，全部分配，否则，一个也不分配。破坏“hold-and-wait”条件缺点：资源利用效率低；一次提出申请困难。解决死锁问题的策略---预防死锁条件3（不剥夺条件）：比较容易否定当进程有新的资源请求时，如果得不到满足，要先释放原先占有的资源，待以后重新申请。等价于此进程“被剥夺”了已经占有的资源。代价大：造成某些进程前期阶段的工作失效，延长了周转时间，降低系统吞吐量这和“静态资源分配”有细微差别！静态资源分配：执行前就申请它所要的全部资源破坏不可剥夺条件：动态分配（边运行，边分配），但一旦在请求过程中得不到满足，要把已占据的也释放解决死锁问题的策略---预防死锁条件4（循环等待条件）：通过有序资源分配法，可以破坏环路条件。实际上系统还可以不采用部分分配（也就是静态资源分配，要么一次申请全部资源到位，达不到要求就不分配），也就破坏了环路等待条件。

有序分配法在这种方法中规定，系统将所有的资源按其类型进行线性排队，并赋予不同的序号。所有进程对资源的请求必须严格按资源序号递增的次序提出，这样，在所形成的资源分配图中，不可能再出现环路，因而摒弃了“循环等待”条件。有序分配法资源集：R={r1,r2,…,rn}

函数：F：RN

例如：R={scanner,tape,printer}F(scanner)=1;F(tape)=2;F(printer)=3;进程pi可以申请资源rj中的实例rl,pi占有rl,F(rl)F(rj)r1r2rkrm......申请次序5.6.2有序分配法证明无死锁（deadlockfree)：反证，假定死锁时刻t1:p1无限等待rk1中的资源实例，被p2占有；

t2:p2无限等待rk2中的资源实例，被p3占有；

…

tn:pn无限等待rkn中的资源实例，被p1占有;

根据有序申请假设：

F(rk1)<F(rk2)<…<F(rkn)<F(rk1)矛盾。有序资源分配法例如：进程P1，使用资源的顺序是R1，R2；

进程P2，使用资源的顺序是R2，R1；若采用动态分配有可能形成环路条件，造成死锁。有序资源分配法采用有序资源分配法：R1的编号为1，R2的编号为2；

P1：申请次序应是：R1，R2

P2：申请次序也应是：R1，R2

虽然一开始P2可能因为等待R1且不占据R2而浪费一些时间，但是这种等待和“奉献精神”换来了避免死锁的发生。这样就破坏了环路条件，避免了死锁的发生。死锁的避免死锁避免不是通过对进程随意强加一些规则，而是通过对每一次资源申请进行认真的分析来判断它是否能安全地分配。允许进程动态的申请资源，但在分配前，应先计算分配的安全性。SafeStateWhenaprocessrequestsanavailableresource,systemmustdecideifimmediateallocationleavesthesysteminasafestate.Systemisinsafestateifthereexistsasafesequenceofallprocesses.

(所谓安全状态，是指系统能按某种进程顺序如<P1,P2,…,Pn>，为每个进程分配其所需的资源，直至最大需求，使每个进程都可以顺利完成。)BasicFactsIfasystemisinsafestatenodeadlocks.Ifasystemisinunsafestatepossibilityofdeadlock.Avoidanceensurethatasystemwillneverenteranunsafestate.不安全状态不一定发生死锁，但死锁一定属于不安全状态。Safe,Unsafe,DeadlockState北京理工大学2002年考研题判断题当由于为进程分配资源使系统处于不安全状态时，系统一定会导致死锁。（）答案：错北京理工大学2002年考研题：死锁的避免是根据（）采取措施实现的。A.配置足够的系统资源B.使进程的推进顺序合理C.破坏死锁的4个必要条件之一D.防止系统进入不安全状态答案：D北京理工大学2002年考研题：死锁的避免是根据（）采取措施实现的。A.配置足够的系统资源B.使进程的推进顺序合理C.破坏死锁的4个必要条件之一D.防止系统进入不安全状态答案：D进程最大需求已分配系统可用P1P2P310495223系统资源总数：12进程最大需求已分配系统可用P1P2P310495232系统资源总数：122、安全状态之例：转化安全状态不安全状态利用银行家算法避免死锁该算法能用于银行系统现金贷款的发放而得名银行家算法的实质就是要设法保证系统动态分配资源后仍然保持安全状态，从而避免死锁的发生。要求进程预先告知自己的最大资源需求，并且假设系统拥有固定的资源总量。Question：资源不足——一定必死吗？行家的例子）银行家问题的例子（竞争资源）银行共有资金10万元，客户u1需贷款3万，客户u2需贷款8万，客户u3需贷款9万。某一时刻：

u2u3u1

已贷款还需资金1万2万2万6万6万3万银行只剩下1万元，造成死锁。对于客户来说，只有所需要的所有贷款全部得到满足，这样生意才能完成，之后才能把所贷款项归还。贷不到款，生意做不成，客户死贷出款得不到归还，破产，银行家死银行如果剩下2万元，又会怎样？银行家算法问题是：是否存在一种算法总能做出正确的选择从而避免死锁？答案是肯定的，但条件是必须事先获得与进程有关的一些特定信息。本节将讨论使用银行家算法（banker’salgorithm）避免死锁的方法。Banker’sAlgorithmMultipleinstances.Eachprocessmustaprioriclaimmaximumuse.Whenaprocessrequestsaresourceitmayhavetowait.Whenaprocessgetsallitsresourcesitmustreturntheminafiniteamountoftime.银行家算法避免死锁算法中最有代表性的算法是DijkstraE.W于1968年提出的银行家算法：它的模型基于一个小城镇的银行家，现将该算法描述如下：假定一个银行家拥有资金，数量为∑，被N个客户共享。银行家对客户提出下列约束条件：银行家算法每个客户必须预先说明自己所要求的最大资金量；每个客户每次提出部分资金量申请和获得分配；如果银行满足了某客户对资金的最大需求量，那么，客户在资金运作后，应在有限时间内全部归还银行。银行家算法一个状态被称为是安全的，其条件是存在一个状态序列能够使所有的客户均得到其所有的贷款(即所有的进程得到所需的全部资源并终止)。当一个银行家的余额不能满足任何一个客户的贷款需求时：由于贷不到款，客户生意做不成，破产死；贷出款得不到归还，银行家破产死——死锁。银行家算法不安全状态并不一定导致死锁，因为顾客有可能不需要它的全部贷款额，但银行家不能指望这种情况发生，不敢抱这种侥幸心理。银行家算法可陈述如下：当一个进程提出资源请求时，假定分配给它，并检查系统因此是否仍处于安全状态。如果安全，则满足它的请求。否则，推迟它的请求。

DataStructuresfortheBanker’sAlgorithmLetn=numberofprocesses,andm=numberofresourcestypes.Available:Vectoroflengthm.Ifavailable[j]=k,therearekinstancesofresourcetypeRj

available.Max:nxmmatrix.IfMax[i,j]=k,thenprocessPi

mayrequestatmostkinstancesofresourcetypeRj.Allocation:nxmmatrix.IfAllocation[i,j]=kthenPiiscurrentlyallocatedkinstancesofRj.Need:nxmmatrix.IfNeed[i,j]=k,thenPimayneedkmoreinstancesofRj

tocompleteitstask.

Need[i,j]=Max[i,j]–Allocation[i,j].两个向量：Work工作向量:它表示系统可提供给进程继续运行所需的资源数目，含m个元素，在执行安全算法开始时，work=Available;Finished向量:表示系统是否有足够的资源分配给进程，使之运行完成。开始时，Finish[i]=false，足够资源分配给进程时，再令Finish[i]=TrueDataStructuresfortheBanker’sAlgorithm安全性算法确定系统是否处于安全状态可分为如下几步1.设Work和Finish

分别是长度为

m

和

n的向量,初始化如下:Work=AvailableFinish[i]=falsefori-1,2,…,n.2.检查这样的

i使其满足:(a)Finish[i]=false(b)Needi

Work如果没有这样的

i存在,那么跳转第4步.3. Work=Work

+Allocationi

Finish[i]=true

返回第2步.4. 如果对所有的i，Finish[i]==true，那么系统就处于安全状态资源请求算法1设Requesti

为进程Pi的请求资源量.如果Requesti[j]=k则表示Pi

需要k个Rj类型的资源。当进程Pi做出资源请求时，会采取如下动作：如果Requesti

Needi

那么跳转到第2步.否则产生出错条件,这是因为进程Pi请求的资源超过自己的需求.如果Requesti

Available,那么跳转到第3步.否则进程Pi

必须等待,这是因为资源不足，没有可以利用的资源。资源请求算法2假定系统可以分配给进程Pi

要求的所有资源，那么按如下方式修改状态：

Available=Available

-Requesti;

Allocationi

=Allocationi+Requesti;

Needi

=

Needi

–

Requesti;;如果所产生的资源分配状态是安全的那么交易完成，且进程

Pi可分配到其所需要的资源.如果所产生的资源分配状态是不安全的进程Pi

必须等待,并且必须恢复到原来资源分配状态。资源分配Pi请求资源Request[I]Need[I]请求超量，错返Request[I]Available不满足，等待Available:=Available-Request[I]Allocation[I]:=Allocation[I]+Request[I]Need[I]:=Need[I]-Request[I]安全确认，pi继续Available:=Available+Request[I]Allocation[I]:=Allocation[I]-Request[I]Need[I]:=Need[I]+Request[I]pi等待FTFTTF银行家算法举例考虑这样一个系统，有5个进程

P0到P4;3种类型资源A、B、C，其中A

有10个实例B

有5个实例,C

有7个实例。T0时刻系统状态如下:

Allocation

Max

Available

ABC ABC ABC

P0 010 753 332

P1 200 322

P2 302 902

P3 211 222

P4 002 433

10,5,7银行家算法例子R={A(10),B(5),C(7)}P={p0,p1,p2,p3,p4}

Claim

Allocation

Need

Available

Work

FinishABCABCABCABCABC753010743332322200122902302600222211011433002431P0:p1:p2:p3:p4:安全进程序列：<p1,p3,p4,p2,p0>p1请求：Request[1]=(1,0,2)思考执行安全算法检查，可以发现<P1,P3,P4,P0,P2>安全序列。思考：那么进程P4请求(3,3,0)可以得到满足吗?北京理工大学2002年在银行家算法，若出现以下资源分配情况系统剩余资源数量=（3，2，2）问该状态是否安全（给出详细的检查过程）？进程资源最大需求已分配资源P07，5，30，1，0P13，2，22，1，0P29，0，23，0，2P32，2，22，1，1P44，3，30，0，2答案进程资源最大需求已分配资源needavailableP07，5，30，1，07,4,33,2,2P13，2，22，1，01,1,2P29，0，23，0，26,0,0P32，2，22，1，10,1,1P44，3，30，0，24,3,1答案进程工作向量已分配资源need工作向量+已分配资源Finish?答案进程工作向量已分配资源need工作向量+已分配资源Finish?p13,2,21,1,22,1,05,3,2trueP35,3,22，1，10,1,17,4,3trueP07,4,37,4,30,1,07,5,3truep27,5,36,0,03,0,210,5,5truep410,5,50,0,24,3,110,5,7true存在一个安全序列p1,p3,p0,p2,p4，所以该状态是安全练习：北京大学1997年OS考研试题系统中有三种资源（A，B，C）和5个进程P1-P5资源总数为（17，5，20），T0时刻系统状态如表所示，系统采用银行家算法实施死锁避免策略最大资源需求量已分配资源量ABCABCP1559212P2536402P34011405P4425204P5424314进程死锁北京大学1997年OS考研试题请解答以下问题：（1）T0时刻是否为安全状态？若是则给出安全序列（2）在T0时刻P2请求资源（0，3，4），是否能够实施资源分配，为什么？（3）在（2）的基础上，若P4请求资源（2，0，1），是否能够实施分配，为什么？（4）在（3）的基础上，若P1请求资源（0，2，0），是否能够实施分配，为什么？进程死锁资源情况安排进程MaxRequestAvailableNeedAllocationAvailable+AllocationFinishABCABCABCABCABCABC工作向量还需要的资源已经分配的资源工作向量+已分配的资源完成情况银行家算法的保守性例子：R={A,B},申请a,b;释放a,bP={p1,p2},p1:abab;p2:bbbaab

Claim

Allocation

Need

Available

Work

FinishABABABABABp1：11001111p2：110011Request[1]=(1,0),安全，分配。练习：某系统中有10台打印机，有三个进程P1、P2、P3分别需要8台、7台和4台。若P1、P2、P3已申请到4台、2台和2台。试问：按银行家算法能安全分配吗？请说明分配过程。银行家算法的保守性Request[2]=(0,1),不安全，不分配，（分配不导致死锁）

Claim

Allocation

Need

Available

Work

FinishABABABABABp1：11100101p2：110011分配后：期末考试模拟题选择银行家算法是一种()算法.

A死锁解除 B死锁避免

C死锁预防 D死锁检测

B判断题：银行家算法是用来预防死锁的.()错死锁的避免预防死锁通常采用静态资源分配或者有序层次资源分配，这样都在某种程度上产生了资源的浪费。为了提高设备的利用率，应采用动态的设备分配方法，但应设法避免死锁(DeadlockAvoidance)

，若存在发生死锁的可能性，则拒绝分配。死锁的避免预防死锁：采用的分配策略本身就否定了产生死锁的四个必要条件之一，这就保证了不会发生死锁；死锁避免：与预防死锁相反，它允许系统中同时存在四个必要条件，如果能掌握并发进程中与每个进程有关的资源动态申请情况，做出明智和合理的选择，仍然可以避免死锁的发生。计算机等级考试三级B类笔试试题

(98年4月)选择题：死锁预防是保证系统不进入死锁状态的静态策略,其解决办法是破坏产生死

锁的四个必要条件之一.下列方法中哪一个是破坏了"循环等待"条件

A)银行家算法

B)一次性分配策略

C)剥夺资源法

D)资源有序分配策略

一道考研题：华中科技大学2000年3个进程共享4个同类资源，这些资源的分配和释放只能一次一个。已知每个进程最多占据2个资源，则该系统——A.有某些资源可能永远得不到该类资源B.必然有死锁C.进程请求该类资源立刻能得到D.必然无死锁答案：D鸽笼原理！计算机等级考试三级B类笔试试题(98年4月)选择题：死锁预防是保证系统不进入死锁状态的静态策略,其解决办法是破坏产生死锁的四个必要条件之一.下列方法中哪一个是破坏了“循环等待”条件

A)银行家算法

B)一次性分配策略

C)剥夺资源法

D)资源有序分配策略

答案：D死锁的检测和解除死锁的检测：死锁的检测代价很高；

通常的方法是程序员的经验，如UNIX系统中，可考察进程的运行时间。在UNIX系统中有命令ps可显示进程占用CPU的时间，若发现有一组进程在一段时间内没有占用CPU，就认为这类进程出现了死锁。资源分配图定义:G=(V,E),V=PR,P={p1,p2,…,pn},R={r1,r2,…,rm},E={(pi,rj)}{(rj,pi)},piP,rjR.

申请边(pi,rj):pi申请rj；分配边(rj,pi):rj分配pi;图示：进程：资源：申请边：由进程到资源类；分配边：由资源实例到进程。Resource-AllocationGraph(1)Asetofvertices(节点)VandasetofedgesE.Vispartitionedintotwotypes:P={P1,P2,…,Pn},thesetconsistingofalltheprocessesinthesystem.R={R1,R2,…,Rm},thesetconsistingofallresourcetypesinthesystem.requestedge

–directededgeP1Rjassignmentedge

–directededgeRj

PiResource-AllocationGraph(2)processresourcePiRjPiRjResourceTypewith4instancesPirequestsinstanceofRjPiisholdinganinstanceofRjRASBTDUC(a)进程A分配了一个资源(b)进程B请求了一个资源(c)进程D和进程形成环路，已处于死锁状态资源分配图

ExampleofaResourceAllocationGraph例1.P={p1,p2,p3},R={r1(1),r2(2),r3(1),r4(3)}E={(p1,r1),(p2,r3),(r1,p2),(r2,p1),(r2,p2),(r3,p3)}p1p2p3r1r3r2r4ResourceAllocationGraphWithADeadlockp1p2p3r1r3r2r4增加边（p3,r2)p1p2p3p4r1r2ResourceAllocationGraphwithacyclebutnodeadlockBasicFactsIfgraphcontainsnocyclesnodeadlock.Ifgraphcontainsacycleifonlyoneinstanceperresourcetype,thendeadlock.ifseveralinstancesperresourcetype,possibilityofdeadlock.资源分配图的约简可以通过对资源分配图的约简，来判断系统是否处于死锁状态．资源分配图中的约简方法如下：(1)寻找一个非孤立且没有请求边的进程结点pi,若无算法结束；(2)去除所有pi的分配边使pi成为一个孤立结点；(3)寻找所有请求边均可满足的进程pj,将pj的请求边全部改为分配边；(4)转步骤(1)．若算法结束时，所有结点均为孤点，则称资源分配图是可以完全约简的，否则称为不可完全约简的．文献已经证明，系统处于死锁状态的充分必要条件是资源分配图不可完全约简．这一结论称为死锁定理．定理：S为死锁状态的充分必要条件是S的资源分配图不可完全约简。判断下列资源分配图所标示的状态是否为死锁p1p2p3化简下面的资源分配图，并利用死锁定理给出相应的结论p2p1死锁检测考虑因素：死锁发生频度；死锁影响进程。1.等待时检测：发现早，恢复代价小，开销大（overhead)。2.定时检测：3.资源（eg.CPU）利用率下降时检测。死锁检测算法数据结构：

Available:array[1..m]ofinteger;Allocation:array[1..n,1..m]ofinteger;Request:array[1..n,1..m]ofinteger;临时变量：

Work:array[1..m]ofinteger;Finish:array[1..n]ofboolean;死锁检测算法Work:=Available;Finish:=false;有满足条件的i:Finish[i]=falseRequest[i]WorkFinish[i]=true;Work:=Work+Allocation[i]Ti,finish[i]=trueTFF无死锁死锁Finish[I]=trueforallocation[I]=0Remarks1.上述算法可以检测到参与死锁的全部进程，包括占有资源和不占有资源的进程。2.如果希望只检测占有资源的进程，初始化时：

Finish[i]=true,forAllocation[I]=0死锁例子例子：R={A(7),B(2),C(6)};P={p0,p1,p2,p3,p4}

Allocation

Request

Available

Work

FinishABCABCABCABCp0:010000000p1:200202p2:303000p3:211100p4:002002未死锁。此时，Request[2]=(0,0,1),死锁，参与死锁进程{p1,p2,p3,p4}死锁检测考虑因素：死锁发生频度；死锁影响进程。1.等待时