《操作系统课件：Chapter-03 Deadlocks》由会员分享，可在线阅读，更多相关《操作系统课件：Chapter-03 Deadlocks（30页珍藏版）》请在金锄头文库上搜索。
1、DeadlocksChapter 3 3.1. Resource 3.2. Introduction to deadlocks 3.3. The ostrich algorithm 3.4. Deadlock detection and recovery 3.5. Deadlock avoidance 3.6. Deadlock prevention 3.7. Other issues 1ResourcesExamples of computer resourcesprinterstape drivestablesProcesses need access to resources in re
2、asonable orderSuppose a process holds resource A and requests resource Bat same time another process holds B and requests Aboth are blocked and remain so2Resources (1)Deadlocks occur when processes are granted exclusive access to deviceswe refer to these devices generally as resourcesPreemptable res
3、ourcescan be taken away from a process with no ill effectsNonpreemptable resourceswill cause the process to fail if taken away3Resources (2)Sequence of events required to use a resource1.request the resource2.use the resource3.release the resource Must wait if request is deniedrequesting process may
4、 be blockedmay fail with error code4Introduction to DeadlocksFormal definition :A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can causeUsually the event is release of a currently held resourceNone of the processes can runrele
5、ase resourcesbe awakened死锁是指系统中多个进程无限制地等待永远不会发生的条件；5Four Conditions for Deadlock1.Mutual exclusion conditioneach resource assigned to 1 process or is available2.Hold and wait conditionprocess holding resources can request additional3.No preemption conditionpreviously granted resources cannot forcibl
6、y taken away4.Circular wait conditionmust be a circular chain of 2 or more processeseach is waiting for resource held by next member of the chain6Deadlock Modeling (1)Strategies for dealing with Deadlocks1.just ignore the problem altogether2.detection and recovery3.dynamic avoidance careful resource
7、 allocation4.prevention negating one of the four necessary conditions7处理死锁的基本方法8Deadlock Modeling (3)Modeled with directed graphs 资源分配图(resource allocation graph)resource R assigned to process Aprocess B is requesting/waiting for resource Sprocess C and D are in deadlock over resources T and U9How d
8、eadlock occursA B CDeadlock Modeling (4)10Deadlock Modeling (5)How deadlock can be avoided(o) (p) (q)11The Ostrich AlgorithmPretend there is no problemReasonable if deadlocks occur very rarely cost of prevention is highUNIX and Windows takes this approachIt is a trade off between conveniencecorrectn
9、ess12Detection with One Resource of Each Type (1)Note the resource ownership and requestsA cycle can be found within the graph, denoting deadlock13Detection with One Resource of Each Type (2)Data structures needed by deadlock detection algorithm14Detection with One Resource of Each Type (3)An exampl
10、e for the deadlock detection algorithm15Recovery from Deadlock (1)Recovery through preemptiontake a resource from some other processdepends on nature of the resourceRecovery through rollbackcheckpoint a process periodicallyuse this saved state restart the process if it is found deadlocked16Recovery
11、from Deadlock (2)Recovery through killing processescrudest but simplest way to break a deadlockkill one of the processes in the deadlock cyclethe other processes get its resources choose process that can be rerun from the beginning17Deadlock AvoidanceResource TrajectoriesTwo process resource traject
12、ories18Safe and Unsafe States (1)Demonstration that the state in (a) is safe(a) (b) (c) (d) (e)19Safe and Unsafe States (2)Demonstration that the sate in b is not safe(a) (b) (c) (d) 20The Bankers Algorithm for a Single ResourceThree resource allocation statessafesafeunsafe(a) (b) (c)银行家算法的特点允许互斥、部分
13、分配和不可抢占，可提高资源利用率；要求事先说明最大资源要求，在现实中很困难；21Bankers Algorithm for Multiple ResourcesExample of bankers algorithm with multiple resources22Deadlock PreventionAttacking the Mutual Exclusion ConditionSome devices (such as printer) can be spooledonly the printer daemon uses printer resourcethus deadlock for
14、 printer eliminatedNot all devices can be spooledPrinciple:avoid assigning resource when not absolutely necessaryas few processes as possible actually claim the resource23Attacking the Hold and Wait ConditionRequire processes to request resources before startinga process never has to wait for what i
15、t needsProblemsmay not know required resources at start of runalso ties up resources other processes could be usingVariation: process must give up all resourcesthen request all immediately needed24Attacking the No Preemption ConditionThis is not a viable optionConsider a process given the printerhal
16、fway through its jobnow forcibly take away printer!? 25Attacking the Circular Wait Condition (1)Normally ordered resourcesA resource graph(a) (b)26Attacking the Circular Wait Condition (1)Summary of approaches to deadlock prevention27Other IssuesTwo-Phase LockingPhase Oneprocess tries to lock all re
17、cords it needs, one at a timeif needed record found locked, start over(no real work done in phase one)If phase one succeeds, it starts second phase, performing updatesreleasing locks Note similarity to requesting all resources at onceAlgorithm works where programmer can arrange program can be stoppe
18、d, restarted28Nonresource DeadlocksPossible for two processes to deadlockeach is waiting for the other to do some taskCan happen with semaphoreseach process required to do a down() on two semaphores (mutex and another)if done in wrong order, deadlock results29StarvationAlgorithm to allocate a resource may be to give to shortest job firstWorks great for multiple short jobs in a systemMay cause long job to be postponed indefinitelyeven though not blockedSolution:First-come, first-serve policy30
