Deadlock Prevention

We know that for a deadlock to occur, all four Coffman conditions must hold true simultaneously. Deadlock Prevention is a strict approach: it designs the system so that at least one of these four conditions can never happen.

By structurally guaranteeing that a deadlock cannot form, we completely eliminate the need for runtime monitoring or recovery algorithms. Let's explore how we can systematically attack and break each of the four conditions.

1. Breaking Mutual Exclusion

The Mutual Exclusion condition states that at least one resource must be non-shareable. To break this, we must make all resources shareable.

For read-only files, this is easy: multiple processes can read a file at the same time. However, for hardware like printers, true sharing is impossible. Two processes cannot print lines of text concurrently on the same page.

The Spooling Workaround

To bypass the physical limitations of a printer, operating systems use spooling. Instead of granting a process direct access to the printer, the OS intercepts the print job and writes it to a temporary file on the disk (a spool). The process thinks it has printed and moves on, while a background daemon handles the actual, sequential printing. From the process's perspective, the resource is now shareable.

Drawback: We cannot use spooling for everything. Some resources (like a mutex lock on a shared memory segment) simply cannot be abstracted away.

2. Breaking Hold and Wait

The Hold and Wait condition requires a process to hold onto its current resources while waiting for new ones. We can break this using two strict protocols:

Protocol	How It Works
Protocol 1: Request All Upfront	A process must request and be allocated all the resources it will ever need before it begins execution. If it cannot get all of them at once, it gets none and waits.
Protocol 2: Release Before Request	A process can only request new resources when it currently holds none. If a process holding resources needs a new one, it must release everything it currently holds first, then request the old and new resources together.

Drawbacks: These protocols are highly inefficient. Protocol 1 leads to low resource utilization because a process might hold a printer for an hour even though it only prints at the very end. Protocol 2 is prone to starvation, as a process might continually release its resources but never manage to grab the complete set it needs to move forward.

3. Breaking No Preemption

The No Preemption condition states that the OS cannot forcefully take resources away from a process. To break this, we give the OS the power to preempt resources.

If Process A is holding resources and requests a new resource that is currently unavailable, Process A is forced to release all the resources it currently holds. Process A is then placed in a waiting state, and its preempted resources can be given to other processes.

Process A will only be restarted when it can successfully regain its old resources along with the new ones it was asking for.

State Restoration Limitation

Preemption is generally only applicable to resources whose state can be easily saved and restored later, such as CPU registers or main memory space. You cannot safely preempt a printer halfway through a print job without ruining the output.

4. Breaking Circular Wait

The Circular Wait condition involves a closed loop of waiting processes. To break this, we impose a total ordering of all resource types, and require that each process requests resources in a strictly increasing order of enumeration.

text

Assign a unique integer to each resource type:
1: Tape Drive
2: Disk Drive
3: Printer

Rule: A process can only request resources with a higher number than the ones it currently holds.

If a process holds the Disk Drive (2), it can request the Printer (3), but it can NEVER request a Tape Drive (1). Because everyone must reach "forward" and never "backward," a circular chain is mathematically impossible to form.

Drawback: This requires developers to strictly adhere to the ordering when writing software, which restricts flexibility and can lead to requesting resources long before they are actually needed (just to respect the order).

Summary of Prevention

Condition to Break	Strategy	Primary Disadvantage
Mutual Exclusion	Spooling / Make shareable	Not all resources can be spooled.
Hold and Wait	Request all upfront or release before requesting	Severe resource underutilization and starvation.
No Preemption	Forcefully reclaim resources	State cannot be saved/restored for all devices.
Circular Wait	Strict numerical ordering of resource requests	Inflexible and burdensome for developers.

Deadlock prevention is bulletproof, but it comes with massive overhead and restrictive rules. For this reason, it is usually reserved for safety-critical embedded systems (like medical devices or aircraft) where a deadlock would be catastrophic.

Applying Prevention Strategies

Question 1 of 1

Test your understanding of how prevention strategies are applied in practice.

An operating system dictates that if a process holding a lock requests another lock that is unavailable, it must drop its current lock and sleep until both are available. Which condition is this OS trying to break?

Deadlock Prevention
1. Breaking Mutual Exclusion
2. Breaking Hold and Wait
3. Breaking No Preemption
4. Breaking Circular Wait
Summary of Prevention