Question 34

Initial conditions:

• Variable $x = 0$.
• Counting semaphore $S = 2$.
• Four processes:
  • $W$: reads $x$, increments by 1, writes $x$.
  • $X$: reads $x$, increments by 1, writes $x$.
  • $Y$: reads $x$, decrements by 2, writes $x$.
  • $Z$: reads $x$, decrements by 2, writes $x$.

Each process executes $P(S)$ before reading $x$ and $V(S)$ after storing $x$.

Because $S$ is initialized to 2, two processes can be concurrently inside the critical region. To maximize the final value of $x$, we want the decrements by $Y$ and $Z$ to be completely overwritten by an increment:

1. Process $W$ executes $P(S)$ (now $S = 1$). $W$ reads $x = 0$ into its local register. $W$ calculates local value $= 0 + 1 = 1$, but is preempted before writing back to $x$.
2. Process $Y$ executes $P(S)$ (now $S = 0$). $Y$ reads $x = 0$, computes $0 - 2 = -2$, writes $x = -2$, and executes $V(S)$ (now $S = 1$).
3. Process $Z$ executes $P(S)$ (now $S = 0$). $Z$ reads $x = -2$, computes $-2 - 2 = -4$, writes $x = -4$, and executes $V(S)$ (now $S = 1$).
4. Now process $W$ resumes. $W$ writes its computed local value $1$ to memory: $x = 1$. Then $W$ executes $V(S)$ (now $S = 2$). At this point, both decrements from $Y$ and $Z$ have been completely overwritten!
5. Finally, process $X$ executes sequentially: $P(S)$ (now $S = 1$), reads $x = 1$, computes $1 + 1 = 2$, writes $x = 2$, and executes $V(S)$ (now $S = 2$).

The maximum possible final value of $x$ is 2.