Course contentsShow
← Computer Science
Lesson 1322 of 2,87230. Process SynchronizationFree lesson

Deadlock Prevention: Breaking Circular Wait

Imposing a total ordering on resources and requiring processes to request resources in increasing order.

Deadlock Prevention: Breaking Circular Wait

You'll learn how to prevent deadlock by imposing a strict ordering on resource acquisition to eliminate circular waiting chains.

The Core Idea

Breaking circular wait is one of the most practical deadlock prevention strategies. The approach is simple: assign a unique numerical order to all resources in the system, and require every process to request resources in strictly increasing order.

By enforcing this rule, it becomes impossible for processes to form a circular chain of waiting. If Process A holds resource 5 and requests resource 10, and Process B holds resource 10, then Process B cannot request resource 5 (since 5 < 10). This eliminates the possibility of A waiting for B while B waits for A.

Why It Works

Think of it like a one-way street system in a city. If every driver must always turn toward higher-numbered streets, no one can circle back to create a traffic loop. Even with many cars (processes) and intersections (resources), circular gridlock becomes structurally impossible.

The Implementation Strategy

  1. Number all resources (locks, files, devices) from 1 to N
  2. Enforce the protocol: A process holding resource i may only request resource j where j > i
  3. Release resources in any order (ordering only matters for acquisition)

For example, if you have:

  • Mutex A = resource #1
  • Mutex B = resource #2
  • Mutex C = resource #3

Every process must acquire them in order: A before B, B before C. A process holding B cannot then try to acquire A.

Trade-offs

This approach is effective but requires careful resource numbering and can be restrictive—sometimes processes must acquire resources they don't immediately need to maintain the ordering constraint.

Key Takeaway: Breaking circular wait through total resource ordering guarantees deadlock prevention by making it impossible for processes to form waiting cycles, at the cost of reduced flexibility in resource acquisition patterns.