Deadlock Prevention

Definition

Deadlock Prevention ensures deadlock is impossible by eliminating one of the four necessary conditions (mutual exclusion, hold-and-wait, no preemption, circular wait) at system design time. It’s the most straightforward approach but often has performance penalties.

Four Conditions and Prevention Strategies

Recall four conditions needed for deadlock:

  1. Mutual Exclusion
  2. Hold and Wait
  3. No Preemption
  4. Circular Wait

Prevent by removing ANY ONE.

Strategy 1: Prevent Mutual Exclusion

Approach: Allow multiple processes to access resource simultaneously

When Possible

Read-Only Resources:

File reading: Multiple processes can read same file simultaneously
Database query: Multiple transactions can execute same SELECT query
Shared library: Multiple processes can execute same code

When NOT Possible

Some resources inherently exclusive:

Printer: Can't print two jobs simultaneously (output mixed)
Database update: Can't update record from two transactions simultaneously (inconsistency)
Mutex: By definition exclusive
Keyboard: Can't input from multiple users simultaneously

Practical Application

Modern systems use readers-writers locks:

Many readers can hold lock simultaneously
But writers get exclusive access
When writer active, readers blocked (and vice versa)

Limitations

  • Can’t eliminate mutual exclusion for all resources
  • Some resources must be exclusive

Grade: Partial prevention (applies to limited resources)

Strategy 2: Prevent Hold-and-Wait

Approach: Process doesn’t hold resources while requesting others

Option A: Get All Resources at Start

Process requests ALL resources needed before starting:

Process:
1. Request(Disk, Printer, Scanner)
2. If all available, get all
3. If any unavailable, wait for all
4. Execute with all resources
5. Release all at once

Advantages:

  • ✓ Simple to implement
  • ✓ Guaranteed no deadlock (can’t hold some while waiting for others)
  • ✓ No complex decision-making

Disadvantages:

  • ❌ Resource Waste: Hold resources during entire execution, even if used only briefly

    Example: Process needs:
- Disk for 1 second
- Printer for 3 seconds
- Scanner for 0.5 seconds
Total runtime: 5 seconds
But holds all 3 for entire 5 seconds (wasteful!)

  • ❌ Poor Concurrency: Other processes blocked waiting for resources

  • ❌ Starvation: If N resources needed and one always busy, process waits forever

  • ❌ Inflexibility: Can’t know all resources in advance (dynamic programs)

Option B: Release Before Requesting

Process releases all resources before requesting new ones:

Process:
while (true) {
    Request(A);
    Use(A);
    Release(A);

    Request(B);
    Use(B);
    Release(B);

    Request(C);
    Use(C);
    Release(C);
}

Advantages:

  • ✓ No resource waste (release after use)
  • ✓ Simpler than pre-allocation

Disadvantages:

  • ❌ Not always applicable: If need A and B simultaneously

    Transfer from Account A to Account B:
1. Lock Account A
2. Read A's balance
3. Need to modify Account B immediately
4. Can't release A before locking B!

  • ❌ Context changes: A may change between release and next request

  • ❌ Complexity: Complex coordination logic

Practical Combination

Use pre-allocation for critical resources, request others dynamically:

Process:
Request(CriticalResource1, CriticalResource2);  // Pre-allocate critical ones

while (true) {
    Request(LessImportantResource);  // Request others dynamically
    Use();
    Release(LessImportantResource);
}

Grade: Good prevention strategy

Strategy 3: Prevent No Preemption

Approach: Allow taking resources from processes

Implementation

If process requests resource and unavailable:

Option 1: Block and wait (current)
Option 2: Preempt from another process and give to requester

Challenges

Problem: Safe preemption requires saving state

For CPU:

Easy to preempt!
- Context switch saves registers
- Preemption transparent
- Works great

For Printer Job:

Hard to preempt!
- Print job: "Print page 1, print page 2, print page 3"
- If preempted mid-job: Output corrupted!
- Need checkpoint/rollback (complex)

For Database Transaction:

Can preempt if rollback supported
- Database keeps logs
- If preempted, rollback transaction
- Other transaction gets lock
- Preempted transaction restarts
- Works but expensive

When Used

  1. Memory: Paging allows “preemption” to disk
  2. CPU: Context switching
  3. Transactions: Some databases support rollback (expensive)

Real-World Example: Process Termination

Most practical form of preemption:

// Deadlock detected!
Force Process A to release its resources
Kill Process A (forcible preemption)
Give resources to Process B
Process A restarts later

(This is detection-and-recovery, not true prevention)

Grade: Limited prevention (works for some resources, not others)

Strategy 4: Prevent Circular Wait

Approach: Impose linear ordering on resources, processes must request in order

How It Works

  1. Number resources: R1, R2, R3, …, Rn
  2. Enforcement rule: Process can only request Ri after holding Rj where j < i
Resources:
Disk = 1
Printer = 2
Scanner = 3
Modem = 4

Valid request sequences:
- Disk, Printer, Scanner
- Printer, Scanner, Modem
- Disk, Modem (any subset respecting order)

Invalid:
- Printer, Disk (wrong order)
- Scanner, Printer (wrong order)

Why It Prevents Circular Wait

Proof:

Assume circular wait exists:
P1 waits for P2's resource, P2 waits for P3's resource, ..., Pn waits for P1's resource

For this to form cycle:
Let R(Pi) = set of resources held by Pi

P1 waits for resource in R(P2)
P2 waits for resource in R(P3)
...
Pn waits for resource in R(P1)

By ordering constraint:
- If P1 holds resource r1 and waits for r2 in R(P2), then r1 < r2
- If P2 holds resource r2 and waits for r3 in R(P3), then r2 < r3
...
- If Pn holds rn and waits for r1 in R(P1), then rn < r1

This creates: r1 < r2 < r3 < ... < rn < r1
Which is impossible!

Therefore: Circular wait impossible with ordering!

Advantages

  • ✓ Simple to understand
  • ✓ Prevents all deadlocks (guaranteed)
  • ✓ Minimal overhead (just enforce ordering)
  • ✓ Works for any number of resources

Disadvantages

  • ❌ Artificial Ordering: Ordering may not match application logic

    Transferring money between accounts:
Account 1, Account 2
But what order? Account 1 < 2, or 2 < 1?

If both Account 1 and 2 used frequently in both orders,
ordering constraint unnecessary for deadlock but adds complexity

  • ❌ Rigidity: All processes must follow same ordering

  • ❌ Inefficiency: May request in different order than optimal

    Process A needs Printer (2), then Disk (1)
Ordering requires: Disk (1), then Printer (2)
So: Request Disk, use it, request Printer
Inefficient if only needed Printer!

Real-World Examples

Database Systems:

Table locks ordered by table ID
All transactions acquire locks in increasing table ID order
Prevents circular waits from table locks

Kernel:

Locks ordered by lock ID
All kernel code acquires locks in order
Prevents kernel deadlocks

Grade: Excellent prevention strategy

Practical Recommendations

Prevention Strategy Choice

Use Prevention When:

  • Deadlock very costly (safety-critical systems)
  • Can design system to respect constraints
  • Performance impact acceptable

Best strategies in practice:

  1. Resource Ordering (Strategy 4): Most practical, good overhead
  2. Careful Design: Minimize lock dependencies
  3. Combination: Multiple strategies for different resources

Example System Design

// Bank account transfer system

// Prevent circular wait using resource ordering:
// Account 1 = 1, Account 2 = 2, ..., Account N = N

Transfer(from_account, to_account, amount):
    // Always acquire in order: smaller ID first
    first = min(from_account, to_account)
    second = max(from_account, to_account)

    Lock(Account[first])
    Lock(Account[second])

    Account[from_account] -= amount
    Account[to_account] += amount

    Unlock(Account[second])
    Unlock(Account[first])

This simple ordering eliminates all deadlock possibilities!

Comparison with Other Strategies

StrategyOverheadComplexityGuaranteeConcurrency
Prevent Mutual ExclusionNoneLowPartialMedium
Prevent Hold-and-WaitMediumMediumFullLow
Prevent No PreemptionHighHighPartialMedium
Prevent Circular WaitLowLowFullHigh

Summary

Prevention eliminates one of four deadlock conditions at design time. Most practical: Resource Ordering (eliminate circular wait) due to simplicity, low overhead, and good concurrency. Hold-and-Wait elimination possible but wasteful. Mutual Exclusion prevention limited to read-only resources. No-Preemption prevention complex for most resources. Modern systems primarily use resource ordering combined with careful system design. Prevention is best for critical systems where deadlock unacceptable.