操作系统教学课件：Chapter 8 Deadlocks

Chapter8：DeadlocksSystemModel（系统模型）DeadlockCharacterization（死锁特征）MethodsforHandlingDeadlocks（处理死锁的方法）DeadlockPrevention（预防死锁）DeadlockAvoidance（死锁避免）DeadlockDetection（死锁检测）RecoveryfromDeadlock（死锁恢复）CombinedApproachtoDeadlockHandling（综合处理方法）Deadlock资源是有限的，对资源的需求可能是无限的当占有了部分资源而渴求更多的资源的时候，可能会引起deadlock（死锁）OS管理着、分配着计算机系统的资源，必须考虑死锁TheDeadlockProblemAsetofblockedprocesseseachholdingaresourceandwaitingtoacquirearesourceheldbyanotherprocessintheset.ExampleSystemhas2tapedrives.P1andP2eachholdonetapedriveandeachneedsanotherone.ExamplesemaphoresAandB,initializedto1

P0

P1wait(A); wait(B)wait(B); wait(A)BridgeCrossingExampleTrafficonlyinonedirection.Eachsectionofabridgecanbeviewedasaresource.Ifadeadlockoccurs,itcanberesolvedifonecarbacksup(preemptresourcesandrollback).Severalcarsmayhavetobebackedupifadeadlockoccurs.Starvationispossible.SystemModelResourcetypesR1,R2,...,RmCPUcycles,memoryspace,I/OdevicesEachresourcetype

RihasWiinstances.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–directededgeP1

Rjassignmentedge–directededgeRj

PiAsetofverticesVandasetofedgesE.Resource-AllocationGraph(Cont.)Process

ResourceTypewith4instancesPi

requestsinstanceofRjPiisholdinganinstanceofRjPiPiRjRjExampleofaResourceAllocationGraphResourceAllocationGraphWithADeadlockResourceAllocationGraphWithACycleButNoDeadlockBasicFactsIfgraphcontainsnocyclesnodeadlock.

Ifgraphcontainsacycleifonlyoneinstanceperresourcetype,thendeadlock.ifseveralinstancesperresourcetype,possibilityofdeadlock.MethodsforHandlingDeadlocksEnsurethatthesystemwillneverenteradeadlockstate.Topreventoravoid Allowthesystemtoenteradeadlockstateandthenrecover.

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.Requiresthatthesystemhassomeadditionalaprioriinformation

available.需要一些先验知识SafeStateWhenaprocessrequestsanavailableresource,systemmustdecideifimmediateallocationleavesthesysteminasafestate.

什么叫安全状态？Systemisinsafestateifthereexistsasafesequenceofallprocesses.

Sequence<P1,P2,…,Pn>issafeifforeachPi,theresourcesthatPicanstillrequestcanbesatisfiedbycurrentlyavailableresources+resourcesheldbyallthePj,withj<i.IfPiresourceneedsarenotimmediatelyavailable,thenPicanwaituntilall

Pj

havefinished.WhenPjisfinished,Picanobtainneededresources,execute,returnallocatedresources,andterminate.WhenPiterminates,Pi+1canobtainitsneededresources,andsoon.基于：进程执行完以后会释放它占用的资源；进程会在有限时间段内执行完；所以，安不安全就是针对当前资源和进程集，看能不能找到进程的安全执行序列BasicFactsIfasystemisinsafestatenodeadlocks.

Ifasystemisinunsafestatepossibilityofdeadlock.

Avoidanceensurethatasystemwillneverenteranunsafestate.死锁避免算法的目的就是让系统从不进入非安全的状态Safe,Unsafe,DeadlockState例子Resourceinstances，12Processes，3MaximumNeeds

currentNeedsP0 10 5P1 4 2P2 9 2死锁避免使系统处于安全状态进程需要申明他需要的资源最大数（不同资源）死锁避免算法要确保系统处于安全状态，即能不能找到进程安全执行序列死锁避免算法资源分配图，适合于每类资源只有一个实例银行家算法，适合于每类资源有多个实例Resource-AllocationGraphAlgorithmClaimedge

Pi

RjindicatedthatprocessPjmayrequestresourceRj;representedbyadashedline.

Claimedgeconvertstorequestedgewhenaprocessrequestsaresource.

Whenaresourceisreleasedbyaprocess,assignmentedgereconvertstoaclaimedge.

Resourcesmustbeclaimedapriori

inthesystem.Resource-AllocationGraphForDeadlockAvoidanceUnsafeStateInResource-AllocationGraphBanker’sAlgorithmMultipleinstances.

Eachprocessmustaprioriclaimmaximumuse.

Whenaprocessrequestsaresourceitmayhavetowait.

Whenaprocessgetsallitsresourcesitmustreturntheminafiniteamountoftime.SafetyalgorithmProcess’resource-requestalgorithmDataStructuresfortheBanker’sAlgorithmAvailable:Vectoroflengthm.Ifavailable[j]=k,therearekinstancesofresourcetypeRj

available.Max:nxmmatrix.IfMax[i,j]=k,thenprocessPi

mayrequestatmostkinstancesofresourcetypeRj.Allocation:nxmmatrix.IfAllocation[i,j]=kthenPiiscurrentlyallocatedkinstancesofRj.Need:nxmmatrix.IfNeed[i,j]=k,thenPimayneedkmoreinstancesofRj

tocompleteitstask.

Need[i,j]=Max[i,j]–

Allocation[i,j].Letn=numberofprocesses,andm=numberofresourcestypes.SafetyAlgorithm1. LetWork

andFinishbevectorsoflengthmandn,respectively.Initialize:Work=AvailableFinish[i]=falsefori=1,2,…,n.2. Findanisuchthatboth:(a)Finish[i]=false(b)

Needi

WorkIfnosuchiexists,gotostep4.3. Work=Work+

Allocationi

Finish[i]=true

gotostep2.4. IfFinish[i]==trueforalli,thenthesystemisinasafestate.Resource-RequestAlgorithmforProcessPi

Request=requestvectorforprocessPi.IfRequesti

[j]=kthenprocessPiwantskinstancesofresourcetypeRj.1. If

Requesti

Needi

gotostep2.Otherwise,raiseerrorcondition,sinceprocesshasexceededitsmaximumclaim.2. IfRequesti

Available,gotostep3.OtherwisePimustwait,sinceresourcesarenotavailable.3. PretendtoallocaterequestedresourcestoPibymodifyingthestateasfollows:

Available=Available-

Requesti;

Allocationi

=Allocationi+Requesti;

Needi

=Needi

–

Requesti;IfsafetheresourcesareallocatedtoPi.IfunsafePimustwait,andtheoldresource-allocationstateisrestoredExampleofBanker’sAlgorithm5processesP0throughP4;3resourcetypesA

(10instances),B(5

instances,andC(7instances).SnapshotattimeT0:

Allocation

Max

Available ABC ABC ABC

P0 010 753 332

P1 200 322

P2 302 902

P3 211 222

P4 002 433 ExampleofBanker’sAlgorithm

Allocation

Max

Available

Need

work

Finish[i] ABC ABC ABC

ABC

ABC

332

332

P0

010 753 743false

P1

200 322 122false

P2

302 902 600false

P3

211

222011false

P4

002 433 431

falseExampleofBanker’sAlgorithm

Allocation

Max

Available

Need

work

Finish[i] ABC ABC ABC

ABC

ABC

332

332

P0

010 753 743false

P1

200 322 122false

P2

302 902 600false

P3

211

222011false

P4

002 433 431

false≤ExampleofBanker’sAlgorithm

Allocation

Max

Available

Need

work

Finish[i] ABC ABC ABC

ABC

ABC

332

532

P0

010 753 743false

P1

200 322 122true

P2

302 902 600false

P3

211

222011false

P4

002 433 431

falseP1+ExampleofBanker’sAlgorithm

Allocation

Max

Available

Need

work

Finish[i] ABC ABC ABC

ABC

ABC

332

532

P0

010 753 743false

P1

200 322 122true

P2

302 902 600false

P3

211

222011false

P4

002 433 431

falseP1≤ExampleofBanker’sAlgorithm

Allocation

Max

Available

Need

work

Finish[i] ABC ABC ABC

ABC

ABC

332

743

P0

010 753 743false

P1

200 322 122true

P2

302 902 600false

P3

211

222011true

P4

002 433 431

falseP1、P3、+ExampleofBanker’sAlgorithm

Allocation

Max

Available

Need

work

Finish[i] ABC ABC ABC

ABC

ABC

332

743

P0

010 753 743false

P1

200 322 122true

P2

302 902 600false

P3

211

222011true

P4

002 433 431

falseP1、P3、≤ExampleofBanker’sAlgorithm

Allocation

Max

Available

Need

work

Finish[i] ABC ABC ABC

ABC

ABC

332

745

P0

010 753 743false

P1

200 322 122true

P2

302 902 600false

P3

211

222011true

P4

002 433 431

trueP1、P3、P4+ExampleofBanker’sAlgorithm

Allocation

Max

Available

Need

work

Finish[i] ABC ABC ABC

ABC

ABC

332

745

P0

010 753 743false

P1

200 322 122true

P2

302 902 600false

P3

211

222011true

P4

002 433 431

trueP1、P3、P4≤ExampleofBanker’sAlgorithm

Allocation

Max

Available

Need

work

Finish[i] ABC ABC ABC

ABC

ABC

332

1047

P0

010 753 743false

P1

200 322 122true

P2

302 902 600true

P3

211

222011true

P4

002 433 431

trueP1、P3、P4、P2

+ExampleofBanker’sAlgorithm

Allocation

Max

Available

Need

work

Finish[i] ABC ABC ABC

ABC

ABC

332

1047

P0

010 753 743false

P1

200 322 122true

P2

302 902 600true

P3

211

222011true

P4

002 433 431

trueP1、P3、P4、P2

≤ExampleofBanker’sAlgorithm

Allocation

Max

Available

Need

work

Finish[i] ABC ABC ABC

ABC

ABC

332

1057

P0

010 753 743true

P1

200 322 122true

P2

302 902 600true

P3

211

222011true

P4

002 433 431

trueP1、P3、P4、P2、P0

+Thesystemisinasafestatesincethesequence<P1,P3,P4,P2,P0>satisfiessafetycriteria.ExampleP1Request(1,0,2)CheckthatRequestAvailable(thatis,(1,0,2)(3,3,2)true.

Allocation

Need

Available ABC ABC ABC

P0 010 743 230

P1

302

020

P2 302 600

P3 211 011

P4 002 431Executingsafetyalgorithmshowsthatsequence<P1,P3,P4,P0,P2>satisfiessafetyrequirement.Canrequestfor(3,3,0)byP4begranted?Canrequestfor(0,2,0)byP0begranted?Example1DeadlockDetectionAllowsystemtoenterdeadlockstate

Detectionalgorithm

RecoveryschemeSingleInstanceofEachResourceTypeMaintainwait-forgraphNodesareprocesses.Pi

PjifPi

iswaitingforPj.

Periodicallyinvokeanalgorithmthatsearchesforacycleinthegraph.

Analgorithmtodetectacycleinagraphrequiresanorderofn2operations,wherenisthenumberofverticesinthegraph.Resource-AllocationGraphandWait-forGraphResource-AllocationGraphCorrespondingwait-forgraphSeveralInstancesofaResourceTypeAvailable:Avectoroflengthmindicatesthenumberofavailableresourcesofeachtype.

Allocation:Annxmmatrixdefinesthenumberofresourcesofeachtypecurrentlyallocatedtoeachprocess.

Request:Annxmmatrixindicatesthecurrentrequestofeachprocess.IfRequest[ij]=k,thenprocessPiisrequestingkmoreinstancesofresourcetypeRj.DetectionAlgorithm1. LetWorkandFinishbevectorsoflengthmandn,respectivelyInitialize:(a)Work=Available(b) Fori=1,2,…,n,if

Allocationi

0,then

Finish[i]=false;otherwise,Finish[i]=true.（没有分配资源的进程当然不用考虑）2. Findanindexisuchthatboth:(a) Finish[i]==false(b)

Requesti

Work

Ifnosuchiexists,gotostep4.DetectionAlgorithm(Cont.)3. Work=Work+Allocationi

（仍旧假定某个进程执行完以后会释放其拥有的资源）

Finish[i]=true

gotostep2.

4. IfFinish[i]==false,forsomei,1in,thenthesystemisindeadlockstate.Moreover,ifFinish[i]==false,thenPiisdeadlocked.

ExampleofDetectionAlgorithmFiveprocessesP0throughP4;

threeresourcetypes

A(7instances),B(2instances),andC(6instances).SnapshotattimeT0:

Allocation Request Available

ABC ABC ABC

P0 010 000 000

P1 200 202

P2 303 000

P3 211 100

P4 002 002ExampleofDetectionAlgorithm

Allocation

Request

Available

work

Fnish[i]

ABC ABC ABCABC

000000

P0 010 000 false

P1 200 202false

P2 303 000false

P3 211 100false

P4 002 002falseExampleofDetectionAlgorithm

Allocation

Request

Available

work

Fnish[i]

ABC ABC ABCABC

000000

P0 010 000 false

P1 200 202false

P2 303 000false

P3 211 100false

P4 002 002false≤ExampleofDetectionAlgorithm

Allocation

Request

Available

work

Fnish[i]

ABC ABC ABCABC

000010

P0 010 000 true

P1 200 202false

P2 303 000false

P3 211 100false

P4 002 002falseP0+ExampleofDetectionAlgorithm

Allocation

Request

Available

work

Fnish[i]

ABC ABC ABCABC

000010

P0 010 000 true

P1 200 202false

P2 303 000false

P3 211 100false

P4 002 002falseP0≤ExampleofDetectionAlgorithm

Allocation

Request

Available

work

Fnish[i]

ABC ABC ABCABC

000313

P0 010 000 true

P1 200 202false

P2 303 000true

P3 211 100false

P4 002 002falseP0、P2+ExampleofDetectionAlgorithm

Allocation

Request

Available

work

Fnish[i]

ABC ABC ABCABC

000313

P0 010 000 true

P1 200 202false

P2 303 000true

P3 211 100false

P4 002 002falseP0、P2≤ExampleofDetectionAlgorithm

Allocation

Request

Available

work

Fnish[i]

ABC ABC ABCABC

000524

P0 010 000 true

P1 200 202false

P2 303 000true

P3 211 100true

P4 002 002falseP0、P2、P3+ExampleofDetectionAlgorithm

Allocation

Request

Available

work

Fnish[i]

ABC ABC ABCABC

000524

P0 010 000 true

P1 200 202false

P2 303 000true

P3 211 100true

P4 002 002falseP0、P2、P3≤ExampleofDetectionAlgorithm

Allocation

Request

Available

work

Fnish[i]

ABC ABC ABCABC

000526

P0 010 000 true

P1 200 202false

P2 303 000true

P3 211 100true

P4 002 002trueP0、P2、P3、P4+ExampleofDetectionAlgorithm

Allocation

Request

Available

work

Fnish[i]

ABC ABC ABCABC

000526

P0 010 000 true

P1 200 202false

P2 303 000true

P3 211 100true

P4 002 002trueP0、P2、P3、P4≤ExampleofDetectionAlgorithm

Allocation

Request

Available

work

Fnish[i]

ABC ABC ABCABC

000726

P0 010 000 true

P1 200 202true

P2 303 000true

P3 211 100true

P4 002 002trueP0、P2、P3、P4、P1+Sequence<P0,P2,P3,P4,P1>willresultinFinish[i]=trueforalli.Example(Cont.)P2requestsanadditionalinstanceoftypeC.

Request ABC

P0 000

P1 201

P2 001

P3 100

P4 002Stateofsystem?CanreclaimresourcesheldbyprocessP0,butinsufficientresourcestofulfillotherprocesses;requests.Deadlockexists,consistingofprocessesP1,

P2,P3,andP4.Detection-AlgorithmUsageWhen,andhowoften,toinvokedependson:Howoftenadeadlockislikelytooccur?Howmanyprocesseswillneedtoberolledback?oneforeachdisjointcycle

Ifdetectionalgorithmisinvokedarbitrarily,theremaybemanycyclesintheresourcegraphandsowewouldnotbeabletotellwhichofthemanydeadlockedprocesses“caused”thedeadlock.

RecoveryfromDeadlock:ProcessTerminationAbortalldeadlockedprocesses.

Abortoneprocessatatimeuntilthedeadlockcycleiseliminated.

Inwhich