Deadlock in DBMS

Introduction

Let's understand deadlock in DBMS with an example of students database, where transaction 1 holds a lock on certain records of the Student table and needs to update those records in the Grade table. Simultaneously, there is transaction 2, which holds locks on some other records in the Grade table and needs to update those records in the Student table, which are already held by transaction 1.

Now, the main problem of deadlock arises when transaction 1 is waiting for Transaction 2 to release its lock and similarly, transaction Transaction 2 is waiting for Transaction 1 to release its lock. All activities come to a halt. Both the transaction involved in such a situation will remain at a standstill until the DBMS detects the deadlock and aborts one of the two transactions that are causing deadlock.

Coffman Conditions

Regarding deadlock in DBMS, there were four conditions stated by Coffman. A deadlock might occur if all of these four Coffman conditions hold true at any point in time.

1. Mutual Exclusion: There should be at least one resource that cannot be utilized by more than one transaction at a time.
2. Hold and wait condition: When any transaction is holding a resource, requests for some more additional resources which are already being held by some other transactions in the system.
3. No preemption condition: Access to a particular resource can never be forcibly taken from a running transaction. Only that running transaction can release a resource that is being held by it.
4. Circular wait condition: In this condition, a transaction is kept waiting for a resource that is at the same time is held by some other transaction and which is further waiting for a third transaction so on and the last transaction is waiting for the very first one. Thus, giving rise to a circular chain of waiting transactions.

Deadlock Handling

Ostrich Algorithm

Ostrich Algorithm is an approach of handling deadlock that involves ignoring the deadlock and pretending that it would never occur. This approach derives its name from the behavior of an Ostrich which is “to stick one’s head in the sand and pretend there is no problem”. Windows and UNIX-based systems use this approach of handling a deadlock.

But now you might question, Why ignore the deadlock?

This is because deadlock is a very rare case and the cost of handling a deadlock is very high. You might have encountered a situation when your system got hanged up and to fix it a restart was needed. In this case, the Operating system ignores the deadlock as the time required to handle the deadlock is higher than the rebooting time of windows. Rebooting is a preferred choice, considering the rarity of deadlock in Windows.

Deadlock Avoidance

• Deadlock avoidance is a technique of detecting any deadlock in advance. Methods like Wait-For graph can be used in smaller databases to detect deadlocks, but in the case of larger databases deadlock prevention measures have to be used.
• When a database gets stuck in a state of deadlock, it is preferred to avoid using that database instead of aborting or rebooting the database server as it wastes of both time and resources.

Deadlock Detection

While a database transaction, if a task waits indefinitely to obtain CPU resources, then DBMS has to check whether that task is in a state of deadlock or not. To detect a deadlock a resource scheduler is used. A resource scheduler can detect deadlock by keeping track of resources allocated to a specific transaction and requested by another transaction.

• Wait-For Graph: This method of detecting deadlocks involves creating a graph based on a transaction and its acquired lock (a lock is a way of preventing multiple transactions from accessing any resource simultaneously). If the created graph contains a cycle/loop, it means a deadlock exists.

DBMS creates a wait-for graph for every transaction/task that is in a waiting state and keeps on checking whether there exists a cycle in any of the graphs or not

The above is a wait-for graph representation for two transactions T1 and T2 in a deadlock situation.

Deadlock Prevention

Avoiding one or more of the above-stated Coffman conditions can lead to the prevention of a deadlock. Deadlock prevention in larger databases is a much more feasible situation rather than handling it.

The DBMS is made to efficiently analyze every database transaction, whether they can cause a deadlock or not, if any of the transactions can lead to a deadlock, then that transaction is never executed.

1. Wait-Die Scheme: When a transaction requests a resource that is already locked by some other transaction, then the DBMS checks the timestamp of both the transactions and makes the older transaction wait until that resource is available for execution.

2. Wound-wait Scheme: When an older transaction demands a resource that is already locked by a younger transaction (a transaction that is initiated later), the younger transaction is forced to kill/stop its processing and release the locked resource for the older transaction's own execution. The younger transaction is now restarted with a one-minute delay, but the timestamp remains the same. If a younger transaction requests a resource held by an older one, the younger transaction is made to wait until the older one releases the resource.

Deadlock Detection in Distributed Systems

Distributed systems in DBMS have multiple components spread across different computing devices that coordinate and communicate actions to appear as a single system to the user. These are also known as distributed computing.

Distributed systems are very vast because of which deadlocks can neither be prevented nor avoided. Thus deadlock detection is the only possible option. Following are the requirements for deadlock detection in distributed systems.

1. Progress: The method should be able to detect all the deadlocks in the system.

2. Safety: The method should not detect false or phantom deadlocks.

Approaches to detect deadlock in the distributed system

1. Centralized Approach: This is the simplest and easiest way of deadlock detection as in this only a single resource is responsible for detecting the deadlock. But it also has its own disadvantages, such as excessive load on a single node and having only a single point of failure that makes the system less reliable.

2. Distributed Approach: Unlike the centralized approach, multiple nodes are responsible for detecting deadlock. Because of this approach multiple nodes there is proper load balancing and no single point of failure that helps to further increase the speed of detecting deadlock.

3. Hierarchical Approach: This Approach integrates both centralized and distributed approaches for deadlock detection. In this, a single node is made to handle a particular selected set of nodes responsible for detecting deadlock.

Read More:

• Serializability in DBMS.
• DBMS Indexing.
• Schedule in DBMS.