Circular Wait

Definition

Circular Wait

Circular wait is a condition in a concurrent system where a closed chain of processes exists such that each process holds at least one resource needed by the next process in the chain.

It is the fourth of the Coffman conditions and the only one that describes a specific sequence of events rather than a static system property. A deadlock occurs if and only if a circular wait exists and cannot be resolved using the existing system protocols (Mutual Exclusion, Hold and Wait, No Preemption).

Resolution via Linear Ordering

A circular wait can be prevented by imposing a strict linear ordering $O$ on all resource types. If every process is forced to request resources in increasing order of their rank, a cycle becomes mathematically impossible.

Prevention of Circular Wait

Assume a circular wait $P_{0} \to P_{1} \to \dots \to P_{n} \to P_{0}$ exists under a linear ordering protocol.

Process $P_{0}$ holds resource $R_{0}$ and requests $R_{1}$ . The protocol requires $O (R_{0}) < O (R_{1})$ .

Process $P_{1}$ holds resource $R_{1}$ and requests $R_{2}$ . The protocol requires $O (R_{1}) < O (R_{2})$ .

By induction, for the chain to reach $P_{n}$ , we must have $O (R_{0}) < O (R_{1}) < \dots < O (R_{n})$ .

For the cycle to close, $P_{n}$ (holding $R_{n}$ ) must request $R_{0}$ . This requires $O (R_{n}) < O (R_{0})$ .

This implies $O (R_{0}) < O (R_{0})$ , which is a contradiction. Thus, no cycle can form.

Lukas' Notes

Circular Wait

Definition

Resolution via Linear Ordering

Graph View

Table of Contents

Backlinks