The Gateway to Computer Science Excellence
+5 votes
3.6k views
Consider three concurrent processes $P1$, $P2$ and $P3$ as shown below, which access a shared variable $D$ that has been initialized to $100$

$\begin{array}{|c|c|c|} \hline P1 & P2 & P3 \\ \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 ____
in Operating System by Veteran (425k points)
edited by | 3.6k views
+1
0 ?
+2
80
0
I also think it is 0.
0

after trying all 6 possible cases [that is complete execution of] D will always be 80 so don't take this 80 as max & min both. THEY SAID MAXIMUM AND MINIMUM "POSSIBLE" values which are 130 and 50

5 Answers

+15 votes
Best answer

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

  1. Read
  2. Calculate
  3. Update

Maximum value:
Run P2 for Read and Calculate. $D = 100$
Run P1 for read and calculate. $D = 100$
Run P2 update. D = $50$
Run P1 update. D = $110$
Run P2 read, calculate and update. $D = 130$

 Minimum Value:
Run P1, P2, P3 for Read and Calculate. $D = 100$
Run P1 update. D = $110$
Run P3 update. D = $120$
Run P2 update. D = $50$

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

by Veteran (60.5k points)
edited by
0

its saying uniprocessor but also time sharing so answer is 80.

0
Ok
+1

@Digvijay Pandey

P2 reads D=100, preempted.
P1(read+calculate+update)  D=D+20,

Now D=120.

P3 (read D i.e =120 + calculate  120+10  + update ) D=D+10,

Now D=130.


Now, P2 has D=100,

Calculate D=100-50
Update D=50
P2 writes the minimum final value which is D=50

 

is this correct sir ??

0

@Bhupendra How will the answer change for a multiprocessor environment?

0

@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".

+33 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

by Active (2k points)
0
Very well explained.From where did u study this in Operating Systems?
0
Nice explaination
0
How will the answer change for a multiprocessor environment?
0
Really good answer, though you could even write Preempt wherever you are not writing the final value.

This will provide even more clarity.

Anyway, this should be the best answer.
+1 vote

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

by Boss (11.4k points)
edited by
0 votes

first P1 will execute, make D=120. then P3 will read the value of D & preempt. Now P2 read D value & execute the statement, new D value is 120-50=70. Now P2 will continue its execution on previously read D value (120) & execute it's statement make D=130. Since P2 executed in last, this D value will be final.

maximum = 130

for minimum, execute in any order without taking any preemption.

minimum = 80

Y-X=50.

here, the key point is we have to take preemption into consideration as processes are not atomic. moreover we are getting maximum(possible) value by taking preemption.

by (421 points)
0 votes

 Minimum value (X) of D will possible when,

  1. P2 reads D=100, preempted.
  2. P1 executes D=D+20, D=120.
  3. P3 executes D=D+10, D=130.
  4. Now, P2 has D=100, executes, D = D-50 = 100-50 = 50. P2 writes D=50 final value.

So, minimum value (X) of D is 50.

Maximum value (Y) of D will possible when,

  1. P1 reads D=100, preempted.
  2. P2 reads D=100, executes, D = D-50 = 100-50 = 50.
  3. Now, P1 executes, D = D+20 = 100+20 = 120.
  4. And now, P3 reads D=120, executes D=D+10, D=130. P3 writes D=130 final value.

So, maximum value (Y) of D is 130.

Therefore,

= Y - X
= 130 - 50
= 80 

So, option (A) is correct.

by Loyal (5.3k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,587 answers
195,788 comments
101,841 users