retagged by
16,841 views
25 votes
25 votes
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 ______
retagged by

6 Answers

Best answer
42 votes
42 votes

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

edited by
89 votes
89 votes

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

9 votes
9 votes

$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$

1 votes
1 votes

$\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$

edited by
Answer:

Related questions

24 votes
24 votes
8 answers
2
Arjun asked Feb 7, 2019
17,134 views
The following C program is executed on a Unix/Linux system :#include<unistd.h int main() { int i; for(i=0; i<10; i++) if(i%2 == 0) fork(); return 0; }The total number of ...
40 votes
40 votes
4 answers
3
18 votes
18 votes
4 answers
4