GATE CS 2019 Q.33 (CS Q.23): Process Synchronization and Concurrency

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 _____________.

Your answer

Official answer and solution

Official answer: 80
From: Official GATE 2019 answer key

Solution

Analyze the possible race conditions and lost updates on variable D to determine the minimum and maximum possible final values.

Each high-level statement D = D + C on a shared variable involves three machine-level steps:

Read D into local register R = D
Compute R = R + C
Store D = R

Initially, $D = 100$ . The three updates are:

$P_1$ : add $20$
$P_2$ : subtract $50$
$P_3$ : add $10$

Finding Maximum Value $Y$ :
To maximize the final value, we want the subtraction by $P_2$ to be overwritten (lost update), while the additions by $P_1$ and $P_3$ take effect:

$P_2$ reads $D = 100$ , then gets preempted.
$P_1$ reads $D = 100$ .
$P_2$ resumes and writes $100 - 50 = 50$ ( $D = 50$ ).
$P_1$ resumes and writes $100 + 20 = 120$ ( $D = 120$ ), overwriting $P_2$ 's decrement.
$P_3$ runs to completion: reads $120$ , adds $10$ , writes $130$ .
Hence, the maximum possible value is $Y = 130$ .

Finding Minimum Value $X$ :
To minimize the final value, we want the additions by $P_1$ and $P_3$ to be overwritten by $P_2$ 's subtraction:

$P_2$ reads $D = 100$ , computes $100 - 50 = 50$ , and is preempted before storing.
$P_1$ runs to completion: reads $100$ , writes $120$ .
$P_3$ runs to completion: reads $120$ , writes $130$ .
$P_2$ resumes and writes its stored value $50$ into $D$ .
Hence, the minimum possible value is $X = 50$ .

Therefore, the difference is:

Y - X = 130 - 50 = 80

Final answer

Common trap

Assuming sequential execution without interleaving, which yields Y - X = 0.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2019 Computer Science and Information Technology (CS)
Question: 33 of 65, printed as CS Q.23
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source