August 21, 2019 , , , , ,
  • If a system does not employ either a deadlock-prevention or a deadlock-avoidance algorithm, then a deadlock situation may occur. In this environment, the system must provide:
  • An algorithm that examines the state of the system to determine whether a deadlock has occurred.
  • An algorithm to recover from the deadlock.

Algorithm for detecting deadlock:
  1. For each node, N in the graph, perform the following five steps with N as the starting node.
  2. Initialize L to the empty list, designate all arcs as unmarked.
  3. Add current node to end of L, check to see if node now appears in L two times. If it does, graph contains a cycle (listed in L), algorithm terminates.
  4. From given node, see if any unmarked outgoing arcs. If so, go to step 5; if not, go to step 6.
  5. Pick an unmarked outgoing arc at random and mark it. Then follow it to the new current node and go to step 3.
  6. If this is initial node, graph does not contain any cycles, algorithm terminates. Otherwise, dead end. Remove it, go back to previous node, make that one current node, go to step 3.

Recovery From Deadlock
When a detection algorithm determines that a deadlock exists, there are two options for breaking a deadlock. One solution is simply to abort one or more processes  to break the circular wait. The second option is to preempt some resources from one or more of the deadlocked processes.

Process Termination: To eliminate deadlocks by aborting a process, we use one of two methods. In both methods, the system reclaims all resources allocated to the terminated processes.


  • Abort all deadlocked processes
  • Abort one process at a time until the deadlock cycle is eliminated –overhead, a deadlock-detection after terminating a process


Resource Preemption: To eliminate deadlocks using resource preemption, we successively preempt some resources from processes and give these resources to other processes until the deadlock cycle is broken. Some issues need to be addressed are:

  • Selecting a victim: Some process will have to rolled back to break deadlock.  Select that process as victim that will incur minimum cost.
  • Rollback: Determine how far to roll back the process
Total rollback: Abort the process and then restart it. More effective is to roll back the process only as far as necessary to break deadlock

Starvation: Starvation happens if same process is always chosen as victim. To avoid this, we include the number of rollbacks in the cost factor.