• In a multi-process system, deadlock is an unwanted situation that arises in a shared resource environment, where a process indefinitely waits for a resource that is held by another process.
• For example, assume a set of transactions {T0, T1, T2, ...,Tn}. T0 needs a resource X to complete its task. Resource X is held by T1, and T1 is waiting for a resource Y, which is held by T2. T2 is waiting for resource Z, which is held by T0. Thus, all the processes wait for each other to release resources. In this situation, - - Deadlocks are not healthy for a system. In case a system is stuck in a deadlock, the transactions involved in the deadlock are either rolled back or restarted.

• Deadlock Detection

  i. A simple way to detect a state of deadlock is with the help of wait-for graph. This graph is constructed and maintained by the system.

  ii. One node is created in the wait-for graph for each transaction that is currently executing.

  iii. Whenever a transaction Ti is waiting to lock an item X that is currently locked by a transaction Tj, a directed edge (Ti->Tj).is created in the wait-for graph.

  iv. When Tj releases the lock(s) on the items that Ti was waiting for, the directed edge is dropped from the wait-for graph.

  v. We have a state of deadlock if and only if the wait-for graph has a cycle. Then each transaction involved in the cycle is said to be deadlocked.

  vi. To detect deadlocks, the system needs to maintain the wait for graph, and periodically to invoke an algorithm that searches for a cycle in the graph.

  vii. To illustrate these concepts, consider the following wait-for graph in figure. Here:

  • Transaction T25 is waiting for transactions T26 and T27.
  • Transactions T27 is waiting for transaction T26.
  • Transaction T26 is waiting for transaction T28.
  • This wait-for graph has no cycle, so there is no deadlock state.
  • Suppose now that transaction T28 is requesting an item held by T27.
  • Then the edge T28 ----------->T27 is added to the wait -for graph, resulting in a new system state as shown in figure.

  • This time the graph contains the cycle.

    T26------>T28------->T27----------->T26

  • It means that transactions T26, T27 and T28 are all deadlocked.

viii. The invoking of deadlock detection algorithm depends on two factors:

• How often does a deadlock occur?
• How many transactions will be affected by the deadlock?

ix. If deadlocks occur frequently, then the detection algorithm should be invoked more frequently than usual. Data items allocated to deadlocked transactions will be unavailable to other transactions until the deadlock can be broken.

x. In the worst case, we would invoke the detection algorithm every time a request for allocation could not be granted immediately.

Deadlock Prevention

i. To prevent any deadlock situation in the system, the DBMS aggressively inspects all the operations, where transactions are about to execute.

ii. The DBMS inspects the operations and analyzes if they can create a deadlock situation. If it finds that a deadlock situation might occur, then that transaction is never allowed to be executed.

iii. There are deadlock prevention schemes that use timestamp ordering mechanism of transactions in order to predetermine a deadlock situation.

iv. Wait-Die Scheme:-

In this scheme, if a transaction requests to lock a resource (data item), which is already held with a conflicting lock by another transaction, then one of the two possibilities may occur −

• If TS(Ti) < TS(Tj) − that is Ti, which is requesting a conflicting lock, is older than Tj − then Ti is allowed to wait until the data-item is available.
• If TS(Ti) > TS(tj) − that is Ti is younger than Tj − then Ti dies. Ti is restarted later with a random delay but with the same timestamp. This scheme allows the older transaction to wait but kills the younger one.

v. Wound-Wait Scheme:-In this scheme, if a transaction requests to lock a resource (data item), which is already held with conflicting lock by some another transaction, one of the two possibilities may occur −

• If TS(Ti) < TS(Tj), then Ti forces Tj to be rolled back − that is Ti wounds Tj. Tj is restarted later with a random delay but with the same timestamp.
• If TS(Ti) > TS(Tj), then Ti is forced to wait until the resource is available.

This scheme, allows the younger transaction to wait; but when an older transaction requests an item held by a younger one, the older transaction forces the younger one to abort and release the item. In both the cases, the transaction that enters the system at a later stage is aborted.