操作系统精髓与设计原理Chap6课件

Concurrency:DeadlockandStarvationChapter61精选可编辑pptOutline6.1PrincipleofDeadlock6.2Deadlockprevention(死锁预防)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(循环等待—在进程资源图中有环路)17精选可编辑pptPossibilityofDeadlockMutualExclusionNopreemptionHoldandwait18精选可编辑pptExistenceofDeadlockMutualExclusionNopreemptionHoldandwaitCircularwaitNecessarycondition19精选可编辑ppt6.2DeadlockPreventionIndirectmethod:preventtheoccurrenceofoneofthethreenecessaryconditions(items1through3)Directmethod:preventtheoccurrenceofacircularwait(item4)20精选可编辑ppt1、MutualexclusionCannotbedisallowed21精选可编辑ppt2、HoldandWait静态分配：Resourcesareallocatedstatically,dynamicrequestsarenotpermitted.Inefficient:BeheldupforalongtimewaitingforallitsresourceResourceallocatedtoaprocessmayremainunusedforalongtime22精选可编辑ppt3、NoPreemption剥夺调度：Whenrequestfurtherresource,releaseitsoriginalresourcesfirst;operatingsystemisallowedtopreempttheresourcesheldbyotherprocess.Onlyappliedtoprocessorormemory23精选可编辑ppt4、Circularwait层次分配：definealinearorderingofresourcetypesandallocatethemaccordingtotheorder24精选可编辑ppt6.3DeadlockAvoidanceAllowsthethreenecessaryconditionsbutmakejudiciouschoicestoassurethatthedeadlockpointisneverreached.Adecisionismadedynamicallywhetherthecurrentresourceallocationrequestwill,ifgranted,potentiallyleadtoadeadlockRequiresknowledgeoffutureprocessrequest25精选可编辑pptTwoApproachesto

DeadlockAvoidanceDonotstartaprocessifitsdemandsmightleadtodeadlockDonotgrantanincrementalresourcerequesttoaprocessifthisallocationmightleadtodeadlock26精选可编辑ppt银行家算法银行家拥有一笔周转资金客户一开始必须说明其最大需求客户要求分期贷款，如果客户能够得到各期贷款，就一定能够归还贷款，否则就一定不能归还贷款只要客户所要求的最大资金量不超过总周转资金，银行家总会在有限时间内满足其需求。银行家应谨慎的贷款，防止出现坏帐用银行家算法避免死锁操作系统（银行家）操作系统管理的资源(周转资金)进程（要求贷款的客户）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基本思想是：系统中的所有进程进入进程集合，在安全状态下系统收到一个进程的资源请求后，先把资源试探性分配给它。现在，系统用剩下的可用资源和每个进程集合中其他进程还要的资源数作比较，在进程集合中找到剩余资源能满足最大需求量的进程，从而，保证这个进程运行完毕并归还全部资源。这时，把这个进程从集合中去掉，系统的剩余资源更多了，再反复执行上述步骤。最后，检查进程集合，若为空表明本次申请可行，系统处于安全状态，可真正实施本次分配；否则，只要有进程执行不完，系统便处于不安全状态，本次资源分配暂不实施，让申请进程等待34精选可编辑ppt设Request是进程Pi的请求向量。如果Request[j]=k,表示进程Pi需要k个Ri类型的资源，进程Pi发出请求后，系统按下述步骤进行检查：(1)如果Request[j]>Claim[i][j]-Alloc[i][j],认为出错，因为所需资源数超过了它所宣布的最大值；否则转(2).(2)如果Request[j]>Available[j],目前尚无足够资源分配，等待；否则转(3)。(3)系统尝试将所需资源分配给Pi，并修改以下数据结构中的值：

Available[j]=Available[j]-Request[j];Alloc[i][j]=Alloc[i][j]+Request[j];(4)进行安全性检查。如果进行了此次资源分配后，系统仍处于安全状态，则分配，否则，尝试分配作废，恢复原来数值，让进程Pi等待。35精选可编辑pptSafetycheck定义工作向量currentavail和布尔型标志possible；初始化currentavail:=available,possible:=true；保持possible:=true，从进程集合rest中找出claim[k,*]-allocation[k,*]≤currentavail的进程来，如找到，则释放这个进程Pk

的全部资源、执行以下操作currentavail:=currentavail+allocation[k,*]，把Pk

从进程集合中去掉rest:=rest-[Pk]；否则Possible:=false，停止执行算法；最后查看进程集rest，若为空集返回安全标记；否则返回不安全标记。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）标记Allocation[k,*]全为0的进程，即possible[k]:=true;(2)currentavail:=available；（3）在rest中查每一个进程Pk,如果claim[k,*]-alloc[k,*]=0，则possible[k]:=true；否则possible[k]:=false；这里k=1,..,n。（4）在rest中找一个进程Pk，需满足条件：possible[k]=false&(request[*]≤currentavail)找到这样的Pk便转（5）；否则转（6）；（5）currentavail:=currentavail+allocation；possible[k]:=true；然后转（4）；(6)如果对k=1,..,n若possible[k]=true不成立，那么，系统出现了死锁，并且possible[k]=false的Pk为死锁进程。47精选可编辑pptStrategiesonceDeadlockDetectedAbortalldeadlockedprocessesBackupeachdeadlockedprocesstosomepreviouslydefinedcheckpoint,andrestartallprocessoriginaldeadlockmayoccurSuccessivelyabortdeadlockedprocessesuntildeadlocknolongerexistsSuccessivelypreemptresourcesuntildeadlocknolongerexists48精选可编辑pptSelectionCriteriaDeadlockedProcessesLeastamountofprocessortimeconsumedsofarLeastnumberoflinesofoutputproducedsofarMostestimatedtimeremainingLeasttotalresourcesallocatedsofarLowestpriority49精选可编辑pptStrengthsandWeaknessesoftheStrategies50精选可编辑ppt6.5AnintegrateddeadlockstrategyGroupresourcesintoanumberofdifferentresourceclassesUsethelinearorderingstrategydefinedpreviouslyforthepreventionofcircularwaittopreventdeadlocksbetweenrecourseclassesWithinaresourceclass,usethealgorithmthatismostappropriateforthatclas