What is the difference between "wait-die" and "wound-wait" deadlock prevention algorithms?

Question

What is the difference between wait-die and wound-wait algorithms?

It seems that both of these deadlock prevention techniques are doing the same thing: A Rollback of older process.

What is the difference between the two?

Please provide a suitable example to contrast the two algorithms.

Selfassured

Answer 1

Wait-Die scheme

It is a non-preemptive technique for deadlock prevention. When transaction T_n requests a data item currently held by T_k, T_n is allowed to wait only if it has a timestamp smaller than that of T_k (That is T_n is older than T_k), otherwise T_n is killed ("die").

In this scheme, if a transaction requests to lock a resource (data item), which is already held with a conflicting lock by another transaction, then one of the two possibilities may occur:

1. Timestamp(T_n) < Timestamp(T_k) − that is T_n, which is requesting a conflicting lock, is older than T_k − then T_n is allowed to "wait" until the data-item is available.

2. Timestamp(T_n) > Timestamp(T_k) − that is T_n is younger than T_k − then T_n is killed ("dies"). T_n is restarted later with a random delay but with the same timestamp(n).

This scheme allows the older transaction to "wait" but kills the younger one ("die").

Example

Suppose that transaction T₅, T₁₀, T₁₅ have time-stamps 5, 10 and 15 respectively.

If T₅ requests a data item held by T₁₀ then T₅ will "wait".

If T₁₅ requests a data item held by T₁₀, then T₁₅ will be killed ("die").

Wound-Wait scheme

It is a preemptive technique for deadlock prevention. It is a counterpart to the wait-die scheme. When Transaction T_n requests a data item currently held by T_k, T_n is allowed to wait only if it has a timestamp larger than that of T_k, otherwise T_k is killed (i.e. T_k is wounded by T_n).

In this scheme, if a transaction requests to lock a resource (data item), which is already held with conflicting lock by some another transaction, one of the two possibilities may occur:

1. Timestamp(T_n) < Timestamp(T_k), then T_n forces T_k to be killed − that is T_n "wounds" T_k. T_k is restarted later with a random delay but with the same timestamp(k).

2. Timestamp(T_n) > Timestamp(T_k), then T_n is forced to "wait" until the resource is available.

This scheme allows the younger transaction requesting a lock to "wait" if the older transaction already holds a lock, but forces the younger one to be suspended ("wound") if the older transaction requests a lock on an item already held by the younger one.

Example

Again, suppose that Transactions T₅, T₁₀, T₁₅ have time-stamps 5, 10 and 15 respectively.

If T₅ requests a data item held by T₁₀, then data item will be preempted from T₁₀ and T₁₀ will be suspended. ("wounded")

If T₁₅ requests a data item held by T₁₀, then T₁₅ will "wait".

Summary

In both the cases, only the transaction that enters the system at a later timestamp (i.e. the younger transaction) might be killed and restarted.

Cascade

Wait-die and wound-wait are first proposed in dl.acm.org/citation.cfm?id=320260. – Masbate

My mnemonic aid for this: place the strategy name on a timeline. Left to the hyphen is old, to the right is young. Every verb (wait, wound, die) is viewed from one fixed transaction Tn. It's easier than it sounds: wound-wait: I'm old: wound, I'm young: wait; wait-die: I'm old: wait, I'm young: die. – Cruiserweight

Answer 2

Parth has given a detailed answer. Here I summarize it in a different way.

Assume that T_n requests a lock held by T_k. The following table summarizes the actions taken for wait-die and wound-wait scheme:

                           wait-die         wound-wait
Tn is younger than Tk      Tn dies          Tn waits
Tn is older than Tk        Tn waits         Tk aborts
      

Both schemes prefer older transactions with an older timestamp.

Masbate

Great answer, but is die same as abort/rollback ? – Kook

@Kook Yes, die is the same as abort/rollback. – Masbate

for the case where Tn is younger than Tk and wound-wait, shouldn't it be Tn waits?? @JingguoYao – Bria

@Bria Yes, you are right. I have fixed the typo. – Masbate

Answer 3

wait-die: When an older transaction tries to lock a DB element that has been locked by a younger transaction, it waits. When a younger transaction tries to lock a DB element that has been locked by an older transaction, it dies.

wound-wait: When an older transaction tries to lock a DB element that has been locked by a younger transaction, it wounds the younger transaction. When a younger transaction tries to lock a DB element that has been locked by an older transaction, it waits.

---

References:

• Preventing deadlock with timestamps: the wait-die method
• Preventing deadlock with timestamps: wound-wait scheme
• Comparing the wait-die and wound-wait schemes

Weathers

Answer 4

The best way to understand two related topics can be achieved by comparison. So, Similarity between wait-die and wound-wait:

1. The older transaction will "win" over the newer transaction.
2. When transactions restart, they keep their timestamps.
3. Eventually, the aborted (younger) transactions will become the oldest transactions in the system.

Difference between wait-die and wound wait:

1. In wait-die, The newer transactions are killed when the newer transaction makes a request for a lock being held by an older transactions.
2. In wound-wait, The newer transactions are killed when an older transaction makes a request for a lock being held by the newer transactions.

Preconcert

Answer 5

I'll put the @JingguoYao's summary a bit differently. I just rearranged it because for me (and others like me) it reads easier like this.

Assume that T_n requests a lock held by T_k. The following table summarizes the actions taken for wait-die and wound-wait scheme:

                Tn is older than Tk     Tn is younger than Tk
wait-die        Tn waits                Tn dies
wound-wait      Tk aborts               Tn waits

Both schemes prefer older transactions with an older timestamp.

Question

For the wound-wait condition in case of "Tn is younger than Tk", it is Tk waits instead of Tn waits – Shaff

@Shaff No, in the wound-wait condition where "Tn is younger than Tk", Tn has to wait, it's correct how it is written. Compare to the accepted answer. Note that all verbs ("wait, die, wound") refer to Tn and not Tk. ("Tn wounds Tk" is just rewritten here as "Tk aborts" which is semantically the same thing). – Cruiserweight

Answer 6

• A deadlock is created when both edges form, as shown in the graph above. A young transaction requests a lock from an old transaction, and an old transaction requests a lock from a young transaction.
• Each of the 2 techniques just prevents one of the edges from being formed while allowing the other edge, hence preemptively preventing a cycle from being formed.
• If you notice, in both strategies, the young transaction gets aborted. Only the initiator of the lock request differs. Aborted transactions are restarted at a later point in time.

Taradiddle

The graphic explained it so well, thank you 👍 – Cruiserweight

Answer 7

In both cases Old is always champ i.e. will survive. Difference is from younger transaction point of view.

If younger one is requesting a resource held by a old trans. , in wait/die he can wait to give respect as Old trans.If younger one is requesting a resource held by a old trans., in wound/die he will be force to rollback as Old trans.

In both scheme old is never in loss.

Refer:https://www.tutorialspoint.com/dbms/dbms_deadlock.htm

Meanly