What are the deadlock prevention algorithms in database?
Notes and Tutorials on How to prevent deadlock? / How to prevent deadlock in DBMS? / Deadlock prevention techniques in DBMS / Wait-die and Wound-wait in DBMS / Database deadlock avoidance / Wait-die and Wound-wait example
The Deadlock prevention protocol prevents the system from deadlock through transaction rollbacks. It chooses rollback over waiting for the lock whenever the wait could cause a deadlock. In this approach we have the following two deadlock prevention algorithms;
1. Wait-die
2. Wound-wait
Assume that a
transaction T1 requests for a lock on a data item X. And, the data item X is
already locked by another transaction T2 in an incompatible mode. Now the
question is “Can we allow transaction T1 to wait or to roll-back?” That is, the
Deadlock Prevention algorithm works by allowing a transaction to wait or
force it to roll-back to prevent the occurrence of deadlock.
1. Wait-Die algorithm:
When a
transaction T1 requests data item X held by transaction T2, deadlock prevention
protocol decides to allow T1 to wait or to roll-back based on the following conditions;
Condition
1: If timestamp of T1 is smaller than the timestamp of T2, ie, T1 started
before T2, then allow T1 to wait for T2 to release lock on X.
For example,
assume that the timestamp of T1 is 1 and that of T2 is 2. According to the
timestamp values, it is clear that T1 started before T2. Let us suppose, T2 has
already locked data item X, before T1. Now, we have to allow T1 (older
transaction) to wait for T2 to release X.
Condition
2: If timestamp of T1 is larger than the timestamp of T2, i.e, T1
started after T2, then roll-back T1. [Also, let T1 starts again with the same
timestamp and request X in a random amount of time.]
For example, assume
that the timestamp of T1 is 2 and that of T2 is 1. According to the timestamp
values, it is clear that T1 started after T2 has started. Let us suppose, T2
has already locked data item X, before T1. Now, roll-back T1 and allow T1 to
start again in a random time interval to request X with the same timestamp.
Deadlock detection techniques INDEX
Database management systems home page
Example 1:
Consider the
transactions T1 and T2 as given in Table 1;
Transaction
T1
TS1 – “2014-03-15 23:50:56”
Older Transaction
|
Transaction
T2
TS2 – “2014-03-15 23:51:12”
Younger Transaction
|
Read (X)
Read (Y)
Write (X)
|
Read (X)
Read (Y)
Write (Y)
|
Table
1 – Transaction T1 started first and then T2
Assume the
following;
- There are only 2 transactions T1 and T2 with timestamps TS1 and TS2 respectively (see the Table 1 heading for timestamps). TS1 < TS2, i.e, T1 is older than T2.
- T1 needs data items X and Y for writing.
- T2 needs data items X and Y for writing.
Let us
suppose that T1 first requests for Exclusive lock on X. Write lock can be
granted by the lock manager. At the same time, T2 requests for Exclusive lock
on Y. Write lock can be granted by the lock manager as there are no lock
requests on Y at the moment.
After
successfully locked X, T1 now requests for Y. But the lock manager cannot grant
lock on Y as Y has been locked by T2 in Write mode. According to Wait-die
algorithm, the older transaction has to wait for the younger to complete. Hence,
T1 has to wait for T2 to complete.
At this
moment, the interesting fact is that both T1 and T2 are waiting for both to
release the locks. Actually this is a deadlock situation. But, Wait-die
algorithm handles it very efficiently. How?
Now, T2
requests for write lock on X. As T1 holds lock on X, the lock manager cannot
grant the lock on X to T2. According to Wait-die algorithm, if a lock requested
by a younger transaction is held by an older transaction, the younger has to
roll-back. Hence, the younger transaction rolls-back after releasing the locks.
When T2 releases all the locks, T1 can acquire lock on Y and hence, the
transaction can be completed successfully.
Here, an
important point to note is that the rolled-back transaction must be allowed to
start again after a random time interval with the same timestamp to retain its
seniority. That is, T2 must be allowed to start with timestamp “2014-03-15 23:51:12”.
Example 2:
Assume the following;
- There are only 2 transactions T1 and T2 with timestamps TS1 and TS2 respectively (see the Table2 heading for timestamps). TS1 < TS2, i.e, T1 is older than T2.
- T1 needs data items X and Y for writing.
- T2 needs data items Y and Z for writing.
Let us
suppose that T1 first requests for exclusive lock on X. Write lock can be
granted by the lock manager. At the same time, T2 requests for exclusive lock
on Y. Write lock can be granted by the lock manager as there are no lock
requests on Y at the moment.
Transaction
T1
TS1 – “2014-03-15 23:50:56”
Older Transaction
|
Transaction
T2
TS2 – “2014-03-15 23:51:12”
Younger Transaction
|
Read (X)
Read (Y)
Write (X)
Wait for T2 to release Y
|
Read (Y)
Read (Z)
Write (Y)
Write (Z)
|
Table
2 – Transactions T1 started first and T2 next
Now, T1
requests for data item Y. The lock manager cannot grant the lock on Y because
the lock is already held by T2. According to Wait-die algorithm, the older
transaction has to wait for the younger to complete. Hence, T1 has to wait for
T2 to complete. After the successful completion, T2 will release lock on data
items it hold. Now, T1 can acquire the lock on Y and continue.
If the same
set of transactions happen in different order, like T2 first then T1, as given
in Table 3 below, roll-back T1.
Transaction
T2
TS2 – “2014-03-15 23:50:56”
Younger Transaction
|
Transaction
T1
TS1 – “2014-03-15 23:51:12”
Older Transaction
|
Read (Y)
Read (Z)
Write (Y)
Write (Z)
|
Read (X)
Read (Y)
Write (X)
Roll-back T1
|
Table
3 – Transaction T2 started first and then T1
This roll-back
ensures that there won’t be any deadlock.
Pictorial Representation of Working of Wait-die algorithm:
Figure 1 - Working of Wait-die algorithm |
* Wait-die is a
non-preemptive technique. That is, the transaction which requests the lock has
to be rolled-back if it cannot gain the lock.
2. Wound-wait algorithm:
When a
transaction T1 requests data item X held by transaction T2, deadlock prevention
protocol decides to allow T1 to wait or to roll-back based on the following conditions;
Condition 1: If
timestamp of T1 is larger than the timestamp of T2, ie, T1 started after T2,
then allow T1 to wait for T2 to release lock on X.
Condition 2:
If timestamp of T1 is smaller than the timestamp of T2, i.e, T1 started before
T2, then roll-back T2. That is, the data item requested by T1 will be preempted
from T2 and T2 is rolled-back.
Pictorial Representation of Working of Wait-die algorithm:
Figure 2 - Working of Wound-wait algorithm |
Points to note:
1. Deadlock
prevention technique is used for a system for which the possibilities for
entering a deadlock state are high.
2. Using 2
Phase Locking protocol to lock all the required data items at once may
help in preventing deadlock at the cost of lower data-item utilization.
3. Every time
Wait-die or Wound-wait roll-back a transaction, it is very important to ensure
that the system does not choose the same transaction repeatedly. The repeated
rollback of same transaction will lead to the state called Starvation. Both Wait-die
and Wound-wait avoids starvation. This is handled by issuing the same timestamp
for the transaction which is rolled back.
4. In Wait-die
scheme, older transaction waits. In Wound-wait scheme, older transaction never
waits.
5. The major drawback: both schemes lead to
unnecessary rollbacks.
Related Links
Deadlock in databaseDeadlock detection techniques INDEX
Database management systems home page