Recovery from Deadlock in Database:
How can we recover from deadlock? / Rollback in deadlock / Guidelines to choose deadlock victim
After
detecting the deadlock, the next important step a system has to take is to
recover the system from the deadlock state. This can be achieved through rolling
back one or more transactions. But the difficult part is to choose one
or more transactions as victims.
Recovery from deadlock can be done in three steps;
1. Selection
of victim: Given a set of deadlocked transactions (transactions that formed
cycles), we have to identify the transaction or transactions that are to be
rolled-back for successful relief from deadlock state. This is done by
identifying the transaction or transactions that are cost minimum. This would mean many things. The following guidelines
would help us.
Guidelines to choose victim:
- The length of the transaction – We need to choose the transaction which is younger.
- The data items used by the transaction – The transactions that are used less number of data items.
- The data items that are to be locked – The transaction that needs to lock many more data items compared to that are already locked.
- How many transactions to be rolled back? – We need to choose transaction or transactions that would cause less number of other transactions to be rolled back (cascading rollback)
2. Rollback: Once we have identified the transaction or transactions that are to be rolled back, then rollback them. This can be done in two ways;
Full rollback
– Simplest of two. Rollback the transaction up to its starting point. That is,
abort the transaction and restart. It will also abort other transactions that
have used the data item changed by the rolled back transaction.
Partial
rollback – it might be the effective one, if the system maintains additional
information like the order of lock requests, save points etc.
3. Starvation:
We must be careful enough to avoid a transaction or transactions to be chosen
repeatedly as victims.