Deadlock Prevention and Avoidance
Learning Goals
- Explain how to break each of the four Coffman conditions to prevent deadlocks.
- Distinguish between deadlock prevention and deadlock avoidance.
- Define safe and unsafe states and understand the Banker's Algorithm data structures (Available, Max, Allocation, Need).
- Apply the Safety Algorithm and Resource-Request Algorithm to a multi-process system to determine safe allocations.
Deadlock Prevention vs. Avoidance: A Strategic Distinction
Before diving into the details, it is essential to understand the difference between prevention and avoidance:
| Aspect | Prevention | Avoidance |
|---|---|---|
| Approach | Ensure at least one of the four necessary conditions can never hold. | Ensure the system never enters an unsafe state. |
| When applied | At system design time — fixed strategy. | At runtime — decision made for each resource request. |
| Guarantee | Deadlock is impossible by design. | Deadlock is avoided as long as safety checks pass. |
| Cost | Low runtime overhead, but may cause low resource utilization. | Higher runtime overhead (must run the Safety Algorithm). |
| Knowledge required | No prior knowledge of future requests needed. | Requires advance knowledge of each process's maximum resource needs. |
| Typical usage | Simple embedded systems, database locking protocols. | Systems with known workloads (e.g., banking, transaction processing). |
Prevention is a static approach — you architect the system so deadlocks are structurally impossible. Avoidance is a dynamic approach — you allow the system to allocate resources freely, but you check every request against a safety criterion.
Part A: Deadlock Prevention — Breaking the Four Conditions
Since a deadlock requires all four conditions to hold simultaneously, we can prevent deadlocks by ensuring at least one condition can never occur.
Strategy 1: Breaking Mutual Exclusion
| Aspect | Detail |
|---|---|
| Idea | Make resources sharable wherever possible. |
| Method | Use spooling (Simultaneous Peripheral Operations On-Line) — instead of allocating the resource directly, a spool (buffer/queue) is used. Only the spooler daemon accesses the physical resource exclusively. |
| Example | Print jobs are spooled to disk; the printer daemon prints them one at a time. Each process "prints" instantly to the spool; no process ever waits for the printer directly. |
| Limitation | Not all resources can be made sharable. Mutex locks, tape drives, and certain hardware devices are inherently exclusive. |
| Key Trade-off | Spooling adds overhead (disk I/O, daemon process) but eliminates printer deadlocks. |
Strategy 2: Breaking Hold and Wait
| Aspect | Detail |
|---|---|
| Idea | A process must not hold resources while waiting for others. |
| Protocol 1 | A process requests all the resources it will ever need before execution begins. If all are available, they are granted; if not, the process waits and holds nothing. |
| Protocol 2 | A process releases all current resources before requesting new ones. It then re-requests everything it needs. |
| Example | A process that needs a printer, a tape drive, and a disk file must request all three at startup. It cannot ask for the printer first, then later ask for the tape drive. |
| Problems | Low resource utilization — resources may sit idle for long periods. Starvation possible — a process that needs many resources may wait indefinitely. |
Strategy 3: Breaking No Preemption
| Aspect | Detail |
|---|---|
| Idea | Allow the OS to forcibly take resources from a process. |
| Method | If a process requests a resource that is not available, the OS checks if the holding process is waiting for other resources. If so, the OS preempts the held resource and gives it to the requestor. The preempted process must later restart from a checkpoint/saved state. |
| Example | Process P₁ holds a tape drive and requests a printer (unavailable). P₂ holds the printer and requests a tape drive. The OS preempts the tape drive from P₁ and gives it to P₂. |
| Difficulty | Preemption is hard to implement for many resources (printer — what happens to the half-printed page?). Only resources whose state can be saved and restored are good candidates (CPU registers, memory pages). |
Strategy 4: Breaking Circular Wait
| Aspect | Detail |
|---|---|
| Idea | Impose a total ordering on resource types and require processes to request resources in increasing order. |
| Method | Assign each resource type a unique number (e.g., R₁ = 1, R₂ = 2, R₃ = 3). A process can request resource Rⱼ only if it holds no resource with a number greater than j. Alternatively, it must request resources in strictly increasing order. |
| Example | If a process needs a printer (R₁ order 2) and a tape drive (R₂ order 5), it must request R₁ first, then R₂. It cannot request R₂ first and then later request R₁. |
| Why it works | Circular wait requires a cycle: P₀ → R₁ → P₁ → R₂ → ... → Rₖ → P₀. With total ordering, if P₀ holds Rⱼ and requests Rₖ where j < k, and P₁ holds Rₖ and requests Rₘ where k > j, a cycle is impossible because resource numbers always increase along the chain. |
| Practical Use | Most real-world prevention. Used in many database systems and file system locks. Easier to implement than the other three strategies. |
Deadlock Prevention and Avoidance — Visual Walkthrough
Part B: Deadlock Avoidance — The Banker's Algorithm
Deadlock avoidance requires knowledge of future resource needs. For each process, the system must know in advance the maximum number of instances of each resource type that the process may need.
Safe vs. Unsafe States
A state is safe if the system can allocate resources to each process in some order and still avoid deadlock. More formally, a state is safe if there exists a safe sequence <P₁, P₂, ..., Pₙ> such that for each Pᵢ, the resources that Pᵢ can still request can be satisfied by the currently available resources plus the resources held by all Pⱼ (where j < i).
| State | Meaning | Can deadlock occur? |
|---|---|---|
| Safe | There exists at least one sequence where all processes can finish. | No — deadlock cannot occur. |
| Unsafe | No such safe sequence exists. | Possibly — deadlock may occur if processes request resources in a certain order. |
| Deadlock | Processes are actually blocked. | Yes — deadlock has occurred. |
Key Insight: An unsafe state is not necessarily a deadlock. It means we cannot guarantee that deadlock will be avoided. An unsafe state may lead to deadlock later, depending on future requests.
This state diagram shows how the system transitions between Safe, Unsafe, and Deadlock states. Notice that Deadlock can only be reached through an Unsafe state, and Recovery is required to return to a Safe state.
Data Structures
The Banker's Algorithm uses four data structures (for a system with n processes and m resource types):
| Structure | Notation | Description | Size |
|---|---|---|---|
| Available | Available[m] | Number of available instances of each resource type | Vector of length m |
| Max | Max[n][m] | Maximum demand of each process | n × m matrix |
| Allocation | Allocation[n][m] | Number of instances currently allocated to each process | n × m matrix |
| Need | Need[n][m] | Remaining need of each process = Max − Allocation | n × m matrix |
Applying the Banker's Algorithm — Complete Worked Example
- 1Step 1
Consider a system with 3 processes (P₀, P₁, P₂) and 2 resource types (R₀ has 10 instances, R₁ has 5 instances). The current snapshot shows: Allocation = P₀: (0,1), P₁: (2,0), P₂: (3,0). Max = P₀: (7,5), P₁: (3,2), P₂: (9,0). Available = (5, 3, 2)? No — let's calculate: Total R₀ = 10, Total R₁ = 5. Allocation sums: R₀ = 0+2+3 = 5, R₁ = 1+0+0 = 1. Available = (10−5, 5−1) = (5, 4).
- 2Step 2
Need = Max − Allocation. For P₀: Need = (7−0, 5−1) = (7, 4). For P₁: Need = (3−2, 2−0) = (1, 2). For P₂: Need = (9−3, 0−0) = (6, 0). So Need = P₀: (7,4), P₁: (1,2), P₂: (6,0). Available = (5, 4).
- 3Step 3
Check each process: P₁'s Need (1,2) ≤ Available (5,4) → P₁ can finish. After P₁ finishes, release its Allocation (2,0): Available becomes (5+2, 4+0) = (7, 4). Now P₀'s Need (7,4) ≤ Available (7,4) → P₀ can finish. After P₀, release (0,1): Available = (7+0, 4+1) = (7, 5). Now P₂'s Need (6,0) ≤ Available (7,5) → P₂ can finish. Safe sequence: <P₁, P₀, P₂>.
- 4Step 4
Suppose P₁ requests (1, 0) more resources. First, check Request ≤ Need: (1,0) ≤ (1,2) ✓. Then check Request ≤ Available: (1,0) ≤ (5,4) ✓. Pretend to grant the request: Allocation P₁ becomes (2+1, 0+0) = (3, 0). Need P₁ becomes (1−1, 2−0) = (0, 2). Available becomes (5−1, 4−0) = (4, 4).
- 5Step 5
Now run the Safety Algorithm on the new state. Available = (4,4). P₁'s Need (0,2) ≤ (4,4) ✓ → P₁ finishes → Available = (4+3, 4+0) = (7,4). P₀'s Need (7,4) ≤ (7,4) ✓ → P₀ finishes → Available = (7+0, 4+1) = (7,5). P₂'s Need (6,0) ≤ (7,5) ✓ → P₂ finishes. Safe sequence <P₁, P₀, P₂> still exists. Therefore the request (1,0) from P₁ can be granted.
- 6Step 6
What if instead, P₀ requests (5, 3) more? Check: (5,3) ≤ Need P₀ (7,4) ✓? No — (5,3) > (7,4) for R₁ (3 > 4)? Actually this is valid for R₁? Let's re-check: P₀ Need = (7,4). Request (5,3): 5 ≤ 7 ✓, 3 ≤ 4 ✓. Check (5,3) ≤ Available (5,4): 5 ≤ 5 ✓, 3 ≤ 4 ✓. Pretend to grant: Allocation P₀ = (0+5, 1+3) = (5,4). Need P₀ = (7−5, 4−3) = (2,1). Available = (5−5, 4−3) = (0,1). Safety check: P₀ Need (2,1) > Available (0,1) → P₀ blocked. P₁ Need (1,2) > Available (0,1) → P₁ blocked. P₂ Need (6,0) > Available (0,1) → P₂ blocked. No process can finish. This is an unsafe state. Therefore the request (5,3) from P₀ must be denied.
Deadlock Handling Mechanisms at a Glance
This comparison table summarizes all four deadlock handling strategies, helping you answer exam questions that ask you to "explain different deadlock handling mechanisms" [2022 Q6a].
| Aspect | Prevention | Avoidance | Detection | Recovery |
|---|---|---|---|---|
| Approach | Ensure at least one Coffman condition can never hold. | Ensure system never enters an unsafe state. | Allow deadlock to occur; detect it when it happens. | Break the deadlock after detection. |
| When applied | System design time — fixed strategy. | At runtime — checked per resource request. | At runtime — periodic or on-demand checks. | After deadlock is detected. |
| Resource utilization | Low — resources may sit idle. | Moderate — resources allocated but safety-checked. | High — resources can be freely allocated until deadlock. | High — but processes may lose work during recovery. |
| Runtime overhead | Low — no runtime calculations. | High — runs Safety Algorithm (O(m×n²)) per request. | Moderate — runs detection algorithm periodically. | High — aborting/preempting processes is costly. |
| Advance knowledge required | No — works without knowledge of future requests. | Yes — processes must declare Max needs. | No — works with current state only. | No — works reactively. |
| Guarantee | Deadlock is impossible by design. | Deadlock is avoided as long as safety checks pass. | No prevention — deadlock can occur but will be caught. | No prevention — deadlock is resolved after the fact. |
| Best suited for | Simple embedded systems, database locking protocols. | Systems with fixed workloads (banking, transaction processing). | General-purpose OS where workload is unpredictable. | Systems where deadlock is rare but unacceptable to design around. |
Exam Tip [2022 Q6a, 2023 Q6a]: When asked to "explain different deadlock handling mechanisms," draw this table and explain any three of the four approaches in detail.
Limitations of Deadlock Avoidance
While the Banker's Algorithm is elegant, it has several practical limitations:
| Limitation | Explanation |
|---|---|
| Advance knowledge required | Processes must declare their maximum resource needs before execution. This is not always practical (e.g., interactive processes that read user input). |
| Fixed number of resources | The algorithm assumes the number of resources and processes is constant. In reality, resources can fail, new processes can be created, and resource instances can be added/removed. |
| No starvation guarantee | A process may wait indefinitely if its requests are repeatedly denied to keep the system safe. Banker's Algorithm does not guarantee fairness. |
| Runtime overhead | Every resource request triggers the Safety Algorithm (O(m × n²) complexity). In a system with many processes and resources, this can become expensive. |
| No resource ordering | The algorithm does not prevent circular wait entirely — it simply avoids entering states that would make deadlock possible. |
When to use each strategy:
| Strategy | Best suited for |
|---|---|
| Prevention (Circular Wait) | Database systems, file systems — simple and predictable. |
| Prevention (Hold and Wait) | Batch processing systems where resources are known upfront. |
| Avoidance (Banker's Algorithm) | Systems with fixed workloads and known resource ceilings — e.g., banking, embedded controllers. |
| Detection + Recovery | General-purpose operating systems where workload is unpredictable (Linux, Windows). |
Knowledge Check
Spooling is a technique that helps break which of the four necessary conditions for deadlock?