展开查看详情
1 .Operating Systems 1 6. Deadlocks 6.1 Deadlocks with Reusable and Consumable Resources 6.2 Approaches to the Deadlock Problem 6.3 A System Model Resource Graphs State Transitions Deadlock States and Safe States 6.4 Deadlock Detection Reduction of Resource Graphs Special Cases of Deadlock Detection 6.5 Recovery from Deadlock 6.6 Dynamic Deadlock Avoidance Claim Graphs The Banker’s Algorithm 6.7 Deadlock Prevention
2 .Operating Systems 2 Deadlocks Informal definition: Process is blocked on resource that will never be released. Deadlocks waste resources Deadlocks are rare: Many systems ignore them Resolved by explicit user intervention Critical in many real-time applications May cause damage, endanger life
3 .Operating Systems 3 Reusable/Consumable Resources Reusable Resources Examples: memory, devices, files, tables Number of units is constant Unit is either free or allocated; no sharing Process requests, acquires, releases units Consumable Resources Examples: messages, signals Number of units varies at runtime Process releases (create) units (w/o acquire) Other process requests and acquires (consumes)
4 .Operating Systems 4 Examples of Deadlocks p1: ... p2: ... open(f1,w); open(f2,w); open(f2,w); open(f1,w); ... ... Deadlock when executed concurrently p1: if (C) send(p2,m); p2: ... while(1) {... while(1) {... recv (p2,m); recv (p1,m); send(p2,m); send(p1,m); ... } ... } Deadlock when C not true
5 .Operating Systems 5 Approaches to Deadlock Problem Detection and Recovery Allow deadlock to happen and eliminate it Avoidance (dynamic) Runtime checks disallow allocations that might lead to deadlocks Prevention (static) Restrict type of request and acquisition to make deadlock impossible
6 .Operating Systems 6 System Model ( reusable only) Resource graph: represents processes, resources, and their interactions Process = Circle Resource = Rectangle with small circles for each unit Request = Edge from process to resource class Allocation = Edge from resource unit to process
7 .Operating Systems 7 System Model: State Transitions Request : Create new request edge p i R j Preconditions: p i has no outstanding requests (= not blocked) number of edges between p i and R j cannot exceed total units of R j Acquisition : Reverse the request edge to p i R j Precondition : All requests of p i are satisfiable (simplifies model) Release : Remove edge p i R j
8 .Operating Systems 8 System Model: State Transitions Resource graph represents current state of the system (snapshot) Every request, acquisition, and release moves the system from one state to another
9 .Operating Systems 9 System Model – more definitions A process is blocked in state S if it cannot request, acquire, or release any resource. A process is deadlocked in state S if it is currently blocked now and remains blocked in all states reachable from state S A state is a deadlock state if it contains a deadlocked process. State S is a safe state if no deadlock state can be reached from S by any sequence of request, acquire, release operations.
10 .Operating Systems 10 Example Assume: 2 processes p 1 , p 2 ; 2 resources R 1 , R 2 , p 1 and p 2 both need R 1 and R 2 p 1 always requests R 1 first, p 2 always requests R 2 first Consider transition by p 1 only
11 .Operating Systems 11 Example p 1 and p 2 both need R 1 and R 2 p 1 requests R 1 before R 2 releases R 2 before R 1 p 2 requests R 2 before R 1 releases R 1 before R 2 consider all possible transitions
12 .Operating Systems 12 Deadlock Detection Graph Reduction : Repeat the following Select unblocked process p Remove p and all request and allocation edges Deadlock Graph not completely reducible . All reduction sequences lead to the same result.
13 .Operating Systems 13 Special Cases of Detection Testing for whether a specific process p is deadlocked: Reduce until p is removed or graph irreducible Continuous detection: Current state not deadlocked Next state T deadlocked only if: Operation was a request by p and p is deadlocked in T Try to reduce T by p
14 .Operating Systems 14 Special Cases of Detection Immediate allocations All satisfiable requests are granted immediately Expedient state : state with no satisfiable request edges If all requests are granted immediately, all states are expedient. Example: not expedient (p1->R1)
15 .Operating Systems 15 Special Cases of Detection Immediate allocations (continued) Knot in expedient state Deadlock Knot : A set K of nodes such that Every node in K reachable from any other node in K No outgoing edges from any node in K Intuition: All processes in K must have outstanding requests Expedient state means requests not satisfiable Therefore all processes are blocked But condition is not sufficient for deadlock – not very useful
16 .Operating Systems 16 Special Cases of Detection For single-unit resources, cycle deadlock Intuition: Cycle: must alternate p and R nodes Every p i on cycle must have a request edge to R i Every R i must have an allocation edge to p i+1 no R is available (single unit) and thus all p’s are blocked
17 .Operating Systems 17 Recovery from Deadlock Process termination Kill all processes involved in deadlock; or Kill one at a time . In what order? b y priority: consistent with scheduling b y cost of restart: length of recomputation b y impact on other processes: CS, producer/consumer Resource preemption Direct: Temporarily remove resource (e.g., Memory) Indirect: Rollback to earlier “checkpoint”
18 .Operating Systems 18 Dynamic Deadlock Avoidance Process indicates maximum resources needed Potential request edge p i R j (dashed) May turn into real request edge Maximum Claim Graph
19 .Operating Systems 19 Dynamic Deadlock Avoidance Theorem: Prevent acquisitions that do not produce a completely reducible graph All state are safe . Banker’s algorithm ( Dijkstra ): Given a satisfiable request, p R , tentatively grant request, changing p R to R p Try to reduce new claim graph If completely reducible proceed . If not, reverse acquisition R p back to p R
20 .Operating Systems 20 Example of banker’s algorithm Which requests for R1 can safely be granted? p1: grant , resulting claim graph is reducible ( p1,p3, p2) p2: do not grant, resulting claim graph is not reducible p3: grant , resulting claim graph is reducible (p3,p1/p2)
21 .Operating Systems 21 Dynamic Deadlock Avoidance Special Case: Single-unit resources Check for cycles after tentative acquisition Disallow if cycle is found, e.g., grant R1 to p2? If claim graph contains no undirected cycles, all states are safe (no directed cycle can ever be formed)
22 .Operating Systems 22 Deadlock Prevention Deadlock requires the following 3 conditions: Mutual exclusion : Resources not sharable Hold and wait: Process must be holding one resource while requesting another Circular wait: At least 2 processes must be blocked on each other
23 .Operating Systems 23 Deadlock Prevention Eliminate mutual exclusion Not possible in most cases Spooling makes I/O devices sharable Eliminate hold-and-wait Request all resources at once Release all resources before a new request Release all resources if current request blocks Eliminate circular wait Order all resources Process must request in ascending order
热门城市
