操作系统第8章

Chapter8：DeadlocksSystemModel（系统模型）DeadlockCharacterization（死锁特征）MethodsforHandlingDeadlocks（处理死锁的方法）DeadlockPrevention（预防死锁）DeadlockAvoidance（死锁避免）DeadlockDetection（死锁检测）RecoveryfromDeadlock（死锁恢复）CombinedApproachtoDeadlockHandling（综合处理方法）Deadlock资源是有限的，对资源的需求可能是无限的当占有了部分资源而渴求更多的资源的时候，可能会引起deadlock（死锁）OS管理着、分配着计算机系统的资源，必须考虑死锁TheDeadlockProblemAsetofblockedprocesseseachholdingaresourceandwaitingtoacquirearesourceheldbyanotherprocessintheset.ExampleSystemhas2tapedrives.P1andP2eachholdonetapedriveandeachneedsanotherone.ExamplesemaphoresAandB,initializedto1P0P1wait(A);wait(B)wait(B);wait(A)BridgeCrossingExampleTrafficonlyinonedirection.Eachsectionofabridgecanbeviewedasaresource.Ifadeadlockoccurs,itcanberesolvedifonecarbacksup(preemptresourcesandrollback).Severalcarsmayhavetobebackedupifadeadlockoccurs.Starvationispossible.SystemModelResourcetypesR1,R2,...,RmCPUcycles,memoryspace,I/OdevicesEachresourcetypeRihasWiinstances.cpu，一个存储，一个硬盘（多个分区）、U盘、光盘……打印机，一个……Eachprocessutilizesaresourceasfollows:requestusereleaseDeadlockCharacterizationMutualexclusion（互斥）:onlyoneprocessatatimecanusearesource.Holdandwait（占有和等待）:aprocessholdingatleastoneresourceiswaitingtoacquireadditionalresourcesheldbyotherprocesses.Nopreemption（非剥夺）:aresourcecanbereleasedonlyvoluntarilybytheprocessholdingit,afterthatprocesshascompleteditstask.Circularwait（循环等待）:thereexistsaset{P0,P1,…,P0}ofwaitingprocessessuchthatP0iswaitingforaresourcethatisheldbyP1,P1iswaitingforaresourcethatisheldbyP2,…,Pn–1iswaitingforaresourcethatisheldbyPn,andP0iswaitingforaresourcethatisheldbyP0.（有环）Deadlockcanariseiffourconditionsholdsimultaneously.Resource-AllocationGraphVispartitionedintotwotypes:P={P1,P2,…,Pn},thesetconsistingofalltheprocessesinthesystem.R={R1,R2,…,Rm},thesetconsistingofallresourcetypesinthesystem.requestedge–directededgeP1Rjassignmentedge–directededgeRjPiAsetofverticesVandasetofedgesE.Resource-AllocationGraph(Cont.)ProcessResourceTypewith4instancesPirequestsinstanceofRjPiisholdinganinstanceofRjPiPiRjRjExampleofaResourceAllocationGraphResourceAllocationGraphWithADeadlockResourceAllocationGraphWithACycleButNoDeadlockBasicFactsIfgraphcontainsnocyclesnodeadlock.Ifgraphcontainsacycleifonlyoneinstanceperresourcetype,thendeadlock.ifseveralinstancesperresourcetype,possibilityofdeadlock.MethodsforHandlingDeadlocksEnsurethatthesystemwillneverenteradeadlockstate.TopreventoravoidAllowthesystemtoenteradeadlockstateandthenrecover.Ignoretheproblemandpretendthatdeadlocksneveroccurinthesystem;usedbymostoperatingsystems,includingUNIX.DeadlockPreventionMutualExclusion–notrequiredforsharableresources;mustholdfornonsharableresources.HoldandWait–mustguaranteethatwheneveraprocessrequestsaresource,itdoesnotholdanyotherresources.Requireprocesstorequestandbeallocatedallitsresourcesbeforeitbeginsexecution,orallowprocesstorequestresourcesonlywhentheprocesshasnone.Lowresourceutilization;starvationpossible.Restrainthewaysrequestcanbemade.会发现：实现这样一个策略可能带来的问题比他所解决的问题更多！DeadlockPrevention(Cont.)NoPreemption–Ifaprocessthatisholdingsomeresourcesrequestsanotherresourcethatcannotbeimmediatelyallocatedtoit,thenallresourcescurrentlybeingheldarereleased.Preemptedresourcesareaddedtothelistofresourcesforwhichtheprocessiswaiting.Processwillberestartedonlywhenitcanregainitsoldresources,aswellasthenewonesthatitisrequesting.CircularWait–imposeatotalorderingofallresourcetypes,andrequirethateachprocessrequestsresourcesinanincreasingorderofenumeration.DeadlockAvoidance死锁避免Simplestandmostusefulmodelrequiresthateachprocessdeclarethemaximumnumberofresourcesofeachtypethatitmayneed.Thedeadlock-avoidancealgorithmdynamicallyexaminestheresource-allocationstatetoensurethattherecanneverbeacircular-waitcondition.无环，安全Resource-allocationstateisdefinedbythenumberofavailableandallocatedresources,andthemaximumdemandsoftheprocesses.Requiresthatthesystemhassomeadditionalaprioriinformationavailable.需要一些先验知识SafeStateWhenaprocessrequestsanavailableresource,systemmustdecideifimmediateallocationleavesthesysteminasafestate.什么叫安全状态？Systemisinsafestateifthereexistsasafesequenceofallprocesses.SequenceP1,P2,…,PnissafeifforeachPi,theresourcesthatPicanstillrequestcanbesatisfiedbycurrentlyavailableresources+resourcesheldbyallthePj,withji.IfPiresourceneedsarenotimmediatelyavailable,thenPicanwaituntilallPjhavefinished.WhenPjisfinished,Picanobtainneededresources,execute,returnallocatedresources,andterminate.WhenPiterminates,Pi+1canobtainitsneededresources,andsoon.基于：进程执行完以后会释放它占用的资源；进程会在有限时间段内执行完；所以，安不安全就是针对当前资源和进程集，看能不能找到进程的安全执行序列BasicFactsIfasystemisinsafestatenodeadlocks.Ifasystemisinunsafestatepossibilityofdeadlock.Avoidanceensurethatasystemwillneverenteranunsafestate.死锁避免算法的目的就是让系统从不进入非安全的状态Safe,Unsafe,DeadlockState例子Resourceinstances，12Processes，3MaximumNeedscurrentNeedsP0105P142P292死锁避免使系统处于安全状态进程需要申明他需要的资源最大数（不同资源）死锁避免算法要确保系统处于安全状态，即能不能找到进程安全执行序列死锁避免算法资源分配图，适合于每类资源只有一个实例银行家算法，适合于每类资源有多个实例Resource-AllocationGraphAlgorithmClaimedgePi