Deadlock Prevention, Avoidance, and Recovery

The City Traffic Planner

Two approaches to preventing gridlock in a city:

Approach 1 — Prevention: Change the road rules permanently. Make all one-way streets. Prohibit left turns at certain intersections. These constraints eliminate the conditions that create gridlock — at the cost of less efficient routes.

Approach 2 — Avoidance: Keep current road rules, but install a smart traffic management system. Before allowing a car onto an intersection, the system checks whether doing so could lead to gridlock. If yes, it holds the car back until it is safe.

Operating systems use the same two approaches to deadlock — and a third one: wait for deadlock to occur, then recover.

Strategy 1: Deadlock Prevention

Idea: Structurally eliminate one of the four Coffman conditions. If any condition cannot hold, deadlock is impossible.

Breaking Mutual Exclusion

Make all resources shareable. Read-only resources (like read-only files) are naturally shareable and cannot cause deadlock.

Limitation: Some resources are inherently non-shareable — a printer printing two jobs simultaneously produces garbage. Mutual exclusion cannot always be eliminated.

Breaking Hold and Wait

Option A: Require each process to request all resources at once before it starts. Either it gets everything or it gets nothing.

Problem: A process may not know all resources it needs before starting. Acquiring all resources upfront leads to poor utilization — a process holds resources it may not need for hours.

Option B: Require a process to release all held resources before requesting new ones.

Problem: Progress and data integrity issues — releasing a half-written database record corrupts data.

Breaking No Preemption

Allow the OS to forcibly take resources from a process when needed by another.

Works for: CPU (context switch), memory pages (swap to disk)

Does not work for: Printers (mid-job preemption ruins the printout), database locks (preempting a lock mid-transaction corrupts data)

Breaking Circular Wait

Impose a global linear ordering on all resource types. Assign each resource type a unique number. Require that every process acquires resources in strictly increasing order of their assigned numbers.

R1 (network socket) = 1
R2 (file lock)      = 2
R3 (database lock)  = 3

Rule: always acquire in order 1 → 2 → 3. Never request a lower-numbered resource while holding a higher one.

If all processes follow this ordering, circular wait becomes mathematically impossible. This is the most practical prevention strategy and is used in kernel lock ordering rules (Linux, Windows kernel developers follow strict lock acquisition orders).

Cost: Processes must be programmed to follow the ordering. Ordering may not match natural access patterns.

Strategy 2: Deadlock Avoidance — The Banker's Algorithm

Idea: Allow normal resource requests, but before granting any request, simulate the result and check whether the resulting state is safe. Grant the request only if the system remains in a safe state.

Safe state: A state where there exists at least one sequence in which all processes can complete without deadlock.

The Banker's Algorithm — Step by Step

Dijkstra named this after bank lending: a bank only lends money if it can guarantee it can satisfy all clients' maximum possible demands from its available reserves.

Given: n processes, m resource types.

Data structures:

• Max[n][m]: maximum demand of each process
• Allocation[n][m]: currently allocated resources
• Available[m]: currently available resources
• Need[n][m] = Max − Allocation: remaining need

Example: 3 Processes, 3 Resource Types (A, B, C)

Available: A=3, B=3, C=2

Safety Algorithm:

1. Initialize Work = Available = [3,3,2], Finish = [false, false, false]
2. Find process i where: Finish[i] = false AND Need[i] ≤ Work
3. If found: Work = Work + Allocation[i], Finish[i] = true, go to step 2
4. If all Finish[i] = true → safe state. The order found is the safe sequence.

Trace:

• Check P0: Need=[7,4,3] ≤ Work=[3,3,2]? No (7>3)
• Check P1: Need=[1,2,2] ≤ Work=[3,3,2]? Yes. Work = [3,3,2]+[2,0,0] = [5,3,2]. Finish[1]=true
• Check P2: Need=[6,0,0] ≤ Work=[5,3,2]? No (6>5)
• Check P0: Need=[7,4,3] ≤ Work=[5,3,2]? No (7>5)
• Check P2: Need=[6,0,0] ≤ Work=[5,3,2]? No

Wait — let me re-check with the standard example values. Using the classic Silberschatz textbook example:

Available: A=3, B=3, C=2

Safety trace:

1. Work=[3,3,2]. P1 need [1,2,2] ≤ [3,3,2] ✓ → Work=[5,3,2], Finish P1
2. P3 need [0,1,1] ≤ [5,3,2] ✓ → Work=[7,4,3], Finish P3
3. P4 need [4,3,1] ≤ [7,4,3] ✓ → Work=[7,4,5], Finish P4
4. P0 need [7,4,3] ≤ [7,4,5] ✓ → Work=[7,5,5], Finish P0
5. P2 need [6,0,0] ≤ [7,5,5] ✓ → Finish P2

Safe sequence: P1 → P3 → P4 → P0 → P2

The system is in a safe state. Any resource request is approved only if the resulting state remains safe.

Strategy 3: Deadlock Detection

If prevention and avoidance are not used, the OS must periodically detect deadlock and recover.

Wait-For Graph

For systems with single-instance resources, build a wait-for graph: nodes are processes, edges represent "is waiting for." Deadlock exists if and only if the graph contains a cycle.

P1 ──waits──→ P2 ──waits──→ P3 ──waits──→ P1   (cycle = deadlock)

Run cycle detection (DFS) periodically. Cost: O(n²) for n processes.

Strategy 4: Recovery from Deadlock

When deadlock is detected, the OS must break it:

Process Termination:

• Kill all deadlocked processes (simple, brutal)
• Kill one process at a time until cycle is broken (cheaper but requires re-detection)

Resource Preemption:

• Select a victim process (minimize cost: remaining burst time, resources held)
• Preempt resources from victim, give them to another process
• Roll back the victim to a safe state (requires checkpoint/rollback support)
• Prevent starvation: do not always pick the same victim

Comparison of Deadlock Strategies

Summary

Deadlock handling is a spectrum from strict prevention to blissful ignorance:

1. Prevention: eliminate a Coffman condition permanently — safest but most restrictive
2. Avoidance: check safety before every allocation — theoretically sound but expensive
3. Detection and Recovery: find deadlocks after they occur — realistic for databases
4. Ignore: accept rare deadlock; let users reboot — pragmatic for general OS

Most production systems use a combination: kernel code follows strict lock ordering (circular wait prevention), database engines use detection and recovery, and user-space application deadlocks are handled by watchdog timers or user restarts.