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
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
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.
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 :
- 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.
- 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.
- 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 can be avoided if resources are allocated in such a way that it avoids the deadlock occurrence. There are two algorithms for deadlock avoidance.
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.
|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.