Deadlock Prevention

Introduction

If you know exactly what conditions cause a fire (fuel, oxygen, heat, chain reaction), you can prevent fires by removing one of these elements. Fire extinguishers work by smothering oxygen, fire-resistant materials remove fuel, and sprinklers remove heat. Similarly, deadlock prevention works by ensuring that at least one of the four necessary conditions can never be satisfied.

Deadlock prevention is the most conservative approach to handling deadlocks. It restructures the system so that deadlocks are structurally impossible. The tradeoff is reduced resource utilization and potentially lower system throughput — we are constraining the system to avoid a problem that might never have occurred anyway.

Strategy 1: Eliminating Mutual Exclusion

Approach: Make resources sharable so multiple processes can use them simultaneously.

Problem: This works for some resources but is impossible for others. A read-only file can be shared, but a printer cannot print two documents simultaneously without producing garbage. Mutex locks exist specifically because the protected resource cannot be shared safely.

Practical application: Spooling. Instead of giving processes direct access to the printer (which requires mutual exclusion), we let them write to a print spool (a buffer). Only the printer daemon directly accesses the printer. This eliminates mutual exclusion from the user process perspective — any number of processes can write to the spool simultaneously.

Limitation: We cannot eliminate mutual exclusion for inherently non-sharable resources like writable files, locks, and unique hardware devices.

Strategy 2: Eliminating Hold and Wait

Approach: Ensure that a process never holds one resource while waiting for another.

Method A: Request All Resources at Once

Before a process begins execution, it must request and receive ALL resources it will ever need. If any resource is unavailable, the process waits without holding anything.

Disadvantage: Low resource utilization. A process that needs a tape drive only at the end must hold it from the beginning. Other processes that need the tape drive now cannot use it.

Method B: Release Before Requesting

A process must release ALL its currently held resources before requesting any new ones. It can then request the old resources plus the new ones together.

Disadvantage: Practical only if the process can save its intermediate state. Releasing a half-modified file and re-acquiring it later could lead to inconsistency.

Real-world analogy: It is like a rule that says you cannot carry books from one library shelf while browsing another. You must return all books before picking up new ones. Inconvenient but prevents the "hold a book from shelf A while waiting for a book from shelf B" scenario.

Strategy 3: Allowing Preemption

Approach: If a process requests a resource that is not available, forcibly take resources from other processes (or from the requesting process itself).

Method A: Preempt from the requesting process

If P1 holds resources and requests a resource that is not available, all of P1's currently held resources are preempted (taken away). P1 must wait until it can get ALL its resources (old + new) simultaneously.

Method B: Preempt from the holding process

If P1 requests a resource held by P2, and P2 is also waiting for something, take the resource from P2 and give it to P1.

Practical application: This works well for resources whose state can be easily saved and restored — CPU registers (context switch is exactly this), memory pages (swap to disk and back). It does NOT work for printers (you cannot un-print half a document) or mutex locks (preemption would violate the mutual exclusion it was protecting).

Strategy 4: Eliminating Circular Wait

Approach: Impose a total ordering on all resource types and require that processes request resources in strictly increasing order.

How Resource Ordering Works

Assign a unique number to each resource type: R1=1, R2=2, ..., Rm=m

Rule: A process can only request resource Rj if j > i for all resources Ri it currently holds.

Why This Prevents Circular Wait

Proof by contradiction: Assume circular wait exists with ordering. Then:

• P1 holds Ri and wants Rj (where j > i since P1 follows the rule)
• P2 holds Rj and wants Rk (where k > j since P2 follows the rule)
• ...
• Pn holds Rz and wants Ri (where i > z since Pn follows the rule)

But this gives us: i < j < k < ... < z < i, which is a contradiction. Therefore, circular wait cannot exist.

Practical Implementation

Limitation: The ordering may not match the natural program logic. A process that naturally needs the printer before the scanner is forced to request them in the opposite order (if scanner has a lower number), leading to holding resources longer than necessary.

Comparison of Prevention Strategies

Key Takeaways

• Deadlock prevention guarantees no deadlock by eliminating at least one necessary condition
• Eliminating mutual exclusion is rarely possible (most resources need exclusive access)
• Eliminating hold-and-wait requires all-at-once allocation (wastes resources) or release-before-request
• Preemption works only for resources whose state is easily saved (CPU, memory) not physical devices
• Resource ordering (eliminating circular wait) is the most commonly used prevention strategy
• All prevention strategies reduce resource utilization as the cost of guaranteed safety
• The choice of strategy depends on the resource types and system requirements