中科大操作系统原理与实现课件7_deadlock.pdf

《中科大操作系统原理与实现课件7_deadlock.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、操作系统原理与设计第7章Deadlocks（死锁）陈香兰中国科学技术大学计算机学院2009年11月05日......提纲BackgroundandSystemModelDeadlockCharacterizationNecessaryConditionsResource-AllocationGraphMethodsforHandlingDeadlocksDeadlockPreventionDeadlockAvoidanceSafeStateResource-AllocationGraphSchemeBanker’sAlgorit

2、hmDeadlockDetection小结和作业......OutlineBackgroundandSystemModelDeadlockCharacterizationNecessaryConditionsResource-AllocationGraphMethodsforHandlingDeadlocksDeadlockPreventionDeadlockAvoidanceSafeStateResource-AllocationGraphSchemeBanker’sAlgorithmDeadlockDetection小结和作

3、业......TheDeadlockProblemdeadlocksituationAsetofblockedprocesseseachholdingaresourceandwaitingtoacquirearesourceheldbyanotherprocessintheset.ExampleISystemhas2diskdrives.IP1andP2eachholdonediskdriveandeachneedsanotherone.ExampleP0P1IsemaphoresAandB,initializedto1wait

4、(A);wait(B)wait(B);wait(A)......BridgeCrossingExampleITrafficonlyinonedirection.IEachsectionofabridgecanbeviewedasaresource.IIfadeadlockoccurs,itcanberesolvedifonecarbacksup(preemptresourcesandrollback).ISeveralcarsmayhavetobebackedupifadeadlockoccurs.IStarvationispos

5、sible.......SystemModelIResourcetypesR1,R2,:::,RmICPUcycles,memoryspace,I/OdevicesIEachresourcetypeRihasWiinstances.IEachprocessutilizesaresourceasfollows:IrequestIuseIrelease......OutlineBackgroundandSystemModelDeadlockCharacterizationNecessaryConditionsResource-All

6、ocationGraphMethodsforHandlingDeadlocksDeadlockPreventionDeadlockAvoidanceSafeStateResource-AllocationGraphSchemeBanker’sAlgorithmDeadlockDetection小结和作业......DeadlockCharacterization:NecessaryConditionsIDeadlockcanariseiffourconditionsholdsimultaneously.IMutualexclus

7、ion:onlyoneprocessatatimecanusearesource.IHoldandwait:aprocessholdingatleastoneresourceiswaitingtoacquireadditionalresourcesheldbyotherprocesses.INopreemption:aresourcecanbereleasedonlyvoluntarilybytheprocessholdingit,afterthatprocesshascompleteditstask.ICircularwait

8、:thereexistsaset{P0,P1,:::,P0}ofwaitingprocessessuchthatP0iswaitingforaresourcethatisheldbyP1,P1iswaitingforaresourcethatisheldbyP2