Showing posts with label Deadlock. Show all posts
Showing posts with label Deadlock. Show all posts

Thursday, March 9, 2023

Deadlock prevention in RDBMS - WOUND-WAIT algorithm

 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.

Related Links

Deadlock in database
Deadlock detection techniques INDEX
Database management systems home page  

Deadlock prevention - Home page




Deadlock prevention in dbms

How to prevent deadlock in database management systems

Wait die and wound wait algorithm in deadlock prevention

Deadlock prevention in RDBMS - WAIT-DIE algorithm

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

Deadlock detection - WOUND-WAIT scheme

Deadlock prevention - Home page



Deadlock prevention in dbms

How to prevent deadlock in database management systems

Wait die and wound wait algorithm in deadlock prevention

Wednesday, January 13, 2016

Wait-die deadlock prevention algorithm in Animation

Animated Wait-die deadlock prevention algorithm / Wait-Die scheme explained / How does wait-die scheme prevents deadlock / Wait-die algorithm example in DBMS


Wait-Die Deadlock Prevention Algorithm







For more examples, please visit:

Deadlock prevention algorithms in database


Wednesday, October 15, 2014

4 necessary conditions for occurrence of deadlock



Four necessary conditions for occurrence of deadlock in databases / Four necessary conditions for deadlock to occur / Necessary and sufficient conditions for deadlock / List and discuss four conditions for deadlock / Necessary conditions that ensures a deadlock occurrence state

 

Necessary conditions for deadlock to occur in database


A deadlock can arise if the following 4 conditions hold simultaneously in a system;

  • Mutual exclusion: At least one resource is held in a non-sharable mode. For example, among transactions if there is any Exclusive lock (Write lock) request, that data item cannot be shared with others.
  • Hold and wait: There is a transaction which acquired and held lock on a data item, and waits for other data item.
  • No preemption: A situation where a transaction releases the locks on data items which it holds only after the successful completion of the transaction. Not on voluntarily.
  • Circular wait: A situation where a transaction say T1 is waiting for another transaction T2 to release lock on some data items, in turn T2 is waiting for another transaction T3 to release lock, and so on.
During transaction processing, if all the said conditions are held then there occurred a deadlock.


Go to Deadlock Handling Techniques in Database page
Go to Database Management Systems Home page

List of necessary conditions for deadlock to happen in database

Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents

data recovery