《现代操作系统全套配套课件4etanenbaumppt及教学资料chapter06-deadlocks》由会员分享，可在线阅读，更多相关《现代操作系统全套配套课件4etanenbaumppt及教学资料chapter06-deadlocks（31页珍藏版）》请在金锄头文库上搜索。
1、Deadlocks,Chapter 6,Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.,Preemptable and Nonpreemptable Resources,Sequence of events required to use a resource Request the resource. Use the resource. Release the resource.,Tanenbaum & Bo, Modern Operatin
2、g Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.,Resource Acquisition (1),Figure 6-1. Using a semaphore to protect resources. (a) One resource. (b) Two resources.,Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.,Resource Acquisit
3、ion (2),Figure 6-2. (a) Deadlock-free code. (b) Code with a potential deadlock.,Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.,Deadlock Definition,A set of processes is deadlocked if Each process in the set waiting for an event That event can be c
4、aused only by another process,Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.,Conditions for Resource Deadlocks,Four conditions that must hold: Mutual exclusion Hold and wait No preemption Circular wait condition,Tanenbaum & Bo, Modern Operating Sy
5、stems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.,Deadlock Modeling (1),Figure 6-3. Resource allocation graphs. (a) Holding a resource. (b) Requesting a resource. (c) Deadlock.,Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.,Deadlock
6、 Modeling (2),Figure 6-4. An example of how deadlock occurs and how it can be avoided.,Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.,Deadlock Modeling (3),Figure 6-4. An example of how deadlock occurs and how it can be avoided.,Tanenbaum & Bo, Mo
7、dern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.,Deadlock Modeling (4),Figure 6-4. An example of how deadlock occurs and how it can be avoided.,Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.,Deadlock Modeling (5),S
8、trategies are used for dealing with deadlocks: Ignore the problem, maybe it will go away. Detection and recovery. Let deadlocks occur, detect them, and take action. Dynamic avoidance by careful resource allocation. Prevention, by structurally negating one of the four required conditions.,Tanenbaum &
9、 Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.,Deadlock Detection with One Resource of Each Type (1),Example of a system is it deadlocked? Process A holds R, wants S Process B holds nothing, wants T Process C holds nothing, wants S Process D holds U, wants S
10、 and T Process E holds T, wants V Process F holds W, wants S Process G holds V, wants U,Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.,Deadlock Detection with One Resource of Each Type (2),Figure 6-5. (a) A resource graph. (b) A cycle extracted fr
11、om (a).,Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.,Algorithm to Detect Deadlocks (1),For each node, N in the graph, perform following five steps with N as starting node. Initialize L to empty list, and designate all arcs as unmarked. Add curre
12、nt node to end of L, check to see if node now appears in L two times. If so, graph contains a cycle (listed in L) and algorithm terminates,Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.,Algorithm to Detect Deadlocks (2),From given node, see if the
13、re are any unmarked outgoing arcs. If so, go to step 5; if not, go to step 6. Pick unmarked outgoing arc at random, mark it. Then follow to new current node and go to step 3. If this is initial node, graph does not contain cycles, algorithm terminates. Otherwise, dead end. Remove it and go back to t
14、he previous node.,Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.,Deadlock Detection with Multiple Resources of Each Type (1),Figure 6-6. The four data structures needed by the deadlock detection algorithm.,Tanenbaum & Bo, Modern Operating Systems:
15、4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.,Deadlock Detection with Multiple Resources of Each Type (2),Deadlock detection algorithm: Look for unmarked process, Pi , for which the 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 th
16、e process, go back to step 1. If no such process exists, algorithm terminates.,Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.,Deadlock Detection with Multiple Resources of Each Type (3),Figure 6-7. An example for the deadlock detection algorithm.,Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.,Recovery from Deadlock,Possible Methods of recovery (though none are “attractive”): Preemption R
