GATE CS 2015 Set 1 Q9 — Concurrency and Synchronization

Let the instructions of processes $P1$ and $P2$ be labeled as follows:

• P1:
  • $I_1$: C = B - 1
  • $I_2$: B = 2 * C
• P2:
  • $I_3$: D = 2 * B
  • $I_4$: B = D - 1

Since $C$ and $D$ are local variables and $B$ is a shared variable (initially $B = 2$), we can trace all $\binom{4}{2} = 6$ possible concurrent interleavings of these instructions:

1. $I_1 \to I_2 \to I_3 \to I_4$:
   • $I_1 \implies C = 2 - 1 = 1$
   • $I_2 \implies B = 2 \times 1 = 2$
   • $I_3 \implies D = 2 \times 2 = 4$
   • $I_4 \implies B = 4 - 1 = 3$
2. $I_3 \to I_4 \to I_1 \to I_2$:
   • $I_3 \implies D = 2 \times 2 = 4$
   • $I_4 \implies B = 4 - 1 = 3$
   • $I_1 \implies C = 3 - 1 = 2$
   • $I_2 \implies B = 2 \times 2 = 4$
3. $I_1 \to I_3 \to I_2 \to I_4$:
   • $I_1 \implies C = 2 - 1 = 1$
   • $I_3 \implies D = 2 \times 2 = 4$
   • $I_2 \implies B = 2 \times 1 = 2$
   • $I_4 \implies B = 4 - 1 = 3$
4. $I_1 \to I_3 \to I_4 \to I_2$:
   • $I_1 \implies C = 2 - 1 = 1$
   • $I_3 \implies D = 2 \times 2 = 4$
   • $I_4 \implies B = 4 - 1 = 3$
   • $I_2 \implies B = 2 \times 1 = 2$
5. $I_3 \to I_1 \to I_2 \to I_4$:
   • $I_3 \implies D = 2 \times 2 = 4$
   • $I_1 \implies C = 2 - 1 = 1$
   • $I_2 \implies B = 2 \times 1 = 2$
   • $I_4 \implies B = 4 - 1 = 3$
6. $I_3 \to I_1 \to I_4 \to I_2$:
   • $I_3 \implies D = 2 \times 2 = 4$
   • $I_1 \implies C = 2 - 1 = 1$
   • $I_4 \implies B = 4 - 1 = 3$
   • $I_2 \implies B = 2 \times 1 = 2$

The set of distinct values that $B$ can take after execution is $\{2, 3, 4\}$. Thus, there are 3 distinct values.