Define deadlock detection and recovery

Mumbai University > Information Technology > Sem 3 > Database Management System

Marks: 10 M

Year: May 2014

1 Answer


System is deadlocked if there is a set of transactions such that every transaction in the set is waiting for another transaction in the set.

Deadlock Detection

  • If the deadlocks are not avoided then another approach is to detect them when they have occurred and recover from them.
  • The basic idea is to check allocation against availability for all possible allocation sequences to determine if the system is in deadlocked state.

Once detected there needs to be way to recover several alternatives exist:

  • Temporarily prevent resources from deadlocked processes
  • Back Off a process to some check point allowing preemption of a needed resource and restarting the process at the checkpoint later
  • Successively kill processes until the system is deadlock free.

Deadlocks can be described as a wait-for graph, which consists of a pair $G = (V,E)$,

  • V is a set of vertices (all the transactions in the system)
  • E is a set of edges; each element is an ordered pair $T_i→T_j.$
  • If $T_i →Tjis$ in $E$, then there is a directed edge from $T_i$ to $T_j$, implying that $T_i$ is waiting for $T_j$ to release a data item. - When $T_i$ requests a data item currently being held by $T_j$, then the edge $T_iT_j$ is inserted in the wait-for graph. This edge is removed only when $T_j$ is no longer holding a data item needed by $T_i$.
  • deadlock-detection algorithm periodically to look for cycles.

enter image description here

Deadlock Recovery

Deadlock recovery is generally used when deadlocks are rare and the cost of recovery is low.

Methods for Recovery

  1. Termination of processes
  • Some victim process is chosen for termination from the cycle of deadlocked processes.
  • This process is terminated, requiring a later restart
  • All the resources allocated to this processes are released, so that they may be reassigned to other deadlocked processes
  • With an appropriately chosen victim process, this should resolve the deadlock.
  1. Rolling back processes
  • In order to rollback a victim process, there needs to have been some previous checkpoint at which time the state of the victim process was saved to stable storage
  • There must also be an assurance that the rolled back process is not holding any resource needed by the other deadlocked processes at that point
  • With an appropriately chosen victim process, needed resources will be released and assigned to other deadlocked processes.
  • This resolves deadlock.
Please log in to add an answer.