Deadlock in DBMS – Causes and Solutions

Deadlock is a most challenging problem in database management systems (DBMS). When two or more transactions in a database management system come into a situation where they are waiting for each other to finish without giving up the necessary process (CPU) and memory resources, it can be problematic and lead to deadlock.

In a multiuser system, when numerous transactions compete for shared resources, there is an increased risk of deadlocks. The system comes to a standstill as a result of these tasks going unfinished and waiting interminably.

In this article, we will cover the concept of deadlock in DBMS in-depth along with its causes, conditions given by Coffman, how to handle and avoid it, etc. We will learn in detail about various techniques to handle deadlock including the ostrich algorithm, bankers algorithm, resource allocation graph (RAG), etc.

What is a Deadlock?

Deadlock is a situation in an operating system when two or more processes wait for an infinite amount of time to acquire resources held by each other. Deadlock occurs in a multitasking system when a group of processes enters a state of indefinite time, with each process waiting on resources held by other processes within the same group.

At its core, deadlock is a circular dependence where every process halts progress, resulting in the entire system grinding to a halt. Deadlock commonly arises in multi-processing— where numerous processes share a particular kind of mutually exclusive resource referred to as a soft lock or software. In effect, deadlock acts like a stopper for any flow — it does not permit anything that would go past it.

Example:

Transaction T1 locks Resource M1 and needs Resource M2 to proceed.

Transaction T2 locks Resource M2 and needs Resource M1 to proceed.

In this example, T1 is waiting for M2, which T2 has locked, thus it is unable to move forward. Likewise, T2 is unable to move forward since it is awaiting M1, which T1 has locked. Consequently, both transactions have reached a state and cannot be resolved without assistance.

Let’s now discuss the causes of deadlock in DBMS.

Several different things can cause deadlocks in DBMS. It is crucial to comprehend these reasons to avoid and lessen deadlocks. 4 conditions cause deadlocks in DBMS:

1. Mutual Exclusion

Mutual exclusion is a condition where only one process at a time can access certain resources. It implies that a minimum of one resource needs to be maintained in a non-shareable mode, which restricts resource usage to a single process at a time.

Example: Let’s say two transactions T1 and t2 need access to the same data row. If T1 locks the row and T2 tries to access it, it has to wait until T1 releases the lock. If T1 subsequently needs a resource that is being used by the T2 there is a situation of mutual exclusion.

 2. Hold and Wait

When a process has at least one resource in hand and is waiting to obtain more, the hold and wait condition occurs.  To put it another way, a process that has at least one resource is waiting to obtain more resources than other processes have.

Example: A situation of Hold and wait will occur if a transaction T1 holds the resource R1 And waits for the resource R2 while T2 holds the resource is and waiting for the resource R1,  both are holding the resources and waiting for the other ones creating a deadlock situation

 3. No Preemption

No preemption is a situation where it is forbidden to forcibly remove resources from a process according to the no preemption condition. A process can only release a resource that it has obtained voluntarily. This means that to free up resources for use by other processes, a process cannot be stopped or preempted. Resources must be freed willingly from processes that are retaining them.

Example: Suppose transaction T1 holds resource R1 and T2 holds resource R2, neither transaction can be preempted.

 4. Circular Wait

A circular wait is a situation or a condition where every part in a circular chain of processes has at least one resource that is required by the process after it. It is a never-ending wait loop that stops any process from obtaining the resources it needs to keep running or where none of the transactions can proceed.

Example: A circular wait condition can occur if a transition T1 waits for a resource that is being held by T2, T2 waits for the resource held by T3 and T3 waits for another resource that is being held by T1, and a deadlock can occur.

Deadlock Handling

The very first approach to handle deadlock is to ignore it. Yes, it is right, just ignore it. This is what the ostrich algorithm implies. But what is an ostrich algorithm?

Deadlock Ignorance

Ostrich Algorithm

The Ostrich Algorithm is a deadlock handling technique that intentionally ignores the issue of deadlocks, adopting a somewhat unorthodox approach. The ostrich, which is wrongly thought to bury its head in the sand to avoid danger, is the source of the word, which denotes a choice to turn a blind eye to a problem rather than face it front-on. It is a very unconventional approach but it works.

How the Ostrich Algorithm Works

The Ostrich Algorithm indicates that the system does not employ any particular mechanism to identify, stop, or break out of deadlocks in the context of deadlock handling. Rather, the system just lets deadlocks happen and doesn’t do anything about them.

If a stalemate occurs, the system can freeze and may need to be broken manually by restarting the computer or ending specific processes. Some of the real-world examples using this algorithm are Windows and UNIX-based systems that use this approach to handle a deadlock.

But why ignore deadlock, if it is important?

Ignoring deadlock is the best way to handle it. This is because the deadlock occurs very rarely, and the cost to handle it is very high compared to any other solution.

Deadlock Avoidance

Deadlock avoidance means to avoid the deadlock in the operating system. It ensures that requests for any resource are fulfilled as long as the system’s final state avoids causing deadlock. The system’s condition will be monitored continually to identify safe and harmful conditions.

Deadlock avoidance can be accomplished by a variety of techniques, such as resource allocation graphs, the bankers’ algorithm, or dynamic resource scheduling for monitoring resource allocation.

Resource Allocation Graph (RAG)

The resource allocation graph (RAG) is the initial method for preventing deadlock. It is a kind of directed graph that illustrates the distribution of resources inside a system. RAG also serves as a state representation for the system. The graph contains all of the processes, resources that have been assigned to them, and resources that each process has requested.

Bankers Algorithm

A well-known deadlock avoidance technique used in database management systems and operating systems is Banker’s Algorithm. It does this by carefully assigning resources to processes so that a system can remain in a secure state without experiencing any deadlocks.

Algorithm Pseudocode:

As per the algorithm,

1. Initialize Work and Finish:

Work = Available = [3, 3, 2]

Finish = [False, False, False]

2. Find a Process that Can Be Satisfied:

Check if there is a process whose Need <= Work and is not finished.

Example:

Consider three resources (R1, R2, R3) with the processes P1, P2, and P3. The available resources are 3, 3, and 2. Check whether the system is in a safe state or unsafe state.

Given,

Max = [[7, 5, 3], [3, 2, 2], [9, 0, 2]]

Allocation = [[0, 1, 0], [2, 0, 0], [3, 0, 2]]

We are given the max, allocation, and available resources. Now to check for a safe or unsafe state, we have to first check how much resources each process needs. Therefore, we calculate the Need using the formula: Need = Max – Allocation.

Need = [[7, 4, 3], [1, 2, 2], [6, 0, 0]]

So, now we need each process (i.e., [[7, 4, 3], [1, 2, 2], [6, 0, 0]]) and the available resources (3, 3, 2). So, we will now allocate the resources in order of the available resources.

Iteration 1:

Check which process Need <= work.

P1: Need = [7, 4, 3], which is not <= Work = [3, 3, 2]

P2: Need = [1, 2, 2], which is <= Work = [3, 3, 2]

Here, in the first iteration, P2 satisfies the condition; therefore, we allocate resources to P2 and mark it as finished. Now, our new work becomes: Work + Allocation[P2] = [3, 3, 2] + [2, 0, 0] = [5, 3, 2]

Iteration 2:

P1: Need = [7, 4, 3], which is not <= Work = [5, 3, 2]

P3: Need = [6, 0, 0], which is <= Work = [5, 3, 2]

Here, as no other process satisfies the condition, therefore we will check if we can satisfy any process with the updated Work:

Process P3: Need = [6, 0, 0], which is not <= Work = [5, 3, 2]

Since no other process satisfies the condition, we determine that the system is in an unsafe state. As the system is in an unsafe state, we also can’t create its Gantt Chart. This is how the banker’s algorithm works.

Deadlock Detection

Detecting a deadlock condition refers to deadlock detection. In simpler terms, the method of determining whether a DBMS has had a deadlock is known as deadlock detection. In DBMS, deadlocks are found using a variety of algorithms and methods. When detected, necessary steps can be followed to break the deadlock.

We use a resource scheduler to detect the deadlocks. By monitoring the resources allotted to one transaction and demanded by another, a resource scheduler can identify deadlocks. Let’s see two algorithms that help in detecting deadlocks.

1. Wait-for Graph

Deadlocks in DBMSs can often be found using the wait-for graph. Using a transaction and the acquired lock, a graph is created to identify deadlocks.  Every transaction in this graph is represented as a node and if a related transaction is waiting for a resource that another transaction has, a directed edge is drawn from one node to the other. A deadlock is said to exist if there is a cycle or loop in the generated graph.

Example:

Let’s suppose there are two transactions T1 and T2. Now T1 waits for the resource held by T2 and T2 waits for the resource held by T1, a cycle is formed through this, indicating a deadlock. Now to detect this cycle, the wait-for graph method is used.

2. Resource Allocation Graph

Deadlock can be detected using another technique called resource allocation graph (RAG). Resources and transactions are shown in this graph as nodes. A request for a resource is shown by an edge connecting a transaction and a resource, whereas an allocation of a resource to a transaction is indicated by an edge connecting a resource and a transaction. This method is somewhat similar to the Wait-for graph where, If there is a cycle in the graph, a deadlock is detected.

Example:

Let’s suppose there are two transactions T1 and T2. Now T1 requests for the resource R1 are allocated to T2 and T2 requests for the resource R2, are allocated to T1, a cycle is formed through this, indicating a deadlock. Now to detect this cycle, the resource allocation graph method is used.

 3. Timeout Mechanism

Using timeouts provides an easier way to discover deadlocks. Under this method, the system considers that a deadlock has occurred and rolls back or terminates a transaction if it waits for a resource for more than a predetermined timeout period.

Example:

T1 may be rolled back by the system to break the deadlock if it attempts to wait for R1 for thirty seconds without success.

Deadlock Prevention

The goal of deadlock prevention is to completely prevent deadlocks by designing a database management system. This can be accomplished by making sure that at least one of Coffman’s prerequisites for deadlock is not met.

Every database transaction is efficiently analysed by the DBMS to determine whether or not it can result in a deadlock. If it can, the transaction is never carried out. This method is very useful and can be highly restrictive for better computing utilisation and decreased system throughput.

1. Wait-Die Scheme

A non-preemptive technique for addressing deadlocks based on process ages is the Wait-Die scheme. Put more simply, the age of a process is determined by the unique timestamp that is assigned to it at the start of the process.

The DBMS verifies the timestamp of both transactions and delays the execution of the older transaction when a transaction seeks a resource that has already been locked by another transaction. Let’s see if it’s working with the help of an example.

Example:

Process P1 has a lower timestamp and Process P2 has a newer timestamp both need a resource R. When P1 asks for resource R that P2 is holding, P1 must wait for P2 to release R. When P2 asks for resource R that P1 is holding, P2 aborts (dies), freeing R so that P1 can use it and P2 can resume later.

 2. Wound-Wait Scheme

Wound-wait is a preemptive technique for addressing deadlocks and is also based on the process ages. But this technique is the opposite of the wait-die scheme.

When a younger process is “wounded” (i.e., preempted) by an older process requesting a resource that it now possesses, the resource is transferred from the younger process to the elder process. After that, the younger process has to wait for the resource to become accessible once more. A younger process must wait if it wants a resource that an older process is holding.

Let’s see the workings of this scheme with the help of an example.

Example:

Suppose a resource R is required by both Process P1 (older process) and Process P2 (newer process). P2 is preempted and made to wait if P1 wants resource R, which is owned by P2. This permits P1 to seize control of resource R. When P2 asks for resource R that P1 is holding, P2 just has to wait for P1 to release the resource.

Deadlock Resolution

The DBMS needs to have methods in place to break deadlocks when they do arise. In most cases, terminating a deadlock entails relinquishing the resources involved in one or more of the transactions.

1. Transaction Rollback

Transaction Rollback means undo or roll back to one of the transactions that is causing the deadlock to occur. This works by releasing the locks that the transaction has, allowing the latest transaction to proceed. Once the latest transactions have performed their work, the rolled-back transaction can re-try.

Example:

Suppose transactions T1, T2, T3 are in a deadlock state, the latest transaction here is T3, therefore the system can choose the T3 to roll back to its previous state by releasing its locks, and thereby allowing T1 and T2 transactions to proceed.

 2. Choosing a Victim

The system must decide which transaction to cancel when rolling back a transaction to break a deadlock. This is carried out by specific standards, such as the priority of the transaction, the quantity of work it has finished, or the quantity of resources it possesses. The transaction that was selected is known as the “victim.”

Example:

Suppose transactions T1 (having a short duration) and T2( having a long duration) are in a deadlock state. The system here can choose to roll back the translation T1 to release its locks, as it can less impact the system performance.

 3. Cascading Rollback

Cascading rollback is a technique used when reversing a single transaction might not always be enough to break a deadlock, therefore we are required to roll back more transactions if the rollback of one causes another deadlock.

Example:

To completely break the deadlock, the system might also need to roll back transaction T2 if rolling back transaction T1 breaks it but causes another one involving T2 and T3.

Best Practices for Deadlock Handling

Deadlock can be handled easily if we follow some of the best practices explained as follows:

• Use Timeouts for Transaction

Timeouts on transactions could be used to address deadlocks by explicitly rolling back those transactions that have taken excessively long to acquire resources.

• Limited size for Transaction

The smaller the transactions are, the lower the chances of deadlocks. This can be achieved by ensuring that large operations are broken down into smaller, more manageable transactions.

• Locking Mechanism

A fine-tuned locking mechanism can reduce the possibility of deadlocks to a great extent: proper lock levels such as row-level or table-level, and right isolation levels based on the requirements of the application.

• Use proper Deadlock recovery tools

Deadlock detection and recovery tools are a common feature in most modern DBMSs. They work by automatically monitoring and resolving deadlocks when they happen.

• Avoid using long transactions

Locks are held for more extended periods by long transactions. Applications can be designed to avoid long transactions, thus reducing the chances of encountering deadlocks.

Deadlocks in Distributed Systems

In distributed database systems, where transactions involve multiple databases or nodes, deadlocks can also happen. Deadlocks in distributed systems cannot be avoided or prevented due to their large scale. Managing deadlocks in distributed systems is more difficult because there are more systems involved and a chance of network latency.

1. Two-phase locking (2PL)

Two-phase locking is one of the several protocols that are used in distributed systems for proper sequencing of transactions to avoid deadlocks.

For example, when a transaction begins in a distributed system, it goes into the growth phase and obtains all the locks that are required. When it reaches the shrinking phase, it releases the locks in reverse order after acquiring all of them. Deadlocks are avoided by this procedure, which makes sure that no additional locks are obtained during the shrinking phase.

 2. Distributed deadlock detection

In a distributed system, the wait-for graphs from each node can be combined to form a global wait-for graph. This global graph is then examined for cycles. In the case of a cycle being detected in it, this indicates that there was a deadlock. Two als: the growing phase acquires locks and the shrinking phase releases locks.

For example, In distributed detection, each node method keeps an eye on its transactions and interacts with other nodes to identify deadlocks. These two techniques are combined in the hierarchical approach, which involves several tiers of nodes in deadlock detection.

 3. Global Wait-for graph

Each waiting process sends a request edge to the resource that it is waiting for.

Detecting deadlocks in a distributed system is even more complex because it means different nodes. Deadlock detection algorithms include the centralised approach, distributed approach, and hierarchical approach.

Suppose, for example, every node generates a wait-for graph that represents the resources and transactions on that node. Once that is done, a global wait-for graph is created by combining these graphs and looking for cycles in it. The system acts to break the deadlock if a cycle is found.

 4. Distributed Time-out scheme

In distributed systems, timeout mechanisms can be applied as well for deadlock detection and resolution. It works this way: if a transaction is waiting for a resource that goes past some specified amount of time, then the system will assume that there is a deadlock and take corrective action.

Let’s take an example where in a distributed system, a system may determine that a deadlock has occurred and undo or roll back the transaction, releasing the locks and enabling other transactions to proceed, if a transaction waits for a resource on a different node for longer than sixty seconds of duration.

Real World Examples of Deadlock

There are various real-world examples where in our daily lives deadlock occurs. Some of the best and most common real-world examples of deadlock are as follows:

1. Banking Systems

In the case of banking systems, the bulk of their transactions involve multiple resources such as savings/current accounts, ledgers, and databases. Deadlocks could arise if many transactions try to make simultaneous transfers of funds between the same accounts, therefore creating a condition of deadlock known as circular wait.

For example, let’s suppose there are two transactions, say T1 and T2, where T1 transfers money from Person A to Person B and T2 transfers money from Person B to Person A. If in this case, T1 locks the account of person A and waits for the account of person B while the other hand T2 locks the account of person B and waits for the account of person A, then a condition of deadlock is said to happen. The deadlock must be detected and resolved by the banking system to let the transactions continue.

2. E-commerce

Online transactions on e-commerce systems involve a large number of transactions, often including transaction management, inventory management, payment processing, and order fulfilment. Deadlocks in this scenario can occur when more than one transaction tries to update the same set of inventory records or process payments at the same time.

 3. Online reservation systems

Another good real-world example is online reservation systems. Deadlocks can occur in online reservation systems, such as those used to book movie tickets, hotel rooms, tickets for events, or flights, when a high number of users try to reserve the same resources at the same time.

For instance, a deadlock arises when Person A attempts to reserve Seat 1 for a movie ticket and locks it, while Person B attempts to reserve Seat 2 and locks it. Both persons then attempt to reserve each other’s reserved seats. To make sure that users finish their reservations, the reservation system needs to identify and break this deadlock.

Conclusion

Deadlock is a critical issue not only in DBMS but also in real-world problems. In this article, we have covered the complete details of the deadlock in DBMS including its basics, causes, and solutions. The article has covered in-depth detail of every topic related to deadlock such as deadlock detection, deadlock prevention, deadlock avoidance, and resolution. Apart from this, we have learned the best practices one should follow to avoid the deadlock in real-life problems.

Deadlock risk can be reduced by putting best practices into operation, such as appropriate locking techniques, resource ordering, and the application of more advanced algorithms. Furthermore, utilising the built-in deadlock detection and recovery features of contemporary DBMS systems can aid in the efficient management of deadlocks, guaranteeing that transactions can move on without being permanently blocked.