Suppose we are executing a set of transactions in the database. Let us assume the transaction as updating the address of an employee ‘James’ with ‘Tom’ address and a second transaction is updating the address of Tom to the address of James. Assume these are the concurrent transactions. What happens in this case? Here the first transaction is trying to update the address by selecting the address of Tom, while the second transaction is trying to select the address of James to update its address. When the first transaction begins it lock the address field of James for update. As soon as it locked the address of James, second transaction begins and it locks address of Tom for update. At this time, first transaction fetches the address of Tom. Since it is already locked for update, his address cannot be read by the first transaction, and it waits for update lock to release. Meanwhile the second transaction fetches the address of James, which is update locked by first transaction and it waits for its release. Here both the transactions are waiting for each other, and it will not release the lock until it is complete. Hence waiting for the other to release the lock will never end and this state of transaction is called deadlock.
Above diagram shows how two transactions are waiting for each other and never completes.
If a deadlock occurs in the database, then the transactions have to be restarted or rolled back. In above case, if the second transaction starts after T1 fetches Tom’s address, then there would not have been a deadlock situation. It has occurred because both the transactions have started simultaneously.
Table of Contents
Deadlock avoidance
It is always better to avoid deadlock in a system rather than aborting or restarting the transaction. This is waste of time and resource. Wait-for-graph is one of the methods for detecting the deadlock situation. But this method is suitable for smaller database. For large database deadlock prevention method may help.
Wait-For-Graph
In this method a graph is drawn based on the transaction and their lock on the resource. If the graph created has a closed loop, then there is a deadlock. In DBMS maintains this graph for all the transactions waiting for the resources and checks if there is a loop.
Suppose T1 and T2 are two transactions. Suppose T1 is requesting for a resource R which is held by T2. In this case, wait for graph draws an arrow from T1 to T2. If T2 releases the resource R, then this arrow is deleted.
Deadlock Prevention
The DBMS verifies each transaction and sees if there can be deadlock situation upon execution of the transaction. If it finds everything is fine, then allows the transaction to execute. If it finds that there can be a deadlock, it never allows the transaction to execute. DBMS basically checks for the timestamp at which a transaction has been initiated and orders the transactions based on it. If there are any transactions at same time period with requesting each other’s resource, then it stops those transactions before executing it. In above case, DBMS will never allow the transaction to execute simultaneously. This method is suitable for large system.
There are different methods to prevent the deadlock
Wait-Die Scheme
In this method, if a transaction request for the resource which is already locked by other transaction, then the DBMS checks for the timestamp of both the transaction and allows older transaction to wait until the resource is available for execution.
Suppose T1 and T2 be two transactions and let timestamp of any transaction T be TS (T). If there is a lock on T2 by some other transaction and T1 is requesting for T2 resources, then DBMS performs following actions :
- Checks if TS (T1)
- If T1 is older transaction and has held some resource with it and if T2 is waiting for it, then T2 is killed and restarted latter with random delay but with the same timestamp. i.e.; if the older transaction has held some resource and younger transaction waits for the resource, then younger transaction is killed and restarted with very minute delay with same timestamp.
In our above example of address update, if T1 is older transaction, then it waits till the address of Tom is available. Meanwhile it kills T2 and makes Address available for T1. Soon T2 will be restarted (hence there will be delay – start → Kill → restart) and it continues with its transaction. By this time T1 would have been completed and T2 will not have to wait. Although all these transactions look like taking time, all this happens in fraction of seconds and we cannot really observe the start/ delay/ restart / End.
Wound Wait Scheme
In this method, if an older transaction requests for a resource held by younger transaction, then older transaction forces younger transaction to kill the transaction and release the resource. The younger transaction is restarted with minute delay but with same timestamp. If the younger transaction is requesting a resource which is held by older one, then younger transaction is asked to wait till older releases it.