您好,欢迎访问三七文档
Chapter8:DeadlocksSystemModel(系统模型)DeadlockCharacterization(死锁特征)MethodsforHandlingDeadlocks(处理死锁的方法)DeadlockPrevention(预防死锁)DeadlockAvoidance(死锁避免)DeadlockDetection(死锁检测)RecoveryfromDeadlock(死锁恢复)CombinedApproachtoDeadlockHandling(综合处理方法)Deadlock资源是有限的,对资源的需求可能是无限的当占有了部分资源而渴求更多的资源的时候,可能会引起deadlock(死锁)OS管理着、分配着计算机系统的资源,必须考虑死锁TheDeadlockProblemAsetofblockedprocesseseachholdingaresourceandwaitingtoacquirearesourceheldbyanotherprocessintheset.ExampleSystemhas2tapedrives.P1andP2eachholdonetapedriveandeachneedsanotherone.ExamplesemaphoresAandB,initializedto1P0P1wait(A);wait(B)wait(B);wait(A)BridgeCrossingExampleTrafficonlyinonedirection.Eachsectionofabridgecanbeviewedasaresource.Ifadeadlockoccurs,itcanberesolvedifonecarbacksup(preemptresourcesandrollback).Severalcarsmayhavetobebackedupifadeadlockoccurs.Starvationispossible.SystemModelResourcetypesR1,R2,...,RmCPUcycles,memoryspace,I/OdevicesEachresourcetypeRihasWiinstances.cpu,一个存储,一个硬盘(多个分区)、U盘、光盘……打印机,一个……Eachprocessutilizesaresourceasfollows:requestusereleaseDeadlockCharacterizationMutualexclusion(互斥):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–directededgeP1Rjassignmentedge–directededgeRjPiAsetofverticesVandasetofedgesE.Resource-AllocationGraph(Cont.)ProcessResourceTypewith4instancesPirequestsinstanceofRjPiisholdinganinstanceofRjPiPiRjRjExampleofaResourceAllocationGraphResourceAllocationGraphWithADeadlockResourceAllocationGraphWithACycleButNoDeadlockBasicFactsIfgraphcontainsnocyclesnodeadlock.Ifgraphcontainsacycleifonlyoneinstanceperresourcetype,thendeadlock.ifseveralinstancesperresourcetype,possibilityofdeadlock.MethodsforHandlingDeadlocksEnsurethatthesystemwillneverenteradeadlockstate.TopreventoravoidAllowthesystemtoenteradeadlockstateandthenrecover.Ignoretheproblemandpretendthatdeadlocksneveroccurinthesystem;usedbymostoperatingsystems,includingUNIX.DeadlockPreventionMutualExclusion–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.需要一些先验知识SafeStateWhenaprocessrequestsanavailableresource,systemmustdecideifimmediateallocationleavesthesysteminasafestate.什么叫安全状态?Systemisinsafestateifthereexistsasafesequenceofallprocesses.SequenceP1,P2,…,PnissafeifforeachPi,theresourcesthatPicanstillrequestcanbesatisfiedbycurrentlyavailableresources+resourcesheldbyallthePj,withji.IfPiresourceneedsarenotimmediatelyavailable,thenPicanwaituntilallPjhavefinished.WhenPjisfinished,Picanobtainneededresources,execute,returnallocatedresources,andterminate.WhenPiterminates,Pi+1canobtainitsneededresources,andsoon.基于:进程执行完以后会释放它占用的资源;进程会在有限时间段内执行完;所以,安不安全就是针对当前资源和进程集,看能不能找到进程的安全执行序列BasicFactsIfasystemisinsafestatenodeadlocks.Ifasystemisinunsafestatepossibilityofdeadlock.Avoidanceensurethatasystemwillneverenteranunsafestate.死锁避免算法的目的就是让系统从不进入非安全的状态Safe,Unsafe,DeadlockState例子Resourceinstances,12Processes,3MaximumNeedscurrentNeedsP0105P142P292死锁避免使系统处于安全状态进程需要申明他需要的资源最大数(不同资源)死锁避免算法要确保系统处于安全状态,即能不能找到进程安全执行序列死锁避免算法资源分配图,适合于每类资源只有一个实例银行家算法,适合于每类资源有多个实例Resource-AllocationGraphAlgorithmClaimedgePi
本文标题:操作系统第8章
链接地址:https://www.777doc.com/doc-5473811 .html