GATE CSE 2019 | Question: 23

Question

Consider three concurrent processes $P_1, P_2$ and $P_3$ as shown below, which access a shared variable $D$ that has been initialized to $100.$ $$\begin{array}{|c|c|c|} \hline P_1 & P_2 & P_3 \\ \hline  : & : & :  \\  : & : & :  \\  D=D+20 & D=D-50 & D=D+10 \\ : & : &  :  \\ : & : & :  \\ \hline \end{array}$$ 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 ______

Comments

This is a concept of overwriting ??

---

Not understand the solution completely . I am still in doubt .  Can anyone clarify it with proper values of D ?

---

https://gateoverflow.in/1545 Similar question !!

Answer 1

$D=100$
Arithmetic operations are not ATOMIC.
These are three step process:

1. Read
2. Calculate
3. Update

Maximum value:

• Run $P_{2}$ for read and Calculate. $D = 100$
• Run $P_{1}$ for read and calculate. $D = 100$
• Run $P_{2}$ update. $D = 50$
• Run $P_{1}$ update. $D = 110$
• Run $P_{2}$ read, calculate and update. $D = 130$

Minimum Value:

• Run $P_{1}, P_{2}, P_{3}$ for Read and Calculate. $D = 100$
• Run $P_{1}$ update. $D = 110$
• Run $P_{3}$ update. $D = 120$
• Run $P_{2}$ update. $D = 50$

Difference between Maximum and Minimum $= 130-50 = 80.$

Comments

@Sambhrant Maurya

In multiprocessor environment, let's assume we have 3 processors for each of the processes. So each process will execute as a whole(if there exists no other processes) in a processor it was assigned. So output certainly depends on the order in which those processes were being assigned to them.

Again we gotta assume the assignments which can result in maximum and minimum value of "D".

---

@Deepak Poonia sir , I think the calculation for max is wrong here,

it should be ,

Maximum value:

• Run $P_{2}$ for read and Calculate. $D = 100$
• Run $P_{1}$ for read and calculate. $D = 100$
• Run $P_{2}$ update. $D = 50$
• Run $P_{1}$ update. $D = 120$
• Run $P_{3}$ read, calculate and update. $D = 130$

---

@Sachin Mittal 1 Sir I think there is some mistake in min value,

It should be,

Minimum value:

• Run $P_{1},P_{2},P_{3}$ for Read and calculate. $D=100$
• Run $P_{1}$ update. $D=120$
• Run $P_{3}$ update. $D=110$
• Run $P_{2}$ update. $D=50$

Answer 2

For minimum value-

P2 should write back the result after P1 and P3 only,but P2 should read the value of "D" before its being modified by P1 and P3(i.e minimum).

So,

P1	P2	P3
	Read(D):100
Read(D): 100
D= D+20: 120
Write(D): 120
		Read(D):120
		D=D+10 : 130
		Write(D): 130
	D= D-50 : 50 Write(D) :50

X = 50

Similarly for maximum value-

P1	P2	P3
Read(D): 100
D= D+20 :120
Write(D): 120
		Read(D): 120
	Read(D): 120
	D= D-50: 70
	Write(D): 70
		D=D +10 : 130 Write(D): 130

So Y = 130

Hence Y-X = 130-50 = 80

Comments

@iwasifirshad   any operation on semaphores are atomic, read, calculate, update all are done at once and not preempted.

---

And if it would have been multiprocessor, then what would be the minimum and maximum value?

@Bikram Sir @Lakshman Sir

---

I think depends on the no. of processors then, If 3 multiprocessors are there then max will be 120 and min will be 50 so 70 would be the answer.

Answer 3

$P1:$ 

1. $Load\ R_{p1},M[D]$
2. $Add\ 20$
3. $Store M[D],R_{p1}$

$P2:$ 

1. $Load\ R_{p2},M[D]$
2. $Sub\ 50$
3. $Store M[D],R_{p2}$

$P3:$ 

1. $Load\ R_{p3},M[D]$
2. $Add\ 10$
3. $Store M[D],R_{p3}$

   ---

    

Minimum Value:

$P2\rightarrow 1|2|preempt$

$P1\rightarrow 1|2|3(D=120)$

$P3\rightarrow 1|2|3(D=130)$

$P2\rightarrow 3$ $(D=50)$

 

Maximum Value:

$P1\rightarrow 1|2|3(D=120)$

$P3\rightarrow 1|2|preempt$

$P2\rightarrow 1|2|3(D=70)$

$P3\rightarrow 3$ $(D=130)$

---

$ANS: 130-50=80$

Answer 4

$\text{(a) - For Max Value}$

$P_1$	$P_2$	$P_3$
$W(S)$	$W(S)$	$W(S)$
$R(D)$	$R(D)$	$R(D)$
$\color{red}{C.S\space to \space P_2}\color{blue}{\space D = 100 \space here}$
$D = D+ 20$	$D = D- 50$	$D = D+ 10$
$W(D)$	$W(D)$	$W(D)$
$P(S)$	$P(S)$	$P(S)$

Start from either $P_1$ or $P_3$ In my case starting from $P_1$ so $P_1$ have $D = 100$ after read it context switched and given charge to $P_2$ ${\color{green}{\text{Why $P_2$ because it can decrease D's value }}}$ so $D's$ value became $50$ now charge returned to $P_1$ but here in $P_1$ D's value is aleady set so here $\text{LOST UPDATE}$ problem arises, so $D = 100+20 = 120$ , Now $P_3$ will start execution. Eventually $D = 120+10 = 130$ so $Y = 130$ 

$\text{(b) - For Min Value}$

$P_1$	$P_2$	$P_3$
$W(S)$	$W(S)$	$W(S)$
$R(D)$	$R(D)$	$R(D)$
	$\color{red}{C.S\space to \space P_1}\color{blue}{\space D = 100 \space here}$
$D = D+ 20$	$D = D- 50$	$D = D+ 10$
$W(D)$	$W(D)$	$W(D)$
$P(S)$	$P(S)$	$P(S)$

We'll start from $P_2$ because it contains negative operation and similiar execution done as $(a)$ so $D = 100 - 50$, $X = 50$

Then the value of $Y - X = 130 - 50 = 80$