operating system《操作系统》ch07-deadlock

Chapter7:DeadlocksChapterObjectivesTodevelopadescriptionofdeadlocks,whichpreventsetsofconcurrentprocessesfromcompletingtheirtasksTopresentanumberofdifferentmethodsforpreventingoravoidingdeadlocksinacomputersystem.ContentOverviewTheDeadlockProblemSystemModelDeadlockCharacterizationMethodsforHandlingDeadlocksDeadlockPreventionDeadlockAvoidanceDeadlockDetectionRecoveryfromDeadlockTheDeadlockProblemAsetofblockedprocesseseachholdingaresourceandwaitingtoacquirearesourceheldbyanotherprocessintheset.ExampleSystemhas2diskdrives.P1andP2eachholdonediskdriveandeachneedsanotherone.ExamplesemaphoresAandB,initializedto1P0P1wait(A);wait(B)wait(B);wait(A)BridgeCrossingExampleTrafficonlyinonedirection.Eachsectionofabridgecanbeviewedasaresource.Ifadeadlockoccurs,itcanberesolvedifonecarbacksup(preemptresourcesandrollback).Severalcarsmayhavetobebackedupifadeadlockoccurs.Starvationispossible.7.1SystemModelResourcetypesR1,R2,...,RmCPUcycles,memoryspace,I/OdevicesEachresourcetypeRihasWiinstances.Eachprocessutilizesaresourceasfollows:requestuserelease7.2DeadlockCharacterizationMutualexclusion:onlyoneprocessatatimecanusearesource.Holdandwait:aprocessholdingatleastoneresourceiswaitingtoacquireadditionalresourcesheldbyotherprocesses.Nopreemption:aresourcecanbereleasedonlyvoluntarilybytheprocessholdingit,afterthatprocesshascompleteditstask.Circularwait:thereexistsaset{P0,P1,…,P0}ofwaitingprocessessuchthatP0iswaitingforaresourcethatisheldbyP1,P1iswaitingforaresourcethatisheldbyP2,…,Pn–1iswaitingforaresourcethatisheldbyPn,andP0iswaitingforaresourcethatisheldbyP0.Deadlockcanariseiffourconditionsholdsimultaneously.Resource-AllocationGraphVispartitionedintotwotypes:P={P1,P2,…,Pn},thesetconsistingofalltheprocessesinthesystem.R={R1,R2,…,Rm},thesetconsistingofallresourcetypesinthesystem.requestedge–directededgeP1Rjassignmentedge–directededgeRjPiAsetofverticesVandasetofedgesE.Resource-AllocationGraph(Cont.)ProcessResourceTypewith4instancesPirequestsinstanceofRjPiisholdinganinstanceofRjPiPiRjRjExampleofaResourceAllocationGraphResourceAllocationGraphWithADeadlockGraphWithACycleButNoDeadlockBasicFactsIfgraphcontainsnocyclesnodeadlock.Ifgraphcontainsacycleifonlyoneinstanceperresourcetype,thendeadlock.ifseveralinstancesperresourcetype,possibilityofdeadlock.7.3MethodsforHandlingDeadlocksEnsurethatthesystemwillneverenteradeadlockstate.Allowthesystemtoenteradeadlockstateandthenrecover.Ignoretheproblemandpretendthatdeadlocksneveroccurinthesystem;usedbymostoperatingsystems,includingUNIX.7.4DeadlockPreventionMutualExclusion–notrequiredforsharableresources;mustholdfornon-sharableresources.HoldandWait–mustguaranteethatwheneveraprocessrequestsaresource,itdoesnotholdanyotherresources.Requireprocesstorequestandbeallocatedallitsresourcesbeforeitbeginsexecution,orallowprocesstorequestresourcesonlywhentheprocesshasnone.Lowresourceutilization;starvationpossible.Restrainthewaysrequestcanbemade.DeadlockPrevention(Cont.)NoPreemption–Ifaprocessthatisholdingsomeresourcesrequestsanotherresourcethatcannotbeimmediatelyallocatedtoit,thenallresourcescurrentlybeingheldarereleased.Preemptedresourcesareaddedtothelistofresourcesforwhichtheprocessiswaiting.Processwillberestartedonlywhenitcanregainitsoldresources,aswellasthenewonesthatitisrequesting.CircularWait–imposeatotalorderingofallresourcetypes,andrequirethateachprocessrequestsresourcesinanincreasingorderofenumeration.7.5DeadlockAvoidanceSimplestandmostusefulmodelrequiresthateachprocessdeclarethemaximumnumberofresourcesofeachtypethatitmayneed.Thedeadlock-avoidancealgorithmdynamicallyexaminestheresource-allocationstatetoensurethattherecanneverbeacircular-waitcondition.Resource-allocationstateisdefinedbythenumberofavailableandallocatedresources,andthemaximumdemandsoftheprocesses.Requiresthatthesystemhassomeadditionalaprioriinformationavailable.SafeStateWhenaprocessrequestsanavailableresource,systemmustdecideifimmediateallocationleavesthesysteminasafestate.SystemisinsafestateifthereexistsasequenceofALLtheprocessesisthesystemssuchthatforeachPi,theresourcesthatPicanstillrequestcanbesatisfiedbycurrentlyavailableresources+resourcesheldbyallthePj,withjsatisfiessafetycriteria.Example:P1Request(1,0,2)CheckthatRequestAvailable(thatis,(1,0,2)(3,3,2)true.AllocationNeedAvailableABCABCABCP0010743230P1302020P2301600P3211011P4002431Executingsafetyalgorithmshowsthatsequencesatisfiessafetyrequirement.Canrequestfor(3,3,0)byP4begranted?Canrequestfor(0,2,0)byP0begranted?7.6DeadlockDetectionAllowsystemtoenterdeadlockstateDetectionalgorithmRecoveryschemeSingleInstanceofEachResourceTypeMaintainwait-forgraphNodesareprocesses.PiPjifPiiswaitingforPj.Periodicallyinvokeanalgorithmthatsearchesforacycleinthegraph.Ifthereisacycle,thereexistsadeadlock.Analgorithmtodetectacycleinagraphrequiresanorderofn2operations,wherenisthenumberofverticesinthegraph.Resource-AllocationGraphandWait-forGraphResource-AllocationGraphCorrespondingwait-forgraphSeveralInstancesofaResourceTypeAvailable:Avectoroflengthmindicatesthenumberofavailableresourcesofeachtype.Allocation:Annxmmatrixdefinesthenumberofresourcesofeachtypecurrentlyallocatedtoeachprocess.Request:Annxmmatrixindicatesthecurrentrequestofeachprocess.IfRequest[ij]=k,thenprocessPiisrequestingkmoreinstancesofresourcetype.Rj.DetectionAlgorithm1.LetWorkandFinishbevectorsoflengthmandn,respectivelyInitialize:(a)Work=AvailableFori=1,2,…,n,ifAllocationi0,thenFinish[i]=false;otherwise,Finish[i]=true.2.Findanindexisuchthatboth:(a)Finish[i]==false(b)RequestiWorkIfnosuchiexists,gotostep4.3.Work=Work+AllocationiFinish[i]=truegotostep2.IfFinish[i]==false,forsomei,1in,thenthesystemisindeadlockstate.Moreover,ifFinish[i]==false,thenPiisdeadlocked.AlgorithmrequiresanorderofO(mxn2)operationstodetectwhetherthesystemisindeadlockedstate.ExampleofDetectionAlgorithm5processesP0throughP4;3resourcetypesA(7instances),B(2instances),andC(6instances).SnapshotattimeT0:AllocationRequestAvailableABCABCABCP0010000000P1200202P2303000P3211100P4002002SequencewillresultinFinish[i]=trueforalli.Example(Cont.)P2requestsanadditionalinstanceoftypeC.RequestABCP0000P1202P2001P3100P4002Stateofsystem?CanreclaimresourcesheldbyprocessP0,butinsufficientresourcestofulfillotherprocesses’requests.Deadlockexists,consistingofprocessesP1,P2,P3,andP4.Detection-AlgorithmUsageWhen,andhowoften,toinvokedependson:Howoftenadeadlockislikelytooccur?Howmanyprocesseswillneedtoberolledback?oneforeachdisjointcycleIfdetectionalgorithmisinvokedarbitrarily,theremaybemanycyclesintheresourcegraphandsowewouldnotbeabletotellwhichofthemanydeadlockedprocesses“caused”thedeadlock.7.7RecoveryfromDeadlock:ProcessTerminationAbortalldeadlockedprocesses.Abortoneprocessatatimeuntilthedeadlockcycleiseliminated.Inwhichordershouldwechoosetoabort?Priorityoftheprocess.Howlongprocesshascomputed,andhowmuchlongertocompletion.Resourcestheprocesshasused.Resourcesprocessneedstocomplete.Howmanyprocesseswillneedtobeterminated.Isprocessinteractiveorbatch?RecoveryfromDeadlock:ResourcePreemptionSelectingavictim–minimizecost.Rollback–returntosomesafestate,restartprocessforthatstate.Starvation–sameprocessmayalwaysbepickedasvictim,includenumberofrollbackincostfactor.EndofChapter7homework:1267101114