Whether you’re a student just starting to learn about operating systems or someone gearing up
for interviews, knowing how deadlock occurs and how to handle it can really give you an advantage.
If you’re eager to master operating system concepts and get hands-on experience with
real projects, don’t miss the Data Structures and Operating Systems Course in Noida offered by
Uncodemy.
What is Deadlock?
A deadlock is a situation in which two or more processes are waiting indefinitely for an event that can only be caused by one of the waiting processes. In simpler terms, each process holds a resource that another process needs, and none can proceed.
Real-World Analogy: Two cars at a narrow bridge, each waiting for the other to move. Neither can proceed until one reverses — a classic deadlock.
Key Points:
- Deadlock is a stable state; without intervention, the system remains stuck.
- It differs from starvation: in deadlock, no process makes progress; in starvation, some processes proceed while others wait indefinitely.
The Four Necessary Conditions (Coffman Conditions)
Deadlock can occur only if all four of the following conditions hold simultaneously:
- Mutual Exclusion: At least one resource must be held in a non-sharable mode (only one process can use it at a time).
- Hold and Wait: A process holding at least one resource is waiting to acquire additional resources held by other processes.
- No Preemption: Resources cannot be forcibly taken away; they can only be released voluntarily by the holding process.
- Circular Wait: A circular chain of two or more processes exists, where each process waits for a resource held by the next process in the chain.
If any one of these conditions is broken, deadlock cannot occur. This is the basis for many deadlock handling techniques.
Resource Allocation Graph
A resource allocation graph is a directed graph that models the state of processes and resources. It has two types of nodes: process nodes (circles) and resource nodes (rectangles). Edges represent requests and assignments.
- A cycle in the graph indicates a potential deadlock. If each resource has a single instance, a cycle means deadlock exists. If resources have multiple instances, a cycle indicates a possible deadlock.
- Deadlock detection algorithms often use this graph to identify cycles.
Deadlock vs Starvation
Deadlock and starvation are often confused but are distinct:
- Deadlock: No process in the set can proceed; the system is frozen. All resources are held, and no progress is possible.
- Starvation: Some processes proceed while others wait indefinitely. The system is not frozen, but fairness is violated. Starvation can end (e.g., via aging) while deadlock cannot resolve itself.
In short: Deadlock implies starvation, but starvation does not imply deadlock.
Deadlock Handling Strategies
Operating systems use four main approaches to deal with deadlock:
- Prevention: Design the system so that at least one of the four Coffman conditions cannot hold.
- Avoidance: Dynamically examine resource requests and ensure the system never enters an unsafe state (e.g., Banker's algorithm).
- Detection and Recovery: Allow deadlock to occur, detect it, then recover by aborting or rolling back processes.
- Ostrich Algorithm: Ignore the problem, assuming deadlocks are rare. Many general-purpose OSes (like Linux and Windows) use this for performance reasons.
Deadlock Prevention
Prevention works by ensuring that at least one necessary condition is never satisfied:
- Break Mutual Exclusion: Make resources sharable when possible (e.g., read-only files). Often impractical for hardware resources.
- Break Hold and Wait: Require processes to request all resources upfront. Or, release all held resources before requesting new ones. This can cause low resource utilization.
- Break No Preemption: Allow the OS to preempt resources. For example, if a process requests a resource held by another, the OS can force the holder to release it. This works for resources whose state can be saved and restored (e.g., CPU registers, memory pages) but not for printers or tape drives.
- Break Circular Wait: Impose a total ordering on resource types. Processes must request resources in increasing order. This is a practical and widely used method.
Deadlock Avoidance: Banker's Algorithm
Avoidance dynamically decides whether to grant a resource request based on the system's current state and the maximum future needs of processes. The system is kept in a "safe state" where there exists at least one sequence of process completions that avoids deadlock.
The Banker's algorithm (by Dijkstra) works as follows:
- Each process declares its maximum resource needs in advance.
- The OS tracks available, allocated, and needed resources.
- When a request arrives, the OS pretends to grant it and checks if the resulting state is safe (i.e., a safe sequence exists). If safe, the request is granted; otherwise, the process waits.
Example: Safe Sequence Check
Copy Code
// Banker's Algorithm - Safety Check (Pseudocode)
int available[RES];
int max[PROC][RES], alloc[PROC][RES], need[PROC][RES];
bool finish[PROC] = {false};
// Compute need = max - alloc
for (i = 0; i < PROC; i++)
for (j = 0; j < RES; j++)
need[i][j] = max[i][j] - alloc[i][j];
int work[RES];
for (j = 0; j < RES; j++) work[j] = available[j];
int count = 0;
while (count < PROC) {
bool found = false;
for (i = 0; i < PROC; i++) {
if (!finish[i]) {
bool possible = true;
for (j = 0; j < RES; j++)
if (need[i][j] > work[j]) { possible = false; break; }
if (possible) {
for (j = 0; j < RES; j++)
work[j] += alloc[i][j];
finish[i] = true;
found = true;
count++;
break;
}
}
}
if (!found) return UNSAFE;
}
return SAFE;
If the system is in a safe state, the request is granted; otherwise, it is denied, and the process waits.
Deadlock Detection and Recovery
Detection allows deadlock to happen, then periodically checks for it:
- Single Instance per Resource Type: Use a wait-for graph. A cycle indicates deadlock.
- Multiple Instances: Use a detection algorithm similar to Banker's safety algorithm.
Once detected, recovery options include:
- Process Termination: Abort all deadlocked processes, or abort one by one until deadlock is broken.
- Resource Preemption: Take resources from some processes and give them to others. This requires rollback to a safe state, which can be complex.
Code Example: Wait-For Graph Detection (C)
Copy Code
#include <stdio.h>
#include <stdbool.h>
#define P 5 // number of processes
int waitForGraph[P][P] = {
{0, 1, 0, 0, 0}, // P0 waits for P1
{0, 0, 1, 0, 0}, // P1 waits for P2
{0, 0, 0, 1, 0}, // P2 waits for P3
{1, 0, 0, 0, 0}, // P3 waits for P0
{0, 0, 0, 0, 0} // P4 not waiting
};
bool visited[P], recStack[P];
bool isCyclic(int v) {
if (!visited[v]) {
visited[v] = recStack[v] = true;
for (int i = 0; i < P; i++) {
if (waitForGraph[v][i]) {
if (!visited[i] && isCyclic(i)) return true;
else if (recStack[i]) return true;
}
}
}
recStack[v] = false;
return false;
}
bool detectDeadlock() {
for (int i = 0; i < P; i++)
if (isCyclic(i)) return true;
return false;
}
int main() {
if (detectDeadlock())
printf("Deadlock detected!\n");
else
printf("No deadlock.\n");
return 0;
}
Output:
Deadlock detected!
Advantages of Deadlock Handling
- Increases system reliability and stability.
- Prevents system hangs and unresponsiveness.
- Helps in designing robust concurrent systems.
- Essential for database systems, real-time systems, and distributed systems.
Limitations of Deadlock Handling
- Prevention and avoidance can lead to low resource utilization and reduced concurrency.
- Detection algorithms consume CPU time and memory.
- Recovery (process termination or rollback) can cause loss of work.
- The Banker's algorithm requires processes to declare maximum needs in advance, which is often impractical.
Applications of Deadlock Concepts
- Database management systems (transaction locking).
- Operating system kernels (resource allocation).
- Distributed systems (message passing and locking).
- Real-time systems (priority inversion and resource sharing).
- Concurrent programming (thread synchronization).
Best Practices to Avoid Deadlocks
- Always acquire locks in a consistent global order.
- Avoid holding multiple locks whenever possible.
- Use timeouts for lock acquisition to break potential deadlocks.
- Design with resource ordering in mind.
- Test concurrent code thoroughly with tools like Helgrind or ThreadSanitizer.
Related Advanced Concepts
Once you understand the basics, explore these related topics:
- Livelock and starvation.
- Priority inversion and priority inheritance.
- Distributed deadlock detection.
- Lock-free and wait-free algorithms.
These topics build on the same principles and are often asked in interviews.
To truly master these advanced concepts and elevate your skills, consider enrolling in the Operating Systems and DSA Course in Noida offered by Uncodemy.
Conclusion
Deadlock is a fundamental problem in concurrent systems. Understanding its causes, the four necessary conditions, and the various handling strategies is crucial for any serious programmer. Whether you choose prevention, avoidance, detection, or the ostrich approach, the key is to design systems that are robust and efficient.
Grasping deadlock concepts not only boosts your confidence but also prepares you for technical interviews and real-world system design challenges.
If you’re serious about mastering operating systems, start by solidifying your understanding of deadlock and then move on to more advanced topics.
Join Uncodemy’s Operating Systems Course in Noida to learn from industry professionals and work on real-time projects.
Frequently Asked Questions (FAQs)
Q1. What is deadlock in an operating system?
Deadlock is a situation where two or more processes wait indefinitely for resources held by each other, and none can proceed.
Q2. What are the four necessary conditions for deadlock?
Mutual exclusion, hold and wait, no preemption, and circular wait (Coffman conditions).
Q3. What is the difference between deadlock and starvation?
Deadlock: no process in the set can proceed. Starvation: some processes proceed while others wait indefinitely. Deadlock implies starvation, but not vice versa.
Q4. What is Banker's algorithm?
Banker's algorithm is a deadlock avoidance algorithm that checks whether granting a resource request keeps the system in a safe state.
Q5. How can deadlock be prevented?
By breaking one of the four Coffman conditions: avoid mutual exclusion, avoid hold and wait, allow preemption, or enforce resource ordering.
Q6. Does C have built-in deadlock handling?
No, C does not have built-in deadlock handling. You must implement it manually using locks, semaphores, and careful design.
