GATE CS 2004 Q48 — Concurrency and Synchronization

To prevent deadlock among competing processes, we must eliminate at least one of the four Coffman conditions. The most common way to prevent circular wait is to enforce a strict global ordering on resource acquisition.

Both processes $P_1$ and $P_2$ access the shared variables $X$ and $Y$, which are protected by the binary semaphores $S_X$ and $S_Y$ respectively. Since both processes modify both variables, each process must acquire both semaphores before entering its critical section.

Analyzing the Options:

• Option A: $P_1$ requests $S_Y$ then $S_X$, while $P_2$ requests $S_X$ then $S_Y$.
  Deadlock scenario: $P_1$ executes $P(S_Y)$ and is preempted. $P_2$ executes $P(S_X)$. Now, $P_1$ is blocked waiting for $S_X$ (held by $P_2$), and $P_2$ is blocked waiting for $S_Y$ (held by $P_1$). This results in a deadlock.
• Option B: $P_1$ requests $S_X$ then $S_Y$, while $P_2$ requests $S_Y$ then $S_X$.
  Deadlock scenario: $P_1$ executes $P(S_X)$ and is preempted. $P_2$ executes $P(S_Y)$. Similar to Option A, this leads to a deadlock.
• Option C: $P_1$ requests $S_X$ twice, and $P_2$ requests $S_Y$ twice. This does not protect both shared variables for either process and is incorrect.
• Option D: Both $P_1$ and $P_2$ request the semaphores in the exact same order: $S_X$ first, followed by $S_Y$.
  Why this avoids deadlock: Whichever process successfully executes $P(S_X)$ first will proceed to request $S_Y$. The other process will be blocked at the very first step ($P(S_X)$) and cannot hold any resource while waiting. Since no circular wait can form, deadlock is completely avoided.

Thus, the correct operators at $L_1, L_2, L_3,$ and $L_4$ are respectively:
$P(S_X), P(S_Y); P(S_X), P(S_Y)$