操作系統(tǒng)教學(xué)課件：Chapter 8 Deadlocks

Chapter8：DeadlocksSystemModel（系統(tǒng)模型）DeadlockCharacterization（死鎖特征）MethodsforHandlingDeadlocks（處理死鎖的方法）DeadlockPrevention（預(yù)防死鎖）DeadlockAvoidance（死鎖避免）DeadlockDetection（死鎖檢測(cè)）RecoveryfromDeadlock（死鎖恢復(fù)）CombinedApproachtoDeadlockHandling（綜合處理方法）Deadlock資源是有限的，對(duì)資源的需求可能是無限的當(dāng)占有了部分資源而渴求更多的資源的時(shí)候，可能會(huì)引起deadlock（死鎖）OS管理著、分配著計(jì)算機(jī)系統(tǒng)的資源，必須考慮死鎖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，一個(gè)存儲(chǔ)，一個(gè)硬盤（多個(gè)分區(qū)）、U盤、光盤……打印機(jī)，一個(gè)……Eachprocessutilizesaresourceasfollows:requestusereleaseDeadlockCharacterizationMutualexclusion（互斥）:onlyoneprocessatatimecanusearesource.Holdandwait（占有和等待）:aprocessholdingatleastoneresourceiswaitingtoacquireadditionalresourcesheldbyotherprocesses.Nopreemption（非剝奪）:aresourcecanbereleasedonlyvoluntarilybytheprocessholdingit,afterthatprocesshascompleteditstask.Circularwait（循環(huán)等待）:thereexistsaset{P0,P1,…,P0}ofwaitingprocessessuchthatP0iswaitingforaresourcethatisheldbyP1,P1iswaitingforaresourcethatisheldbyP2,…,Pn–1iswaitingforaresourcethatisheldbyPn,andP0iswaitingforaresourcethatisheldbyP0.（有環(huán)）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.會(huì)發(fā)現(xiàn)：實(shí)現(xiàn)這樣一個(gè)策略可能帶來的問題比他所解決的問題更多！DeadlockPrevention(Cont.)NoPreemption

–Ifaprocessthatisholdingsomeresourcesrequestsanotherresourcethatcannotbeimmediatelyallocatedtoit,thenallresourcescurrentlybeingheldarereleased.Preemptedresourcesareaddedtothelistofresourcesforwhichtheprocessiswaiting.Processwillberestartedonlywhenitcanregainitsoldresources,aswellasthenewonesthatitisrequesting.

CircularWait

–imposeatotalorderingofallresourcetypes,andrequirethateachprocessrequestsresourcesinanincreasingorderofenumeration.DeadlockAvoidance死鎖避免Simplestandmostusefulmodelrequiresthateachprocessdeclarethemaximumnumberofresourcesofeachtypethatitmayneed.

Thedeadlock-avoidancealgorithmdynamicallyexaminestheresource-allocationstatetoensurethattherecanneverbeacircular-waitcondition.

無環(huán)，安全Resource-allocationstateisdefinedbythenumberofavailableandallocatedresources,andthemaximumdemandsoftheprocesses.Requiresthatthesystemhassomeadditionalaprioriinformation

available.需要一些先驗(yàn)知識(shí)SafeStateWhenaprocessrequestsanavailableresource,systemmustdecideifimmediateallocationleavesthesysteminasafestate.

什么叫安全狀態(tài)？Systemisinsafestateifthereexistsasafesequenceofallprocesses.

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

Pj

havefinished.WhenPjisfinished,Picanobtainneededresources,execute,returnallocatedresources,andterminate.WhenPiterminates,Pi+1canobtainitsneededresources,andsoon.基于：進(jìn)程執(zhí)行完以后會(huì)釋放它占用的資源；進(jìn)程會(huì)在有限時(shí)間段內(nèi)執(zhí)行完；所以，安不安全就是針對(duì)當(dāng)前資源和進(jìn)程集，看能不能找到進(jìn)程的安全執(zhí)行序列BasicFactsIfasystemisinsafestatenodeadlocks.

Ifasystemisinunsafestatepossibilityofdeadlock.

Avoidanceensurethatasystemwillneverenteranunsafestate.死鎖避免算法的目的就是讓系統(tǒng)從不進(jìn)入非安全的狀態(tài)Safe,Unsafe,DeadlockState例子Resourceinstances，12Processes，3MaximumNeeds

currentNeedsP0 10 5P1 4 2P2 9 2死鎖避免使系統(tǒng)處于安全狀態(tài)進(jìn)程需要申明他需要的資源最大數(shù)（不同資源）死鎖避免算法要確保系統(tǒng)處于安全狀態(tài)，即能不能找到進(jìn)程安全執(zhí)行序列死鎖避免算法資源分配圖，適合于每類資源只有一個(gè)實(shí)例銀行家算法，適合于每類資源有多個(gè)實(shí)例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.（沒有分配資源的進(jìn)程當(dāng)然不用考慮）2. Findanindexisuchthatboth:(a) Finish[i]==false(b)

Requesti

Work

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

（仍舊假定某個(gè)進(jìn)程執(zhí)行完以后會(huì)釋放其擁有的資源）

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