The GATE Grind

GATE 2019 CS – Question 33

Operating System · Concurrency and Synchronization · 1 mark · Numerical answer

Consider three concurrent processes P1, P2 and P3 as shown below, which access a shared variable D that has been initialized to 100.

P1P2P3
D = D + 20D = D − 50D = 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}.$$

More Concurrency and Synchronization questions

All Concurrency and Synchronization questions →