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.

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-waitTn is younger than Tk      Tn dies          Tn waitsTn is older than Tk        Tn waits         Tk aborts      

Both schemes prefer older transactions with an older timestamp.

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