操作系統(tǒng)原理：CH08-Deadlock

Module8:Deadlocks（死鎖）SystemModel（系統(tǒng)模型）DeadlockCharacterization（死鎖特征）MethodsforHandlingDeadlocks（處理死鎖的方法）DeadlockPrevention（預(yù)防死鎖）DeadlockAvoidance（死鎖避免）DeadlockDetection（死鎖檢測）RecoveryfromDeadlock（死鎖恢復(fù)）CombinedApproachtoDeadlockHandling（綜合處理方法）TheDeadlockProblem（死鎖問題）Asetofblockedprocesseseachholdingaresourceandwaitingtoacquirearesourceheldbyanotherprocessintheset.

（一組等待的進(jìn)程，其中每一個進(jìn)程都持有資源，并且等待著由這個組中其他進(jìn)程所持有的資源）死鎖Deadlock：計算機系統(tǒng)中多道程序并發(fā)執(zhí)行時，兩個或兩個以上的進(jìn)程由于競爭資源而造成的一種互相等待的現(xiàn)象（僵局），如無外力作用，這些進(jìn)程將永遠(yuǎn)不能再向前推進(jìn)。TheDeadlockProblemExample1Systemhas2tapedrives.（系統(tǒng)有兩個磁帶設(shè)備）P1andP2eachholdonetapedriveandeachneedsanotherone.（進(jìn)程P1和P2各占有一個磁帶設(shè)備并且實際需要兩個磁帶）Example2semaphoresAandB,initializedto1（信號量A，B初始化為1）

P0 P1wait(A); wait(B)wait(B); wait(A)如果一個進(jìn)程要使用OS管理的資源，需先向系統(tǒng)提出申請，如果有可用資源，系統(tǒng)才進(jìn)行分配。資源的分類,根據(jù)資源性質(zhì)：可搶占資源—指資源占有進(jìn)程雖然需要使用該資源，但另一個進(jìn)程卻可強行把資源從占有者進(jìn)程處搶來。不可搶占資源—指只有占用者進(jìn)程不再需要使用該資源而主動釋放資源外，其它進(jìn)程不得在占有者進(jìn)程使用資源過程中強行搶占。

根據(jù)使用方式：共享資源和獨占資源。根據(jù)使用期限；永久資源和臨時性資源。資源共享:CPU、主存、硬盤獨占:打印機，讀卡機，磁帶驅(qū)動器可順序重復(fù)使用的資源由一個進(jìn)程產(chǎn)生，被另外一個進(jìn)程使用短暫時間之后便無用的資源BridgeCrossingExample

（過橋的例子）Trafficonlyinonedirection.（只有一個方向）Eachsectionofabridgecanbeviewedasaresource.

（橋的每一個部分都可以看成資源）Ifadeadlockoccurs,itcanberesolvedifonecarbacksup(preemptresourcesandrollback).

（如果死鎖發(fā)生，它可以由一輛車返回而解決，搶占資源并回退）Severalcarsmayhavetobebackedupifadeadlockoccurs.

（如果死鎖發(fā)生，可能很多車都不得不返回）Starvationispossible.（有可能產(chǎn)生饑餓）死鎖的原因和條件競爭資源引起死鎖當(dāng)系統(tǒng)中供多個進(jìn)程所使用的資源，不足以同時滿足它們的需要時，引起它們對資源的競爭而產(chǎn)生死鎖進(jìn)程推進(jìn)順序不當(dāng)引起死鎖在多道程序系統(tǒng)中，并發(fā)執(zhí)行的進(jìn)程推進(jìn)序列不可予測有些推進(jìn)順序，進(jìn)程可以順利完成有的推進(jìn)順序會引起進(jìn)程無限期地等待永遠(yuǎn)不會發(fā)生的條件而不能向前推進(jìn)，造成死鎖P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)③④③③③②②①①進(jìn)程P1、P2并發(fā)執(zhí)行。資源R1、R2各有一個曲線4將進(jìn)入不安全區(qū)域（進(jìn)程推進(jìn)順序非法）P1S1S3P2P3S2P1：Release(S1);Request(S3)P2：Release(S2);Request(S1)P3：Release(S3);Request(S2)不可能發(fā)生死鎖P1：Request(S3);Release(S1)P2：Request(S1);Release(S2)P3：Request(S2);Release(S3)可能發(fā)生死鎖S1、S2、S3是臨時資源DeadlockCharacterization

（死鎖的特性）Mutualexclusion:onlyoneprocessatatimecanusearesource.（互斥：一次只有一個進(jìn)程可以使用一個資源）Holdandwait:aprocessholdingatleastoneresourceiswaitingtoacquireadditionalresourcesheldbyotherprocesses.

（占有并等待：一個至少持有一個資源的進(jìn)程等待獲得額外的由其他進(jìn)程所持有的資源）(請求與保持)Deadlockcanariseiffourconditionsholdsimultaneously.（四個條件同時出現(xiàn)，死鎖將會發(fā)生）DeadlockCharacterization

（死鎖的特性）Nopreemption:aresourcecanbereleasedonlyvoluntarilybytheprocessholdingit,afterthatprocesshascompleteditstask. （不可搶占：一個資源只有當(dāng)持有它的進(jìn)程完成任務(wù)后，自由的釋放）(非剝奪)Circularwait:thereexistsaset{P0,P1,…,P0}ofwaitingprocessessuchthatP0iswaitingforaresourcethatisheldby

P1,P1iswaitingforaresourcethatisheldbyP2,…,Pn–1iswaitingforaresourcethatisheldbyPn,andP0iswaitingforaresourcethatisheldbyP0.（循環(huán)等待：等待資源的進(jìn)程之間存在環(huán)）SystemModel（系統(tǒng)模型）Resourcetypes（資源類型）R1,R2,...,Rm

CPUcycles,memoryspace,I/Odevices（CPU周期，內(nèi)存空間，I/O設(shè)備）EachresourcetypeRihasWiinstances.

（每一種資源Ri有Wi

種實例）Eachprocessutilizesaresourceasfollows

（每一個進(jìn)程如下的利用資源）request（申請）use（使用）Release（釋放）Resource-AllocationGraph

（資源分配圖）Vispartitionedintotwotypes:（V被分為兩個部分）P={P1,P2,…,Pn},thesetconsistingofalltheprocessesinthesystem.（P：含有系統(tǒng)中全部的進(jìn)程）R={R1,R2,…,Rm},thesetconsistingofallresourcetypesinthesystem.（R：含有系統(tǒng)中全部的資源）requestedge–directededgeP1Rj（請求邊：直接P1Rj

）assignmentedge–directededgeRj

Pi（分配邊：P1Rj

）AsetofverticesVandasetofedgesE.（一個頂點的集合V和邊的集合E）Resource-AllocationGraph(Cont.)

資源分配圖續(xù)Process進(jìn)程

ResourceTypewith4instances有四個實例的資源類型Pi

requestsinstanceofRj

（

Pi

請求一個Rj的實例）PiisholdinganinstanceofRj（

Pi

持有一個Rj的實例）PiPiRjRjExampleofaResourceAllocationGraph

資源分配圖的例子ResourceAllocationGraphWithADeadlock

有死鎖的資源分配圖ResourceAllocationGraphWithACycleButNoDeadlock

有環(huán)但沒有死鎖的資源分配圖BasicFacts（基本事實）Ifgraphcontainsnocyclesnodeadlock.（如果圖沒有環(huán)，那么不會有死鎖）Ifgraphcontainsacycle（如果圖有環(huán)）ifonlyoneinstanceperresourcetype,thendeadlock.

（如果每一種資源類型只有一個實例，那么死鎖發(fā)生）ifseveralinstancesperresourcetype,possibilityofdeadlock.

（如果一種資源類型有多個實例，可能死鎖）MethodsforHandlingDeadlocks

處理死鎖的方法忽略、預(yù)防、避免、檢測、解除Ignoretheproblemandpretendthatdeadlocksneveroccurinthesystem;usedbymostoperatingsystems,includingUNIX.（忽略這個問題，假裝系統(tǒng)中從未出現(xiàn)過死鎖。這個方法被大部分的操作系統(tǒng)采用，包括UNIX）鴕鳥策略Ensurethatthesystemwillneverenteradeadlockstate.（確保系統(tǒng)永遠(yuǎn)不會進(jìn)入死鎖狀態(tài)）預(yù)防死鎖，避免死鎖Allowthesystemtoenteradeadlockstateandthenrecover.

（允許系統(tǒng)進(jìn)入死鎖狀態(tài)，然后恢復(fù)系統(tǒng)）死鎖檢測鴕鳥策略象鴕鳥一樣對死鎖視而不見處理死鎖的代價很大，而且常常給用戶帶來許多不便的限制。大多數(shù)用戶寧可在極偶然的情況下發(fā)生死鎖，也不愿限制每個用戶只能創(chuàng)建一個進(jìn)程、只能打開一個文件等等。于是不得不在方便性和正確性之間作出折衷。DeadlockPrevention（死鎖的預(yù)防）MutualExclusion–notrequiredforsharableresources;mustholdfornonsharableresources.

（互斥：共享資源不是必須的，必須保持非共享資源）HoldandWait–mustguaranteethatwheneveraprocessrequestsaresource,itdoesnotholdanyotherresources.

（占有并等待：必須保證進(jìn)程申請資源的時候沒有占有其他資源）Requireprocesstorequestandbeallocatedallitsresourcesbeforeitbeginsexecution,orallowprocesstorequestresourcesonlywhentheprocesshasnone.

（要求進(jìn)程在執(zhí)行前一次申請全部的資源，只有沒有占有資源時才可以分配資源）Lowresourceutilization;starvationpossible.

（利用率低，可能出現(xiàn)饑餓）Restrainthewaysrequestcanbemade.（抑制死鎖發(fā)生的必要條件）DeadlockPrevention(Cont.)

死鎖的預(yù)防（續(xù)）NoPreemption–（非搶占）Ifaprocessthatisholdingsomeresourcesrequestsanotherresourcethatcannotbeimmediatelyallocatedtoit,thenallresourcescurrentlybeingheldarereleased.（如果一個進(jìn)程的申請沒有實現(xiàn)，它要釋放所有占有的資源）Preemptedresourcesareaddedtothelistofresourcesforwhichtheprocessiswaiting.（先占的資源放入進(jìn)程等待資源列表中）Processwillberestartedonlywhenitcanregainitsoldresources,aswellasthenewonesthatitisrequesting.

（進(jìn)程在有新的資源請求時，若能夠重新得到舊的資源，可以重新開始）NoPreemption–（非搶占）另外一種解決方案:當(dāng)進(jìn)程A提出資源申請時,首先檢查這些資源是否可用是,則分配之,否則檢查這些資源是否已分配給了另外的進(jìn)程(而這個進(jìn)程又在等待其他的資源)如果存在這樣的進(jìn)程B,從進(jìn)程B剝奪進(jìn)程A所需的資源分配給進(jìn)程A使用.相反,則進(jìn)程A等待,當(dāng)進(jìn)程A在等待的過程中,它所持有資源可能會被剝奪分配給其他的進(jìn)程.這樣,進(jìn)程A只有得到了它正在申請有資源以及等待過程中被剝奪的資源后,才能恢復(fù)運行.CircularWait–imposeatotalorderingofallresourcetypes,andrequirethateachprocessrequestsresourcesinanincreasingorderofenumeration.（循環(huán)等待：將所有的資源類型放入資源列表中，并且要求進(jìn)程按照資源表申請資源）所有進(jìn)程對資源的請求必須嚴(yán)格按資源序號遞增的次序提出?？傆幸粋€進(jìn)程占據(jù)了較高序號的資源，它繼續(xù)請求的資源必然是空閑的，可以一直向前推進(jìn)。在資源分配圖中不可能出現(xiàn)環(huán)路，因而摒棄了“環(huán)路等待”條件這種策略可以提高資源利用率，但在進(jìn)程使用各類資源的順序與系統(tǒng)規(guī)定的順序不同時會造成資源浪費的情況。上述預(yù)防死鎖的方法通過限制資源請求來打破死鎖的四個必要條件之一，從而預(yù)防死鎖的發(fā)生。其可能的副作用：降低設(shè)備利用率和吞吐量可能有進(jìn)程饑餓DeadlockAvoidance（死鎖避免）允許進(jìn)程動態(tài)地申請資源，系統(tǒng)在進(jìn)行資源分配之前，先計算資源分配的安全性若此次分配不會導(dǎo)致系統(tǒng)從安全狀態(tài)向不安全狀態(tài)轉(zhuǎn)換，便可將資源分配給進(jìn)程；否則不分配資源，進(jìn)程必須阻塞等待。Safe

State安全狀態(tài)是指系統(tǒng)的一種狀態(tài)，在此狀態(tài)下,系統(tǒng)能按某種順序（例如P1、P2……Pn）來為各個進(jìn)程分配其所需資源，直至最大需求，使每個進(jìn)程都可順序地一個個地完成。這個序列（P1、P2…….Pn）稱為安全序列。若某一時刻不存在一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)。SafeState（安全狀態(tài)）Whenaprocessrequestsanavailableresource,systemmustdecideifimmediateallocationleavesthesysteminasafestate.

（當(dāng)進(jìn)程申請一個有效的資源的時候，系統(tǒng)必須確定分配后是安全的）Systemisinsafestateifthereexistsasafesequenceofallprocesses.（如果存在一個安全序列系統(tǒng)處于安全態(tài)）Sequence<P1,P2,…,Pn>issafeifforeachPi,theresourcesthatPicanstillrequestcanbesatisfiedbycurrentlyavailableresources+resourcesheldbyallthePj,withj<I.

（進(jìn)程序列是安全的，如果每一個進(jìn)程Pi所申請的可以被滿足的資源數(shù)加上其他進(jìn)程所持有的該資源數(shù)小于系統(tǒng)總數(shù)）IfPiresourceneedsarenotimmediatelyavailable,thenPicanwaituntilallPj

havefinished.WhenPjisfinished,Picanobtainneededresources,execute,returnallocatedresources,andterminate.WhenPiterminates,Pi+1canobtainitsneededresources,andsoon.例：系統(tǒng)中有P1、P2和P3三個進(jìn)程和12臺磁帶機。各進(jìn)程最大需求和T0時刻分配狀態(tài)如下：進(jìn)程 最大需求已分配還需請求可用

P110 55 3P24 2 2 P392 7 分析T0狀態(tài)，可以找到一個安全序列（P2、P1、P3）,即系統(tǒng)按此進(jìn)程序列分配資源，每個進(jìn)程都可順利完成，其步驟如下：先將可用的3臺磁帶機中2臺分配給P2，P2滿足了最大的資源需求，在有限時間內(nèi)運行完畢，釋放它占有的全部資源，使可用資源數(shù)量增至5臺。再將可用的5臺磁帶機分配給P1，最后將可用10臺中7臺磁帶機分配給P3這樣三進(jìn)程可按照（P2、P1、P3）序列順序地一個個執(zhí)行完成，則（P2、P1、P3）序列是安全序列，T0時刻狀態(tài)是安全狀態(tài)由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換如果在T0

狀態(tài)不按安全序列進(jìn)行分配，可能會導(dǎo)致系統(tǒng)進(jìn)入一個不安全狀態(tài)，例如在T0狀態(tài)下P3申請1臺磁帶機。如系統(tǒng)實施此次分配使系統(tǒng)狀態(tài)由T0變?yōu)門1狀態(tài)T1時刻狀態(tài)：進(jìn)程最大需求已分配還需請求可用可用

分配資源前釋放資源后

P1105 5

>

P24 22=< 2

4P39 3

6

>

因為找不到一個安全序列使所有進(jìn)程順序地一個個地運行完畢，所以T1狀態(tài)是不安全狀態(tài)，由于實施分配給1臺磁帶機給P3的操作會引起系統(tǒng)狀態(tài)由安全狀態(tài)T0向不安全狀態(tài)下的轉(zhuǎn)換，所以為了避免死鎖，上述的分配只是安全檢測，檢測后判定這樣的申請不能滿足，P3為申請1臺磁帶機而必須阻塞等待。BasicFacts（基本事實）Ifasystemisinsafestatenodeadlocks.

（如果一個系統(tǒng)在安全狀態(tài)，就沒有死鎖）Ifasystemisinunsafestatepossibilityofdeadlock.

（如果一個系統(tǒng)不是處于安全狀態(tài)，就有可能死鎖）Avoidanceensurethatasystemwillneverenteranunsafestate.

（避免：確保系統(tǒng)永遠(yuǎn)不會進(jìn)入死鎖狀態(tài)）Safe,unsafe,deadlockstatespaces

安全、不安全、死鎖狀態(tài)空間DeadlockAvoidance（死鎖避免）Simplestandmostusefulmodelrequiresthateachprocessdeclarethemaximumnumberofresourcesofeachtypethatitmayneed.（一個簡單而有效的模型要求每一個進(jìn)程聲明它所需要的資源的最大數(shù)）Thedeadlock-avoidancealgorithmdynamicallyexaminestheresource-allocationstatetoensurethattherecanneverbeacircular-waitcondition.（死鎖避免算法動態(tài)檢查資源分配狀態(tài)以確保不會出現(xiàn)循環(huán)等待的情況）Resource-allocationstateisdefinedbythenumberofavailableandallocatedresources,andthemaximumdemandsoftheprocesses.（資源分配狀態(tài)定義為可用的與已分配的資源數(shù)，和進(jìn)程所需的最大資源量）Requiresthatthesystemhassomeadditionalaprioriinformation

available.（需要系統(tǒng)有一些額外的信息）Singleinstanceofaresourcetype資源有單個實例Usearesource-allocationgraph資源分配圖Multipleinstancesofaresourcetype資源有多個實例Usethebanker’salgorithm銀行家算法Resource-AllocationGraphAlgorithm

資源分配圖算法Claimedge

Pi

RjindicatedthatprocessPjmayrequestresourceRj;representedbyadashedline. (claimedge申請邊Pi

Rj代表進(jìn)程Pi可能會申請資源Ri，表示為虛線）Claimedgeconvertstorequestedgewhenaprocessrequestsaresource.（一個進(jìn)程申請資源的時候，申請邊轉(zhuǎn)化為請求邊）Whenaresourceisreleasedbyaprocess,assignmentedgereconvertstoaclaimedge.（當(dāng)資源被進(jìn)程釋放的時候，分配邊轉(zhuǎn)化為申請邊）Resourcesmustbeclaimedaprioriinthesystem.

（系統(tǒng)中的資源必須被事先聲明）當(dāng)一個進(jìn)程Pi申請資源Rj時，由循環(huán)檢測算法來檢查:如果把圖中的申請邊PiRj轉(zhuǎn)為分配邊Rj

Pi

，圖中是否會出現(xiàn)環(huán)路，只有不出現(xiàn)環(huán)路，才實施資源分配。Resource-AllocationGraphForDeadlockAvoidance

死鎖避免的資源分配圖UnsafeStateInAResource-AllocationGraph

不安全的狀態(tài)圖Banker’sAlgorithm（銀行家算法）Multipleinstances.（多個實例）Eachprocessmustaprioriclaimmaximumuse.

（每一個進(jìn)程必須事先聲明使用的最大量）Whenaprocessrequestsaresourceitmayhavetowait.

（當(dāng)一個進(jìn)程請求資源，它可能要等待）Whenaprocessgetsallitsresourcesitmustreturntheminafiniteamountoftime.

（當(dāng)一個進(jìn)程得到所有的資源，它必須在有限的時間釋放它們）DataStructuresfortheBanker’sAlgorithm

銀行家算法的數(shù)據(jù)結(jié)構(gòu)Available:Vectoroflengthm.Ifavailable[j]=k,therearekinstancesofresourcetypeRj

available.

（如果available[j]=k,那么資源Rj有k個實例有效）Max:nxmmatrix.IfMax[i,j]=k,thenprocessPi

mayrequestatmostkinstancesofresourcetypeRj.

（如果Max[i,j]=k,那么進(jìn)程Pi可以最多請求資源Rj的k個實例）Letn=numberofprocesses,andm=numberofresourcestypes.N為進(jìn)程的數(shù)目，M為資源類型的數(shù)目Allocation:nxmmatrix.IfAllocation[i,j]=kthenPiiscurrentlyallocatedkinstancesofRj.

（如果Allocation[i,j]=k,那么進(jìn)程Pj當(dāng)前分配了k個資源Rj的實例）Need:nxmmatrix.IfNeed[i,j]=k,thenPimayneedkmoreinstancesofRj

tocompleteitstask.

（如果Need[i,j]=k,那么進(jìn)程Pi還需要k個資源Rj的實例）

Need[i,j]=Max[i,j]–Allocation[i,j].DataStructuresfortheBanker’sAlgorithm

銀行家算法的數(shù)據(jù)結(jié)構(gòu)SafetyAlgorithm（安全算法）1. LetWorkandFinishbevectorsoflengthmandn,respectively.Initialize（讓W(xué)ork和Finish作為長度為m和n的向量）Work:=AvailableFinish[i]=falsefori-1,3,…,n.2. Findandisuchthatboth:（找到i）(a)Finish[i]=false(b)Needi

WorkIfnosuchiexists,gotostep4.3. Work:=Work+Allocationi

Finish[i]:=true

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

進(jìn)程Pi的資源請求

Requesti=requestvectorforprocessPi.IfRequesti

[j]=kthenprocessPiwantskinstancesofresourcetypeRj. 1. IfRequesti

Needi

gotostep2.Otherwise,raiseerrorcondition,sinceprocesshasexceededitsmaximumclaim.2. IfRequesti

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

Available:=Available–Requesti;

Allocationi

:=Allocationi+Requesti;

Needi

:=

Needi–Requesti;;4.用安全算法進(jìn)行檢查,看系統(tǒng)是否處于安全狀態(tài)IfsafetheresourcesareallocatedtoPi.IfunsafePimustwait,andtheoldresource-allocationstateisrestoredExampleofBanker’sAlgorithm

銀行家算法的例子5processesP0throughP4;3resourcetypesA(10instances),

B(5instances,andC(7instances).（5個進(jìn)程P0到P4:3個資源類型A(10個實例），B（5個實例），C（7個實例））SnapshotattimeT0:（時刻T0的片段）

Allocation

Max

Available ABC ABC ABC

P0 010 753 332

P1 200 322

P2 302 902

P3 211 222

P4 002 433 Example(Cont.)（例子續(xù)）Thecontentofthematrix.NeedisdefinedtobeMax–Allocation.（矩陣的內(nèi)容。需要被定義為最大值）

Need

ABC

P0 743

P1 122

P2 600

P3 011

P4 431Thesystemisinasafestatesincethesequence<P1,P3,P4,P2,P0>satisfiessafetycriteria.（系統(tǒng)在安全的狀態(tài)因為序列P1,P3,P4,P2,P0滿足了安全的標(biāo)準(zhǔn)）用安全檢測算法看能否找到一個安全序列Work[]=available=(3,3,2)Finish[i]=false(i=0..4)

WorkneedallocationfinishP1332122200TP3532011211TP4743431002TP2745600302TP01047743010T存在安全序列：（P1，P3，P4，P2，P0）Example(Cont.)通常，安全序列不是唯一的Work[]=available=(3,3,2)Finish[i]=false(i=0..4)

WorkneedallocationfinishP3332011211TP4543431002TP1545122200TP2745600302TP01047743010T安全序列：（P3，P4，P1，P2，P0）Example(Cont.)Example(Cont.):P1request(1,0,2)

例子續(xù)CheckthatRequestAvailable(thatis,(1,0,2)(3,3,2)true.

(檢查請求小于有效（就是說，(1,0,2)(3,3,2)為真）

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.（執(zhí)行安全算法表明序列p1,p3,p4,p0,p2滿足要求）Canrequestfor(3,3,0)byP4begranted?（p4的(3,3,0)可以通過？）Canrequestfor(0,2,0)byP0begranted?（p0的(0,2,0)可以通過？）DeadlockDetection（死鎖檢測）Allowsystemtoenterdeadlockstate（允許進(jìn)入死鎖狀態(tài)）Detectionalgorithm（檢測死鎖）Recoveryscheme（恢復(fù)策略）SingleInstanceofEachResourceType

每一種資源類型只有一個實例Maintainwait-forgraph（維護(hù)等待圖）Nodesareprocesses.（節(jié)點是進(jìn)程）Pi

Pj

ifPi

iswaitingfor

Pj.（Pi

Pj表明Pi在等待Pj.）Periodicallyinvokeanalgorithmthatsearchesforacycleinthegraph.（定期調(diào)用算法來檢查是否有環(huán)）Analgorithmtodetectacycleinagraphrequiresanorderofn2operations,wherenisthenumberofverticesinthegraph.（一個檢查圖中是否有環(huán)的算法需要n2的操作來進(jìn)行，n為圖中的節(jié)點數(shù)）Resource-AllocationGraphAndWait-forGraph

資源分配圖和等待圖Resource-AllocationGraphCorrespondingwait-forgraphSeveralInstancesofaResourceType

一個資源類型的多個實例Available:Avectoroflengthmindicatesthenumberofavailableresourcesofeachtype.

（可用：一個長度m的向量代表每種資源類型的有效數(shù)目）Allocation:Annxmmatrixdefinesthenumberofresourcesofeachtypecurrentlyallocatedtoeachprocess.

（分配：一個nxm

的矩陣定義了當(dāng)前分配的每一種資源類型的實例數(shù)目）Request:Annxmmatrixindicatesthecurrentrequestofeachprocess.IfRequest[i,j]=k,thenprocessPiisrequestingkmoreinstancesofresourcetype.Rj.

（請求：一個nxm

的矩陣使命了當(dāng)前的進(jìn)程請求。如果Request[i,j]=k,那么進(jìn)程Pi請求k個Rj資源的實例）DetectionAlgorithm(檢測算法）1. LetWorkandFinishbevectorsoflengthmandn,respectivelyInitialize(讓W(xué)ork和Finish作為長度為m和n的向量）(a)Work:=Available(b) Fori=1,2,…,n,ifAllocationi

0,then

Finish[i]:=false;otherwise,Finish[i]:=true.2. Findanindexisuchthatboth（找到下標(biāo)i）(a) Finish[i]=false(b) Requesti

WorkIfnosuchiexists,gotostep4.（如果沒有這樣的i存在，轉(zhuǎn)4）DetectionAlgorithm(Cont.)3. Work:=Work+Allocationi

Finish[i]:=true

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

Algorithmrequiresanorderofmxn2operationstodetectwhetherthesystemisindeadlockedstate.算法需要mxn2的操作來判斷是否系統(tǒng)處于死鎖狀態(tài)ExampleofDetectionAlgorithm

檢測算法的例子FiveprocessesP0throughP4;

threeresourcetypes

A(7instances),B(2instances),andC(6instances). （五個進(jìn)程p0到p4,三個資源類型A（7個實例），B（2個實例）,C（6個實例）SnapshotattimeT0（時刻Tn的狀態(tài)）

Allocation Request Available

ABC ABC ABC

P0 010 000 000

P1 200 202

P2 303 000

P3 211 100

P4 002 002Sequence<P0,P2,P3,P1,P4>willresultinFinish[i]=trueforalli.Example(Cont.)（例子續(xù)）P2requestsanadditionalinstanceoftypeC.（P2請求C的實例）

Request ABC

P0 000

P1 201

P2 001

P3 100

P4 002Stateofsystem?（系統(tǒng)的狀態(tài)）CanreclaimresourcesheldbyprocessP0,butinsufficientresourcestofulfillotherprocesses;requests.

（可以歸還P0所有的資源，但是資源不夠完成其他進(jìn)程的請求）Deadlockexists,consistingofpr