Deadlock Solution

Definition

Deadlock Solution refers to the three fundamental approaches to handle deadlocks in a system: Prevention, Avoidance, and Detection-and-Recovery. Each has different trade-offs. Most modern systems combine these strategies.

Three Approaches to Deadlock

Deadlock Problem
    ↓
┌───┴─────┬──────────┐
│         │          │
Prevent  Avoid      Detect &
         Recovery

Approach 1: Prevention

Goal: Eliminate one of the four necessary conditions for deadlock

When: At system design time

Guarantee: Deadlock impossible

Strategy 1a: Remove Mutual Exclusion

Make resource sharable:

Problem: Can’t share everything

• Printer: Can’t print multiple jobs simultaneously
• Database record: Can’t update from multiple processes
• Mutex: By definition can’t share

Where applicable:

• Read-only files (sharable)
• CPU time (scheduling handles sharing)

Trade-off: Limits what can be protected

Strategy 1b: Remove Hold-and-Wait

Don’t hold resources while waiting:

Option 1: Get all resources at start

Process must request ALL resources at beginning
If unavailable, can't start
If available, holds all during execution

Pros:

• ✓ Simple
• ✓ Guaranteed no deadlock

Cons:

• ❌ Wastes resources (holds unused)
• ❌ If N=1000 resources, must request all 1000
• ❌ Low concurrency

Option 2: Release all before requesting new

Process requests A
Uses A
Releases A (can't hold A while requesting B!)
Requests B
Uses B
Releases B

Pros:

• ✓ No resource waste

Cons:

• ❌ Not always possible (need both simultaneously)
• ❌ Performance overhead

Strategy 1c: Remove No Preemption

Allow taking resources from process:

Problem: Not always safe

• Printer job: Preempt = corrupted printout
• Database transaction: Preempt = partial update

Where applicable:

• CPU (context switch any time)
• Memory (page out to disk)

Trade-off: Can cause inconsistency for some resources

Strategy 1d: Remove Circular Wait

Impose ordering on resources:

How:

1. Number all resources: R1, R2, R3, …, Rn
2. Processes must request in order (increasing)

Example:

Resource 1: Disk
Resource 2: Printer
Resource 3: Scanner

Process must request: Disk, then Printer, then Scanner
Never: Printer then Disk (violates ordering)

Why it works:

If all processes request in same order
P1: (1, 2)
P2: (1, 3)
P3: (2, 3)

Can't form circular wait:
P1→P2→P1 impossible because both want 1 first

Pros:

• ✓ Simple conceptually
• ✓ Prevents circular wait
• ✓ Minimal overhead

Cons:

• ❌ May not match application logic
• ❌ All processes must follow same order

Approach 2: Avoidance

Goal: Grant resources carefully to maintain safe state

When: At runtime

Mechanism: Before granting request, check if system stays in safe state

Trade-off: May deny requests (process waits) even if resource available

Safe vs Unsafe State

Safe State:

• No deadlock exists
• Deadlock won’t occur even if processes use maximum resources

Unsafe State:

• Deadlock might occur (not guaranteed)
• Risky to allocate resources

Banker’s Algorithm

Most famous deadlock avoidance algorithm

Analogy: Bank manager deciding to give loans

Setup:

• Know maximum resource each customer needs
• Know currently available resources
• Before granting loan, check if system remains safe

Pros:

• ✓ Deadlock guaranteed not to occur
• ✓ Maximum concurrency (more than prevention)
• ✓ Flexible

Cons:

• ❌ Complex (simulate future states)
• ❌ Overhead at every allocation
• ❌ Must know maximum resource needed (may not be known)

(Covered in detail in separate topic)

Approach 3: Detection and Recovery

Goal: Let deadlock happen, detect it, then recover

When: At runtime (monitoring)

Approach:

1. System continues normally
2. Deadlock detection algorithm checks periodically
3. If deadlock found, recovery algorithm kicks in

Detection Algorithm

Use Resource Allocation Graph:

• If cycle exists → Deadlock (for single resource type)
• If cycle AND certain conditions → Deadlock (multiple resource types)

Complexity:

• Single resource type: O(n²)
• Multiple resource types: O(n³)

When to check:

• Every resource request (expensive)
• Periodically (every second, minute)
• When system seems stuck (on-demand)

Recovery Strategies

1. Process Termination

Kill processes to break cycle:

Abort all: Kill all processes in deadlock

• Simple but expensive
• Lose all work

Abort one at a time: Kill one, rerun detection

• More expensive computationally
• Minimal work loss

Criteria for which to kill:

• Youngest process (least work done)
• Process with fewest resources (least to give back)
• Lowest priority process
• Process that will release most resources

2. Resource Preemption

Take away resources and reallocate:

Challenges:

• Which process to preempt from?
• Give resources to which waiting process?
• Avoid starvation of same process?

Problematic: Process state may be inconsistent

Better approach:

• Take checkpoint before allocation
• If preempted, rollback to checkpoint
• Process restarts from checkpoint

Comparison of Three Approaches

Practical Systems

Most systems use COMBINATION:

Database Systems:

• Prevention: Resource ordering for table locks
• Avoidance: Some deadlock detection
• Recovery: Deadlock detection, rollback transactions

OS (Windows, Linux):

• Prevention: Careful lock ordering in kernel
• Detection: Periodic check for hung processes
• Recovery: Kill offending processes

Distributed Systems:

• Prevention: Global ordering of locks (difficult)
• Avoidance: Limited (hard to predict in distributed)
• Detection: Cycle detection in wait graph
• Recovery: Abort transactions, retry

When to Use Each?

Use Prevention When:

• System resources limited
• Deadlock very expensive
• Can reorganize to avoid conditions
• Real-time constraints (no waiting)

Use Avoidance When:

• Can predict resource needs accurately
• Have some flexibility in allocation
• Want good concurrency with guarantees

Use Detection and Recovery When:

• Deadlock rare
• Want maximum concurrency
• Can afford occasional deadlock
• Have good recovery mechanism

Summary

Three approaches handle deadlock: Prevention (eliminate condition at design), Avoidance (safe allocation at runtime), Detection-and-Recovery (monitor and fix). Prevention simplest but limits concurrency. Avoidance provides middle ground but complex. Detection-and-recovery allows maximum concurrency but tolerates deadlock. Most practical systems combine elements of all three. Choice depends on system requirements, resource availability, and importance of deadlock-free guarantee.