Deadlock prevention algorithms in database management systems, wait-die algorithm, example transactions deadlock, how does wait-die algorithm work? deadlock prevention schemes
1. Wait-Die algorithm:
Wait-die algorithm is one of the deadlock prevention 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.
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.
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 prevention in dbms
How to prevent deadlock in database management systems
Wait die and wound wait algorithm in deadlock prevention
