操作系统原理：CH08-Deadlock

Module8:Deadlocks（死锁）SystemModel（系统模型）DeadlockCharacterization（死锁特征）MethodsforHandlingDeadlocks（处理死锁的方法）DeadlockPrevention（预防死锁）DeadlockAvoidance（死锁避免）DeadlockDetection（死锁检测）RecoveryfromDeadlock（死锁恢复）CombinedApproachtoDeadlockHandling（综合处理方法）TheDeadlockProblem（死锁问题）Asetofblockedprocesseseachholdingaresourceandwaitingtoacquirearesourceheldbyanotherprocessintheset.

（一组等待的进程，其中每一个进程都持有资源，并且等待着由这个组中其他进程所持有的资源）死锁Deadlock：计算机系统中多道程序并发执行时，两个或两个以上的进程由于竞争资源而造成的一种互相等待的现象（僵局），如无外力作用，这些进程将永远不能再向前推进。TheDeadlockProblemExample1Systemhas2tapedrives.（系统有两个磁带设备）P1andP2eachholdonetapedriveandeachneedsanotherone.（进程P1和P2各占有一个磁带设备并且实际需要两个磁带）Example2semaphoresAandB,initializedto1（信号量A，B初始化为1）

P0 P1wait(A); wait(B)wait(B); wait(A)如果一个进程要使用OS管理的资源，需先向系统提出申请，如果有可用资源，系统才进行分配。资源的分类,根据资源性质：可抢占资源—指资源占有进程虽然需要使用该资源，但另一个进程却可强行把资源从占有者进程处抢来。不可抢占资源—指只有占用者进程不再需要使用该资源而主动释放资源外，其它进程不得在占有者进程使用资源过程中强行抢占。

根据使用方式：共享资源和独占资源。根据使用期限；永久资源和临时性资源。资源共享:CPU、主存、硬盘独占:打印机，读卡机，磁带驱动器可顺序重复使用的资源由一个进程产生，被另外一个进程使用短暂时间之后便无用的资源BridgeCrossingExample

（过桥的例子）Trafficonlyinonedirection.（只有一个方向）Eachsectionofabridgecanbeviewedasaresource.

（桥的每一个部分都可以看成资源）Ifadeadlockoccurs,itcanberesolvedifonecarbacksup(preemptresourcesandrollback).

（如果死锁发生，它可以由一辆车返回而解决，抢占资源并回退）Severalcarsmayhavetobebackedupifadeadlockoccurs.

（如果死锁发生，可能很多车都不得不返回）Starvationispossible.（有可能产生饥饿）死锁的原因和条件竞争资源引起死锁当系统中供多个进程所使用的资源，不足以同时满足它们的需要时，引起它们对资源的竞争而产生死锁进程推进顺序不当引起死锁在多道程序系统中，并发执行的进程推进序列不可予测有些推进顺序，进程可以顺利完成有的推进顺序会引起进程无限期地等待永远不会发生的条件而不能向前推进，造成死锁P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)③④③③③②②①①进程P1、P2并发执行。资源R1、R2各有一个曲线4将进入不安全区域（进程推进顺序非法）P1S1S3P2P3S2P1：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)可能发生死锁S1、S2、S3是临时资源DeadlockCharacterization

（死锁的特性）Mutualexclusion:onlyoneprocessatatimecanusearesource.（互斥：一次只有一个进程可以使用一个资源）Holdandwait:aprocessholdingatleastoneresourceiswaitingtoacquireadditionalresourcesheldbyotherprocesses.

（占有并等待：一个至少持有一个资源的进程等待获得额外的由其他进程所持有的资源）(请求与保持)Deadlockcanariseiffourconditionsholdsimultaneously.（四个条件同时出现，死锁将会发生）DeadlockCharacterization

（死锁的特性）Nopreemption:aresourcecanbereleasedonlyvoluntarilybytheprocessholdingit,afterthatprocesshascompleteditstask. （不可抢占：一个资源只有当持有它的进程完成任务后，自由的释放）(非剥夺)Circularwait:thereexistsaset{P0,P1,…,P0}ofwaitingprocessessuchthatP0iswaitingforaresourcethatisheldby

P1,P1iswaitingforaresourcethatisheldbyP2,…,Pn–1iswaitingforaresourcethatisheldbyPn,andP0iswaitingforaresourcethatisheldbyP0.（循环等待：等待资源的进程之间存在环）SystemModel（系统模型）Resourcetypes（资源类型）R1,R2,...,Rm

CPUcycles,memoryspace,I/Odevices（CPU周期，内存空间，I/O设备）EachresourcetypeRihasWiinstances.

（每一种资源Ri有Wi

种实例）Eachprocessutilizesaresourceasfollows

（每一个进程如下的利用资源）request（申请）use（使用）Release（释放）Resource-AllocationGraph

（资源分配图）Vispartitionedintotwotypes:（V被分为两个部分）P={P1,P2,…,Pn},thesetconsistingofalltheprocessesinthesystem.（P：含有系统中全部的进程）R={R1,R2,…,Rm},thesetconsistingofallresourcetypesinthesystem.（R：含有系统中全部的资源）requestedge–directededgeP1Rj（请求边：直接P1Rj

）assignmentedge–directededgeRj

Pi（分配边：P1Rj

）AsetofverticesVandasetofedgesE.（一个顶点的集合V和边的集合E）Resource-AllocationGraph(Cont.)

资源分配图续Process进程

ResourceTypewith4instances有四个实例的资源类型Pi

requestsinstanceofRj

（

Pi

请求一个Rj的实例）PiisholdinganinstanceofRj（

Pi

持有一个Rj的实例）PiPiRjRjExampleofaResourceAllocationGraph

资源分配图的例子ResourceAllocationGraphWithADeadlock

有死锁的资源分配图ResourceAllocationGraphWithACycleButNoDeadlock

有环但没有死锁的资源分配图BasicFacts（基本事实）Ifgraphcontainsnocyclesnodeadlock.（如果图没有环，那么不会有死锁）Ifgraphcontainsacycle（如果图有环）ifonlyoneinstanceperresourcetype,thendeadlock.

（如果每一种资源类型只有一个实例，那么死锁发生）ifseveralinstancesperresourcetype,possibilityofdeadlock.

（如果一种资源类型有多个实例，可能死锁）MethodsforHandlingDeadlocks

处理死锁的方法忽略、预防、避免、检测、解除Ignoretheproblemandpretendthatdeadlocksneveroccurinthesystem;usedbymostoperatingsystems,includingUNIX.（忽略这个问题，假装系统中从未出现过死锁。这个方法被大部分的操作系统采用，包括UNIX）鸵鸟策略Ensurethatthesystemwillneverenteradeadlockstate.（确保系统永远不会进入死锁状态）预防死锁，避免死锁Allowthesystemtoenteradeadlockstateandthenrecover.

（允许系统进入死锁状态，然后恢复系统）死锁检测鸵鸟策略象鸵鸟一样对死锁视而不见处理死锁的代价很大，而且常常给用户带来许多不便的限制。大多数用户宁可在极偶然的情况下发生死锁，也不愿限制每个用户只能创建一个进程、只能打开一个文件等等。于是不得不在方便性和正确性之间作出折衷。DeadlockPrevention（死锁的预防）MutualExclusion–notrequiredforsharableresources;mustholdfornonsharableresources.

（互斥：共享资源不是必须的，必须保持非共享资源）HoldandWait–mustguaranteethatwheneveraprocessrequestsaresource,itdoesnotholdanyotherresources.

（占有并等待：必须保证进程申请资源的时候没有占有其他资源）Requireprocesstorequestandbeallocatedallitsresourcesbeforeitbeginsexecution,orallowprocesstorequestresourcesonlywhentheprocesshasnone.

（要求进程在执行前一次申请全部的资源，只有没有占有资源时才可以分配资源）Lowresourceutilization;starvationpossible.

（利用率低，可能出现饥饿）Restrainthewaysrequestcanbemade.（抑制死锁发生的必要条件）DeadlockPrevention(Cont.)

死锁的预防（续）NoPreemption–（非抢占）Ifaprocessthatisholdingsomeresourcesrequestsanotherresourcethatcannotbeimmediatelyallocatedtoit,thenallresourcescurrentlybeingheldarereleased.（如果一个进程的申请没有实现，它要释放所有占有的资源）Preemptedresourcesareaddedtothelistofresourcesforwhichtheprocessiswaiting.（先占的资源放入进程等待资源列表中）Processwillberestartedonlywhenitcanregainitsoldresources,aswellasthenewonesthatitisrequesting.

（进程在有新的资源请求时，若能够重新得到旧的资源，可以重新开始）NoPreemption–（非抢占）另外一种解决方案:当进程A提出资源申请时,首先检查这些资源是否可用是,则分配之,否则检查这些资源是否已分配给了另外的进程(而这个进程又在等待其他的资源)如果存在这样的进程B,从进程B剥夺进程A所需的资源分配给进程A使用.相反,则进程A等待,当进程A在等待的过程中,它所持有资源可能会被剥夺分配给其他的进程.这样,进程A只有得到了它正在申请有资源以及等待过程中被剥夺的资源后,才能恢复运行.CircularWait–imposeatotalorderingofallresourcetypes,andrequirethateachprocessrequestsresourcesinanincreasingorderofenumeration.（循环等待：将所有的资源类型放入资源列表中，并且要求进程按照资源表申请资源）所有进程对资源的请求必须严格按资源序号递增的次序提出。总有一个进程占据了较高序号的资源，它继续请求的资源必然是空闲的，可以一直向前推进。在资源分配图中不可能出现环路，因而摒弃了“环路等待”条件这种策略可以提高资源利用率，但在进程使用各类资源的顺序与系统规定的顺序不同时会造成资源浪费的情况。上述预防死锁的方法通过限制资源请求来打破死锁的四个必要条件之一，从而预防死锁的发生。其可能的副作用：降低设备利用率和吞吐量可能有进程饥饿DeadlockAvoidance（死锁避免）允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的安全性若此次分配不会导致系统从安全状态向不安全状态转换，便可将资源分配给进程；否则不分配资源，进程必须阻塞等待。Safe

State安全状态是指系统的一种状态，在此状态下,系统能按某种顺序（例如P1、P2……Pn）来为各个进程分配其所需资源，直至最大需求，使每个进程都可顺序地一个个地完成。这个序列（P1、P2…….Pn）称为安全序列。若某一时刻不存在一个安全序列，则称系统处于不安全状态。SafeState（安全状态）Whenaprocessrequestsanavailableresource,systemmustdecideifimmediateallocationleavesthesysteminasafestate.

（当进程申请一个有效的资源的时候，系统必须确定分配后是安全的）Systemisinsafestateifthereexistsasafesequenceofallprocesses.（如果存在一个安全序列系统处于安全态）Sequence<P1,P2,…,Pn>issafeifforeachPi,theresourcesthatPicanstillrequestcanbesatisfiedbycurrentlyavailableresources+resourcesheldbyallthePj,withj<I.

（进程序列是安全的，如果每一个进程Pi所申请的可以被满足的资源数加上其他进程所持有的该资源数小于系统总数）IfPiresourceneedsarenotimmediatelyavailable,thenPicanwaituntilallPj

havefinished.WhenPjisfinished,Picanobtainneededresources,execute,returnallocatedresources,andterminate.WhenPiterminates,Pi+1canobtainitsneededresources,andsoon.例：系统中有P1、P2和P3三个进程和12台磁带机。各进程最大需求和T0时刻分配状态如下：进程 最大需求已分配还需请求可用

P110 55 3P24 2 2 P392 7 分析T0状态，可以找到一个安全序列（P2、P1、P3）,即系统按此进程序列分配资源，每个进程都可顺利完成，其步骤如下：先将可用的3台磁带机中2台分配给P2，P2满足了最大的资源需求，在有限时间内运行完毕，释放它占有的全部资源，使可用资源数量增至5台。再将可用的5台磁带机分配给P1，最后将可用10台中7台磁带机分配给P3这样三进程可按照（P2、P1、P3）序列顺序地一个个执行完成，则（P2、P1、P3）序列是安全序列，T0时刻状态是安全状态由安全状态向不安全状态的转换如果在T0

状态不按安全序列进行分配，可能会导致系统进入一个不安全状态，例如在T0状态下P3申请1台磁带机。如系统实施此次分配使系统状态由T0变为T1状态T1时刻状态：进程最大需求已分配还需请求可用可用

分配资源前释放资源后

P1105 5

>

P24 22=< 2

4P39 3

6

>

因为找不到一个安全序列使所有进程顺序地一个个地运行完毕，所以T1状态是不安全状态，由于实施分配给1台磁带机给P3的操作会引起系统状态由安全状态T0向不安全状态下的转换，所以为了避免死锁，上述的分配只是安全检测，检测后判定这样的申请不能满足，P3为申请1台磁带机而必须阻塞等待。BasicFacts（基本事实）Ifasystemisinsafestatenodeadlocks.

（如果一个系统在安全状态，就没有死锁）Ifasystemisinunsafestatepossibilityofdeadlock.

（如果一个系统不是处于安全状态，就有可能死锁）Avoidanceensurethatasystemwillneverenteranunsafestate.

（避免：确保系统永远不会进入死锁状态）Safe,unsafe,deadlockstatespaces

安全、不安全、死锁状态空间DeadlockAvoidance（死锁避免）Simplestandmostusefulmodelrequiresthateachprocessdeclarethemaximumnumberofresourcesofeachtypethatitmayneed.（一个简单而有效的模型要求每一个进程声明它所需要的资源的最大数）Thedeadlock-avoidancealgorithmdynamicallyexaminestheresource-allocationstatetoensurethattherecanneverbeacircular-waitcondition.（死锁避免算法动态检查资源分配状态以确保不会出现循环等待的情况）Resource-allocationstateisdefinedbythenumberofavailableandallocatedresources,andthemaximumdemandsoftheprocesses.（资源分配状态定义为可用的与已分配的资源数，和进程所需的最大资源量）Requiresthatthesystemhassomeadditionalaprioriinformation

available.（需要系统有一些额外的信息）Singleinstanceofaresourcetype资源有单个实例Usearesource-allocationgraph资源分配图Multipleinstancesofaresourcetype资源有多个实例Usethebanker’salgorithm银行家算法Resource-AllocationGraphAlgorithm

资源分配图算法Claimedge

Pi

RjindicatedthatprocessPjmayrequestresourceRj;representedbyadashedline. (claimedge申请边Pi

Rj代表进程Pi可能会申请资源Ri，表示为虚线）Claimedgeconvertstorequestedgewhenaprocessrequestsaresource.（一个进程申请资源的时候，申请边转化为请求边）Whenaresourceisreleasedbyaprocess,assignmentedgereconvertstoaclaimedge.（当资源被进程释放的时候，分配边转化为申请边）Resourcesmustbeclaimedaprioriinthesystem.

（系统中的资源必须被事先声明）当一个进程Pi申请资源Rj时，由循环检测算法来检查:如果把图中的申请边PiRj转为分配边Rj

Pi

，图中是否会出现环路，只有不出现环路，才实施资源分配。Resource-AllocationGraphForDeadlockAvoidance

死锁避免的资源分配图UnsafeStateInAResource-AllocationGraph

不安全的状态图Banker’sAlgorithm（银行家算法）Multipleinstances.（多个实例）Eachprocessmustaprioriclaimmaximumuse.

（每一个进程必须事先声明使用的最大量）Whenaprocessrequestsaresourceitmayhavetowait.

（当一个进程请求资源，它可能要等待）Whenaprocessgetsallitsresourcesitmustreturntheminafiniteamountoftime.

（当一个进程得到所有的资源，它必须在有限的时间释放它们）DataStructuresfortheBanker’sAlgorithm

银行家算法的数据结构Available:Vectoroflengthm.Ifavailable[j]=k,therearekinstancesofresourcetypeRj

available.

（如果available[j]=k,那么资源Rj有k个实例有效）Max:nxmmatrix.IfMax[i,j]=k,thenprocessPi

mayrequestatmostkinstancesofresourcetypeRj.

（如果Max[i,j]=k,那么进程Pi可以最多请求资源Rj的k个实例）Letn=numberofprocesses,andm=numberofresourcestypes.N为进程的数目，M为资源类型的数目Allocation:nxmmatrix.IfAllocation[i,j]=kthenPiiscurrentlyallocatedkinstancesofRj.

（如果Allocation[i,j]=k,那么进程Pj当前分配了k个资源Rj的实例）Need:nxmmatrix.IfNeed[i,j]=k,thenPimayneedkmoreinstancesofRj

tocompleteitstask.

（如果Need[i,j]=k,那么进程Pi还需要k个资源Rj的实例）

Need[i,j]=Max[i,j]–Allocation[i,j].DataStructuresfortheBanker’sAlgorithm

银行家算法的数据结构SafetyAlgorithm（安全算法）1. LetWorkandFinishbevectorsoflengthmandn,respectively.Initialize（让Work和Finish作为长度为m和n的向量）Work:=AvailableFinish[i]=falsefori-1,3,…,n.2. Findandisuchthatboth:（找到i）(a)Finish[i]=false(b)Needi

WorkIfnosuchiexists,gotostep4.3. Work:=Work+Allocationi

Finish[i]:=true

gotostep2.4. IfFinish[i]=trueforalli,thenthesystemisinasafestate.Resource-RequestAlgorithmforProcessPi

进程Pi的资源请求

Requesti=requestvectorforprocessPi.IfRequesti

[j]=kthenprocessPiwantskinstancesofresourcetypeRj. 1. IfRequesti

Needi

gotostep2.Otherwise,raiseerrorcondition,sinceprocesshasexceededitsmaximumclaim.2. IfRequesti

Available,gotostep3.OtherwisePimustwait,sinceresourcesarenotavailable.3. PretendtoallocaterequestedresourcestoPibymodifyingthestateasfollows:

Available:=Available–Requesti;

Allocationi

:=Allocationi+Requesti;

Needi

:=

Needi–Requesti;;4.用安全算法进行检查,看系统是否处于安全状态IfsafetheresourcesareallocatedtoPi.IfunsafePimustwait,andtheoldresource-allocationstateisrestoredExampleofBanker’sAlgorithm

银行家算法的例子5processesP0throughP4;3resourcetypesA(10instances),

B(5instances,andC(7instances).（5个进程P0到P4:3个资源类型A(10个实例），B（5个实例），C（7个实例））SnapshotattimeT0:（时刻T0的片段）

Allocation

Max

Available ABC ABC ABC

P0 010 753 332

P1 200 322

P2 302 902

P3 211 222

P4 002 433 Example(Cont.)（例子续）Thecontentofthematrix.NeedisdefinedtobeMax–Allocation.（矩阵的内容。需要被定义为最大值）

Need

ABC

P0 743

P1 122

P2 600

P3 011

P4 431Thesystemisinasafestatesincethesequence<P1,P3,P4,P2,P0>satisfiessafetycriteria.（系统在安全的状态因为序列P1,P3,P4,P2,P0满足了安全的标准）用安全检测算法看能否找到一个安全序列Work[]=available=(3,3,2)Finish[i]=false(i=0..4)

WorkneedallocationfinishP1332122200TP3532011211TP4743431002TP2745600302TP01047743010T存在安全序列：（P1，P3，P4，P2，P0）Example(Cont.)通常，安全序列不是唯一的Work[]=available=(3,3,2)Finish[i]=false(i=0..4)

WorkneedallocationfinishP3332011211TP4543431002TP1545122200TP2745600302TP01047743010T安全序列：（P3，P4，P1，P2，P0）Example(Cont.)Example(Cont.):P1request(1,0,2)

例子续CheckthatRequestAvailable(thatis,(1,0,2)(3,3,2)true.

(检查请求小于有效（就是说，(1,0,2)(3,3,2)为真）

Allocation

Need

Available ABC ABC ABC

P0 010 743 230

P1 302 020

P2 302 600

P3 211 011

P4 002 431Executingsafetyalgorithmshowsthatsequence<P1,P3,P4,P0,P2>satisfiessafetyrequirement.（执行安全算法表明序列p1,p3,p4,p0,p2满足要求）Canrequestfor(3,3,0)byP4begranted?（p4的(3,3,0)可以通过？）Canrequestfor(0,2,0)byP0begranted?（p0的(0,2,0)可以通过？）DeadlockDetection（死锁检测）Allowsystemtoenterdeadlockstate（允许进入死锁状态）Detectionalgorithm（检测死锁）Recoveryscheme（恢复策略）SingleInstanceofEachResourceType

每一种资源类型只有一个实例Maintainwait-forgraph（维护等待图）Nodesareprocesses.（节点是进程）Pi

Pj

ifPi

iswaitingfor

Pj.（Pi

Pj表明Pi在等待Pj.）Periodicallyinvokeanalgorithmthatsearchesforacycleinthegraph.（定期调用算法来检查是否有环）Analgorithmtodetectacycleinagraphrequiresanorderofn2operations,wherenisthenumberofverticesinthegraph.（一个检查图中是否有环的算法需要n2的操作来进行，n为图中的节点数）Resource-AllocationGraphAndWait-forGraph

资源分配图和等待图Resource-AllocationGraphCorrespondingwait-forgraphSeveralInstancesofaResourceType

一个资源类型的多个实例Available:Avectoroflengthmindicatesthenumberofavailableresourcesofeachtype.

（可用：一个长度m的向量代表每种资源类型的有效数目）Allocation:Annxmmatrixdefinesthenumberofresourcesofeachtypecurrentlyallocatedtoeachprocess.

（分配：一个nxm

的矩阵定义了当前分配的每一种资源类型的实例数目）Request:Annxmmatrixindicatesthecurrentrequestofeachprocess.IfRequest[i,j]=k,thenprocessPiisrequestingkmoreinstancesofresourcetype.Rj.

（请求：一个nxm

的矩阵使命了当前的进程请求。如果Request[i,j]=k,那么进程Pi请求k个Rj资源的实例）DetectionAlgorithm(检测算法）1. LetWorkandFinishbevectorsoflengthmandn,respectivelyInitialize(让Work和Finish作为长度为m和n的向量）(a)Work:=Available(b) Fori=1,2,…,n,ifAllocationi

0,then

Finish[i]:=false;otherwise,Finish[i]:=true.2. Findanindexisuchthatboth（找到下标i）(a) Finish[i]=false(b) Requesti

WorkIfnosuchiexists,gotostep4.（如果没有这样的i存在，转4）DetectionAlgorithm(Cont.)3. Work:=Work+Allocationi

Finish[i]:=true

gotostep2.4. IfFinish[i]=false,forsomei,1in,thenthesystemisindeadlockstate.Moreover,ifFinish[i]=false,thenPiisdeadlocked.

Algorithmrequiresanorderofmxn2operationstodetectwhetherthesystemisindeadlockedstate.算法需要mxn2的操作来判断是否系统处于死锁状态ExampleofDetectionAlgorithm

检测算法的例子FiveprocessesP0throughP4;

threeresourcetypes

A(7instances),B(2instances),andC(6instances). （五个进程p0到p4,三个资源类型A（7个实例），B（2个实例）,C（6个实例）SnapshotattimeT0（时刻Tn的状态）

Allocation Request Available

ABC ABC ABC

P0 010 000 000

P1 200 202

P2 303 000

P3 211 100

P4 002 002Sequence<P0,P2,P3,P1,P4>willresultinFinish[i]=trueforalli.Example(Cont.)（例子续）P2requestsanadditionalinstanceoftypeC.（P2请求C的实例）

Request ABC

P0 000

P1 201

P2 001

P3 100

P4 002Stateofsystem?（系统的状态）CanreclaimresourcesheldbyprocessP0,butinsufficientresourcestofulfillotherprocesses;requests.

（可以归还P0所有的资源，但是资源不够完成其他进程的请求）Deadlockexists,consistingofpr