GATE CS 2019 Set 1 — Question 33

To find the minimum and maximum possible values of the shared variable $D$ after the execution of the three concurrent processes, we must analyze the read-modify-write operations at the assembly level. Each high-level statement D = D + value is translated into three machine instructions:Let the initial value of $D$ be $D_0 = 100$. The three processes perform the following operations:

• P1: $D = D + 20$ (Local register $R_1$)
• P2: $D = D - 50$ (Local register $R_2$)
• P3: $D = D + 10$ (Local register $R_3$)

If all processes execute sequentially without any interleaved preemption, the final value of $D$ is:$$D_{\text{sequential}} = 100 + 20 - 50 + 10 = 80$$However, due to concurrent execution and preemption, some updates can be overwritten (lost update problem).---

1. Finding the Minimum Value ($X$)

To minimize the final value of $D$, we want the largest increment (which is $+20$ from P1) to be overwritten/lost, while ensuring the decrement ($-50$ from P2) is successfully applied.Consider the following interleaving sequence:

• Reads $D = 100$.
• Updates $D = 100 + 10 = 110$.

4. P2 runs to completion:

• Reads $D = 110$.
• Updates $D = 110 - 50 = 60$.

5. P1 resumes and writes its calculated value:

• It calculates $R_1 = 100 + 20 = 120$.
• It writes $D = 120$. (At this point, the updates of P3 and P2 are overwritten).

This sequence results in $D = 120$, which is not the minimum. To get a smaller value, we can overwrite the increments of both P1 and P3, or let the decrement overwrite the increments.Let's try to make the decrement of P2 overwrite the increments:

• Reads $D = 100$.
• Updates $D = 100 + 20 = 120$.

4. P3 runs to completion:

• Reads $D = 120$.
• Updates $D = 120 + 10 = 130$.

5. P2 resumes:

• It decrements its local copy: $R_2 = 100 - 50 = 50$.
• It writes $D = 50$.

Here, the updates of both P1 and P3 are completely overwritten by P2's write operation.
Thus, the minimum possible value of $D$ is:$$X = 50$$---

2. Finding the Maximum Value ($Y$)

To maximize the final value of $D$, we want the decrement ($-50$ from P2) to be overwritten/lost, while the increments are preserved.Consider the following interleaving sequence:

• Reads $D = 100$.
• Updates $D = 100 + 20 = 120$.

4. P2 resumes:

• It decrements its local copy: $R_2 = 100 - 50 = 50$.
• It writes $D = 50$. (P1's update of 120 is overwritten).

5. P3 runs to completion:

• Reads $D = 50$.
• Updates $D = 50 + 10 = 60$.

This gives $D = 60$. We can get a much larger value if we overwrite P2's update using P1 or P3:

• Reads $D = 100$.
• Updates $D = 100 - 50 = 50$.

4. P3 runs to completion:

• Reads $D = 50$.
• Updates $D = 50 + 10 = 60$.

5. P1 resumes:

• It increments its local copy: $R_1 = 100 + 20 = 120$.
• It writes $D = 120$.

Here, the updates of both P2 and P3 are overwritten by P1's write operation.
Thus, the maximum possible value of $D$ is:$$Y = 120$$---

3. Calculating $Y - X$

Using the obtained minimum and maximum values:

• Minimum value, $X = 50$
• Maximum value, $Y = 120$

$$Y - X = 120 - 50 = 70$$Alternative Check for Maximum Value ($Y$):
Can we achieve a higher value than $120$?
Suppose P1 and P3 both execute their reads when $D = 100$.

• Reads $D = 100$.
• Updates $D = 100 - 50 = 50$.

4. P1 resumes and writes:

• Updates $D = 100 + 20 = 120$.

5. P3 resumes and writes:

• Updates $D = 100 + 10 = 110$.

This results in $110$, which is less than $120$.Suppose we execute P2 first, then let P1 overwrite it, and then P3 runs:Let's verify if this sequence is valid:

• P1 reads $D = 100$ into $R_1$. [Preempted]
• P2 reads $D = 100$, decrements to $50$, and writes $D = 50$. [Completed]
• P1 resumes, calculates $R_1 = 100 + 20 = 120$, and writes $D = 120$. [Completed]
• P3 reads $D = 120$, increments to $130$, and writes $D = 130$. [Completed]

In this valid execution sequence, the decrement of P2 is completely lost because P1 overwrites it, and then P3 successfully adds its increment of $10$ on top of P1's update. Thus, the actual maximum value is:$$Y = 130$$Using this corrected maximum value:$$Y - X = 130 - 50 = 80$$