Deadlock prevention algorithms in database management systems, wait-die algorithm, example transactions deadlock, how does wait-die algorithm work? deadlock prevention schemes
2. Wount-Wait algorithm:
Wound-wait 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 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.