Detection and recoveryDeadlock Humor 2Two drivers were approaching a one-lane bridge. They reached the middle of the bridge at the same time, forcing a confrontation. They got out of their cars and went nose to nose. One driver said, “I don’t back up for idiots.” The other driver calmly got back in his car and started backing up. He said, “No problem --- I do.” (Deitel et al)Moral of the story: Processes are neither stubborn nor co-operative, so deadlock is a painful experience at best. Usually, one or more processes will have to be “backed out” of the deadlock, losing some or all of their work.Deadlock Permanent blocking of a set of processes that either  compete for system resources or communicate with each other Involve conflicting needs for resources by two or more processes No efficient solution3Necessary conditions for deadlock  Mutual exclusion Only one process may use a resource at a time Hold-and-wait A process holding one resource is waiting to acquire additional resources held by other processes  No preemption No resource can be forcibly removed form a process holding it4Deadlocked condition Circular wait There exists a permanent, circular sequence of processes such that each process is waiting for a resource held by the preceding process5Resource-Allocation Graph (RAG) A set of Vertices V and a set of Edges E V is partitioned into two types: P = {P1, P2, …, Pn}, the set consisting of all the processes in the system. R = {R1, R2, …, Rm}, the set consisting of all resource types in the system. request edge – directed edge Pi Rj assignment edge – directed edge RjPi6RAG example with a deadlock7Basic facts If graph contains no cycles  no deadlock. If graph contains a cycle  if only one instance per resource type, then deadlock. if several instances per resource type, possibility of deadlock.8Approaches to deadlock handling Ignore Deadlock (Ostrich approach) If infrequent enough and result is not serious Used by most operating systems, including UNIX Deadlock Prevention Prevent one of the necessary/sufficient conditions Deadlock Avoidance Allow the 3 necessary conditions Dynamically make choices to avoid deadlock decide based on knowledge of future requests i.e., find a safe path9Approaches to deadlock handling Deadlock Detection and Recovery Periodically run algorithm to detect circular waiting After detecting deadlock, run a recovery algorithm to remove deadlock10Deadlock detection and recovery Allow system to enter deadlock state  Detection algorithm Recovery scheme11Q1Deadlock detection algorithm Determine if all requests can be satisfied eventually  Simulate  granting of resources to processes and  returning of those resources when processes complete Mark processes that can complete  These are NOT deadlocked A deadlock exists if and only if there are unmarked processes at the end of the algorithm These ARE deadlocked processes12Q2Comments Algorithm does not guarantee that deadlock will not occur  depends on order in which requests are granted Just determines if deadlock currently exists13Q3Deadlock detection algorithm Process i requests req[i, *] additional resources14Avail_tmp[*] = Avail[*];Rest = . . . Set of all processes with Alloc[i,*] != 0 . . .safePath = True;while (safePath) {// find a process whose request can be satisfiedif (there exists a process i such that req[i, *] <= Avail_tmp[*]) {// simulate process i completingAvail_tmp[*] = Avail_tmp[*] + Alloc[i,*];Rest = Rest – { Pi};} elsesafePath = False;}. . . Each process in Rest is deadlocked . . .Example of detection algorithm Five processes P0through P4 three resource types A (7), B (2), and C (6). Snapshot at time T0:Allocation Request AvailableA B C A B C A B CP00 1 0 0 0 0 0 0 0P12 0 0 2 0 2P23 0 3 0 0 0P3 2 1 1 1 0 0 P4 0 0 2 0 0 215Example continues … P2requests an additional instance of type C after P0completesAllocation RequestAvailableA B C A B C A B CP00 0 0 0 0 0 0 1 0P12 0 0 2 0 2P23 0 3 0 0 1 P3 2 1 1 1 0 0 P4 0 0 2 0 0 2 State of the system?16Q4Recovery from deadlock Kill deadlocked processes  Preempt resources from deadlocked processes Roll back each deadlocked process to some safe state and restart them  Widely used in current database systems. Danger of the same situation occurring again. 17Q5Recovery: Process Termination Abort all deadlocked processes Abort one process at a time until no deadlock In which order should we choose to abort? Priority of the process. How long process has computed, and how much longer to completion. Resources the process has used. Resources process needs to complete. How many processes will need to be terminated.  Is process interactive or batch?18Recovery: Resource Preemption Selecting a victim – minimize cost Rollback – return to some safe state, restart process from that state Starvation – same process may always be picked as victim  include number of rollback in cost factor19Deadlock handling: Combined Approach Combine the three basic approaches prevention avoidance detectionusing the optimal approach for each resource class in the system Partition resources into ordered classes Use most appropriate technique for handling deadlocks within each class20Deadlock should not be ignored A real-time control system monitoring a gasoline refinery  Need to ensures the safe and proper operation of the refinery An avoidance strategy or prevention strategy must be employed A computerized pacemaker  Can’t afford to miss a single beat Deadlock avoidance or prevention must be employed21Q6Deadlock should not be ignored Embedded systems – cell phones, PDAs.  These are SoCs or system on chips i.e. everything is on one chip and SoCs are characterized by a small set of resources and real-time processing constraints.  Can’t have a system administrator come in and decide which process to kill after deadlock has been detected.  Either a prevention or avoidance strategy must be employed.22Dining Philosopher Problem23 Five philosophers who alternately think and eat Share a fork with each neighbor Assume each philosopher picks up left fork, then right fork, then eats Deadlock if all are hungry at the same timeSolutions: Dining