Question 16

To prevent deadlock among concurrent processes, the necessary condition of circular wait must be broken. Imposing a global linear order on resources guarantees deadlock freedom.

Let us analyze Option B:

• Process X: $P(b) \to P(a) \to P(c)$
• Process Y: $P(b) \to P(c) \to P(d)$
• Process Z: $P(a) \to P(c) \to P(d)$

Notice that:

1. Semaphore $b$ is the first semaphore requested by both X and Y. Because $b$ is a binary semaphore initialized to 1, exactly one of X or Y can acquire $b$.
   • If X acquires $b$, Y cannot proceed at all (blocked on its first operation $P(b)$).
   • If Y acquires $b$, X cannot proceed at all (blocked on its first operation $P(b)$).
2. Suppose X acquires $b$:
   • Y is blocked at its start.
   • Process Z begins by acquiring $a$. If $a$ is available, Z acquires $a$ and proceeds to $P(c)$ and $P(d)$. Neither X nor Y holds $c$ or $d$, so Z acquires both, enters its critical section, and signals $a, c, d$.
   • Once Z signals $a$, X acquires $a$, then $c$, completes, and signals $b, a, c$.
   • Finally, Y unblocks on $b$ and runs to completion.
3. Suppose Y acquires $b$:
   • X is blocked at its start.
   • Z acquires $a$, while Y acquires $c$ and $d$. Process Y completes and releases $b, c, d$. Then Z acquires $c, d$, completes, and releases $a, c, d$. Finally X executes.

In all possible interleavings of Option B, no cycle of waiting processes can ever develop.

In contrast, Option A allows the classic circular wait: X holds $a$ waiting for $b$, Y holds $b$ waiting for $c$, and Z holds $c$ waiting for $a$, causing deadlock.