CCH08_Deadlock(操作系统).ppt

Module8:Deadlocks（死锁）,SystemModel（系统模型）DeadlockCharacterization（死锁特征）MethodsforHandlingDeadlocks（处理死锁的方法）DeadlockPrevention（预防死锁）DeadlockAvoidance（死锁避免）DeadlockDetection（死锁检测）RecoveryfromDeadlock（死锁恢复）CombinedApproachtoDeadlockHandling（综合处理方法）,TheDeadlockProblem（死锁问题）,Asetofblockedprocesseseachholdingaresourceandwaitingtoacquirearesourceheldbyanotherprocessintheset.（一组等待的进程，其中每一个进程都持有资源，并且等待着由这个组中其他进程所持有的资源）死锁Deadlock：计算机系统中多道程序并发执行时，两个或两个以上的进程由于竞争资源而造成的一种互相等待的现象（僵局），如无外力作用，这些进程将永远不能再向前推进。,如果一个进程要使用OS管理的资源，需先向系统提出申请，如果有可用资源，系统才进行分配。资源的分类,根据资源性质：可抢占资源指资源占有进程虽然需要使用该资源，但另一个进程却可强行把资源从占有者进程处抢来。不可抢占资源指只有占用者进程不再需要使用该资源而主动释放资源外，其它进程不得在占有者进程使用资源过程中强行抢占。,根据使用方式：共享资源和独占资源。根据使用期限；永久资源和临时性资源。,可顺序重复使用的资源,由一个进程产生，被另外一个进程使用短暂时间之后便无用的资源,TheDeadlockProblem,Example1Systemhas2tapedrives.（系统有两个磁带设备）P1andP2eachholdonetapedriveandeachneedsanotherone.（进程P1和P2各占有一个磁带设备并且实际需要两个磁带）Example2semaphoresAandB,initializedto1（信号量A，B初始化为1）P0P1wait(A);wait(B)wait(B);wait(A),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将进入不安全区域（进程推进顺序非法）,P1：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:thereexistsasetP0,P1,P0ofwaitingprocessessuchthatP0iswaitingforaresourcethatisheldbyP1,P1iswaitingforaresourcethatisheldbyP2,Pn1iswaitingforaresourcethatisheldbyPn,andP0iswaitingforaresourcethatisheldbyP0.（循环等待：等待资源的进程之间存在环）,SystemModel（系统模型）,Resourcetypes（资源类型）R1,R2,.,RmCPUcycles,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：含有系统中全部的资源）requestedgedirectededgeP1Rj（请求边：直接P1Rj）assignmentedgedirectededgeRjPi（分配边：P1Rj）,AsetofverticesVandasetofedgesE.（一个顶点的集合V和边的集合E）,Resource-AllocationGraph(Cont.)资源分配图续,Process进程ResourceTypewith4instances有四个实例的资源类型PirequestsinstanceofRj（Pi请求一个Rj的实例）PiisholdinganinstanceofRj（Pi持有一个Rj的实例）,Pi,Pi,Rj,Rj,ExampleofaResourceAllocationGraph资源分配图的例子,ResourceAllocationGraphWithADeadlock有死锁的资源分配图,ResourceAllocationGraphWithACycleButNoDeadlock有环但没有死锁的资源分配图,BasicFacts（基本事实）,Ifgraphcontainsnocyclesnodeadlock.（如果图没有环，那么不会有死锁）Ifgraphcontainsacycle（如果图有环）ifonlyoneinstanceperresourcetype,thendeadlock.（如果每一种资源类型只有一个实例，那么死锁发生）ifseveralinstancesperresourcetype,possibilityofdeadlock.（如果一种资源类型有多个实例，可能死锁）,MethodsforHandlingDeadlocks处理死锁的方法,Ensurethatthesystemwillneverenteradeadlockstate.（确保系统永远不会进入死锁状态）Allowthesystemtoenteradeadlockstateandthenrecover.（允许系统进入死锁状态，然后恢复系统）Ignoretheproblemandpretendthatdeadlocksneveroccurinthesystem;usedbymostoperatingsystems,includingUNIX.（忽略这个问题，假装系统中从未出现过死锁。这个方法被大部分的操作系统采用，包括UNIX）预防、避免、检测、解除,DeadlockPrevention（死锁的预防）,MutualExclusionnotrequiredforsharableresources;mustholdfornonsharableresources.（互斥：共享资源不是必须的，必须保持非共享资源）HoldandWaitmustguaranteethatwheneveraprocessrequestsaresource,itdoesnotholdanyotherresources.（占有并等待：必须保证进程申请资源的时候没有占有其他资源）Requireprocesstorequestandbeallocatedallitsresourcesbeforeitbeginsexecution,orallowprocesstorequestresourcesonlywhentheprocesshasnone.（要求进程在执行前一次申请全部的资源，只有没有占有资源时才可以分配资源）Lowresourceutilization;starvationpossible.（利用率低，可能出现饥饿）,Restrainthewaysrequestcanbemade.（抑制死锁发生的必要条件）,DeadlockPrevention(Cont.)死锁的预防（续）,NoPreemption（非抢占）Ifaprocessthatisholdingsomeresourcesrequestsanotherresourcethatcannotbeimmediatelyallocatedtoit,thenallresourcescurrentlybeingheldarereleased.（如果一个进程的申请没有实现，它要释放所有占有的资源）Preemptedresourcesareaddedtothelistofresourcesforwhichtheprocessiswaiting.（先占的资源放入进程等待资源列表中）Processwillberestartedonlywhenitcanregainitsoldresources,aswellasthenewonesthatitisrequesting.（进程在有新的资源请求时，若能够重新得到旧的资源，可以重新开始）CircularWaitimposeatotalorderingofallresourcetypes,andrequirethateachprocessrequestsresourcesinanincreasingorderofenumeration.（循环等待：将所有的资源类型放入资源列表中，并且要求进程按照资源表申请资源）,DeadlockAvoidance（死锁避免）,Simplestandmostusefulmodelrequiresthateachprocessdeclarethemaximumnumberofresourcesofeachtypethatitmayneed.（一个简单而有效的模型要求每一个进程声明它所需要的资源的最大数）Thedeadlock-avoidancealgorithmdynamicallyexaminestheresource-allocationstatetoensurethattherecanneverbeacircular-waitcondition.（死锁避免算法动态检查资源分配状态以确保不会出现循环等待的情况）Resource-allocationstateisdefinedbythenumberofavailableandallocatedresources,andthemaximumdemandsoftheprocesses.（资源分配状态定义为可用的与已分配的资源数，和进程所需的最大资源量）,Requiresthatthesystemhassomeadditionalaprioriinformationavailable.（需要系统有一些额外的信息）,SafeState,安全状态是指系统的一种状态，在此状态下,系统能按某种顺序（例如P1、P2Pn）来为各个进程分配其所需资源，直至最大需求，使每个进程都可顺序地一个个地完成。这个序列（P1、P2.Pn）称为安全序列。若某一时刻不存在一个安全序列，则称系统处于不安全状态。,SafeState（安全状态）,Whenaprocessrequestsanavailableresource,systemmustdecideifimmediateallocationleavesthesysteminasafestate.（当进程申请一个有效的资源的时候，系统必须确定分配后是安全的）Systemisinsafestateifthereexistsasafesequenceofallprocesses.（系统处于安全态，如果存在一个安全序列）SequenceissafeifforeachPi,theresourcesthatPicanstillrequestcanbesatisfiedbycurrentlyavailableresources+resourcesheldbyallthePj,withjI.（进程序列是安全的，如果每一个进程Pi所申请的可以被满足的资源数加上其他进程所持有的该资源数小于系统总数）IfPiresourceneedsarenotimmediatelyavailable,thenPicanwaituntilallPjhavefinished.WhenPjisfinished,Picanobtainneededresources,execute,returnallocatedresources,andterminate.WhenPiterminates,Pi+1canobtainitsneededresources,andsoon.,BasicFacts（基本事实）,Ifasystemisinsafestatenodeadlocks.（如果一个系统在安全状态，就没有死锁）Ifasystemisinunsafestatepossibilityofdeadlock.（如果一个系统不是处于安全状态，就有可能死锁）Avoidanceensurethatasystemwillneverenteranunsafestate.（避免：确保系统永远不会进入死锁状态）,Safe,unsafe,deadlockstatespaces安全、不安全、死锁状态空间,Resource-AllocationGraphAlgorithm资源分配图算法,ClaimedgePiRjindicatedthatprocessPjmayrequestresourceRj;representedbyadashedline.(边PiRj代表进程Pi申请资源Ri，表示为虚线）Claimedgeconvertstorequestedgewhenaprocessrequestsaresource.（一个进程申请资源的时候连一个边）Whenaresourceisreleasedbyaprocess,assignmentedgereconvertstoaclaimedge.（当资源被释放的时候，取消边）Resourcesmustbeclaimedaprioriinthesystem.（系统中的资源必须被声明为一个priori）,Resource-AllocationGraphForDeadlockAvoidance死锁避免的资源分配图,UnsafeStateInAResource-AllocationGraph不安全的状态图,BankersAlgorithm（银行家算法）,Multipleinstances.（多个实例）Eachprocessmustaprioriclaimmaximumuse.（每一个进程必须事先声明使用的最大量）Whenaprocessrequestsaresourceitmayhavetowait.（当一个进程请求资源，它可能要等待）Whenaprocessgetsallitsresourcesitmustreturntheminafiniteamountoftime.（当一个进程得到所有的资源，它必须在有限的时间释放它们）,DataStructuresfortheBankersAlgorithm银行家算法的数据结构,Available:Vectoroflengthm.Ifavailablej=k,therearekinstancesofresourcetypeRjavailable.（如果availablej=k,那么资源Rj有k个实例有效）Max:nxmmatrix.IfMaxi,j=k,thenprocessPimayrequestatmostkinstancesofresourcetypeRj.（如果Maxi,j=k,那么进程Pi可以最多请求资源Rj的k个实例）,Letn=numberofprocesses,andm=numberofresourcestypes.N为进程的数目，M为资源类型的数目,Allocation:nxmmatrix.IfAllocationi,j=kthenPiiscurrentlyallocatedkinstancesofRj.（如果Allocationi,j=k,那么进程Pj当前分配了k个资源Rj的实例）Need:nxmmatrix.IfNeedi,j=k,thenPimayneedkmoreinstancesofRjtocompleteitstask.（如果Needi,j=k,那么进程Pi还需要k个资源Rj的实例）Needi,j=Maxi,jAllocationi,j.,DataStructuresfortheBankersAlgorithm银行家算法的数据结构,SafetyAlgorithm（安全算法）,1.LetWorkandFinishbevectorsoflengthmandn,respectively.Initialize（让Work和Finish作为长度为m和n的向量）Work:=AvailableFinishi=falsefori-1,3,n.2.Findandisuchthatboth:（找到i）(a)Finishi=false(b)NeediWorkIfnosuchiexists,gotostep4.3.Work:=Work+AllocationiFinishi:=truegotostep2.4.IfFinishi=trueforalli,thenthesystemisinasafestate.,Resource-RequestAlgorithmforProcessPi进程Pi的资源请求,Requesti=requestvectorforprocessPi.IfRequestij=kthenprocessPiwantskinstancesofresourcetypeRj.1.IfRequestiNeedigotostep2.Otherwise,raiseerrorcondition,sinceprocesshasexceededitsmaximumclaim.2.IfRequestiAvailable,gotostep3.OtherwisePimustwait,sinceresourcesarenotavailable.3.PretendtoallocaterequestedresourcestoPibymodifyingthestateasfollows:Available:=AvailableRequesti;Allocationi:=Allocationi+Requesti;Needi:=NeediRequesti;IfsafetheresourcesareallocatedtoPi.IfunsafePimustwait,andtheoldresource-allocationstateisrestored,ExampleofBankersAlgorithm银行家算法的例子,5processesP0throughP4;3resourcetypesA(10instances),B(5instances,andC(7instances).（5个进程P0到P4:3个资源类型A(10个实例），B（5个实例），C（7个实例）SnapshotattimeT0:（时刻T0的片段）AllocationMaxAvailableABCABCABCP0010753332P1200322P2302902P3211222P4002433,Example(Cont.)（例子续）,Thecontentofthematrix.NeedisdefinedtobeMaxAllocation.（矩阵的内容。需要被定义为最大值）NeedABCP0743P1122P2600P3011P4431Thesystemisinasafestatesincethesequencesatisfiessafetycriteria.（系统在安全的状态因为序列P1,P3,P4,P2,P0满足了安全的标准）,用安全检测算法看能否找到一个安全序列Work=available=(3,3,2)Finishi=false(i=0.4)WorkneedallocationfinishP1332122200TP3532011211TP4743431002TP2745600302TP01047743010T存在安全序列：（P1，P3，P4，P2，P0）,Example(Cont.),通常，安全序列不是唯一的Work=available=(3,3,2)Finishi=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)为真）AllocationNeedAvailableABCABCABCP0010743230P1302020P2302600P3211011P4002431Executingsafetyalgorithmshowsthatsequencesatisfiessafetyrequirement.（执行安全算法表明序列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.（节点是进程）PiPjifPiiswaitingforPj.（PiPj表明Pi在等待Pj.）Periodicallyinvokeanalgorithmthatsearchesforacycleinthegraph.（定期调用算法来检查是否有环）Analgorithmtodetectacycleinagraphrequiresanorderofn2operations,wherenisthenumberofverticesinthegraph.（一个检查图中是否有环的算法需要n2的操作来进行，n为图中的节点数）,Resource-AllocationGraphAndWait-forGraph资源分配图和等待图,Resource-AllocationGraph,Correspondingwait-forgraph,SeveralInstancesofaResourceType一个资源类型的多个实例,Available:Avectoroflengthmindicatesthenumberofavailableresourcesofeachtype.（可用：一个长度m的向量代表每种资源类型的有效数目）Allocation:Annxmmatrixdefinesthenumberofresourcesofeachtypecurrentlyallocatedtoeachprocess.（分配：一个nxm的矩阵定义了当前分配的每一种资源类型的实例数目）Request:Annxmmatrixindicatesthecurrentrequestofeachprocess.IfRequesti,j=k,thenprocessPiisrequestingkmoreinstancesofresourcetype.Rj.（请求：一个nxm的矩阵使命了当前的进程请求。如果Requesti,j=k,那么进程Pi请求k个Rj资源的实例）,DetectionAlgorithm(检测算法）,1.LetWorkandFinishbevectorsoflengthmandn,respectivelyInitialize(让Work和Finish作为长度为m和n的向量）(a)Work:=Available(b)Fori=1,2,n,ifAllocationi0,thenFinishi:=false;otherwise,Finishi:=true.2.Findanindexisuchthatboth（找到下标i）(a)Finishi=false(b)RequestiWorkIfnosuchiexists,gotostep4.（如果没有这样的i存在，转4）,DetectionAlgorithm(Cont.),3.Work:=Work+AllocationiFinishi:=truegotostep2.4.IfFinishi=false,forsomei,1in,thenthesystemisindeadlockstate.Moreover,ifFinishi=false,thenPiisdeadlocked.,Algorithmrequiresanorderofmxn2operationstodetectwhetherthesystemisindeadlockedstate.算法需要mxn2的操作来判断是否系统处于死锁状态,ExampleofDetectionAlgorithm检测算法的例子,FiveprocessesP0throughP4;threeresourcetypesA(7instances),B(2instances),andC(6instances).（五个进程p0到p4,三个资源类型A（7个实例），B（2个实例）,C（6个实例）SnapshotattimeT0（时刻Tn的状态）AllocationRequestAvailableABCABCABCP0010000000P1200202P2303000P3211100P4002002SequencewillresultinFinishi=trueforalli.,Example(Cont.)（例子续）,P2requestsanadditionalinstanceoftypeC.（P2请求C的实例）RequestABCP0000P1201P2001P3100P4002Stateofsystem?（系统的状态）CanreclaimresourcesheldbyprocessP0,butinsufficientresourcestofulfillotherprocesses;requests.（可以归还P0所有的资源，但是资源不够完成其他进程的请求）Deadlockexists,consistingofprocessesP1,P2,P3,andP4.（死锁存在，包括进程P1,P2,P3和P4),Detection-AlgorithmUsage检测算法的应用,When,andhowoften,toinvokedependson:（何时，如何频度的调用取决于）Howoftenadeadlockislikelytooccur?（死锁可能发生的频度）Howmanyprocesseswillneedtoberolledback?（多少进程可能需要反转）oneforeachd