Lecture 13OutlineDeadlocks 1Deadlocks 2Deadlocks 3Deadlocks 4System ModelNecessary ConditionsResource Allocation Graph 1Resource Allocation Graph 2Resource Allocation Graph 3Resource Allocation Graph 4Resource Allocation Graph 5Resource Allocation Graph 6Resource Allocation Graph 7Handling Deadlocks 1Handling Deadlocks 2Prevention 1Prevention 2Prevention 3Prevention 4Prevention 5Prevention 6Wednesday, February 9 CS 470 Operating Systems - Lecture 13 1Lecture 13Reminder: Homework 3 due todayQuestions?Wednesday, February 9 CS 470 Operating Systems - Lecture 13 2OutlineDeadlocksNecessary conditionsResource allocation graphDeadlock preventionWednesday, February 9 CS 470 Operating Systems - Lecture 13 3DeadlocksIn considering concurrent processes, we have encountered several problems that have the possibility of deadlock.Some problems can prevent deadlock by the use of specific steps. E.g., Dining Philosophers problem.Generally, this is a hard problem, and we would like a general solution that can be applied to an entire system.Wednesday, February 9 CS 470 Operating Systems - Lecture 13 4DeadlocksFormally, deadlock is defined as a set of processes { P0, …, Pn } where each process is requesting a resource that is held by another process. For example, a one-lane bridge that can hold two cars as shown below:NW-slot E-slotWednesday, February 9 CS 470 Operating Systems - Lecture 13 5DeadlocksEastbound car:1. Request (W-slot)2. Use (W-slot)3. Request (E-slot)4. Release (W-slot)5. Use (E-slot)6. Release (E-slot)Westbound car:1. Request (E-slot)2. Use (E-slot)3. Request (W-slot)4. Release (E-slot)5. Use (W-slot)6. Release (W-slot)Call the two resources W-slot and E-slot. Each resource is requested, used, and released.Wednesday, February 9 CS 470 Operating Systems - Lecture 13 6DeadlocksClearly, a car going in each direction can "execute" steps 1 and 2 simultaneously. Each car is then holding the slot the other car is requesting, so both must wait.What can we do to "fix" this situation?Wednesday, February 9 CS 470 Operating Systems - Lecture 13 7System ModelSystem consists ofSet of resource types { R1, …, Rn } that may be physical (e.g., CPU, disk, memory, printer) or logical (e.g., file, data objects), where there may be more than one instance of each resource. E.g., 1 CPU, 3 disks, 2 printers.Set of processes { P1, …, Pn }Processes make requests for resources (and may have to wait), the system allocates the resources to the processes, and the processes release resources when they are done using them.Wednesday, February 9 CS 470 Operating Systems - Lecture 13 8Necessary ConditionsThere are four necessary conditions to have deadlock:Mutual exclusion - at least one of the resources must require exclusive access.Hold and wait (also called wait-for) - each process must request (and possibly wait for) a resource while holding another resource.Non-preemption - resources cannot be preempted cheaplyCircular wait - a cycle of hold and wait must exist.Apply these to the bridge exampleWednesday, February 9 CS 470 Operating Systems - Lecture 13 9Resource Allocation GraphCan describe the wait-for relationship pictorially using a resource allocation graph.Vertices: set of processes { P0, …, Pn }, set of resource types { R0, …, Rn }. In addition, indicate the number of instances of each resource in parentheses.Edges: PiRj means that process Pi requests resource Rj, RjPi means that resource Rj is held by process Pi.Wednesday, February 9 CS 470 Operating Systems - Lecture 13 10Resource Allocation GraphFor example, P = { P1, P2, P3, P4 }, indicated by circles. R = { R1(1), R2(2), R3(1), R4(3) }, indicated by rectangles with dots for each instance. E = { P1R1, P2R3, R1P2, R2P2, R2P1, R3P3 }.P1P2P3P4R1R3R2R4held-by edgerequest edgeWednesday, February 9 CS 470 Operating Systems - Lecture 13 11Resource Allocation GraphWhen a request is made, a request edge is added to the graph. If it can be fulfilled immediately, it is transformed into a held-by edge (i.e., reverse direction of edge).When a release happens, the held-by edge is removed, and the graph checked to see if any request edges can be satisfied.Wednesday, February 9 CS 470 Operating Systems - Lecture 13 12Resource Allocation GraphFor any resource allocation graph, it can be shown that, if the graph contains no cycles, then no process in the system is deadlocked.If the graph does contain a cycle, then a deadlock may exist. If there is only one instance of each resource type, then a deadlock has occurred. I.e., in this case a cycle is a necessary and sufficient condition to determine deadlock.Wednesday, February 9 CS 470 Operating Systems - Lecture 13 13Resource Allocation GraphIf some resource types have several instances, then a cycle does not necessarily imply a deadlock has occurred. That is, a cycle is a necessary, but not a sufficient condition for a deadlock in those scenarios.For example, suppose P3 requests an instance of R2. Since there are no available instances, a request edge P3R2 is added to the graph as shown on the next slide.Wednesday, February 9 CS 470 Operating Systems - Lecture 13 14Resource Allocation GraphThere are now two minimal cyclesP1R1P2R3P3R2P1P2R3P3R2P2 All three processes are in deadlock. None holding can finish to release a resource.P1P2P3P4R1R3R2R4new request edgeWednesday, February 9 CS 470 Operating Systems - Lecture 13 15Resource Allocation GraphIf the second instance of R2 was held by P4 instead of P2, there would still be a cycle:P1R1P3R2P1But this time there is no deadlock, since P4 can finish and release R2 for P3 to use.P1P2P3P4R1R3R2R4new request edgeWednesday, February 9 CS 470 Operating Systems - Lecture 13 16Handling DeadlocksAs noted with the bridge example, there are different ways to handle deadlock:Prevention: define how requests are granted using fixed rules so that deadlock can never happenAvoidance: deadlock never happens in these schemes, too, but the determination of whether to grant a request is made at run-time and depends on the state of the systemDetect and recover: allow deadlock to happen, take steps to recoverWednesday, February 9 CS 470 Operating Systems - Lecture 13 17Handling DeadlocksOf course, can always ignore the problem and pretend it never