GATE CS 2019 Q23 — Concurrency and Synchronization

Each assignment statement $D = D + k$ is executed at the machine level as three instructions:

1. Read: Load $D$ into a local register $R_i$.
2. Modify: $R_i \leftarrow R_i + k$.
3. Write: Store $R_i$ back to $D$.

To find the minimum and maximum possible final values of $D$ (initialized to $100$):

1. Minimum Value ($X$):

We want the decrement operation of $P_2$ ($-50$) to overwrite the increments of $P_1$ and $P_3$:

• $P_2$ reads $D = 100$ ($R_2 = 100$).
• $P_1$ and $P_3$ execute completely in sequence, updating $D$ to $130$ ($100 \to 120 \to 130$).
• $P_2$ resumes, decrements its register ($R_2 = 50$), and writes $D = 50$.

Thus, the minimum value is $X = 50$.

2. Maximum Value ($Y$):

We want the increment of $P_3$ ($+10$) to overwrite the decrement of $P_2$ ($-50$):

• $P_1$ executes completely, updating $D$ to $120$.
• $P_3$ reads $D = 120$ ($R_3 = 120$).
• $P_2$ reads $D = 120$ ($R_2 = 120$).
• $P_2$ decrements and writes $D = 70$.
• $P_3$ resumes, increments its register ($R_3 = 130$), and writes $D = 130$.

Thus, the maximum value is $Y = 130$.

The required difference is: