Although concurrency control techniques ensure Serializability, it may at times lead to a situation known as deadlocks in database.
Introduction – Deadlocks
A deadlock can be defined as a situation where each transaction that is executing concurrently is blocked in a circular wait situation. A deadlock is created because of exclusive locks used by transactions. None of the transaction is able to unblock itself unless there is an external intervention.
This external intervention will force some transaction to release the resources exclusively locked by some transactions.
Conditions necessary for a Deadlock
For a deadlock to occur some conditions must be followed necessarily. These conditions are as follows:
- Mutual Exclusion: In this condition a data item can be locked exclusively by one transaction only at a given point of time.
- Hold and Wait: This is also known as partial allocation. This condition happens when a transaction acquires some of the required data items but it requires other data items which are currently under exclusive locks by other transactions.
- Non Pre-emptive Scheduling: Here a data item can only be unlocked by the transaction that holds the exclusive lock on it.
- Circular Wait: In this condition two or more transactions wait indefinitely for the release of a lock acquired by other transactions.
To order to avoid a deadlock at least one of the above conditions must not occur.
Example of a Deadlock
Let us consider two transactions – T1 and T2 working on two tables – table A and table B. Now consider the following operations for these transactions:
- Transaction T1 holds a lock on a table A. Now, T2 wants to acquire a write lock on this table.
- Transaction T2 holds a lock on another table B. Now, T1 wants to acquire a lock on this table.
The above situation can be depicted as follows:
In this diagram,
Solid arrow represents Locks Acquired by the transaction
Dotted arrow represents Locks Desired by the transaction
Now it is clear from the diagram above that unless transaction T2 gives up its lock on table B transaction T1 cannot proceed with the lock. Similarly, unless transaction T1 gives up its lock on table A, transaction T2 cannot proceed.
As a result, both the transactions depend on releasing of locks by each other in order to proceed.The releasing of locks can never happen automatically. Hence, this situation will result in a deadlock.
Solution for dealing with Deadlocks in Database
Once a deadlock has been identified one of the transactions must be selected and rolled back. This will help in releasing all the locks that the transaction had held. Hence the deadlock would be broken. The transaction which is selected to be rolled back is called a victim.
A deadlock is undesirable but often deadlocks can be avoided. Hence, when a deadlock occurs, we must deal with it in a proper manner. Some of the ways in which we can deal with the deadlock are as follows:
- Deadlock Prevention.
- Deadlock Detection.
- Deadlock Resolution.
We would study about them in the upcoming articles.