TIFR CSE 2015 | Part B | Question: 14

Question

Consider the following concurrent program (where statements separated by | | with-in cobegin-coend are executed concurrently).

x:=1 
cobegin 
   x:= x + 1 ||    x:= x + 1  ||    x:= x + 1  
coend

Reading and writing of variables is atomic but evaluation of expressions is not atomic. The set of possible values of $x$ at the end of execution of the program is

• A. $\left \{ 4 \right \}$
• B. $\left \{ 2, 3, 4 \right \}$
• C. $\left \{2, 4  \right \}$
• D. $\left \{ 2, 3 \right \}$
• E. $\left \{2  \right \}$

Answer 1

Reading and writing is atomic but evaluation not atomic

So, 

1. read $1$, evaluate $1$ time, write $2$
2. read $1$, evaluate $2$ time, write $3$
3. read $1$, evaluate $3$ time, write $4$

Answer will be (B) $2,3,4$

Comments

but it says "at the end of execution of the program". try to evaluate in any order, we will get only one value for X i.e x=4.

option A should be the answer.

---

@srestha

please verify

---

2,3,4 is correct ..

i numbered all exp 1, 2, 3

i am executing like 1 2 3 it will give 4 ,

if evaluating all concurrent means all expression read x=1 and evulate same time it will give 2 as op..

now if i do like evaluate exp1 which give 2 then  2 exp in which i read only x value which is 2 and preempt this and evaluate exp 3 which also take x as2 and after executing x=3 , now i came back to exp 2 which was preempted it simmply add 1 to x=2(which is already read so it will not take new value ) and give op as x=3 so , 2 3 4 as op possible

---

see the Bikram sir comment, he explain beautifully.

https://gateoverflow.in/25109/tifr2012-b-9

and see this also https://gateoverflow.in/18751/tifr2010-b-28

---

(where statements separated by | | with-in cobegin coend are executed concurrently)

i think this is the key line, all 3 cases separated with | | are executed concurrently and it is asking for possible values so answer is 2, 3, 4.

---

So, TIFR has some questions in repetition as well. Same was asked in $\mathbf{2012}$, just the equations changed.

Answer 2

consider 1) x=x+1 ,  2) x=x+1 ,  3) x=x+1

case 1: - [ 1) reads x=1 ] preempts -> [ 2) reads x=1 ] preempts -> [ 3) reads x=1  and perform x+1 and stores in x now x = 2 ]

                similarly [ 1) comes back performs x+1 and stores x now x=2] , for [ 2) also performs x+1 stores x now x=2]

                value of x for [ 1) is 2 ] , [ 2) is 2 ] , [ 3) is 2]  =  =  {2}

 

case 2:-  [ 1) reads x=1 perform x+1 stores in x now x = 2] , [ 2) reads x=2 ] preempts -> [ 3) reads x=2 and perform x+1 and                           stores x=3]

               similarly [ 2) comes back and perform x+1 stores x=3]

               value of x for [ 1) is 2] , [ 2) is 3 ], [ 3) is 3] == {2, 3}

 

case 3:- no one preempts [ 1) reads x= 1 and perform x+1 and stores x now x=2], [2 reads x=2 and perform x+1 and stores x now                x =3], [ 3) reads x = 3 and perform x+1 and now x=4]

              value of x for [ 1) is 2], [ 2) is 3], [ 3) is 4] == {2,3,4}

question is asked for possible values since possible values are {2}, {2,3}, {2,3,4}

but {2,3,4 } is only option which includes {2} as well as {2,3}

option is b) correct answer

Comments

NYC EXPLANATION

Answer 3

we can do this, in this way also -

(1) first run all three parallely  so we get x= 2

(2) first run first statement(x=1+1=2) then second (x=2+1=3)then third so finally x=3+1=4

(3)first run any of two parallely so x will become x=2 then run third statement now x =2+1=3

{2,3,4} possible values of x.