Titas Gas Assistant Engineer (CSE): Exam: 24.05.2024 (BUET)প্রশ্ন ও সমাধান

Circular Wait is one of the four necessary (Coffman) conditions for a deadlock to occur in an operating system. It exists when a set of two or more processes forms a closed chain, where each process is waiting for a resource that is held by the next process in the chain, and the last process is waiting for a resource held by the first process -- creating a cycle of dependency with no process able to proceed.

Formally: there exists a set of processes {P0, P1, P2, ..., Pn} such that P0 is waiting for a resource held by P1, P1 is waiting for a resource held by P2, ..., P(n-1) is waiting for a resource held by Pn, and Pn is waiting for a resource held by P0.

graph LR
  P1((P1)) -- waits for --> R1[Resource 1 held by P2]
  R1 --> P2((P2))
  P2 -- waits for --> R2[Resource 2 held by P3]
  R2 --> P3((P3))
  P3 -- waits for --> R3[Resource 3 held by P1]
  R3 --> P1

Example: Process P1 holds a Printer and requests a Scanner; Process P2 holds the Scanner and requests the Printer. Neither can proceed -- a two-process circular wait.

Why it matters: Circular wait is necessary for deadlock along with Mutual Exclusion, Hold-and-Wait, and No Preemption -- all four conditions must hold simultaneously for a deadlock to occur. Breaking circular wait alone is sufficient to prevent deadlock, which is why it is the condition most commonly targeted in Deadlock Prevention schemes.

Prevention technique: Impose a strict total ordering on all resource types (e.g., number each resource type) and require every process to request resources only in strictly increasing order of this numbering. This makes it mathematically impossible to form a cycle, since a process holding a higher-numbered resource can never wait on a lower-numbered resource already held by a process ahead of it in the ordering.

Exam takeaway: Circular wait is the only one of the four Coffman conditions that can be eliminated purely through a resource-ordering policy, without sacrificing resource utilization the way eliminating Mutual Exclusion or Hold-and-Wait would.