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

.,Concurrency:DeadlockandStarvation,Chapter6,.,Outline,6.1PrincipleofDeadlock6.2Deadlockprevention(死锁预防)6.3Deadlockavoidance(死锁避免)6.4Deadlockdetection(死锁检测),.,6.1Principleofdeadlock,Definition:PermanentblockingofasetofprocessesthateithercompeteforsystemresourcesorcommunicatewitheachotherNoefficientsolutionInvolveconflictingneedsforresourcesbytwoormoreprocesses,.,1、ReusableResources,Usedbyoneprocessatatimeandnotdepleted(消耗掉)bythatuseProcessesobtainresourcesthattheylaterreleaseforreusebyotherprocessesProcessors,I/Ochannels,mainandsecondarymemory,files,databases,andsemaphoresDeadlockoccursifeachprocessholdsoneresourceandrequeststheother,.,ExampleofDeadlock,D,Request60Kbytes;,P2,.,.,Request70Kbytes;,Request80Kbytes;,.,2、ConsumableResources,Created(produced)anddestroyed(consumed)byaprocessInterrupts,signals,messages,andinformationinI/ObuffersDeadlockmayoccurifaReceivemessageisblockingMaytakeararecombinationofeventstocausedeadlock,.,ExampleofDeadlock,Deadlockoccursifreceiveisblocking,P1,.,.,Receive(P2);,Send(P2,M1);,P2,.,.,Receive(P1);,Send(P1,M2);,.,3、ResourceAllocationGraphs,Directedgraphthatdepictsastateofthesystemofresourcesandprocesses,.,ResourceAllocationGraphs,.,.,4、ConditionsforDeadlock,Mutualexclusion(互斥排它性访问资源)onlyoneprocessmayusearesourceatatimeHold-and-wait(占有且等待拥有部分资源,还要请求新的)Aprocessdoesnotrequestallofitsrequiredresourcesatonetime,.,ConditionsforDeadlock,Nopreemption(非剥夺性排他性访问资源)Ifaprocessholdingcertainresourcesisdeniedafurtherrequest,thatprocessmustnotreleaseitsoriginalresourcesIfaprocessrequestsaresourcethatiscurrentlyheldbyanotherprocess,theoperatingsystemisnotallowedtopreemptthesecondprocessandrequireittoreleaseitsresources,.,ConditionsforDeadlock,Circularwait(循环等待在进程资源图中有环路),.,PossibilityofDeadlock,MutualExclusionNopreemptionHoldandwait,.,ExistenceofDeadlock,MutualExclusionNopreemptionHoldandwaitCircularwait,Necessarycondition,.,6.2DeadlockPrevention,Indirectmethod:preventtheoccurrenceofoneofthethreenecessaryconditions(items1through3)Directmethod:preventtheoccurrenceofacircularwait(item4),.,1、Mutualexclusion,Cannotbedisallowed,.,2、HoldandWait,静态分配：Resourcesareallocatedstatically,dynamicrequestsarenotpermitted.Inefficient:BeheldupforalongtimewaitingforallitsresourceResourceallocatedtoaprocessmayremainunusedforalongtime,.,3、NoPreemption,剥夺调度：Whenrequestfurtherresource,releaseitsoriginalresourcesfirst;operatingsystemisallowedtopreempttheresourcesheldbyotherprocess.Onlyappliedtoprocessorormemory,.,4、Circularwait,层次分配：definealinearorderingofresourcetypesandallocatethemaccordingtotheorder,.,6.3DeadlockAvoidance,Allowsthethreenecessaryconditionsbutmakejudiciouschoicestoassurethatthedeadlockpointisneverreached.Adecisionismadedynamicallywhetherthecurrentresourceallocationrequestwill,ifgranted,potentiallyleadtoadeadlockRequiresknowledgeoffutureprocessrequest,.,TwoApproachestoDeadlockAvoidance,DonotstartaprocessifitsdemandsmightleadtodeadlockDonotgrantanincrementalresourcerequesttoaprocessifthisallocationmightleadtodeadlock,银行家算法银行家拥有一笔周转资金客户一开始必须说明其最大需求客户要求分期贷款，如果客户能够得到各期贷款，就一定能够归还贷款，否则就一定不能归还贷款只要客户所要求的最大资金量不超过总周转资金，银行家总会在有限时间内满足其需求。银行家应谨慎的贷款，防止出现坏帐用银行家算法避免死锁操作系统（银行家）操作系统管理的资源(周转资金)进程（要求贷款的客户）,Single-resource,Totalresource:10,不死锁,死锁,Safety,Safety,unsafety,Anotherexample,.,1、Processinitiationdenial,.,OnlyRiC(n+1)i+Cki对i=1,.,m,k=1,.,n;Anewprocesswillbestarted.,.,2、ResourceAllocationDenial,ReferredtoasthebankersalgorithmStateofthesystemisthecurrentallocationofresourcestoprocessSafestateiswherethereisatleastonesequencethatdoesnotresultindeadlockUnsafestateisastatethatisnotsafe,Bankeralgorithm,基本思想是：系统中的所有进程进入进程集合，在安全状态下系统收到一个进程的资源请求后，先把资源试探性分配给它。现在，系统用剩下的可用资源和每个进程集合中其他进程还要的资源数作比较，在进程集合中找到剩余资源能满足最大需求量的进程，从而，保证这个进程运行完毕并归还全部资源。这时，把这个进程从集合中去掉，系统的剩余资源更多了，再反复执行上述步骤。最后，检查进程集合，若为空表明本次申请可行，系统处于安全状态，可真正实施本次分配；否则，只要有进程执行不完，系统便处于不安全状态，本次资源分配暂不实施，让申请进程等待,设Request是进程Pi的请求向量。如果Requestj=k,表示进程Pi需要k个Ri类型的资源，进程Pi发出请求后，系统按下述步骤进行检查：(1)如果RequestjClaimij-Allocij,认为出错，因为所需资源数超过了它所宣布的最大值；否则转(2).(2)如果RequestjAvailablej,目前尚无足够资源分配，等待；否则转(3)。(3)系统尝试将所需资源分配给Pi，并修改以下数据结构中的值：Availablej=Availablej-Requestj;Allocij=Allocij+Requestj;(4)进行安全性检查。如果进行了此次资源分配后，系统仍处于安全状态，则分配，否则，尝试分配作废，恢复原来数值，让进程Pi等待。,Safetycheck,定义工作向量currentavail和布尔型标志possible；初始化currentavail:=available,possible:=true；保持possible:=true，从进程集合rest中找出claimk,*-allocationk,*currentavail的进程来，如找到，则释放这个进程Pk的全部资源、执行以下操作currentavail:=currentavail+allocationk,*，把Pk从进程集合中去掉rest:=rest-Pk；否则Possible:=false，停止执行算法；最后查看进程集rest，若为空集返回安全标记；否则返回不安全标记。,.,DeterminationofaSafeStateInitialState,.,DeterminationofaSafeStateP2RunstoCompletion,.,DeterminationofaSafeStateP1RunstoCompletion,.,DeterminationofaSafeStateP3RunstoCompletion,.,DeterminationofanUnsafeState,.,DeterminationofanUnsafeState,.,DeadlockAvoidanceLogic,.,DeadlockAvoidanceLogic,.,DeadlockAvoidance,MaximumresourcerequirementmustbestatedinadvanceProcessesunderconsiderationmustbeindependent;nosynchronizationrequirementsTheremustbeafixednumberofresourcestoallocateNoprocessmayexitwhileholdingresources,.,6.4DeadlockDetection,定义布尔型向量possiblek，k=1,.,n。检测死锁算法如下：（1）标记Allocationk,*全为0的进程，即possiblek:=true;(2)currentavail:=available；（3）在rest中查每一个进程Pk,如果claimk,*-allock,*=0，则possiblek:=true；否则possiblek:=false；这里k=1,.,n。（4）在rest中找一个进程Pk，需满足条件：possiblek=false&(request*currentavail)找到这样的Pk便转（5）；否则转（6）；（5）currentavail:=currentavail+allocation；possiblek:=true；然后转（4）；(6)如果对k=1,.,n若possiblek=true不成立，那么，系统出现了死锁，并且possiblek=false的Pk为死锁进程。,.,StrategiesonceDeadlockDetected,AbortalldeadlockedprocessesBackupeachdeadlockedprocesstosomepreviouslydefinedcheckpoint,andrestartallprocessoriginaldeadlockmayoccurSuccessivelyabortdeadlockedprocessesuntildeadlocknolongerexistsSuccessivelypreemptresourcesuntildeadlocknolongerexists,.,SelectionCriteriaDeadlockedProcesses,LeastamountofprocessortimeconsumedsofarLeastnumberoflinesofoutputproducedsofarMostestimatedtimeremainingLeasttotalresourcesallocatedsofarLowestpriority,.,StrengthsandWeaknessesoftheStrategies,.,6.5Anintegrateddeadlockstrategy,GroupresourcesintoanumberofdifferentresourceclassesUsethelinearorderingstrategydefinedpreviouslyforthepreventionofcircularwaittopreventdeadlocksbetweenrecourseclassesWithinaresourceclass,usethealgorithmthatismostappropriateforthatclass,.,Anexample,resourcesSwappablespace