Deadlock in DBMS

Coffman Conditions

The Coffman Conditions, often referred to as the Coffman's Conditions or Coffman's Locking Conditions, are a group of requirements that must all be met for a deadlock to develop in a system of concurrent computation or resource allocation. Computer scientist Edward G. Coffman Jr. created these criteria.

The three Coffman Conditions are Mutual Exclusion (ME), Hold and Wait (HW), and No Preemption (NP). For a system to potentially reach a deadlock, these three requirements must exist. Deadlocks are unlikely to occur if any one of these conditions is not met. Systems often use deadlock detection and resolution techniques or make sure that at least one of the Coffman Conditions is violated to prevent and manage deadlocks.

Mutual Exclusion

It is a key idea in computer science and concurrent programming, which limits access to a resource, data structure, or crucial area of code to one process, thread, or task at a time.

Some key characteristics of Mutual Exclusion are:-

• Critical Sections: When writing critical sections of code, mutual exclusion is frequently used. An area in a programme where shared resources or data are accessed or changed is known as a key section. 
   
• Concurrency: Several threads or processes can operate simultaneously in modern computing systems. These concurrent entities may access shared resources simultaneously if suitable synchronisation measures are not present, which could result in unpredictable and inaccurate behaviour.
   
• Deadlock: While maintaining mutual exclusion is key, it's also essential to prevent deadlock, which occurs when many threads or processes are awaiting a resource held by another for an extended period.

Hold and Wait

"Hold and Wait" is one of the four requirements for a deadlock to happen in a concurrent system. A process holding resources now can ask for more without releasing the ones it now has. In other words, a process may already have some resources and still seek more, which could result in a situation where several processes are each holding some resources while awaiting more, which is known as a stalemate.

Some strategies to address Hold and Wait are:-

• Resource Allocation
• Graph Banker's Algorithm 
• Timeouts and Resource Releasing
•  Resource Prioritization

No Preemption

According to the "No Preemption" condition, once a process acquires a resource, it cannot lose access to it until the process voluntarily releases it. In other words, No other process or system entity may forcibly remove Resource X from Process A without Process A's consent if Process A is the process holding the resource.

This condition makes sure that a process can finish working without being stopped or losing access to resources. Preempting resources from a process may result in errors, damaged data, or unfavorable system behavior.

Circular Wait

The "Circular Wait" refers to a particular situation in which there is a circular chain or succession of processes, each of which is waiting for a resource held by the process after it.

Condition of  Circular Wait:

A circular dependence graph between processes is what defines the "Circular Wait" condition. In this circumstance:

• Process A is awaiting a resource that Process B is holding.
• Process B is awaiting a resource that Process C is holding.
• Process C is awaiting a resource that Process D is holding.
• And so on….
   

When the chain of dependencies finally comes to an end, a dependency loop is formed because Process B is waiting for a resource that Process A is holding.

Also See, File System vs DBMS

Deadlock Avoidance 

• Proactive Strategy: Deadlock algorithms are developed to anticipate and prevent deadlocks before they start. They examine the demands for resources and distribute them in a way that guarantees safe execution without the danger of a deadlock.
   
• Suitable for Smaller Databases: Mechanisms for avoiding deadlocks perform well in situations where there are a sufficient number of resources and processes. 
   
• Deadlock Prevention for Larger Databases: Implementing pure deadlock prevention techniques might be difficult in larger and more complicated databases or systems due to increased resource contention. In these situations, a variety of tactics, such as deadlock detection and deadlock avoidance methods, may be used to keep the system stable.
   
• Application-Consistent Logic: Circular waiting is one of the conditions that can lead to deadlock. Application-consistent logic refers to the rules and policies implemented inside an application or system to ensure that resource requests and releases are carried out in a manner that avoids circular waiting.
   
• Resource Conservation: Reducing the need for resource allocation and reallocation is one of the main advantages of deadlock avoidance. Carefully allocating resources enables operations to run smoothly without becoming halted by deadlock. 
   

Deadlock Detection

In a database management system, if a transaction gets blocked indefinitely to obtain a lock, the system uses deadlock detection methods to detect if the transaction is in a deadlock or not. One of the methods is Wait-for-graph. 

In this method, we draw a graph for the transactions and their locks. If the graph contains a cycle, then a deadlock has occurred.

Wait for Graph

• Wait For Graph (WFG) is a technique used to detect deadlocks.
   
• It is suitable for smaller databases.
   
• A directed graph is constructed, known as the Wait For Graph. This graph represents the transactions among processes and resources.
   
• Nodes represent transactions, and edges represent requests.
   
• A deadlock is detected when a cycle is formed in the graph.
   

Let's understand this Algorithm using an example. Take the scenario shown in the image above. There are two transactions T1 and T2.

1. Start a graph with T1. T1 is requesting some data so it can begin.
    
2. The data requested by T1 is held by T2. Thus  T1 will wait for T2 to complete and release the lock on data. T1 will point at T2 on the graph.
    
3. Now if T2 is looking for data which is held by T1, then we have a deadlock. T2 will point at T1.
    
4. A cycle is formed here as shown in the image.

Recommended Topic, B+ Tree in DBMS, Multiple Granularity in DBMS

Deadlock Detection in Distributed Systems

Deadlock detection in distributed systems is a challenging and critical aspect of ensuring system reliability and efficiency. In a distributed environment, resources are spread across multiple interconnected nodes, making the management and allocation of these resources more complex than in centralized systems. A deadlock occurs when a group of processes each hold a resource and wait indefinitely for another resource held by another process in the group, leading to a situation where none of the processes can proceed. Detecting deadlocks in distributed systems involves identifying these cycles of inter-process dependencies over the network.

Due to the decentralized nature of distributed systems, traditional deadlock detection techniques used in single-system environments are not directly applicable. Therefore, deadlock detection in distributed systems often relies on constructing a global wait-for graph that represents the current allocation of resources and the requests processes are making. This graph is constructed by collecting information from all nodes in the system, which can be a challenging task given the potential for incomplete or outdated information due to network latency and the asynchronous nature of distributed systems.

Deadlock Prevention

Deadlock prevention is an approach used in computer science and operating systems to proactively prevent the formation of deadlocks by removing one or more of the prerequisites for a deadlock to arise. The goal of deadlock prevention is to make sure that the system never enters a situation in which processes are stalled and unable to advance because of resource contention.

There are two methods for Deadlock Prevention:

1. Wait-Die Method
    
2. Wound-Wait Method

Wait-Die Method

Wait-Die is a non-preemptive type of deadlock prevention method. Since it is non-preemptive, CPU time will be distributed unevenly among all transactions. One transaction cannot be preempted between executing (it executes until it’s complete Burst Time).

In the Wait-Die Method, a transaction is made to wait if it has arrived before the other transaction or is killed.

Let’s consider two transactions Ti and Tj. Consider a situation where Ti requests the data member lock which Tj holds. Then Ti can wait only if the timestamp of Ti is lesser than that of the Tj.

i.e.,
if  (timestamp (Ti) < timestamp(Tj)) then Ti can wait for Tj to release the lock.
else if  (timestamp (Ti) > timestamp (Tj)) then Ti is killed or rolled-back.

Wound-Wait Method

Wound-Wait is a preemptive type deadlock prevention method. It ensures that all transactions get equal CPU time. The transactions are not executed to entire burst-time; they can be preempted during their execution to get CPU time for other transactions.

The wound-wait schema is the opposite of the wait-die schema; here, the transaction waits if it has arrived after the other transaction, or the other transaction is rolled back.

Again, let’s consider two transactions Ti and Tj, where Ti requests a data-lock held by Tj.

if  (timestamp (Ti) > timestamp (Tj)) then Ti can wait for Tj to release the lock.
else if  (timestamp (Ti) < timestamp (Tj)) then Tj is killed or rolled-back
 

Note: In Wait-Die Method, Ti is getting rolled back, whereas, in Wound-Wait, Tj is rolled back.

You can also read about the Log based recovery.

Must Read: Aggregation in DBMS

Ignore Deadlock - Ostrich Algorithm

The "Ignore Deadlock" or "Ostrich Algorithm" is not a suggested or useful method for resolving deadlocks in computer systems. It's more of a humorous or ironic idea than a practical one for breaking deadlocks. The term "Ostrich Algorithm" refers to the concept of putting one's head in the sand, unfortunately an ostrich, to avoid dealing with a problem.

Ignoring deadlocks can have serious consequences, including system failures, data corruption, and user annoyance. In concurrent systems, deadlocks are a major problem that must be solved to preserve system performance and dependability.

Frequently Asked Questions

How can deadlocks be resolved?

Deadlocks can be overcome via several techniques, such as process rollback, resource preemption, and process termination. These strategies aim to put an end the condition of periodic waiting and enable the impacted processes to move forward.

What are two options for breaking the deadlock?

The two options for breaking the deadlock are:-

• Process Termination: To free up the resources they are holding and end the deadlock, end one or more of the processes involved.
   
• Resource Preemption: To end the impasse and break the circular wait state, forcibly preempt resources from one or more processes.

How can we overcome the deadlock in DBMS?

Techniques like deadlock detection, avoidance, prevention, and resolution can be used to manage deadlocks in a DBMS. To keep the system stable and guarantee data integrity, these techniques help in the detection, proactive prevention, or resolution of deadlocks.

Conclusion

In this blog, we have learnt detailed information about Deadlock in DBMS.

For more exciting and informative technical blogs, you can check the Coding Ninjas Blogs library.

Also Read - Cardinality In DBMS and Recursive Relationship in DBMS

Don't stop here, Ninja; check out the Top 100 SQL Problems to get hands-on experience with frequently asked interview questions and land your dream job.

You can also consider our DBMS Course to give your career an edge over others.