Process of recovery from deadlock in database

Recovery from Deadlock in Database:

How can we recover from deadlock? / Rollback in deadlock / Guidelines to choose deadlock victim

Refer here for Deadlock detection.

After detecting the deadlock, the next important step a system has to take is to recover the system from the deadlock state. This can be achieved through rolling back one or more transactions. But the difficult part is to choose one or more transactions as victims.

Recovery from deadlock can be done in three steps;

1. Selection of victim: Given a set of deadlocked transactions (transactions that formed cycles), we have to identify the transaction or transactions that are to be rolled-back for successful relief from deadlock state. This is done by identifying the transaction or transactions that are cost minimum. This would mean many things. The following guidelines would help us.

Guidelines to choose victim:

• The length of the transaction – We need to choose the transaction which is younger.

• The data items used by the transaction – The transactions that are used less number of data items.

• The data items that are to be locked – The transaction that needs to lock many more data items compared to that are already locked.

• How many transactions to be rolled back? – We need to choose transaction or transactions that would cause less number of other transactions to be rolled back (cascading rollback)

2. Rollback: Once we have identified the transaction or transactions that are to be rolled back, then rollback them. This can be done in two ways;

Full rollback – Simplest of two. Rollback the transaction up to its starting point. That is, abort the transaction and restart. It will also abort other transactions that have used the data item changed by the rolled back transaction.

Partial rollback – it might be the effective one, if the system maintains additional information like the order of lock requests, save points etc.

3. Starvation: We must be careful enough to avoid a transaction or transactions to be chosen repeatedly as victims.

Deadlock detection technique in Database

Deadlock detection technique in Database

How to detect deadlock in Oracle / Deadlock detection in database / What is deadlock in database / What is Wait-for graph / How to construct Wait-for graph / Deadlock detection with Wait-for graph

The other type of algorithm, other than Deadlock Prevention schemes, works by identifying the deadlock state if one occurred. For this we need the algorithm should be allowed to examine the system periodically to detect the deadlock if any. To make this idea works, we need some or all of the following;

• The allocation of available data items to individual transactions and the transactions that are in queue for some data items. This information can be taken from Lock Manager component of Database systems.

• An algorithm which can determine the state of the system, i.e, whether the system entered a deadlock state or not.

How do we get rid of the deadlock which has happened?

Deadlock detection can be done using the concept of directed graph called Wait-for graph. This graph consists of set of vertices (the set of transactions) and set of edges (the waiting state of one transaction for the data item held by other transaction).

• Set of vertices – the set of transactions currently going on in a Database system, like T1, T2, … Tn.

• Set of edges – the ordered pair of transactions represented like T_i → T_j. This means that the transaction T_i is waiting for a resource held by transaction T_j.

An example Wait-for-graph is given in Figure 1.

Figure 1 - Wait-for-graph with two transactions that are Deadlocked

How do we construct a Wait-for graph?

It is very simple. When a transaction T_i waits for other transaction T_j which currently holds the data item needed by Ti, we shall insert an edge Ti → Tj into the Wait-for graph.

Let us discuss with an example;

Assume that there are 4 transactions that are going on in a system at a particular point in time. Let us name the transactions as T1, T2, T3, and T4. The data items and the lock modes needed for the data items for all the transactions are given in table 1 below;

Transactions	Data items requested	Lock mode
T1	Q	Shared lock
T2	P Q	Exclusive lock Exclusive lock
T3	Q	Shared lock
T4	P	Exclusive lock

Table 1 - Some active Transactions

Stage 1: Assume that T1 has acquired lock on Q and being executed. The wait-for graph contains no edges. It contains only transaction T1 as given in the figure 2.

Figure 2 - Stage 1, T1 locked a data item Q

Stage 2: Now, transaction T2 started and requesting for the data items P and Q in write mode. The lock manager can grant lock on P, but cannot grant lock on Q as Q is already held by T1 and the held lock and requested lock are incompatible. At this stage, a new edge is inserted like T2 → T1 into the Wait-for graph and the graph looks like the figure 3 given below;

Figure 3 - Stage 2, edge (T2,T1) is inserted

Stage 3: Now, transaction T3 requests for data item Q. The lock manager can grant lock on Q to transaction T3. The reason is, T1 locked Q in read mode and T3 requests in read mode, and they are compatible. Hence, the lock is granted. So, no new edge is included in the Wait-for graph (Figure 4).

Figure 4 - At stage 3, no changes

Stage 4: Next, transaction T4 requests data item P in write mode. Again, P is held by T2 and in incompatible mode. So, the lock manager cannot grant. Hence, a new edge T4 → T2 is included in the graph. Now, the wait-for graph looks like the one given in the figure 5 below;

Figure 5 - Stage 4, new edge (T4,T2) is inserted

If we get any more requests, the graph will grow this way. At the same time, if any transactions releases the lock held by them, then the wait-for edge will be removed.

How does the Wait-for-graph help in detecting the deadlock?

Deadlock presents in a system if and only if we encounter a cycle in the Wait-for graph. Then, every transaction which is part of the cycle in the Wait-for graph will be treated as in the deadlock state. To detect this, the system has to employ the algorithm which checks the Wait-for graph for possible deadlock periodically.

The Wait-for graph given in the Figure 1, has formed a cycle. That is, T1 is waiting for the resource held by T2 and T2 in turn waiting for resources held by T1.

This deadlock situation need not involve all the transactions that are happening in a time. It may involve some of the transactions that are part of Wait-for graph at that moment as given in Figure 6.

Figure 6 - Wait-for-graph with both deadlocked transactions and free transactions

In Figure 6, only the transactions T1, T2 and T3 are formed a cycle, thereby entered a deadlock state. Transactions T4 and T5 are not part of the current deadlock state.

Related Links

Deadlock in database
Deadlock detection techniques INDEX
Database management systems home page 

How to detect deadlock in dbms using wait for graph?

Wait for graph and deadlock detection in dbms