现代操作系统 Chapter 6.ppt

1、Chapter 6 Deadlock,2,Contents,6.1 Resources 6.2 Introduction to deadlocks 6.3 The ostrich algorithm 6.4 Deadlock detection and recovery 6.5 deadlock avoidance 6.6 deadlock prevention,3,6.1 Resources,Resources (资源)：需要排他性使用的对象。资源可以是硬件设备或是一组信息（一个排他使用的表格、数据库中的一条记录等）。 某些类型的资源会有若干个相同的实例。,4,6.1.1 Preemptab

2、le and Nonpreemptable Resources,Preemptable Resource(可抢占资源): it can be taken away from the process owning it with no ill effects. Example: Memory, CPU, Nonpreemptable Resource(不可抢占资源): it cannot be taken away from its current owner without causing the computation to fail. Deadlocks involve nonpreemp

3、table resources.,5,Preemptable and Nonpreemptable Resources,Sequence of events required to use a resource: Request the resource. Use the resource. Release the resource. Assume: when a process is denied a resource request, it is put to sleep.,6,6.1.2 Resource Acquisition(获取),One way of allowing user

4、management of resources is to associate a semaphore with each resource.,Figure 6-1. Using a semaphore to protect resources. (a) One resource. (b) Two resources.,7,Resource Acquisition,Consider a situation with two processes, A and B, and two resources.,Figure 6-2. (a) Deadlock-free code.,8,Figure 6-

5、2. (b) Code with a potential deadlock.,Resource Acquisition,9,6.2 Introduction To Deadlocks,Deadlock can be defined formally as follows: 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 cause. 在一个进程集合中，若每个进程都在等待某些事件（指：释放资源）的

6、发生，而这些事件又必须由这个进程集合中的其它进程来产生，则该进程集合处于死锁状态。,10,6.2.1 Conditions for Resource Deadlocks,Mutual exclusion condition (互斥条件). Each resource is either currently assigned to exactly one process or is available. Hold and wait condition (占有与等待条件). Process currently holding resources that were granted earlier

7、can request new resources. No preemption condition (不可抢占条件). Resources previously granted cannot be forcibly taken away from a process. They must be explicitly released by the process holding them. Circular wait condition (环路等待条件). There must be a circular chain of two or more processes, each of whi

8、ch is waiting for a resource held by the next member of the chain.,11,Conditions for Resource Deadlocks,All four of these conditions must be present for a resource deadlock to occur. If one of them is absent, no resource deadlock is possible.,12,6.2.2 Deadlock Modeling,How can these four conditions

9、be modeled using directed graphs (有向图)? Two kinds of nodes: Process: shown as circles Resources: shown as squares Two kinds of directed arcs: A directed arc from a resource to a process means that the resource has previously been requested by, granted to, and is currently held by that process. A dir

10、ected arc from a process to a resource means that the process is currently blocked waiting for that resource.,13,Deadlock Modeling,Figure 6-3. Resource allocation graphs. (a) Holding a resource. (b) Requesting a resource. (c) Deadlock.,14,Deadlock Modeling,15,Deadlock Modeling,Strategies for dealing

11、 with deadlocks: Just ignore the problem. Detection and recovery (检测与恢复). Let deadlocks occur, detect them, take action. Dynamic avoidance (避免) by careful resource allocation. Prevention (防止), by structurally negating one of the four required conditions.,16,6.3 The Ostrich (鸵鸟) Algorithm,The simples

12、t approach is the ostrich algorithm: stick your head in the sand and pretend there is no problem at all.,17,6.4 Deadlock Detection and Recovery,When this technique is used, the system does not attempt to prevent deadlocks from occurring. Instead, it lets them occur, tries to detect when this happens

13、, and then takes some action to recover after the fact.,18,6.4.1 Deadlock Detection with One Resource of Each Type,The simplest case: only one resource of each type exists. For such a system, we can construct a resource graph. If this graph contains one or more cycles, a deadlock exists. Any process

14、 that is part of a cycle is deadlocked. If no cycles exist, the system is not deadlocked.,19,Deadlock Detection with One Resource of Each Type (2),Example:,Figure 6-5. (a) A resource graph. (b) A cycle extracted from (a).,20,Deadlock Detection with One Resource of Each Type (3),Algorithm for detecti

15、ng deadlock: For each node, N in the graph, perform the following five steps with N as the starting node. Initialize L to the empty list, designate all arcs as unmarked. Add current node to end of L, check to see if node now appears in L two times. If it does, graph contains a cycle (listed in L), a

16、lgorithm terminates.,21,Deadlock Detection with One Resource of Each Type (4),From given node, see if any unmarked outgoing arcs. If so, go to step 5; if not, go to step 6. Pick an unmarked outgoing arc at random and mark it. Then follow it to the new current node and go to step 3. If this is initia

17、l node, graph does not contain any cycles, algorithm terminates. Otherwise, dead end. Remove it, go back to previous node, make that one current node, go to step 3.,22,6.4.2 Deadlock Detection with Multiple Resources of Each Type,We now present a matrix-based algorithm for detecting deadlock among n

18、 processes, P1 through Pn. Assume that: E: the existing resource vector. it gives the total number of instances of each resource in existence. A: the available resource vector. Ai gives the number of instances of resource i that are currently available.,23,Deadlock Detection with Multiple Resources

19、of Each Type (2),C: the current allocation matrix. The i-th row of C tells how many instances of each resource class Pi currently holds. R: the request matrix.,24,Deadlock Detection with Multiple Resources of Each Type (3),Deadlock detection algorithm: Look for an unmarked process, Pi , for which th

20、e i-th row of R is less than or equal to A. If such a process is found, add the i-th row of C to A, mark the process, and go back to step 1. If no such process exists, the algorithm terminates. When the algorithm finishes, all the unmarked processes are deadlocked.,25,Deadlock Detection with Multipl

21、e Resources of Each Type (4),Example:,26,6.4.3 Recovery from Deadlock,1. Recovery through preemption In some cases it may be possible to temporarily take a resource away from its current owner and give it to another process. 2. Recovery through rollback (回滚) The system designers and machine operator

22、s can arrange to have processes checkpointed periodically. Checkpointing a process means that its state is written to a file so that it can be restarted later.,27,Recovery from Deadlock,When a deadlock is detected, it is easy to see which resources are needed. To do the recovery, a process that owns

23、 a needed resource is rolled back to a point in time before it acquired that resource by starting one of its earlier checkpoints. 3. Recovery through killing processes The crudest way to break a deadlock is to kill one or more processes. One possibility is to kill a process in the cycle. A process n

24、ot in the cycle can be chosen as the victim in order to release its resources.,28,6.5 Deadlock Avoidance,In the discussion of deadlock detection, we assumed that when a process asks for resources, it asks for them all at once. However, in most systems, resources are requested one at a time. The syst

25、em must be able to decide whether granting a resource is safe or not and only make the allocation when it is safe. Is there an algorithm that can always avoid deadlock by making the right choice all the time?,29,6.5.1 Resource Trajectories (轨迹图),The main algorithms for doing deadlock avoidance are b

26、ased on the concept of safe sates (安全状态).,30,Resource Trajectories,31,6.5.2 Safe and Unsafe States,A state is said to be safe if there is some scheduling order in which every process can run to completion even if all of them suddenly request their maximum number of resources immediately. Unsafe stat

27、e Difference: From a safe state the system can guarantee that all processes will finish; From an unsafe state, no such guarantee can be given.,32,Safe and Unsafe States,Figure 6-9. Demonstration that the state in (a) is safe.,Figure 6-10. Demonstration that the state in (b) is not safe.,33,6.5.3 The

28、 Bankers Algorithm for a Single Resource,The bankers algorithm (银行家算法),Figure 6-11. Three resource allocation states: (a) Safe. (b) Safe. (c) Unsafe.,34,The Bankers Algorithm for a Single Resource,The bankers algorithm considers each request as it occurs, and sees if granting it leads to a safe stat

29、e. If it does, the request is granted; otherwise, it is postponed until later. To see if a state is safe, the banker checks to see if he has enough resources to satisfy some customer.,35,Figure 6-12. The bankers algorithm with multiple resources.,6.5.4 The Bankers Algorithm for Multiple Resources,36

30、,The Bankers Algorithm for Multiple Resources,Algorithm for checking to see if a state is safe: Look for a row, R, whose unmet resource needs all A. If no such row exists, system will eventually deadlock since no process can run to completion. Assume process of row chosen requests all resources it n

31、eeds and finishes. Mark process as terminated, add all its resources to the A vector. Repeat steps 1 and 2 until either all processes marked terminated (initial state was safe) or no process left whose resource needs can be met (there is a deadlock).,37,6.6 Deadlock Prevention,Attacking the mutual e

32、xclusion condition Attacking the hold and wait condition Attacking the no preemption condition Attacking the circular wait condition,Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639,38,6.6.1 Attacking the mutual exclusion condition,互斥条件是由设备的固有特性

33、所决定的，不仅不能改变，还应加以保证。 By spooling (假脱机) printer output, several processes can generate output at the same time. In this model, the only process that actually requests the physical printer is the printer daemon (守护进程). Since daemon never requests any other resources, we can eliminate deadlock for the p

34、rinter.,39,6.6.2 Attacking the hold and wait condition,If we can prevent processes that hold resources from waiting for more resources, we can eliminate deadlocks. Method 1: require all processes to request all their resources before starting execution. The problem of method 1? Many processes do not

35、 know how many resources they will need until they have started running. Resources will not be used optimally.,40,Attacking the hold and wait condition,Method 2: require a process requesting a resource to first temporarily release all the resources it currently holds. Then it tries to get everything it need all at once.,41,6.6.3 Attacking the no preemption condition,If a process has been assigned the printer and is in the middle of printing its output, forcibly taking away the printer because a n