Deadlock Handling In DBMS

Deadlock Handling In DBMS

Definition of Deadlock

In a database, a deadlock is an unwanted situation in which two or more transactions are waiting indefinitely for one another to give up locks

Deadlock Prevention 

There are two approaches to deadlock prevention.

First approach, this approach ensures that no cyclic waits can occur by ordering the requests for locks, or requiring all locks to be acquired together.

In this each transaction locks all its data items before its begins execution. There are two disadvantages of this protocol :

  • It is often hard to predict, before the transaction begins, what data items need to be locked.
  • Data item utilization may be very low, since many of the data items may be locked but unused for a long time.

Second approach, this approach use preemption(temporarily interrupting) and transaction rollbacks.

In preemption, when a transaction T2 requests a lock that transaction T1 holds, the lock granted to T1 may be preempted by rolling back of T1 and granting of lock to T2. To control the preemption, we assign a unique timestamp to each transaction when it begins. The system uses these timestamps only to decide whether a transaction should wait or roll back. If a transaction is rolled-back, it retains its “old” timestamp when restarted.

Also Read: DCL Statements In DBMS

Deadlock Detection 

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. One node is created in the wait-for graph for each transaction that is currently executing. 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. When Tj releases the lock(s) on the items that Ti was waiting for, the directed edge is dropped from the wait-for graph. 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. 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.

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.

Deadlocks can be described precisely in terms of a directed graph called a wait-for-graph. This graph consists of a pair G = (V, E), where V is a set of vertices(or transactions) and E is set of edges

Invoking the deadlock detection algorithm

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?

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. In the worst case, we would invoke the detection algorithm every time a request for allocation could not be granted immediately.

Recovery from Deadlock

When a detection algorithm determines that a deadlock exists the system must recover from the deadlock. The most common solution is to roll back one or more transaction to break the deadlock. Three actions need to be taken :

  1. Selection of a Victim: we must determine which transactions to roll back to break the deadlock. We should roll back those transaction that will incur the minimum cost.
  2. Rollback: we must determine how far this transaction should be rolled back. The simplest way is total rollback i.e abort the transaction and then restart it. However, it is more effective to roll back the transaction only as far as necessary to break the deadlock.
  3. Starvation: It may happen that the some transaction is always picked up as a victim and they never able to complete its task thus there is a starvation. We must ensure that a transaction can be picked as a victim only finite number of times.

Deadlock Avoidance

Deadlock can be avoided if resources are allocated in such a way that it avoids the deadlock occurrence. There are two algorithms for deadlock avoidance.

  • Wait/Die
  • Wound/Wait

Here is the table representation of resource allocation for each algorithm. Both of these algorithms take process age into consideration while determining the best possible way of resource allocation for deadlock avoidance.

Wait/Die Wound/Wait
Older transaction needs a resource held by younger transaction Older process waits Younger process dies
Younger transaction needs a resource held by older transaction Younger process dies Younger process waits

 

Thank you so much for reading.

About Robin Steve

X_Skull-Bleed Is his favorite nickname. He is Gaming Addict wanted to beat Shroud and Ninja. Shares Knowledge by Writing Content For Friends. ;) Loves to read love stories.

View all posts by Robin Steve →

Leave a Reply

Your email address will not be published. Required fields are marked *