Deadlock Detection and Avoidance

In our last discussion on synchronization, we saw how semaphores and monitors help processes cooperate and share resources safely. We also touched upon a dangerous side effect of improper resource locking: deadlock, where processes get stuck waiting for each other in a circular chain, bringing everything to a halt.

This lesson dives deep into the world of deadlocks, a critical topic in operating systems and a favorite for GATE numerical and conceptual questions. We will start by formally defining what a deadlock is and identifying the four conditions that must be met for one to occur. Then, you will learn how to analyze a system's state to determine if a deadlock exists using a Resource Allocation Graph (RAG). Finally, we will explore a powerful deadlock avoidance technique, the Banker's Algorithm, which ensures the system never enters an unsafe state. By the end, you'll be equipped to solve the kind of complex resource management problems that frequently appear in the exam.

The Four Horsemen of Deadlock

A deadlock is a state where a set of processes are blocked because each process is holding a resource and waiting for another resource that is held by another process in the set. Think of two cars meeting head-on in a single-lane tunnel; neither can move forward until the other backs up, but neither is willing to do so.

For a deadlock to occur, four conditions, often called the Coffman conditions, must hold simultaneously:

Mutual Exclusion: At least one resource must be held in a non-shareable mode. Only one process at a time can use the resource. If another process requests that resource, it must be delayed until the resource has been released.
Hold and Wait: A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes.
No Preemption: Resources cannot be preempted; that is, a resource can only be released voluntarily by the process holding it, after that process has completed its task.
Circular Wait: A set of waiting processes ${P_{0}, P_{1}, \dots, P_{n}}$ must exist such that $P_{0}$ is waiting for a resource held by $P_{1}$ , $P_{1}$ is waiting for a resource held by $P_{2}$ , ..., $P_{n - 1}$ is waiting for a resource held by $P_{n}$ , and $P_{n}$ is waiting for a resource held by $P_{0}$ .

If any one of these conditions is absent, a deadlock cannot occur. This fact forms the basis for deadlock prevention strategies, but our focus today is on detection and avoidance.

Detecting Deadlock with Resource Allocation Graphs

A Resource Allocation Graph (RAG) is a directed graph used to describe the state of resource allocation in a system. It consists of:

A set of vertices V, partitioned into two types:
- $P = {P_{1}, P_{2}, \dots, P_{n}}$ , the set of all active processes.
- $R = {R_{1}, R_{2}, \dots, R_{m}}$ , the set of all resource types.
A set of edges E:
- Request Edge: A directed edge from a process $P_{i}$ to a resource type $R_{j}$ ( $P_{i} \to R_{j}$ ) signifies that process $P_{i}$ has requested an instance of $R_{j}$ and is waiting.
- Assignment Edge: A directed edge from a resource type $R_{j}$ to a process $P_{i}$ ( $R_{j} \to P_{i}$ ) signifies that an instance of $R_{j}$ has been allocated to $P_{i}$ .

How we interpret a cycle in the RAG depends on the number of instances of each resource.

If each resource type has only a single instance: A cycle in the RAG is a necessary and sufficient condition for deadlock. If you find a cycle, a deadlock exists. No cycle means no deadlock.
If resource types have multiple instances: A cycle is a necessary but not sufficient condition for deadlock. A cycle indicates the possibility of a deadlock, but the system might still be able to find a safe execution path.

The video below explains this distinction and demonstrates a systematic algorithm for detecting deadlocks in a multi-instance RAG, which is a common scenario in GATE problems.

L-4.3: Multi-Instance Resource Allocation Graph with Example | Operating System

This Gate Smashers video provides a clear, step-by-step method for analyzing multi-instance Resource Allocation Graphs, a crucial skill for GATE.

Pay close attention to these parts of the video: The Core Problem: Watch the introduction to understand why detecting deadlock in multi-instance RAGs is more complex than in single-instance ones. This is covered from the start. Systematic Detection Method: Observe how the graph is converted into Allocation and Request tables, and how the Current Availability is used to simulate process execution. This is demonstrated from this section. Key Theoretical Point: The video clearly summarizes the crucial difference between single-instance and multi-instance systems regarding cycles. This is a vital takeaway for theory questions, explained from this summary. GATE-Style Example: Follow the detailed walkthrough of a complex, GATE-level problem from this example. Try to build the Allocation and Request tables yourself as you watch. Final Conclusion: The video ends by reinforcing the necessary vs. sufficient conditions. Make sure you understand this point from the conclusion.

As you saw in the video, the deadlock detection algorithm for multi-instance RAGs works as follows:

From the RAG, construct the Allocation matrix (what each process holds), the Request matrix (what each process wants), and the Available vector (what resources are free).
Look for a process that is not blocked, meaning its requests can be satisfied by the currently available resources.
If such a process is found, assume it runs to completion and releases all its allocated resources. Add these released resources back to the Available vector.
Repeat this process. If all processes can run to completion, there is no deadlock. If you reach a point where no remaining process can have its request fulfilled, then the system is in a deadlock, and the remaining processes are part of it.

Deadlock Avoidance: The Banker's Algorithm

While detection is useful, it's a reactive approach. A proactive approach is deadlock avoidance, where the OS ensures it never enters an unsafe state. An unsafe state is one that might lead to a deadlock. A safe state is one where there is at least one sequence of process execution (a "safe sequence") that allows all processes to complete without deadlocking.

The classic algorithm for deadlock avoidance is the Banker's Algorithm. It's named after the analogy of a banker who has a fixed amount of capital and must decide whether to grant loans to customers. Each customer has a pre-stated credit limit (maximum need), and the banker must ensure that they never allocate their cash in such a way that they cannot satisfy the needs of all their customers.

The Banker's Algorithm requires that each process declare its maximum resource needs in advance. It then operates in two parts:

Safety Algorithm: This determines if the current system state is safe.
Resource-Request Algorithm: When a process requests resources, this algorithm determines if granting the request immediately will leave the system in a safe state.

The following video provides an exceptionally clear, numerical walkthrough of both parts of the Banker's Algorithm. This is exactly the type of problem you can expect in the GATE exam.

Lec24 Deadlock Avoidance: Bankers(Resource Request Algorithm) with example |Operating System

This lecture from Jenny's Lectures CS IT breaks down the Banker's Algorithm into manageable steps with a detailed numerical example, covering both safety checking and resource requests.

To master this algorithm, study the video in stages: Calculating the Need Matrix: The first step is always to calculate how many more resources each process might still need. Understand this simple but crucial calculation from this section. The formula is: Need = Maximum - Allocation. The Safety Algorithm: Watch carefully as the algorithm is applied to find a safe sequence. The core idea is to find a process whose Need can be satisfied by the Available resources, execute it, and add its Allocation to the Available pool. Follow the step-by-step process from this walkthrough. The Resource-Request Algorithm (Part 1 - Safe Request): This is the most critical part. See how the system handles a new request from a process. It involves three steps: checking if the request is valid (Request <= Need), checking if resources are available (Request <= Available), and then "pretending" to grant the request and running the safety algorithm to see if the resulting state is safe. This example shows a request that is safely granted. Watch from this demonstration. The Resource-Request Algorithm (Part 2 - Unsafe Request): Now watch an example where granting a request would lead to an unsafe state. This demonstrates why the Banker's Algorithm is so powerful—it denies the request to avoid potential deadlock, even if the resources are technically available at that moment. This is explained from this part. Formal Steps: Finally, review the formal summary of the algorithm's steps from this recap.

To summarize the logic from the video:

To check if a request from process $P_{i}$ can be granted:

Check if Request_i <= Need_i. If a process requests more than it declared it would ever need, this is an error.
Check if Request_i <= Available. If the resources aren't free, the process must wait.
If both are true, simulate the allocation:
- Available = Available - Request_i
- Allocation_i = Allocation_i + Request_i
- Need_i = Need_i - Request_i
Run the Safety Algorithm on this new, hypothetical state.
If the safety algorithm finds a safe sequence, the state is safe. Grant the request and commit to the new state.
If the state is found to be unsafe, deny the request and roll back the changes from step 3. The process $P_{i}$ must wait.

Conclusion

In this lesson, we demystified the concept of deadlock, a critical challenge in concurrent systems. You are now equipped with the analytical tools to handle this topic for the GATE exam.

Here are the main takeaways:

Deadlock requires four simultaneous conditions: Mutual Exclusion, Hold and Wait, No Preemption, and Circular Wait.
Resource Allocation Graphs (RAGs) are used to visualize the system state. For single-instance resources, a cycle guarantees a deadlock. For multi-instance resources, a cycle is a necessary but not sufficient condition; you must use a detection algorithm.
The Banker's Algorithm is a deadlock avoidance strategy that ensures the system always stays in a safe state. It uses the Safety Algorithm to check if a state is safe and the Resource-Request Algorithm to decide whether to grant new resource requests.

We've now covered how to manage processes that share resources and contend for them. In our next lesson, we will shift our focus to another fundamental OS task: CPU Scheduling. We'll explore various algorithms (like FCFS, SJF, Round Robin, and Priority Scheduling) that the operating system uses to decide which of the many ready processes gets to run on the CPU, and how these choices impact system performance metrics like turnaround time and waiting time.

Recommended resources

The Four Horsemen of Deadlock

Detecting Deadlock with Resource Allocation Graphs

Deadlock Avoidance: The Banker's Algorithm

Conclusion