操作系統(tǒng)精髓與設(shè)計原理Chap6課件

Concurrency:DeadlockandStarvationChapter61精選可編輯pptOutline6.1PrincipleofDeadlock6.2Deadlockprevention(死鎖預(yù)防)6.3Deadlockavoidance(死鎖避免)6.4Deadlockdetection(死鎖檢測)2精選可編輯ppt6.1PrincipleofdeadlockDefinition:PermanentblockingofasetofprocessesthateithercompeteforsystemresourcesorcommunicatewitheachotherNoefficientsolutionInvolveconflictingneedsforresourcesbytwoormoreprocesses3精選可編輯ppt4精選可編輯ppt5精選可編輯ppt6精選可編輯ppt1、ReusableResourcesUsedbyoneprocessatatimeandnotdepleted(消耗掉)bythatuseProcessesobtainresourcesthattheylaterreleaseforreusebyotherprocessesProcessors,I/Ochannels,mainandsecondarymemory,files,databases,andsemaphoresDeadlockoccursifeachprocessholdsoneresourceandrequeststheother7精選可編輯pptExampleofDeadlock,D&T8精選可編輯pptAnotherExampleofDeadlockSpaceisavailableforallocationof200Kbytes,andthefollowingsequenceofeventsoccurDeadlockoccursifbothprocessesprogresstotheirsecondrequestP1......Request80Kbytes;Request60Kbytes;P2......Request70Kbytes;Request80Kbytes;9精選可編輯ppt2、ConsumableResourcesCreated(produced)anddestroyed(consumed)byaprocessInterrupts,signals,messages,andinformationinI/ObuffersDeadlockmayoccurifaReceivemessageisblockingMaytakeararecombinationofeventstocausedeadlock10精選可編輯pptExampleofDeadlockDeadlockoccursifreceiveisblockingP1......Receive(P2);Send(P2,M1);P2......Receive(P1);Send(P1,M2);11精選可編輯ppt3、ResourceAllocationGraphsDirectedgraphthatdepictsastateofthesystemofresourcesandprocesses12精選可編輯pptResourceAllocationGraphs13精選可編輯ppt14精選可編輯ppt4、ConditionsforDeadlockMutualexclusion(互斥—排它性訪問資源)onlyoneprocessmayusearesourceatatimeHold-and-wait(占有且等待—擁有部分資源,還要請求新的)Aprocessdoesnotrequestallofitsrequiredresourcesatonetime15精選可編輯pptConditionsforDeadlockNopreemption(非剝奪性—排他性訪問資源)Ifaprocessholdingcertainresourcesisdeniedafurtherrequest,thatprocessmustnotreleaseitsoriginalresourcesIfaprocessrequestsaresourcethatiscurrentlyheldbyanotherprocess,theoperatingsystemisnotallowedtopreemptthesecondprocessandrequireittoreleaseitsresources16精選可編輯pptConditionsforDeadlockCircularwait(循環(huán)等待—在進(jìn)程資源圖中有環(huán)路)17精選可編輯pptPossibilityofDeadlockMutualExclusionNopreemptionHoldandwait18精選可編輯pptExistenceofDeadlockMutualExclusionNopreemptionHoldandwaitCircularwaitNecessarycondition19精選可編輯ppt6.2DeadlockPreventionIndirectmethod:preventtheoccurrenceofoneofthethreenecessaryconditions(items1through3)Directmethod:preventtheoccurrenceofacircularwait(item4)20精選可編輯ppt1、MutualexclusionCannotbedisallowed21精選可編輯ppt2、HoldandWait靜態(tài)分配：Resourcesareallocatedstatically,dynamicrequestsarenotpermitted.Inefficient:BeheldupforalongtimewaitingforallitsresourceResourceallocatedtoaprocessmayremainunusedforalongtime22精選可編輯ppt3、NoPreemption剝奪調(diào)度：Whenrequestfurtherresource,releaseitsoriginalresourcesfirst;operatingsystemisallowedtopreempttheresourcesheldbyotherprocess.Onlyappliedtoprocessorormemory23精選可編輯ppt4、Circularwait層次分配：definealinearorderingofresourcetypesandallocatethemaccordingtotheorder24精選可編輯ppt6.3DeadlockAvoidanceAllowsthethreenecessaryconditionsbutmakejudiciouschoicestoassurethatthedeadlockpointisneverreached.Adecisionismadedynamicallywhetherthecurrentresourceallocationrequestwill,ifgranted,potentiallyleadtoadeadlockRequiresknowledgeoffutureprocessrequest25精選可編輯pptTwoApproachesto

DeadlockAvoidanceDonotstartaprocessifitsdemandsmightleadtodeadlockDonotgrantanincrementalresourcerequesttoaprocessifthisallocationmightleadtodeadlock26精選可編輯ppt銀行家算法銀行家擁有一筆周轉(zhuǎn)資金客戶一開始必須說明其最大需求客戶要求分期貸款，如果客戶能夠得到各期貸款，就一定能夠歸還貸款，否則就一定不能歸還貸款只要客戶所要求的最大資金量不超過總周轉(zhuǎn)資金，銀行家總會在有限時間內(nèi)滿足其需求。銀行家應(yīng)謹(jǐn)慎的貸款，防止出現(xiàn)壞帳用銀行家算法避免死鎖操作系統(tǒng)（銀行家）操作系統(tǒng)管理的資源(周轉(zhuǎn)資金)進(jìn)程（要求貸款的客戶）27精選可編輯pptSingle-resourceTotalresource:1028精選可編輯pptCash=2P:2(4)Q:4(2)R:2(6)Cash=6P:2(4)R:2(6)Cash=8R:2(6)Cash=2P:2(4)Q:4(2)R:2(6)Cash=1P:4(2)Q:2(2)R:3(5)Cash=0P:5(1)Q:2(2)R:3(6)不死鎖死鎖29精選可編輯pptSafetySafetyunsafetyAnotherexample30精選可編輯ppt1、Processinitiationdenial31精選可編輯pptOnlyRi≥C(n+1)i+∑Cki

對i=1,..,m,k=1,..,n;Anewprocesswillbestarted.32精選可編輯ppt2、ResourceAllocationDenialReferredtoasthebanker’salgorithmStateofthesystemisthecurrentallocationofresourcestoprocessSafestateiswherethereisatleastonesequencethatdoesnotresultindeadlockUnsafestateisastatethatisnotsafe33精選可編輯pptBankeralgorithm基本思想是：系統(tǒng)中的所有進(jìn)程進(jìn)入進(jìn)程集合，在安全狀態(tài)下系統(tǒng)收到一個進(jìn)程的資源請求后，先把資源試探性分配給它。現(xiàn)在，系統(tǒng)用剩下的可用資源和每個進(jìn)程集合中其他進(jìn)程還要的資源數(shù)作比較，在進(jìn)程集合中找到剩余資源能滿足最大需求量的進(jìn)程，從而，保證這個進(jìn)程運行完畢并歸還全部資源。這時，把這個進(jìn)程從集合中去掉，系統(tǒng)的剩余資源更多了，再反復(fù)執(zhí)行上述步驟。最后，檢查進(jìn)程集合，若為空表明本次申請可行，系統(tǒng)處于安全狀態(tài)，可真正實施本次分配；否則，只要有進(jìn)程執(zhí)行不完，系統(tǒng)便處于不安全狀態(tài)，本次資源分配暫不實施，讓申請進(jìn)程等待34精選可編輯ppt設(shè)Request是進(jìn)程Pi的請求向量。如果Request[j]=k,表示進(jìn)程Pi需要k個Ri類型的資源，進(jìn)程Pi發(fā)出請求后，系統(tǒng)按下述步驟進(jìn)行檢查：(1)如果Request[j]>Claim[i][j]-Alloc[i][j],認(rèn)為出錯，因為所需資源數(shù)超過了它所宣布的最大值；否則轉(zhuǎn)(2).(2)如果Request[j]>Available[j],目前尚無足夠資源分配，等待；否則轉(zhuǎn)(3)。(3)系統(tǒng)嘗試將所需資源分配給Pi，并修改以下數(shù)據(jù)結(jié)構(gòu)中的值：

Available[j]=Available[j]-Request[j];Alloc[i][j]=Alloc[i][j]+Request[j];(4)進(jìn)行安全性檢查。如果進(jìn)行了此次資源分配后，系統(tǒng)仍處于安全狀態(tài)，則分配，否則，嘗試分配作廢，恢復(fù)原來數(shù)值，讓進(jìn)程Pi等待。35精選可編輯pptSafetycheck定義工作向量currentavail和布爾型標(biāo)志possible；初始化currentavail:=available,possible:=true；保持possible:=true，從進(jìn)程集合rest中找出claim[k,*]-allocation[k,*]≤currentavail的進(jìn)程來，如找到，則釋放這個進(jìn)程Pk

的全部資源、執(zhí)行以下操作currentavail:=currentavail+allocation[k,*]，把Pk

從進(jìn)程集合中去掉rest:=rest-[Pk]；否則Possible:=false，停止執(zhí)行算法；最后查看進(jìn)程集rest，若為空集返回安全標(biāo)記；否則返回不安全標(biāo)記。36精選可編輯pptDeterminationofaSafeState

InitialState37精選可編輯pptDeterminationofaSafeState

P2RunstoCompletion38精選可編輯pptDeterminationofaSafeState

P1RunstoCompletion39精選可編輯pptDeterminationofaSafeState

P3RunstoCompletion40精選可編輯pptDeterminationofan

UnsafeState41精選可編輯pptDeterminationofan

UnsafeState42精選可編輯pptDeadlockAvoidanceLogic43精選可編輯pptDeadlockAvoidanceLogic44精選可編輯pptDeadlockAvoidanceMaximumresourcerequirementmustbestatedinadvanceProcessesunderconsiderationmustbeindependent;nosynchronizationrequirementsTheremustbeafixednumberofresourcestoallocateNoprocessmayexitwhileholdingresources45精選可編輯ppt6.4DeadlockDetection46精選可編輯ppt定義布爾型向量possible[k]，k=1,..,n。檢測死鎖算法如下：（1）標(biāo)記Allocation[k,*]全為0的進(jìn)程，即possible[k]:=true;(2)currentavail:=available；（3）在rest中查每一個進(jìn)程Pk,如果claim[k,*]-alloc[k,*]=0，則possible[k]:=true；否則possible[k]:=false；這里k=1,..,n。（4）在rest中找一個進(jìn)程Pk，需滿足條件：possible[k]=false&(request[*]≤currentavail)找到這樣的Pk便轉(zhuǎn)（5）；否則轉(zhuǎn)（6）；（5）currentavail:=currentavail+allocation；possible[k]:=true；然后轉(zhuǎn)（4）；(6)如果對k=1,..,n若possible[k]=true不成立，那么，系統(tǒng)出現(xiàn)了死鎖，并且possible[k]=false的Pk為死鎖進(jìn)程。47精選可編輯pptStrategiesonceDeadlockDetectedAbortalldeadlockedprocessesBackupeachdeadlockedprocesstosomepreviouslydefinedcheckpoint,andrestartallprocessoriginaldeadlockmayoccurSuccessivelyabortdeadlockedprocessesuntildeadlocknolongerexistsSuccessivelypreemptresourcesuntildeadlocknolongerexists48精選可編輯pptSelectionCriteriaDeadlockedProcessesLeastamountofprocessortimeconsumedsofarLeastnumberoflinesofoutputproducedsofarMostestimatedtimeremainingLeasttotalresourcesallocatedsofarLowestpriority49精選可編輯pptStrengthsandWeaknessesoftheStrategies50精選可編輯ppt6.5AnintegrateddeadlockstrategyGroupresourcesintoanumberofdifferentresourceclassesUsethelinearorderingstrategydefinedpreviouslyforthepreventionofcircularwaittopreventdeadlocksbetweenrecourseclassesWithinaresourceclass,usethealgorithmthatismostappropriateforthatclas