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

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 T AnotherExampleofDeadlock Spaceisavailableforallocationof200Kbytes andthefollowingsequenceofeventsoccurDeadlockoccursifbothprocessesprogresstotheirsecondrequest P1 Request80Kbytes 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 OnlyRi C n 1 i Cki对i 1 m k 1 n Anewprocesswillbestarted 2 ResourceAllocationDenial Referredtoasthebanker salgorithmStateofthesystemisthecurrentallocationofresourcestoprocessSafestateiswherethereisatleastonesequencethatdoesnotresultindeadlockUnsafestateisastatethatisnotsafe Bankeralgorithm 基本思想是 系统中的所有进程进入进程集合 在安全状态下系统收到一个进程的资源请求后 先把资源试探性分配给它 现在 系统用剩下的可用资源和每个进程集合中其他进程还要的资源数作比较 在进程集合中找到剩余资源能满足最大需求量的进程 从而 保证这个进程运行完毕并归还全部资源 这时 把这个进程从集合中去掉 系统的剩余资源更多了 再反复执行上述步骤 最后 检查进程集合 若为空表明本次申请可行 系统处于安全状态 可真正实施本次分配 否则 只要有进程执行不完 系统便处于不安全状态 本次资源分配暂不实施 让申请进程等待 设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等待 Safetycheck 定义工作向量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 若为空集返回安全标记 否则返回不安全标记 DeterminationofaSafeStateInitialState DeterminationofaSafeStateP2RunstoCompletion DeterminationofaSafeStateP1RunstoCompletion DeterminationofaSafeStateP3RunstoCompletion DeterminationofanUnsafeState DeterminationofanUnsafeState DeadlockAvoidanceLogic DeadlockAvoidanceLogic DeadlockAvoidance MaximumresourcerequirementmustbestatedinadvanceProcessesunderconsiderationmustbeindependent nosynchronizationrequirementsTheremustbeafixednumberofresourcestoallocateNoprocessmayexitwhileholdingresources 6 4DeadlockDetection 定义布尔型向量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为死锁进程 StrategiesonceDeadlockDetected AbortalldeadlockedprocessesBackupeachdeadlockedprocesstosomepreviouslydefinedcheckpoint andrestartallprocessoriginaldeadlockmayoccurSuccessivelyabortdeadlockedprocessesuntildeadlocknolongerexistsSuccessivelypreemptresourcesuntildeadlocknolongerexists SelectionCriteriaDeadlockedProcesses LeastamountofprocessortimeconsumedsofarLeastnumberoflinesofoutputproducedsofarMostestimatedtimeremainingLeasttotalresourcesallocatedsofarLowestpriority StrengthsandWeaknessesoftheStrategies 6 5Anintegrateddeadlockstrategy GroupresourcesintoanumberofdifferentresourceclassesUsethelinearorderingstrategydefinedpreviouslyforthepreventionofcircularwaittopreventdeadlocksbetweenrecourseclassesWithinaresourceclass usethealgorithmthatismostappropriateforthatclass Anexample resources S