Dead-Lock Handling
A system is said to be in a state of deadlock if there exists a set of transactions such that every transaction waits for another transaction in the set.
That is, if there are ‘n’ numbers of transactions (T21, T2,…Tn) such that T1 is waiting for T2, T2 is waiting for T3 and so on. Tn-1 is waiting for Tn and also Tn is waiting for T1.
There are two principal methods to deal with deadlocks.
- Deadlock Prevention Protocol: This is to ensure that the system will never enter a deadlock state.
- Deadlock Detection Protocol and Deadlock Recovery Protocol: Here, we allow the system to enter a deadlock state and then try to recover from it.
Here, both the methods result in transaction rollback.
Deadlock Prevention :
There are two approaches to this.
- This ensures that no cyclic waits can occur by ordering the requests for locks or requiring all locks to be acquired together.
- This is closer to deadlock recovery and performs transaction rollback instead of waiting for a lock, whenever the wait could potentially result in the deadlock.
In the first approach, each transaction locks all its data items before it begins the transaction,i.e., either all are locked in one step or none are locked.
The second approach is to use preemption and transaction rollbacks. In preemption, when a transaction Tj requests a lock that transaction Ti holds, the lock granted to Ti may be preempted by rolling back of Ti and granting of the lock to Tj.
To control the preemption, one can assign a unique timestamp, based on a counter or on the system clock, to each transaction when it begins.
The system uses these timestamps only to decide whether a transaction should wait or roll back.
The following are two different deadlock-prevention schemes using timestamps are :
(a) The Wait-Die scheme: It is a non-preemptive technique. When a transaction Ti requests a data item currently held by Tj, Ti is allowed to wait only if it has a timestamp smaller than that of Tj. Otherwise, Ti is rolled back(dies).
Ex: Let there be three transactions T14, T15, T16 with timestamps 5, 10, 15 respectively.
If T14 requests a data item held by T15, then T14 will wait. If T16 requests a data item held by T15, then T16 will be rolled back.
(b) The Wound-Wait scheme: It is a preemptive technique. When a transaction Ti requests a data item currently held by Tj, Ti is allowed to wait only if it has a timestamp larger than that of Tj. (That is Ti is younger than Tj). Otherwise, Tj is rolled back.
Reference Link