Circular Wait

operating-systems concurrency

Definition

Circular Wait

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

Formally, for processes $P_0,P_1,\dots ,P_n$: $P_i$ holds resource $R_i$ and requests $R_{(i+1)\mathrm{mod}(n+1)}$.

Prevention

Strict Linear Ordering

Impose a strict linear ordering on all resource types. Each process must request resources in increasing order of the ordering.

Circular Wait Prevention

Assume a circular wait exists under strict linear ordering of resource types. Let the cycle be

$$P_0\to P_1\to \cdots \to P_n\to P_0.$$

Since each process requests a resource with higher order than the one it currently holds:

$$O(R_0)<O(R_1)<\cdots <O(R_n)<O(R_0).$$

This is a contradiction. Therefore, no circular wait can occur.