OS Notes
Understanding deadlocks in operating systems — what they are, why they occur, real-world examples, system model, and overview of handling strategies including prevention, avoidance, and detection.
Introduction
Picture four cars arriving simultaneously at a four-way intersection with no traffic lights. Each car wants to go straight, but they are all blocking each other. No car can move forward because the car to its right is in the way. Nobody can back up because cars behind them have also entered the intersection. Everyone is stuck permanently. This is a deadlock.
In operating systems, a deadlock occurs when two or more processes are waiting for resources held by each other, creating a circular chain of dependencies that can never be resolved. None of the processes can proceed because each is waiting for the other to release a resource first. Without external intervention, the deadlock persists forever.
Formal Definition
A set of processes is in a deadlock state when every process in the set is waiting for an event that can only be caused by another process in the same set. Since all processes are waiting, none can cause the events that would wake up the others.
A Simple Example
Consider two processes and two resources (a printer and a scanner):
P1 holds the printer and waits for the scanner. P2 holds the scanner and waits for the printer. Neither can proceed. This is deadlock.
// Deadlock scenario in code
// Thread 1
pthread_mutex_lock(&printer_lock); // Acquires printer
sleep(1); // Context switch happens here
pthread_mutex_lock(&scanner_lock); // BLOCKED — Thread 2 has it!
// ... use both ...
pthread_mutex_unlock(&scanner_lock);
pthread_mutex_unlock(&printer_lock);
// Thread 2
pthread_mutex_lock(&scanner_lock); // Acquires scanner
sleep(1); // Context switch happens here
pthread_mutex_lock(&printer_lock); // BLOCKED — Thread 1 has it!
// ... use both ...
pthread_mutex_unlock(&printer_lock);
pthread_mutex_unlock(&scanner_lock);System Model
To formally analyze deadlocks, we define a system model:
Resources: R1, R2, ..., Rm (CPU cycles, memory, I/O devices, files, semaphores) Each resource type Ri has Wi instances (e.g., a system might have 3 printers, 2 tape drives)
Processes: P1, P2, ..., Pn
Each process uses resources in this sequence:
- Request — Ask for the resource. If not available, wait.
- Use — Operate on the resource.
- Release — Free the resource for others.
Real-World Deadlock Examples
Example 1: Database Transactions
Two transactions updating bank accounts:
- Transaction T1: Transfer from Account A to B (locks A, then needs B)
- Transaction T2: Transfer from Account B to A (locks B, then needs A)
Both deadlock if they acquire their first lock simultaneously.
Example 2: Traffic Gridlock
A real physical deadlock occurs in cities when cars fill an intersection from all four directions. New York City has "Don't Block the Box" laws specifically to prevent this deadlock condition.
Example 3: Dining Philosophers
Five philosophers sit at a round table with five chopsticks. Each needs two chopsticks to eat. If all five simultaneously pick up their left chopstick, nobody can get a right chopstick — deadlock!
Example 4: Disk and Memory
Process A holds 80% of memory and needs the disk. Process B holds the disk and needs more memory. Neither can proceed.
Deadlock vs Starvation vs Livelock
It is important to distinguish deadlock from similar-sounding problems:
| Condition | Description | Example |
|---|---|---|
| Deadlock | Processes permanently blocked waiting for each other | P1 waits for P2, P2 waits for P1 |
| Starvation | Process waits indefinitely because others keep getting resources | Low-priority process never scheduled |
| Livelock | Processes keep changing state but make no progress | Two people in corridor keep stepping aside for each other |
In starvation, the waiting process could eventually run if circumstances change. In deadlock, no amount of waiting will resolve the situation without intervention.
Four Strategies for Handling Deadlocks
Operating systems can handle deadlocks in four ways, ranging from proactive to reactive:
1. Deadlock Prevention
Ensure that at least one of the four necessary conditions can never hold. Design the system so deadlocks are structurally impossible. Conservative but may reduce resource utilization.
2. Deadlock Avoidance
Allow resources to be requested dynamically but make careful allocation decisions to ensure the system never enters an unsafe state. Requires advance knowledge of resource needs (Banker's Algorithm).
3. Deadlock Detection and Recovery
Allow deadlocks to occur, but detect them when they happen and take action to recover (kill a process, preempt resources). Used when deadlocks are rare and prevention is too costly.
4. Ignore the Problem (Ostrich Algorithm)
Pretend deadlocks do not exist. If the cost of prevention exceeds the cost of occasional deadlocks (which can be resolved by rebooting), simply ignore the problem. This is what most desktop operating systems (Windows, Linux) actually do for many resource types.
Why Studying Deadlocks Matters
You might think deadlocks are rare. In reality, they are more common than you would expect:
- Database systems handle deadlocks constantly (detected and resolved automatically)
- Multi-threaded programs are notorious for deadlock bugs
- Distributed systems face deadlocks across network boundaries (much harder to detect)
- The 2003 Northeast blackout (affecting 55 million people) was partly caused by a software race condition similar to deadlock
Understanding deadlocks helps you write correct concurrent programs and design systems that handle resource contention gracefully.
Key Takeaways
- Deadlock occurs when processes form a circular wait for resources held by each other
- Deadlock is permanent — it will never resolve without external intervention
- The system model defines resources with instances and processes that request, use, and release them
- Deadlock differs from starvation (indefinite waiting) and livelock (activity without progress)
- Four handling strategies exist: prevention, avoidance, detection/recovery, and ignoring
- Most general-purpose OS use a combination of strategies for different resource types
- Understanding deadlocks is essential for writing correct concurrent and distributed software
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Introduction to Deadlocks.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Operating Systems topic.
Search Terms
operating-systems, operating systems, operating, systems, deadlocks, deadlock, introduction, introduction to deadlocks
Related Operating Systems Topics