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 Ti → Tj. This
means that the transaction Ti is waiting for a resource held by
transaction Tj.
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 Ti waits for other transaction Tj
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