Deadlock in DBMS

A deadlock is a condition where two or more transactions are waiting indefinitely for one another to give up locks. Deadlock is said to be one of the most feared complications in DBMS as no task ever gets finished and is in a waiting state forever.

For example: In the student table, transaction T1 holds a lock on some rows and needs to update some rows in the grade table. Simultaneously, transaction T2 holds locks on some rows in the grade table and needs to update the rows in the Student table held by Transaction T1.

Now, the main problem arises. Now Transaction T1 is waiting for T2 to release its lock and similarly, transaction T2 is waiting for T1 to release its lock. All activities come to a halt state and remain at a standstill. It will remain at a standstill until the DBMS detects the deadlock and aborts one of the transactions.

Deadlock Avoidance

• When a database is stuck in a deadlock state, then it is better to avoid the database rather than abort or restarting the database. This is a waste of time and resources.
• A deadlock avoidance mechanism is used to detect any deadlock situation in advance. A method like "wait for graph" is used for detecting the deadlock situation but this method is suitable only for the smaller database. For the larger database, the deadlock prevention method can be used.

Deadlock Detection

In a database, when a transaction waits indefinitely to obtain a lock, then the DBMS should detect whether the transaction is involved in a deadlock or not. The lock manager maintains a Wait for the graph to detect the deadlock cycle in the database.

Wait for Graph

• This is a suitable method for deadlock detection. In this method, a graph is created based on the transaction and its lock. If the created graph has a cycle or closed loop, then there is a deadlock.
• The wait for the graph is maintained by the system for every transaction which is waiting for some data held by the others. The system keeps checking the graph if there is any cycle in the graph.

The wait for a graph for the above scenario is shown below:

closed-loop

Deadlock Prevention

• The deadlock prevention method is suitable for a large database. If the resources are allocated in such a way that deadlock never occurs, then the deadlock can be prevented.
• The Database management system analyzes the operations of the transaction whether they can create a deadlock situation or not. If they do, then the DBMS never allowed that transaction to be executed.

Wait-Die scheme

In this scheme, if a transaction requests for a resource that is already held with a conflicting lock by another transaction then the DBMS simply checks the timestamp of both transactions. It allows the older transaction to wait until the resource is available for execution.

Let's assume there are two transactions Ti and Tj and let TS(T) is a timestamp of any transaction T. If T2 holds a lock by some other transaction and T1 is requesting resources held by T2 then the following actions are performed by DBMS:

1. Check if TS(Ti) < TS(Tj) - If Ti is the older transaction and Tj has held some resource, then Ti is allowed to wait until the data item is available for execution. That means if the older transaction is waiting for a resource that is locked by the younger transaction, then the older transaction is allowed to wait for the resource until it is available.
2. Check if TS(T_i) < TS(Tj) - If Ti is an older transaction and has held some resource and if Tj is waiting for it, then Tj is killed and restarted later with the random delay but with the same timestamp.

Wound wait scheme

• In the wound wait scheme, if the older transaction requests for a resource that is held by the younger transaction, then the older transaction forces the younger one to kill the transaction and release the resource. After the minute delay, the younger transaction is restarted but with the same timestamp.
• If the older transaction has held a resource that is requested by the Younger transaction, then the younger transaction is asked to wait until the older one releases it.