Deadlocks: Conditions and Prevention
A deadlock occurs when a set of processes are each waiting for a resource held by another in the set — and none can make progress. The classic example: four philosophers sitting around a table, each holding one fork, waiting for the fork on their right.
The Four Necessary Conditions (Coffman)
A deadlock can only occur if all four of these conditions hold simultaneously:
- Mutual exclusion — at least one resource cannot be shared (e.g., a printer can only be used by one process 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 — a resource cannot be forcibly taken away from a process; it must be released voluntarily.
- Circular wait — there is a set of processes such that each is waiting for a resource held by the next in the cycle.
Prevention: Breaking One Condition
If you can ensure that at least one condition is never true, deadlocks are impossible.
| Strategy | Which condition it breaks | How |
|---|---|---|
| No hold-and-wait | Break #2 | Require processes to request all resources at once before starting. If not all are available, wait. |
| Allow preemption | Break #3 | When a process requests a resource that is held, preempt the holder's resources. |
| Resource ordering | Breaks #4 | Impose a total ordering on resource types. Processes must request resources in increasing order. |
| One resource per type | Breaks #4 | Ensure each resource type has exactly one instance; then circular wait is impossible. |
Avoidance: The Banker's Algorithm
Instead of prevention, a system can avoid deadlocks by checking whether granting a resource request could potentially lead to an unsafe state. The Banker's Algorithm works as follows:
- The system knows the maximum demand of each process.
- When a process requests resources, the system simulates the allocation.
- If the resulting state is "safe" (there exists a sequence in which all processes can complete), the request is granted.
- If the state is "unsafe," the request is delayed.
This approach is conservative — it may deny requests that would not actually deadlock — but it guarantees safety if the demand estimates are accurate.
Detection and Recovery
Some systems allow deadlocks to occur and then recover from them:
- Detection — Periodically check for cycles in the resource allocation graph. If a cycle exists, there may be a deadlock.
- Recovery — Options include:
- Kill processes in the cycle
- Preempt resources from processes
- Pay a cost (rollback)
Real-World Considerations
Most operating systems (including Linux) do not implement full deadlock prevention or avoidance for general resources. Instead, they rely on:
- Lock ordering — a coding convention that breaks circular wait
- Locks with timeouts —
pthread_mutex_timedlock()gives up after a deadline instead of blocking forever - Deadlock detection tools — like
lockdepin Linux, which instruments locks to detect potential deadlocks at runtime
References
This article is part of the Advanced Networking and Performance learning path.