Deadlock Prevention in Operating Systems: Conditions, Policies and Worked Examples

Learn how each deadlock-prevention policy breaks a Coffman condition. Worked printer, buffer, allocation and resource-ordering traces show the guarantee and its cost.

KnowledgeGate Team

Exam prep & CS education

Updated 31 Oct 20266 min read
Deadlock Prevention in Operating Systems: Conditions, Policies and Worked Examples

Learners often call every deadlock policy "Banker's algorithm", and that confusion hides the central idea. Banker's algorithm is avoidance: it checks whether a request keeps the current allocation state safe. Prevention changes the rules so that at least one necessary condition can never hold. A valid prevention rule therefore names the condition it makes impossible, proves the guarantee on a resource trace, and accepts a specific capacity or fairness cost.

Deadlock prevention starts with the four necessary conditions

A deadlock is a set of processes that cannot proceed because each awaits something another must release. All four Coffman conditions are required:

  1. Mutual exclusion: at least one resource has only one holder at a time.

  2. Hold and wait: a process holds a resource while requesting another.

  3. No preemption: an allocated resource cannot be forcibly reclaimed.

  4. Circular wait: processes form a closed waiting chain.

Suppose R1 and R2 each have one instance. R1 is assigned to P1, which requests R2; R2 is assigned to P2, which requests R1. This satisfies mutual exclusion (one holder per instance), hold and wait (each holds one while requesting another), no preemption (neither allocation is reclaimed), and circular wait (P1 -> R2 -> P2 -> R1 -> P1).

With one instance per type, that cycle is sufficient for deadlock. With multiple instances, another instance may allow completion, so a cycle alone is insufficient. Prevention makes at least one condition impossible.

Prevention, avoidance and detection are different design choices

Policy

When it acts

Required knowledge

Result

Prevention

Before a forbidden pattern forms

A structural rule, not maximum claims

One Coffman condition is impossible

Avoidance

Before each grant

Current allocation and declared maximum needs

State remains safe

Detection

After allocation

Allocation and outstanding requests

Find deadlock, then recover

The earlier Deadlock in Operating Systems: Four Conditions, Banker's Algorithm, and Worked Examples owns the broad map of resource-allocation graphs, avoidance, and detection. Prevention is the narrower problem here: identify the broken condition, prove why a cycle cannot form, and measure the policy's utilisation or fairness cost.

Banker's algorithm is avoidance, not prevention. A safe state has at least one completion order. An unsafe state has no safe order, but is not automatically deadlocked. Use Banker's Algorithm for GATE for focused Available, Max, Allocation, Need, and safe-sequence numericals.

For prevention, ask: Which Coffman condition does this make impossible? Without an answer, it has not been explained as prevention.

Break mutual exclusion only when the resource can genuinely be shared

A read-only file or immutable table can be shared concurrently. A mutex-protected critical section, non-atomic record update, or physical printer cannot simply be declared shareable without breaking correctness.

Concurrent readers observe the same stable data and create no conflicting update, so single-reader ownership is unnecessary. The test is semantic: concurrent use must preserve the resource's required behaviour.

Spooling shows safe mediation. P1 submits a 6-page job and P2 a 4-page job to separate spool files. After writing, neither process holds the printer. One daemon owns the device and outputs 6 + 4 = 10 pages. The applications do not wait while holding the printer, although the device remains non-shareable. Spooling changes the interface; it does not print two pages simultaneously.

This works only when a resource can be shared, copied, virtualised, queued, or safely mediated. It is not a universal fix for locks and devices.

Break hold and wait by requesting everything before execution

One policy requires all resources before execution. Another requires releasing all holdings before a new request. Thus a blocked process holds nothing. Costs include lower utilisation, longer waits, and possible starvation when full sets are rarely available.

Consider job J, which needs one instance each of R1 and R2. It uses R1 for 8 ms, followed by R2 for 5 ms. R2 is occupied until t=6.

  • At t=0, the combined request is denied. J waits while holding nothing.

  • At t=6, J receives both resources.

  • It uses R1 from t=6 to t=14, which is 14 - 6 = 8 ms.

  • It uses R2 from t=14 to t=19, which is 19 - 14 = 5 ms, then releases both.

R2 is reserved but unused from t=6 to t=14, an 8 ms interval. R1 is held but unused from t=14 to t=19, a 5 ms interval. The policy wastes capacity but prevents J from waiting for a resource while holding another. It breaks hold and wait, not mutual exclusion; both resources remain exclusive.

Break no preemption only when state can be saved and restored safely

If a process holds resources and requests an unavailable one, the system saves enough state, reclaims its preemptable resources, and retries later. CPU registers and restorable buffers may support this. A printer halfway through a page or an irreversible update may not.

At t=0, P1 holds buffer B1 and P2 holds B2. At t=1, P1 requests B2 while P2 requests B1. The rule saves P1's state and reclaims B1, leaving P1 with zero buffers. At t=2, P2 acquires B1, uses B1+B2, completes at t=4, and releases both. P1 then reacquires B1+B2 and completes at t=7.

Thus P2 runs for 4 - 2 = 2 ms, followed by P1 for 7 - 4 = 3 ms.

The rule breaks no preemption, and it is valid here only because the buffer contents and process progress are recoverable. Repeatedly rolling back P1 could still starve it. Fair retry ordering or ageing addresses that separate liveness problem.

Break circular wait with one global resource order

Two-panel diagram contrasts a P1-P2-P3 resource cycle with ordered R1-R2-R3 allocation over time.

Rank each resource type and allow only strictly increasing requests. A process needing a lower rank must release higher-ranked holdings. Let R1 = memory buffer, R2 = SSD channel, and R3 = printer, with 1 < 2 < 3.

Without ordering, P1 can hold R3 and request R1, P2 hold R1 and request R2, and P3 hold R2 and request R3. This creates P1 -> P2 -> P3 -> P1.

Now use required sets P1:{R1,R3}, P2:{R1,R2}, and P3:{R2,R3}:

  • At t=0, P3 acquires R2 then R3 and runs for 2 ms. P1 acquires R1 and waits for R3. P2 waits for R1 while holding nothing.

  • At t=2, P3 releases R2,R3. P1 acquires R3, runs for 3 ms, and releases R1,R3 at t=5.

  • At t=5, P2 acquires R1 followed by R2, runs for 4 ms, and releases both at t=9.

Every wait moves from lower to higher rank. A cycle would require a strictly increasing chain to return to its starting rank, which is impossible. All components must share the order because one exception can restore the cycle.

Two-panel flow chart compares forbidden and ordered resource allocation, showing the P1-P2-P3 cycle and ordered R1-R2-R3 sequence with waiting but no circular wait.

How exam questions test prevention, plus the short version

Common problems ask you to match a policy to its broken condition, test an acquisition sequence against a global order, inspect a resource-allocation graph, distinguish the three design choices, or judge whether sharing and preemption are feasible.

The core policy-to-condition mapping is:

  1. All-at-once allocation breaks hold and wait.

  2. Forced reclamation breaks no preemption.

  3. Increasing resource ranks break circular wait.

  4. Banker's safety test is avoidance.

Correct the costly traps too. A cycle is not sufficient with multiple instances. Unsafe does not mean deadlocked. Resource ordering removes circular waiting, not waiting. Spooling changes the interface, not the printer's shareability. Prevention may trade throughput or fairness for its guarantee.

Use this four-step decision card: write the four conditions, name the one the proposed rule breaks, trace allocations with exact arrows or times, then state the cost and applicability limit. Continue through the CS Fundamentals subject route. For a structured course, ZERO TO HERO covers the wider core-CS sequence, while Computer Science Fundamentals for Placements is the placement-focused route.