Whenever a deadlock is detected within transactions using any of the deadlock detection techniques, the deadlock must be recovered so that the transactions can perform their respective operations. The process of recovering from the deadlock situation is known as DBMS Deadlock Recovery.
Method used for DBMS Deadlock Recovery
The most common method to recover from a deadlock is to rollback one or more transactions until a no deadlock situation is reached. The actions that would be taken for deadlock recovery will be as follows:
- Choice of the Victim Transaction
- Roll back
- Starvation
Choice of the Victim Transaction
The transaction which is chosen for a rollback when a deadlock situation is reached is known as a victim transaction and the method is known as victim selection.
The victim may be selected based on any of the following criterions.
- Transaction may be selected randomly.
- Transaction will be selected depending on when the transaction started to run. That is the youngest transaction may be selected as the victim because it would have done the least amount of work.
- The transaction which needs a greater number of data items to be locked.
- The transaction which has done least number of data updates to the database because all the data written or changed in the database must be undone in the case of all a rollback.
- The transaction which would affect the roll back of a least number of other transactions. This means the victim transaction must lead to least amount of cascade rollback.
So, we can see that the victim transaction must be such a transaction which would incur the minimum cost.
Roll back
Once the victim transaction is selected the next important point to decide is how far this transaction should be rolled back. There are two ways in which the transaction can be rolled back. these are as follows:
- One of the simplest solutions is to roll back the transaction entirely and restart it later. This is referred to as a full rollback.
- On the other hand, some transactions can be rolled back to a particular point which is enough to break the deadlock. This type of rollback is known as a partial rollback. In such transactions additional information regarding the state of the current transaction execution, bookmark information, locks required etc. must be maintained by the system.
Starvation
Starvation is a condition which arises when one same transaction is always picked as the victim transaction. When the same transaction is rolled back again and again it will never complete its execution.
In other words, we can say that when a transaction cannot proceed for an indefinite period of time and other transactions in the system continue to execute normally, such a situation is called starvation or Live Lock.
For example, let us assume there are two transactions T1 and T2 which are trying to acquire a lock on a data item X. The scheduler grants the lock to T1. As a result, T2 has to wait for the lock. Now beforeT1 unlocks the data item X, a new transaction T3 also wants to acquire the lock on the data item X. Now, if the scheduler grants the lock to T3, T2 again has to wait for the lock. As a result,T2 has to wait indefinitely even if there is no deadlock. Hence, this situation is called starvation.
Solution to Starvation
In order to avoid the situation of starvation to implement DBMS Deadlock Recovery we can choose one of the following ways:
- A transaction must be picked as the victim transaction only a finite number of times. This can be done by maintaining an index to how many times a transaction has aborted and rolled back.
- The scheduler must follow the policy of first come first serve basis.
Be First to Comment