Deadlock Prevention algorithms in Database

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.

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 database
Deadlock detection techniques INDEX
Database management systems home page  

Deadlock prevention in dbms

How to prevent deadlock in database management systems

Wait die and wound wait algorithm in deadlock prevention