Transcript Deadlocks
Course Overview Principles of Operating Systems Introduction Computer System Structures Operating System Structures Processes Process Synchronization Deadlocks CPU Scheduling © 2000 Franz Kurfess Memory Management Virtual Memory File Management Security Networking Distributed Systems Case Studies Conclusions Deadlocks 1 Chapter Overview Deadlock and Starvation Motivation Objectives Deadlock Principles Starvation Deadlock Conditions Mutual Exclusion Hold and Wait No Preemption Circular Wait © 2000 Franz Kurfess Dealing with Deadlock Deadlock Prevention Deadlock Avoidance Deadlock Detection and Recovery Deadlock and Operating Systems Important Concepts and Terms Chapter Summary Deadlocks 2 Motivation there is the potential of conflicts for processes who cooperate or share resources deadlock and starvation are the most severe conflicts, leading to the permanent halting of the processes affected common practice is not satisfactory ad hoc solutions neglecting the problem © 2000 Franz Kurfess Deadlocks 3 Objectives recognize potential problems with the coordination of activities for several processes (cooperation or resource sharing) understand the necessary conditions for a formal deadlock situation distinguish deadlocks from other reasons for “frozen” systems analyze the status of a system based on resource allocation graphs apply deadlock prevention, avoidance, and detection principles and algorithms to sets of processes © 2000 Franz Kurfess Deadlocks 4 “Deadlocked” Systems term “deadlock” is often used casually to indicate that the computer system doesn’t respond (it is “frozen”) there are other reasons for a system to be in such a state the endless loop waiting for an event that may never occur synchronization between processes deadlock needs to be defined carefully to distinguish it from these other reasons © 2000 Franz Kurfess Deadlocks 5 Deadlock Principles permanent mutual blocking of a set of resources that either compete for resources or cooperate on a task deadlocked processes don’t make any progress, and never finish their execution deadlocked processes may tie up system resources © 2000 Franz Kurfess Deadlocks 6 Starvation a process can’t proceed because other processes always have the resources it needs the request of the process is never satisfied in principle, it is possible to get the resource, but doesn’t happen because of low priority of the process timing of resource requests ill-designed resource allocation or scheduling algorithm different © 2000 Franz Kurfess from deadlock Deadlocks 7 Examples Starvation batch processes with low priority in a heavily used time-sharing system crossing a very busy road trying to call a very popular phone number NJIT modem pool radio station giveaways getting into a very popular course with limited enrollment © 2000 Franz Kurfess Deadlocks 8 Solution Starvation fairness: each process gets its fair share of all resources it requests how is fair defined? how is it enforced? aging the priority of a request is increased the longer the process waits for it © 2000 Franz Kurfess Deadlocks 9 Resource Types reusable resources can be used repeatedly by different processes does not imply simultaneous use OS examples: CPU, main memory, I/O devices, data structures consumable resources are produced by one entity, and consumed by another reuse is not possible, or impractical OS examples: messages © 2000 Franz Kurfess Deadlocks 10 Example Reusable Resources main memory allocation two processes make successive requests for main memory the overall memory size is 16 MByte Process A request 5 MBytes; request 8 MBytes; Process B request 7 MBytes; request 7 MBytes; deadlock no process can proceed unless one gives up some memory (preemption) frequent solutions: preallocation, virtual memory © 2000 Franz Kurfess Deadlocks 11 Example Consumable Resources message passing two processes wait for a message from each other, and then send one to each other receive operation is blocking (process can’t continue) Process A receive (B); send (B); Process B receive (A); send(A); deadlock no process can proceed because it is waiting for a message from the other no easy solution © 2000 Franz Kurfess Deadlocks 12 Deadlock on Resources usually based on design or programming errors these errors may be difficult or impossible to avoid interaction between different modules interaction between independent programs very difficult to detect may not occur during testing may occur very infrequently in the field © 2000 Franz Kurfess Deadlocks 13 Resource Allocation Graphs processes hold, request and release resources resources resource types specify a class of resources individual instances are identical from the process’ perspective resource assignment an instance of a resource is currently held by a process indicated by an assignment edge resource request a process wants to acquire another instance of a resource indicated by a request edge © 2000 Franz Kurfess Deadlocks 14 Resource Allocation Graphs R1 R2 R3 Assignment Edge P1 P2 P3 P4 P5 Request Edge R4 © 2000 Franz Kurfess R5 R6 R7 Deadlocks 15 Resource Allocation Graph with Cycle R1 P1 P1 -> R1 -> P2 -> R1, P1 -> R1 -> P2 -> R3 -> P1 P2 R2 © 2000 Franz Kurfess there is at least one cycle in the graph processes and resources involved e.g. R3 is there a deadlock? no, we have enough resources to satisfy all requests Deadlocks 16 Resource Allocation Graph with Deadlock R1 P1 R2 P2 R3 there must be at least one cycle in the graph cycles are candidates for deadlock is there a deadlock? yes, there are not enough resources in R2 to satisfy all requests by P1 and P2 processes and resources involved © 2000 Franz Kurfess P1 -> R2 -> P2 -> R2 Deadlocks 17 Cycles and Deadlocks if there is a cycle in the resource allocation graph, there may be a deadlock cycles a without deadlock are possible deadlock can only occur if there is a cycle no deadlock without a cycle © 2000 Franz Kurfess Deadlocks 18 Safe States a system is in a safe state if resources can be allocated to processes without getting into a deadlock the order in which resources are allocated must be flexible a sequence of processes is a safe sequence if the resources that a process may request are satisfiable by the currently available resources plus resources held by other processes this must hold for all processes in the system the process may have to wait until other processes are finished © 2000 Franz Kurfess Deadlocks 19 Safe State Space if a system is in a safe state there are no deadlocks in an unsafe state, there is a possibility of deadlocks Deadlock unsafe safe © 2000 Franz Kurfess Deadlocks 20 Dining Philosophers, Again var chopstick: array [0..4] of semaphore; repeat wait(chopstick[i]); wait(chopstick[i + 1 mod 5]); ... -- eat ... signal(chopstick[i]); signal(chopstick[i + 1 mod 5]); ... -- think ... until false; R4 R0 P4 P1 R1 R3 P3 © 2000 Franz Kurfess P0 R2 P2 Deadlocks 21 Why Deadlock? reasons for potential deadlock mutual exclusion two philosophers cannot use a chopstick simultaneously use a protocol that prevents philosophers from picking up their chopsticks simultaneously picking up one chopstick if the other is not available supervisor an authority that can tell philosophers what to do may use preemption of resources seating philosopher arrangement don’t seat philosophers around a round table may require more n+1 chopsticks for n philosophers several conditions must hold simultaneously © 2000 Franz Kurfess Deadlocks 22 Conditions for Deadlock all four conditions must hold simultaneously mutual exclusion hold and wait no preemption circular wait the term deadlock is often used sloppily in situations that don’t constitute a formal deadlock as described above © 2000 Franz Kurfess Deadlocks 23 Mutual Exclusion only one process can hold a resource at one point at least one resource may be used in a mutually exclusive way only requests by other processes are delayed usually determined by the needs of the resource, not under the control of the OS examples: CPU, printer, write on files © 2000 Franz Kurfess Deadlocks 24 Hold and Wait one process holds a resource and waits to acquire other resources currently held by other processes the processes doesn’t release its current resources may be necessary, or a consequence of bad program design examples: memory segments, I/O devices, chopsticks © 2000 Franz Kurfess Deadlocks 25 No Preemption a resource is released by a process only voluntarily no intervention by the OS or other processes examples: “cooperative multitasking” (MacOS) © 2000 Franz Kurfess Deadlocks 26 Circular Wait each process holds at least one resources needed by another process the set of processes together with the request and hold links forms a cycle there must be a set of processes P0, P1, ..., PN such that Pi is waiting on Pi+1 and PN is waiting on P0 examples: © 2000 Franz Kurfess dining philosophers, memory requests Deadlocks 27 Deadlock Examples examples studying students traffic intersection narrow tunnel single-track railroad airline reservation system evaluation four conditions: mutual exclusion, hold and wait, no preemption, circular wait © 2000 Franz Kurfess Deadlocks 28 Studying Students studying students: both students need the textbook and the course notes to study, but there is only one copy of each consider the following situation: Student A get coursenotes get textbook study release textbook release coursenotes © 2000 Franz Kurfess Student B get textbook get coursenotes study release coursenotes release textbook Deadlocks 29 Students Evaluation mutual exclusion books and course notes can be used only by one student hold and wait a student who has the book waits for the course notes, or vice versa no preemption there is no authority to take away book or course notes from a student circular wait student A waits for resources held by student B, who waits for resources held by A © 2000 Franz Kurfess Deadlocks 30 Traffic Intersection at a four-way intersection, four cars arrive simultaneously if all proceed, they will be stuck in the middle © 2000 Franz Kurfess Deadlocks 31 Traffic Evaluation mutual cars exclusion can’t pass each other in the intersection hold and wait vehicles proceed to the center, and wait for their path to be clear no preemption there circular is no authority to remove some vehicles wait vehicle 1 waits for vehicle 2 to move, which waits for 3, which waits for 4, which waits for 1 © 2000 Franz Kurfess Deadlocks 32 Narrow Tunnel in a narrow tunnel, there is enough room for most vehicles to pass each other if two large trucks arrive simultaneously, they won’t be able to pass each other © 2000 Franz Kurfess Deadlocks 33 Tunnel Evaluation mutual exclusion trucks can’t pass each other in the tunnel hold and wait trucks occupy part of the tunnel and wait for their path to become clear no preemption there is no authority to remove the trucks circular truck wait 1 waits for truck 2 to move, which waits for 1 © 2000 Franz Kurfess Deadlocks 34 Single-Track Railroad two trains arrive from different directions on a singletrack section railroad evaluation mutual exclusion trains can’t pass each other on the single track hold and wait no trains occupy part of the track and wait for their path to become clear preemption there is no authority to remove the trains circular wait train 1 waits for train 2 to move, which waits for 1 © 2000 Franz Kurfess Deadlocks 35 Airline Reservation System two agents book flights in from EWR to FRA to MUC agent A books flights EWR to FRA first agent B books FRA to MUC first flight records are locked during booking Agent A lock EWR-FRA lock FRA-MUC -- finalize booking release FRA-MUC release EWR-FRA © 2000 Franz Kurfess Agent B lock FRA-MUC lock EWR-FRA -- finalize booking release EWR-FRA release FRA-MUC Deadlocks 36 Reservation Evaluation mutual flight exclusion records are locked hold and wait one agent locks one segment and waits for the other to become available no preemption there circular agent is no authority to remove the locks held by an agent wait A waits for agent B to unlock a segment, who waits for A © 2000 Franz Kurfess Deadlocks 37 Dealing with Deadlocks protocol have strict rules that prevent a deadlock from occurring recover allow the system to enter a deadlock there must be a way to recover from the deadlock situation ignoring the deadlock frequently used in operating systems Windows, MacOS, Unix, ... © 2000 Franz Kurfess Deadlocks 38 Dealing with Deadlocks deadlock based on protocols deadlock check avoidance for safe state deadlock run prevention detection and recovery into a deadlock, detect it, and recover © 2000 Franz Kurfess Deadlocks 39 Deadlock Prevention set of rules ensures that at least one of the four necessary conditions for deadlock doesn’t hold mutual exclusion hold and wait no preemption circular wait may result in low resource utilization, reduced system throughput example: traffic lights, no trucks in the narrow tunnel © 2000 Franz Kurfess Deadlocks 40 Denying Mutual Exclusion if all resources were sharable there would not be any deadlock some resources can be made sharable for example, spooling printer output some e.g. resources are intrinsically non-sharable CPU (at the instruction time scale) © 2000 Franz Kurfess Deadlocks 41 Denying Hold And Wait prevent processes that hold resources from waiting for more resources processes request and are allocated all their resources before they start executing low resource utilization rate processes can request resources only if they have none indefinite postponement © 2000 Franz Kurfess Deadlocks 42 Denying No Preemption means that processes may be preempted by the OS should only done when necessary resources of a process trying to acquire another unavailable resource may be preempted preempt resources of processes waiting for additional resources, and give some to the requesting process possible only for some types of resources state must be easily restorable e.g. CPU, memory frequently © 2000 Franz Kurfess used when applicable Deadlocks 43 Denying Circular Wait break the cycle of waiting processes impose a total ordering of all resource types resources may only requested in increasing order of enumeration no process can request a resource with a lower number than what it is already holding ordering © 2000 Franz Kurfess should take typical order of usage into account Deadlocks 44 Safe Philosophers solution based on monitors deadlock prevention is used by designing the program with certain restrictions basic idea a philosopher picks up a chopstick only if the other one is available as well philosophers inform each other when they are done © 2000 Franz Kurfess Deadlocks 45 Philosophers with Monitors type dining-philosophers = monitor var state: array [0..4] of (thinking, hungry, eating); var self: array [0..4] of condition; procedure entry pickup(i: 0..4); begin state[i] := hungry; test(i); if state[i] <> eating then self[i].wait; end; procedure entry putdown(i: 0..4); begin state[i] := thinking; test(i-1 mod 5); test(i+1 mod 5); end; © 2000 Franz Kurfess [Silberschatz & Galvin, 1998] Deadlocks 46 Philosophers with Monitors (cont.) procedure test(k: 0..4); begin if (state[k-1] mod 5 <> eating and state[k] = hungry and state[k+1] mod 5 <> eating) then begin state[k] := eating; self[k].signal; end; end; begin for i := 0 to 4 do state[i] := thinking; end; © 2000 Franz Kurfess [Silberschatz & Galvin, 1998] Deadlocks 47 Deadlock Avoidance makes sure the system stays in a safe state if a request is satisfied prevents circular waits requires additional information at the beginning of the execution of a process maximum number of instances per resource type for each process © 2000 Franz Kurfess Deadlocks 48 Safe State A system is in a safe state when given the current allocation the system is able to handle any number of requests, in some order, without getting into a deadlock. © 2000 Franz Kurfess Deadlocks 49 Example Bank gives loans to customers maximum allocation = credit limit BANK $10 A B C $5 $7 $3 © 2000 Franz Kurfess Maximum Allocation Deadlocks 50 Safe State? Will the bank be able to give each customer a loan up to the full credit limit? not necessarily all customers simultaneously order is not important customers will pay back their loan once their credit limit is reached BANK $2 Current Allocation A $3 $5 © 2000 Franz Kurfess B $4 $7 Maximum Allocation C $1 $3 Deadlocks 51 Still Safe? after customer B requests and is granted $1, is the bank still safe? BANK $1 Current Allocation A $3 $5 B $5 $7 C $1 $3 Maximum Allocation © 2000 Franz Kurfess Deadlocks 52 Safe State Space Safe unsafe deadlock © 2000 Franz Kurfess Deadlocks 53 Bank Safe State Space unsafe Safe (3,4,1) x (3,5,1) x deadlock © 2000 Franz Kurfess Deadlocks 54 Banker’s Algorithm before a request is granted, check the system’s state assume the request is granted if it is still safe, the request can be honored otherwise the process has to wait overly careful there are cases when the system is unsafe, but not in a deadlock © 2000 Franz Kurfess Deadlocks 55 Example Banker’s Algorithm initially given: current allocation, maximum allocation, available resources Process P0 P1 P2 P3 P4 © 2000 Franz Kurfess Current Allocation A B C D E 1 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 1 1 1 1 0 0 1 0 0 Maximum Allocation A B C D E 2 0 2 1 3 1 2 1 2 2 2 1 3 1 2 0 1 2 1 2 1 1 1 2 2 Available A B C D E 1 0 1 0 1 Deadlocks 56 needed allocation is calculated by subtracting the current allocation from the maximum allocation Process P0 P1 P2 P3 P4 Current Allocation A B C D E 1 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 1 1 1 1 0 0 1 0 0 Needed Allocation A B C D E 1 0 1 1 3 0 1 1 1 2 2 1 3 1 1 0 0 1 0 1 1 1 0 2 2 Available A B C D E 1 0 1 0 1 1 1 2 1 2 <P3> © 2000 Franz Kurfess Deadlocks 57 available resources are increased because processes that are finished return their resources Process P0 P1 P2 P3 P4 Current Allocation A B C D E 1 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 1 1 1 1 0 0 1 0 0 Needed Allocation A B C D E 1 0 1 1 3 0 1 1 1 2 2 1 3 1 1 0 0 1 0 1 1 1 0 2 2 Available A B C D E 1 0 1 0 1 1 1 2 1 2 2 2 2 2 2 <P3, P1> © 2000 Franz Kurfess Deadlocks 58 Process P0 P1 P2 P3 P4 Current Allocation A B C D E 1 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 1 1 1 1 0 0 1 0 0 Needed Allocation A B C D E 1 0 1 1 3 0 1 1 1 2 2 1 3 1 1 0 0 1 0 1 1 1 0 2 2 Available A B C D E 1 0 1 0 1 1 1 2 1 2 2 2 2 2 2 2 2 3 2 2 <P3, P1, P4> © 2000 Franz Kurfess Deadlocks 59 Process P0 P1 P2 P3 P4 Current Allocation A B C D E 1 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 1 1 1 1 0 0 1 0 0 Needed Allocation A B C D E 1 0 1 1 3 0 1 1 1 2 2 1 3 1 1 0 0 1 0 1 1 1 0 2 2 Available A B C D E 1 0 1 0 1 1 1 2 1 2 2 2 2 2 2 2 2 3 2 2 2 2 3 2 3 <P3, P1, P4, P2> © 2000 Franz Kurfess Deadlocks 60 if there is a sequence in which all processes get their needed allocation, the system is in a safe state Process P0 P1 P2 P3 P4 Current Allocation A B C D E 1 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 1 1 1 1 0 0 1 0 0 Needed Allocation A B C D E 1 0 1 1 3 0 1 1 1 2 2 1 3 1 1 0 0 1 0 1 1 1 0 2 2 Available A B C D E 1 0 1 0 1 1 1 2 1 2 2 2 2 2 2 2 2 3 2 2 2 2 3 2 3 3 2 4 2 3 <P3, P1, P4, P2, P0> © 2000 Franz Kurfess Deadlocks 61 What if P0 requests and is granted one instance of resource A? adjust current and needed allocation, available resources Process P0 P1 P2 P3 P4 © 2000 Franz Kurfess Current Allocation A B C D E 2 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 1 1 1 1 0 0 1 0 0 Needed Allocation A B C D E 0 0 1 1 3 0 1 1 1 2 2 1 3 1 1 0 0 1 0 1 1 1 0 2 2 Available A B C D E 0 0 1 0 1 Deadlocks 62 Process P0 P1 P2 P3 P4 Current Allocation A B C D E 2 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 1 1 1 1 0 0 1 0 0 Needed Allocation A B C D E 0 0 1 1 3 0 1 1 1 2 2 1 3 1 1 0 0 1 0 1 1 1 0 2 2 Available A B C D E 0 0 1 0 1 0 1 2 1 2 <P3> © 2000 Franz Kurfess Deadlocks 63 Process P0 P1 P2 P3 P4 Current Allocation A B C D E 2 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 1 1 1 1 0 0 1 0 0 Needed Allocation A B C D E 0 0 1 1 3 0 1 1 1 2 2 1 3 1 1 0 0 1 0 1 1 1 0 2 2 Available A B C D E 0 0 1 0 1 0 1 2 1 2 1 2 2 2 2 <P3, P1> © 2000 Franz Kurfess Deadlocks 64 Process P0 P1 P2 P3 P4 Current Allocation A B C D E 2 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 1 1 1 1 0 0 1 0 0 Needed Allocation A B C D E 0 0 1 1 3 0 1 1 1 2 2 1 3 1 1 0 0 1 0 1 1 1 0 2 2 Available A B C D E 0 0 1 0 1 0 1 2 1 2 1 2 2 2 2 1 2 3 2 2 <P3, P1, P4> © 2000 Franz Kurfess Deadlocks 65 Process P0 P1 P2 P3 P4 Current Allocation A B C D E 2 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 1 1 1 1 0 0 1 0 0 Needed Allocation A B C D E 0 0 1 1 3 0 1 1 1 2 2 1 3 1 1 0 0 1 0 1 1 1 0 2 2 <P3, P1, P4> © 2000 Franz Kurfess Available A B C D E 0 0 1 0 1 0 1 2 1 2 1 2 2 2 2 1 2 3 2 2 Conflict! Deadlocks 66 Example 1 Banker’s Algorithm initially given: current allocation, maximum allocation, available resources Process P0 P1 P2 P3 P4 P5 © 2000 Franz Kurfess Current Allocation AB C D 0 2 0 1 1 1 3 0 0 0 1 0 1 2 0 1 0 0 0 0 1 1 1 1 Maximum Allocation A B C D 1 2 0 1 1 2 3 2 0 0 3 0 2 3 0 1 0 0 0 1 3 3 4 1 Available A B C D 1 0 0 1 Deadlocks 67 Ex. 1 Resource Allocation Graph B B A Assignment Edge P0 P1 P2 P3 P4 P5 Request Edge C © 2000 Franz Kurfess D Deadlocks 68 Example 1 (cont.) needed allocation is calculated by subtracting the current allocation from the maximum allocation all calculations are done for each element of the vector Process P0 P1 P2 P3 P4 P5 © 2000 Franz Kurfess Current Allocation AB C D 0 2 0 1 1 1 3 0 0 0 1 0 1 2 0 1 0 0 0 0 1 1 1 1 Needed Allocation A B C D 1 0 0 0 0 1 0 2 0 0 2 0 1 1 0 0 0 0 0 1 2 2 3 0 Available A B C D 1 0 0 1 Deadlocks 69 Example 1 (cont.) select a process whose request (needed allocation) could be satisfied with the available resources there may be several candidates (e.g. P0, P4) Process P0 P1 P2 P3 P4 P5 © 2000 Franz Kurfess Current Allocation AB C D 0 2 0 1 1 1 3 0 0 0 1 0 1 2 0 1 0 0 0 0 1 1 1 1 <P0> Needed Allocation A B C D 1 0 0 0 0 1 0 2 0 0 2 0 1 1 0 0 0 0 0 1 2 2 3 0 Available A B C D 1 0 0 1 Deadlocks 70 Example 1 (cont.) the resources held by this process are added to the available resources because processes that are finished return their resources Process P0 P1 P2 P3 P4 P5 Current Allocation AB C D 0 2 0 1 1 1 3 0 0 0 1 0 1 2 0 1 0 0 0 0 1 1 1 1 Needed Allocation A B C D 1 0 0 0 0 1 0 2 0 0 2 0 1 1 0 0 0 0 0 1 2 2 3 0 Available A B C D 1 0 0 1 1 2 0 2 <P0> © 2000 Franz Kurfess Deadlocks 71 Example 1 (cont.) the next process is selected the previous process is marked as already checked Process P0 P1 P2 P3 P4 P5 Current Allocation AB C D 0 2 0 1 1 1 3 0 0 0 1 0 1 2 0 1 0 0 0 0 1 1 1 1 Needed Allocation A B C D 1 0 0 0 0 1 0 2 0 0 2 0 1 1 0 0 0 0 0 1 2 2 3 0 Available A B C D 1 0 0 1 1 2 0 2 <P0, P3> © 2000 Franz Kurfess Deadlocks 72 Example 1 (cont.) and its resources are added to the available resources Process P0 P1 P2 P3 P4 P5 Current Allocation AB C D 0 2 0 1 1 1 3 0 0 0 1 0 1 2 0 1 0 0 0 0 1 1 1 1 Needed Allocation A B C D 1 0 0 0 0 1 0 2 0 0 2 0 1 1 0 0 0 0 0 1 2 2 3 0 Available A B C D 1 0 0 1 1 2 0 2 2 4 0 3 <P0, P3> © 2000 Franz Kurfess Deadlocks 73 Example 1 (cont.) the next process is selected, and its resources are added to the available resources Process P0 P1 P2 P3 P4 P5 Current Allocation AB C D 0 2 0 1 1 1 3 0 0 0 1 0 1 2 0 1 0 0 0 0 1 1 1 1 Needed Allocation A B C D 1 0 0 0 0 1 0 2 0 0 2 0 1 1 0 0 0 0 0 1 2 2 3 0 Available A B C D 1 0 0 1 1 2 0 2 2 4 0 3 3 5 3 3 <P0, P3, P1> © 2000 Franz Kurfess Deadlocks 74 Example 1 (cont.) the next process is selected, and its resources are added to the available resources Process P0 P1 P2 P3 P4 P5 Current Allocation AB C D 0 2 0 1 1 1 3 0 0 0 1 0 1 2 0 1 0 0 0 0 1 1 1 1 Needed Allocation A B C D 1 0 0 0 0 1 0 2 0 0 2 0 1 1 0 0 0 0 0 1 2 2 3 0 Available A B C D 1 0 0 1 1 2 0 2 2 4 0 3 3 5 3 3 3 5 4 3 <P0, P3, P1, P2> © 2000 Franz Kurfess Deadlocks 75 Example 1 (cont.) the next process is selected, and its resources are added to the available resources Process P0 P1 P2 P3 P4 P5 Current Allocation AB C D 0 2 0 1 1 1 3 0 0 0 1 0 1 2 0 1 0 0 0 0 1 1 1 1 Needed Allocation A B C D 1 0 0 0 0 1 0 2 0 0 2 0 1 1 0 0 0 0 0 1 2 2 3 0 Available A B C D 1 0 0 1 1 2 0 2 2 4 0 3 3 5 3 3 3 5 4 3 3 5 4 3 <P0, P3, P1, P2, P4> © 2000 Franz Kurfess Deadlocks 76 Example 1 (cont.) the last process (P5) is selected, and its resources are added to the available resources Process P0 P1 P2 P3 P4 P5 © 2000 Franz Kurfess Current Allocation AB C D 0 2 0 1 1 1 3 0 0 0 1 0 1 2 0 1 0 0 0 0 1 1 1 1 Needed Allocation A B C D 1 0 0 0 0 1 0 2 0 0 2 0 1 1 0 0 0 0 0 1 2 2 3 0 <P0, P3, P1, P2, P4, P5> Available A B C D 1 0 0 1 1 2 0 2 2 4 0 3 3 5 3 3 3 5 4 3 3 5 4 3 4 6 5 4 Deadlocks 77 Outcome Example 1 all processes have been checked successfully there is at least one sequence in which the requests of the processes can be satisfied safely the final value for the “available” vector indicates the total number of resources © 2000 Franz Kurfess Deadlocks 78 Example 2 Banker’s Algorithm slight modification of the previous example: holds 2 2 0 1 instead of 1 2 0 1 this changes Current Allocation, Needed Allocation, and Available Current Maximum Process Allocation Allocation Available AB C D A B C D A B C D P0 0 2 0 1 1 2 0 1 0 0 0 1 P1 1 1 3 0 1 2 3 2 P2 0 0 1 0 0 0 3 0 P3 2 2 0 1 2 3 0 1 P4 0 0 0 0 0 0 0 1 P5 1 1 1 1 3 3 4 1 P3 © 2000 Franz Kurfess Deadlocks 79 Ex. 2 Resource Allocation Graph B B A Assignment Edge P0 P1 P2 P3 P4 P5 Request Edge C © 2000 Franz Kurfess D Deadlocks 80 Example 2 (cont.) needed allocation is calculated by subtracting the current allocation from the maximum allocation all calculations are done for each element of the vector Process P0 P1 P2 P3 P4 P5 © 2000 Franz Kurfess Current Allocation AB C D 0 2 0 1 1 1 3 0 0 0 1 0 2 2 0 1 0 0 0 0 1 1 1 1 Needed Allocation A B C D 1 0 0 0 0 1 0 2 0 0 2 0 0 1 0 0 0 0 0 1 2 2 3 0 Available A B C D 0 0 0 1 Deadlocks 81 Example 2 (cont.) select a process whose request (needed allocation) could be satisfied with the available resources Process P0 P1 P2 P3 P4 P5 © 2000 Franz Kurfess Current Allocation AB C D 0 2 0 1 1 1 3 0 0 0 1 0 2 2 0 1 0 0 0 0 1 1 1 1 <P4> Needed Allocation A B C D 1 0 0 0 0 1 0 2 0 0 2 0 0 1 0 0 0 0 0 1 2 2 3 0 Available A B C D 0 0 0 1 Deadlocks 82 Example 2 (cont.) the resources held by this process are added to the available resources because processes that are finished return their resources Process P0 P1 P2 P3 P4 P5 Current Allocation AB C D 0 2 0 1 1 1 3 0 0 0 1 0 2 2 0 1 0 0 0 0 1 1 1 1 Needed Allocation A B C D 1 0 0 0 0 1 0 2 0 0 2 0 0 1 0 0 0 0 0 1 2 2 3 0 Available A B C D 0 0 0 1 0 0 0 1 <P4> © 2000 Franz Kurfess Deadlocks 83 Example 2 (cont.) the next process is selected the previous process is marked as already checked Process P0 P1 P2 P3 P4 P5 Current Allocation AB C D 0 2 0 1 1 1 3 0 0 0 1 0 2 2 0 1 0 0 0 0 1 1 1 1 Needed Allocation A B C D 1 0 0 0 0 1 0 2 0 0 2 0 0 1 0 0 0 0 0 1 2 2 3 0 <P4> © 2000 Franz Kurfess Available A B C D 0 0 0 1 0 0 0 1 Conflict! Deadlocks 84 Outcome Example 2 not all processes could be checked successfully there is no sequence in which the requests of the processes can be satisfied safely the system is in an unsafe state involving all processes except P4 © 2000 Franz Kurfess Deadlocks 85 Detection and Recovery the system must provide an algorithm to examine whether a deadlock has occurred recover from the deadlock requires run-time overhead due to maintaining information and executing a detection algorithm the potential losses inherent in recovery © 2000 Franz Kurfess Deadlocks 86 Detection: Single Instance all resource types have only one instance a cycle in the resource allocation graph means there is a deadlock a cycle detection algorithm requires an order of n2 operations for n nodes in the graph (processes + resources) © 2000 Franz Kurfess Deadlocks 87 Resource Allocation Graphs R1 R2 R3 Assignment Edge P1 P2 P3 P4 P5 Request Edge R4 © 2000 Franz Kurfess R5 R6 R7 Deadlocks 88 Detection: Multiple Instances there are several instances for each resource type an algorithm similar to deadlock avoidance (banker’s algorithm) is used to determine whether the system is deadlocked order of m * n2 operations (m = no. of resource types, n = no. of processes) requires how often the algorithm is invoked depends on the likelihood for deadlock to occur the number of processes affected by deadlock © 2000 Franz Kurfess Deadlocks 89 Recovery resume operation after a deadlock has been detected preemption rollback killing processes © 2000 Franz Kurfess Deadlocks 90 Ignoring the Problem simplest approach better performance and less restrictive system problem: possibility of occasional deadlocks example: Unix © 2000 Franz Kurfess Deadlocks 91 Deadlock in Operating Systems combined approach resources are partitioned into hierarchically ordered classes a resource-ordering technique is applied to the classes within each class, one particular approach to deadlocks can be used guarantees that a deadlock cannot involve more than one class, and the whole system is safe © 2000 Franz Kurfess Deadlocks 92 Example Combined Approach classes of resources system used by the OS user resources memory memory used by a user process process resources resources available to processes devices, files swap space space for processes on a background storage device © 2000 Franz Kurfess Deadlocks 93 Solution Combined Approach resource ordering between the four classes individual approaches within each class system prevention: resource ordering within the class user resources memory preemption: swap a process to secondary storage process deadlock avoidance: processes inform the OS in advance about resources to be requested swap resources space prevention: all required resources are allocated at the same time (preallocation) © 2000 Franz Kurfess Deadlocks 94 Important Concepts and Terms Banker’s algorithm circular wait condition deadlock deadlock avoidance deadlock detection deadlock prevention dining philosophers hold and wait condition instance monitor mutual exclusion condition © 2000 Franz Kurfess no preemption condition process preemption recovery resource resource allocation resource allocation graph resource type safe state starvation synchronization termination Deadlocks 95 Summary Deadlocks deadlock is a specific situation characterized by four criteria mutual exclusion, hold and wait, no preemption, circular wait it prevents affected processes from continuing their execution deadlock can be dealt with by prevention, avoidance, detection, or by ignoring the problem various algorithms based on resource allocation graphs e.g. banker’s algorithm © 2000 Franz Kurfess Deadlocks 96