GATE 2019 CS – Question 33
Consider three concurrent processes P1, P2 and P3 as shown below, which access a shared variable D that has been initialized to 100.
| P1 | P2 | P3 |
|---|---|---|
| D = D + 20 | D = D − 50 | D = D + 10 |
The processes are executed on a uniprocessor system running a time-shared operating system. If the minimum and maximum possible values of D after the three processes have completed execution are X and Y respectively, then the value of Y − X is ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 80
Explanation
Each assignment is really three steps: **read** $D$, **compute**, **write** $D$. A time-sharing OS can interleave these steps in many ways.
**Minimum value $X$.** Let $P_2$ read $D=100$ first and be delayed. Let $P_1$ and $P_3$ run and finish ($D=130$). Now $P_2$ writes $100-50=50$, overwriting everything. So $X=50$ (no schedule can go lower, since only $P_2$ subtracts).
**Maximum value $Y$.** Let $P_2$ read $D=100$ and be delayed. Run $P_3$ completely ($D=110$). Let $P_1$ read $110$. Now let $P_2$ write $50$. Finally $P_1$ writes $110+20=130$, wiping out $P_2$'s update. So $Y=130$.
$$Y-X=130-50=\mathbf{80}.$$