Deadlock
Understanding resource competition, the four necessary conditions, and strategies for handling deadlocks in modern systems.
What is a Deadlock?
In a multi-programming environment, several processes compete for a finite number of resources. When a process requests a resource, if that resource is not available because it is currently allocated to another process, the requesting process enters a waiting state.
Sometimes, that waiting process is never able to change its state because the resource it has requested is busy (and remains busy forever). When a set of processes are in this state, it is called a Deadlock.
Core Definitions
"Deadlock is a situation in a computer environment where a set of processes get permanently stuck because each process is waiting for a resource held by another process, and none of them can proceed."
"Deadlock is a bug present in the process/thread synchronization method."
System Resources
A resource can be physical hardware or logical entities that a process requests to execute. Examples of resources include:
- Memory space
- CPU cycles
- Files
- Locks (Mutexes/Semaphores)
- Sockets
- I/O devices (Printers, Keyboards, etc.)
⭐ Resource Instance Property: A single resource type can have multiple instances. For example, the CPU is a resource type, and a multi-core system has multiple CPU instances.
Resource Utilization Lifecycle
Under normal operation, a process or thread utilizes a resource by following this sequence:
- Request: The process requests the resource. If the resource is free, the request is granted. If the resource is currently allocated to another process, the requesting process enters a waiting state.
- Allocate (Use): The process successfully acquires the resource and utilizes it (e.g., executing on a CPU, writing to a file, sending data over a socket).
- Release: Once execution is completed, the process releases the resource, making it available for other waiting processes.
Graph Representations
In system modeling (Resource Allocation Graphs), requests and assignments are represented by directed edges:
Deadlock Necessary Conditions
A deadlock state can arise if and only if the following four conditions hold simultaneously in a system. Click each condition below to explore its details, real-world analogy, and prevention strategy:
Interactive Deadlock Simulator
Simulate processes requesting and releasing resources to see how cycles are formed and resolved.
Methods for Handling Deadlock
Operating systems use different strategies depending on application constraints and execution overhead. Click the tabs below to explore the three standard deadlock handling techniques:
Prevention & Avoidance (Ensuring Safe State)
This strategy ensures that the system never enters a deadlock state.
- Prevention: Statically design rules that prevent at least one of the 4 necessary conditions from occurring. E.g., preventing circular wait by ordering all resources.
- Avoidance: The system dynamically tracks resources and requests (using algorithms like the Banker's Algorithm) to ensure that granting a resource cannot lead to an unsafe state.
Deadlock Prevention
The goal of Deadlock Prevention is to design system protocols such that at least one of the 4 necessary conditions is never satisfied. If we can guarantee this, a deadlock is mathematically impossible.
1. Eliminating Mutual Exclusion
This rule mandates using locks (mutual exclusion) only for non-shareable resources.
- Shareable Resources: Resources like Read-Only files do not require exclusive access and can be read by multiple processes/threads concurrently.
- Limitations: We cannot completely prevent deadlocks by denying the Mutual Exclusion condition, because some resources (like printers or locks) are intrinsically non-shareable.
2. Eliminating Hold & Wait
To ensure this condition never occurs, the OS must guarantee that whenever a process requests a resource, it does not hold any other resource.
Each process must request and be allocated all its required resources before starting execution.
Allow a process to request a resource only when it has no resources allocated. If it requires additional resources, it must release all currently allocated resources first.
3. Eliminating No Preemption
If resources can be preempted (taken away forcefully), then deadlocks can be broken. The system follows these protocols:
- If a process currently holding some resources requests another resource that cannot be immediately allocated, all the resources the process is currently holding are preempted (released). The process is suspended and will restart only after it regains all of its previously held and newly requested resources.
- When a process requests a resource, we first check its availability. If it is not available (because it is held by another process), we check if the holder process is itself waiting for additional resources. If so, we **preempt the desired resource from the waiting process** and allocate it to the requesting process.
4. Eliminating Circular Wait
To ensure this condition never occurs, the OS can impose a total ordering on all resource allocations.
If Processes P1 and P2 both require resources R1 and R2, locking on these resources should be designed such that both processes try to lock R1 first, and then R2. Since P1 and P2 attempt to acquire locks in the exact same sequence, a circular wait cycle cannot form.
Deadlock Avoidance
Deadlock Avoidance is a dynamic strategy where the OS monitors the resource allocation state to ensure the system never enters an unsafe state that could potentially lead to a deadlock.
⚠️ Core Principle: Unsafe State ≠ Deadlock, but it can lead to one.
Safe State
A state is safe if the system can allocate resources to each process in some sequence (Safe Sequence) and still avoid a deadlock.
Unsafe State
A state where the system cannot guarantee that a deadlock will not occur. An unsafe state is not a deadlock, but it gives processes the opportunity to request resources that can trigger a deadlock.
How it Works
To make allocation decisions, the OS needs to anticipate competition. The OS must continuously know:
Based on these metrics (number of processes, maximum resource demand per process, current allocations, and maximum available resource instances), the OS decides:
If granting request leads to Unsafe State → Denied (Wait) ✗
▶Banker's Algorithm
A classic deadlock avoidance algorithm designed for systems with multiple resource instances. It determines if a resource request can be safely granted by simulating the allocation and checking if a safe sequence exists.
Go to Step-by-Step Solver ↓Banker's Algorithm (Safety Solver)
The Banker's Algorithm is a deadlock avoidance and safety testing algorithm. It simulates the allocation of resources and checks if the system will remain in a Safe State.
To execute this algorithm, the OS must know:
Interactive Step-by-Step Solver
Total Resources: A = 10, B = 5, C = 7
| Process | Allocated (A B C) | Max Need (A B C) | Remaining Need (A B C) | Status |
|---|---|---|---|---|
| P1 | 0 1 0 | 7 5 3 | 7 4 3 | Waiting |
| P2 | 2 0 0 | 3 2 2 | 1 2 2 | Waiting |
| P3 | 3 0 2 | 9 0 2 | 6 0 0 | Waiting |
| P4 | 2 1 1 | 4 2 2 | 2 1 1 | Waiting |
| P5 | 0 0 2 | 5 3 3 | 5 3 1 | Waiting |
Initial state. Available resources are [3, 3, 2]. Safe Sequence is empty.
Deadlock Detection & Recovery
If a system has not implemented deadlock prevention or deadlock avoidance, a deadlock state may occur. In this case, the system must employ Deadlock Detection and Recovery algorithms to run periodically.
OS Deadlock Detection Loop
If no deadlock is found, the system continues operating and schedules the next run.
Detection Algorithms
a) Single Instance of Each Resource Type
For systems where each resource type has only one instance, the OS uses the Wait-For Graph method.
We construct a Wait-For Graph by removing the Resource nodes from the Resource Allocation Graph (RAG). If process P1 is waiting for resource R1, which is currently held by process P2, we draw a direct edge P1 → P2.
👉 Detection Rule: Once the Wait-For Graph is created, if a cycle is found, a deadlock exists.
b) Multiple Instances of Resource Types
If resources have multiple instances, wait-for graphs are insufficient. In this case, the OS uses Banker's Algorithm to run safety tests periodically. If the algorithm determines that no safe execution sequence exists:
Recovery from Deadlock
Once a deadlock is detected, the OS recovers using one of the following methods:
a) Process Termination
Ending the deadlocked processes to release their locked resources:
- Abort all deadlocked processes: Immediately breaks the deadlock but discards all progress of these processes.
- Abort processes one-by-one: Suspend one process at a time and re-run the detection algorithm until the deadlock cycle is broken.
b) Resource Preemption
Taking resources away from processes and reallocating them to others:
Successively preempt (reclaim) some resources from processes and give these resources to other active processes until the deadlock cycle is broken.
OS Architect Deadlock Challenge
Test your understanding of the core concepts in this chapter. Step into the shoes of an Operating System Architect and make design decisions to resolve deadlocks.