Table of Contents

1 Deadlock Handling in DBMS

Deadlock Handling in DBMS

Deadlock Handling in DBMS is a process of managing the deadlock situation.
Deadlock handling in DBMS can be achieved through deadlock avoidance, deadlock prevention and deadlock recovery methods.
Deadlock in DBMS is a situation when in a set of transactions, no transaction can progress further.
In this Deadlock Handling in DBMS tutorial, we have explained the answer of the questions What is Deadlock in DBMS ? and How to handle deadlock ?
There are several deadlock handling mechanisms used to handle the in Deadlock in DBMS.
This tutorial is specially prepared for computer science students who study in B.TECH(CS)/MCA/BCA.
Deadlock handling is also an important topic for GATE(CS/IT) and UGC NET exam.
This tutorial will also help students who are preparing for GATE(CS/IT) 2021 and UGC NET (Exam).
Students are requested to read this tutorial completely and give their feedback in the comment section.

Your feedback is valuable for us to prepare the study material as per the reader’s expectation.

Content at Glance

The following contents are discussed here in this deadlock handling in Database management System Tutorials.

What is Deadlock?
What are the necessary conditions for Deadlock in DBMS?
What types of Problems arise due to Deadlock in the Transaction ?
How to handle Deadlock in DBMS?
What is Deadlock Avoidance?
What is Deadlock Prevention?
What are different Deadlock Detection and Recovery from Deadlock in DBMS ?

Let’s start the study with an introduction to Deadlock.

What is Deadlock in DBMS ?

In Database Management System, Deadlock is a situation when in a set of transactions, no transaction can progress further.
A system is said to be in a deadlock state if there exists a set of Transactions such that every transaction from the set is waiting for another transaction to be completed in the set.
If there exists a set of waiting transaction such that one transaction is waiting for the next transaction to unlock the data item and a circular waits condition is formed, then in this situation, there is no chance that any transaction can progress. This situation is known as Deadlock.

Example of Deadlock in DBMS

We can also understand the Deadlock in DBMS by a simple example.

Let us consider two tables, Student and Course.

Suppose, at a particular instance of time, a Transaction T1 holds a lock on some rows of the Student table and needs to update some of those rows of Course Table held by another Transaction T2 time.

Simultaneously Transaction T2 need to update those rows of the Student table held by transaction T1

Here in this situation Progress of both transaction T1 and T2 will stop because T1 is waiting for T2 to release the Lock and T2 is waiting for t1 to release the Lock. So there is a circular wait condition. This situation is known as Deadlock.

Note – To understand the basic concepts of transaction, students can study this basic transaction tutorial concept.

What is Data Item Allocation Sequence?

All transactions must follow a sequence to access or use a data item which is as follows-

1) Request: Here, the transaction submits a request to use a Data Item to grant a Lock on the data item.

2) Use: If the system grants the request, the transaction acquires the Lock on the data item and will be in a state to use that data item. This state is known as Active State.

If the system does not grant the transaction’s request to Lock the data item at that time because of Data Item is locked already by another transaction, the requested transaction will wait for Unlocking the data item.

3) Release: After using the data item, the transaction will Unlock the data item and release it.

What are the Necessary Conditions for Deadlock?

There are four necessary conditions in the presence of which there may be a case of Deadlock in DBMS. These conditions are as follow –

1) Mutual Exclusion: To maintain Consistency in the system, any data item can be accessed by one and only one transaction at a time. Another transaction is not allowed to access that data item. This is what is called Mutual Exclusion.

2) Hold and Wait: Let us consider a transaction locks a data item at a time. Now, if the transaction wants to access other data items, it has to wait as it can not access two data items at a time. This condition is known as Hold and Wait.

3) No Preemption: Transaction will only access the data item when that data item is released (if the data item is locked) by another transaction it means the transaction should not take the data item forcefully.

4) Circular Wait: If there are three transactions such that-

Each transaction has to wait for each transaction to end first, which will cause a deadlock.

If any one of these four conditions is not fulfilled, the system will not enter a deadlock.

If any one of these four conditions are not fulfilled, the system will not enter a deadlock.

What Problem will Deadlock Cause?

If the system lacks a proper method to deal with Deadlock, then the following problems may arise-

1) In Real-Time System, it may cause a huge loss. For example, if in the stock exchange, banking sector, air traffic control, and big databases, the system stay on hold for some time, they would have to face a huge loss.

2) Deadlock will lead to reduce data item utilization and decrease efficiency. If the system is on hold, it will cause a loss of time, and thus the system becomes inefficient.

Process of Deadlock Handling in DBMS

There are three methods are used to handle the deadlock in system

(A) Deadlock Prevention

To ensure the system will never enter a deadlock state, for example, systems like 2PL or Time-Stamping Protocol etc. Preventive measures are to take if there is a deadlock state very frequently.

The deadlock Prevention method is generally suitable for a large database. If the data item is allocated so that it never leads to Deadlock, then Deadlock can be prevented.

To prevent the deadlock in database management system, analyze the transaction’s operations whether they can create a deadlock situation or not; if they do, then DBMS never allows that transaction to be executed.

(B) Deadlock Detection and Recovery

If a transaction waits indefinitely to acquire a lock in a database management system, then DBMS should detect whether a transaction is involved in Deadlock or not.
The Lock Manager will maintain a graph to detect the cycle in the graph.
Suppose the possibility for entering a deadlock in a system is very less. In that case, the system is first allowed to enter the Deadlock first and then taken measures to recover from the situation.

(C) Deadlock Avoidance

Deadlock Avoidance is a deadlock handling mechanism that handles the Deadlock before it’s occurring.
The deadlock avoidance mechanism analyzes the transaction and Lock to determine whether or not waiting for a lead to Deadlock.
While a transaction is executing and requests a data item, if at that time a data item is not being used by another transaction or there is no lock on a data item, then the transaction will apply the Lock on that data item and will use it.
If the data item is using by another transaction at that time, then the requested transaction needs to wait, but here, this is important to note that by keeping the requested transaction in a waiting state, if it leads to Deadlock, we have to avoid it.

Note – We will discuss the Deadlock Detection in more detail.

Deadlock Detection

The progress of the system will get suspended if there is a deadlock. Hence to ensure whether the system’s progress is suspended due to Deadlock or not, it’s important first to detect Deadlock.

Data Item Allocation Graph

It is a graphical representation to denote that how the allocation of data items in the system is made, how to depict that a transaction has placed a request to the operating system and to check whether the request is granted or not.

Data item allocation graph mainly consists of four components.

1) The circles will denote the transactions.

2) The rectangular boxes will denote data items. Whenever a data item is non-shareable, a single dot will be denoted inside the rectangle, i.e. only one transaction can access that data item. If the number of instances is more than one or multiplied, then the data item is sharable to that limit. i.e. if there are two dots, it can be shared with two transactions.

3) the third component is the allocation edge. It means when the edge is directed from the data item to the transaction, i.e. one of the data item instances is already allocated to the transaction.

4) When an edge is directed from the transaction to the data item, it is called the request edge. Request edge means the transaction has requested to get one of the instances of the data item.

One simple graph is shown below-

If there is no complete or closed path in the data item allocation graph, the system will be Deadlock free.

In the graph shown above, there is a cycle from. If there is a cycle present, then Deadlock may or may not occur in the system.

Now from the graph, we can see it is not waiting for any transaction to complete. Hence when will be completed, all the transactions will be completed one by one, and the system will not be in a deadlock.

Deadlock Recovery

There are two main methods for deadlock recovery. These are-

1) Transaction Termination

This means to kill transactions. It can be done with again two ways-

a)Abort all deadlocked transactions. It means that all the transactions that are in the deadlocked state have to be terminated. Then we will go for the allocation of the data items.
b)Until the deadlock cycle is eliminated, we need to abort one transaction at a time. We have to detect first which transaction is in wait and hold and have to terminate the transaction.

2) Data item Preemption

Three steps follow it-

Selecting a victim: To select a transaction to take away the data items with the minimum cost and allocate the data items to the waiting transaction.
Rollback: To terminate transactions one by one till there is no deadlock. When the system is in a safe state, the data item allocation has to be resumed.
Starvation: After terminating one transaction in the deadlock state, many data items are free to be allocated to other transactions, and thus the Deadlock can be removed.