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