GATE CS 2013 Q34 — Concurrency and Synchronization

Since the counting semaphore $S$ is initialized to $2$, at most two processes can enter their critical sections concurrently. This concurrency allows for "lost updates" when two processes read the same value of $x$ before either writes it back.

To maximize the final value of $x$, we want the decrement operations of $Y$ and $Z$ to be overwritten (lost) by the increment operations of $W$ and $X$. We can achieve this with the following sequence starting with $x = 0$ and $S = 2$:

1. Phase 1 (Overwriting $Y$'s decrement):
   • $Y$ and $W$ enter the critical section ($S$ becomes $0$).
   • $Y$ reads $x = 0$.
   • $W$ reads $x = 0$.
   • $Y$ decrements $x$ to $-2$, writes $x = -2$, and exits ($S$ becomes $1$).
   • $W$ increments its local copy ($0 + 1 = 1$), writes $x = 1$, and exits ($S$ becomes $2$).
2. Phase 2 (Overwriting $Z$'s decrement):
   • $Z$ and $X$ enter the critical section ($S$ becomes $0$).
   • $Z$ reads $x = 1$.
   • $X$ reads $x = 1$.
   • $Z$ decrements $x$ to $-1$, writes $x = -1$, and exits ($S$ becomes $1$).
   • $X$ increments its local copy ($1 + 1 = 2$), writes $x = 2$, and exits ($S$ becomes $2$).

After all processes terminate, the maximum possible value of $x$ is $2$.