Introduction
Deadlock prevention and deadlock avoidance are two proactive strategies that stop deadlocks from ever occurring, in contrast to detection-and-recovery which lets them happen and cleans up afterward. Prevention works by structurally guaranteeing that at least one of the four Coffman conditions can never hold. Avoidance is more dynamic: it allows all four conditions to be possible in principle, but uses runtime information about maximum future resource claims to ensure the system never enters an unsafe state. The most famous avoidance algorithm is Dijkstra's Banker's Algorithm.
Cricket analogy: Prevention is like a league rule that permanently bans any team from holding one ground while requesting another, structurally ruling out gridlock; avoidance is more like a scheduler that lets teams hold and request grounds freely but only approves a fixture if every team's declared maximum ground needs can still be met safely, as in Dijkstra's Banker's Algorithm.
Explanation
Prevention techniques target one condition each: to break Mutual Exclusion, make resources shareable where possible (not always feasible, e.g. printers). To break Hold and Wait, require a process to request all resources it will ever need at once, or release all held resources before requesting more. To break No Preemption, allow the OS to preempt resources from a waiting process and give them to a requesting one, then restart the process later with the resource. To break Circular Wait, impose a strict total ordering on resource types and require every process to request resources in strictly increasing order. Avoidance, by contrast, requires each process to declare its maximum resource demand in advance. The Banker's Algorithm then simulates resource allocation and only grants a request if the resulting state is 'safe' — meaning there exists some ordering of process completions where every process can eventually get its maximum need satisfied using currently available plus released resources.
Cricket analogy: To break Circular Wait, a board can impose a strict order on ground bookings so every team must request grounds in increasing order, while an avoidance scheme like the Banker's Algorithm requires each team to declare its maximum ground needs upfront and only grants a booking if a safe completion order for all teams still exists.
Example — Banker's Algorithm Safety Check
Resource types: A, B, C Processes: P0..P4
Available = [3, 3, 2]
Allocation Max Need = Max - Allocation
A B C A B C A B C
P0 0 1 0 7 5 3 7 4 3
P1 2 0 0 3 2 2 1 2 2
P2 3 0 2 9 0 2 6 0 0
P3 2 1 1 2 2 2 0 1 1
P4 0 0 2 4 3 3 4 3 1
Safety algorithm (Work = Available, Finish[i] = false for all i):
Step 1: Work = [3,3,2]
Try P1: Need[1]=[1,2,2] <= Work? yes
Work = Work + Allocation[1] = [3,3,2]+[2,0,0] = [5,3,2]; Finish[P1]=true
Step 2: Try P3: Need[3]=[0,1,1] <= Work[5,3,2]? yes
Work = [5,3,2]+[2,1,1] = [7,4,3]; Finish[P3]=true
Step 3: Try P4: Need[4]=[4,3,1] <= Work[7,4,3]? yes
Work = [7,4,3]+[0,0,2] = [7,4,5]; Finish[P4]=true
Step 4: Try P0: Need[0]=[7,4,3] <= Work[7,4,5]? yes
Work = [7,4,5]+[0,1,0] = [7,5,5]; Finish[P0]=true
Step 5: Try P2: Need[2]=[6,0,0] <= Work[7,5,5]? yes
Work = [7,5,5]+[3,0,2] = [10,5,7]; Finish[P2]=true
All processes finished => system is in a SAFE state.
Safe sequence: <P1, P3, P4, P0, P2>Analysis
The trace above shows the Safety Algorithm, the core building block of the Banker's Algorithm. Whenever a process requests additional resources, the Resource-Request Algorithm first pretends to grant the request (temporarily updating Available, Allocation, and Need), then re-runs this exact Safety Algorithm. If a safe sequence still exists after the pretend-allocation, the request is granted for real; if no safe sequence can be found, the requesting process must wait, and the state is rolled back. In our example, the safe sequence P1 -> P3 -> P4 -> P0 -> P2 proves that no matter what order processes eventually make their maximum claims, the system has a way to satisfy everyone without deadlock, so granting requests that preserve this kind of safe state is always deadlock-free.
Cricket analogy: Before confirming a new ground booking, a scheduler using the Safety Algorithm pretends to grant it, updates the availability tally, and re-checks whether a safe sequence still exists across all teams; the sequence P1 -> P3 -> P4 -> P0 -> P2 shows every team can eventually get its grounds, so the pretend-booking is confirmed for real.
Key Takeaways
- Prevention structurally eliminates one of the four Coffman conditions (e.g., strict resource ordering to break circular wait).
- Avoidance is dynamic: it uses declared maximum claims and the Banker's Algorithm to only permit requests that keep the system in a safe state.
- A safe state is one where at least one safe sequence of process completions exists; an unsafe state does not necessarily mean deadlock, but risks it.
- The Safety Algorithm has complexity O(m x n^2) for n processes and m resource types, since it may scan all processes up to n times.
- Prevention tends to reduce resource utilization and concurrency; avoidance offers better utilization but requires advance knowledge of maximum claims, which is often impractical.
Practice what you learned
1. Which deadlock-prevention technique directly targets the 'Circular Wait' condition?
2. In the Banker's Algorithm, what does 'Need' represent for a process?
3. In the worked example, what is the first process the Safety Algorithm can satisfy given Available = [3,3,2]?
4. What does it mean if the system is in an 'unsafe' state?
5. What is a key practical limitation of the Banker's Algorithm in real operating systems?
Was this page helpful?
You May Also Like
Deadlock Conditions
The four necessary conditions (Coffman conditions) that must hold simultaneously for a deadlock to occur.
Deadlock Detection and Recovery
Letting deadlocks occur, detecting them via cycle/graph algorithms, and recovering through termination or preemption.
Introduction to Deadlocks
Get a high-level preview of what deadlock is and the four necessary conditions that must all hold for it to occur.
OS Design Tradeoffs
A grounded look at the core engineering tradeoffs behind major operating system design decisions.