Deadlock Avoidance
Admit a request only if the resulting state is safe. Banker's algorithm is the classic.
Level: advanced
What is it?
Deadlock avoidance evaluates resource requests against the current allocation and declared future needs. The OS grants a request only if the hypothetical post-allocation state remains safe: there is some sequence in which each process can obtain its remaining resources, finish, and release what it holds.
Why does it matter?
A locally valid allocation can create a globally unsafe state. Avoidance preserves a possible completion order, but requires useful knowledge of maximum demands and adds decision cost at allocation time.
Mental model
A state is safe when you can write a finish order for every process under the available resources and its declared remaining need. Unsafe means no such proof is available; it does not mean a deadlock already exists.
How it works
- Available counts currently free instances of each resource type.
- Need is often computed as Max minus Allocation when the classic Banker model is used.
- Safety testing repeatedly finds a process whose remaining need fits the current work vector, then assumes it finishes and releases its allocation.
- A safe state has at least one completion sequence; an unsafe state may or may not be deadlocked now.
- Avoidance is practical only when maximum claims and resource models are sufficiently predictable.
Steps
- Start with Available and each process's Need and Allocation vectors.
- Find a process whose Need is less than or equal to the current Work vector in every resource dimension.
- Assume it finishes and add its Allocation to Work; record the process in the safe sequence.
- Repeat until all processes finish (safe) or no unfinished process qualifies (unsafe).
Real-world usage
- Solving Banker's algorithm tables and safe-sequence questions.
- Understanding admission control and reserved-capacity trade-offs.
- Explaining why a request can be denied even when enough resource units are currently free.
Common mistakes
- Equating unsafe with already deadlocked.
- Comparing resource vectors component-wise incorrectly.
- Adding Need back to Work when a process finishes; the newly available resources are its Allocation.
Interview questions
What does a safe state guarantee?
There exists an order in which every process can finish using currently available resources plus resources released by earlier completed processes.
Why might a request be denied even if Available is large enough now?
Granting it may leave a state with no safe completion sequence, so future progress cannot be guaranteed under the declared maximum demands.