edited by
3,708 views
16 votes
16 votes

Consider the concurrent program:

x: 1;
    cobegin
        x:= x + 3 || x := x + x + 2
    coend

Reading and writing of variables is atomic, but the evaluation of an expression is not atomic.

The set of possible values of variable $x$ at the end of the execution of the program is:

  1. $\{4\}$
  2. $\{8\}$
  3. $\{4, 7, 10\}$
  4. $\{4, 7, 8, 10\}$
  5. $\{4, 7, 8\}$
edited by

4 Answers

Best answer
15 votes
15 votes
    cobegin
        x:= x + 3 || x := x + x + 2
    coend

This implies that the two statements x:=x+3 and x :=x+x+2 can execute sequentially as well as parallelly..

Now,

Sequential part :

$x:= x + 3 \ || \ x := x + x + 2$

$x =1$ ( initial value )

First run $x = x+3$ , value of $x$ becomes $4$

Now $x=4$,  run $x = x + x + 2$  value of $x$ will be $4+4+2=10$

Finally x becomes 10.


Parallel  part:

Initialized value of $x =1$

Both will take $x$ as $1$ initially and then run independently, so

$x= x+3  = 1+3 = 4$

$x=x+x+2= 1+1+2 = 4$

But final write will be done by the process $x=x+x+2$

It will give value $4$.

$x=x+x+2$ completed its execution before $x=x+3.$

Then, x= x+3 will read value of $x$ as $4$ and then $x=x+3$ i.e. $x= 4+3 = 7$

So, here we get $\left \{ 4,7 \right \}$

Final answer is combination of both sequential and parallel part:

which is $\mathbf{\{ 4,7,10 \}}$

Option (C) .

edited by
5 votes
5 votes

Well as it is given , "Reading and writing of variables is atomic, but the evaluation of an expression is not atomic."

We can convert above program into assembly language

Expression 1 :- x = x + 1

Load x,R1; (Atomic Read)

R1 = R1 + 3;

store R1,x; (Atomic Write)

Expression 2 :- x = x + x + 2

read x.R2 ;

x = R2 + R2 + 2;

store R2,x;

This 2 code will execute giving us answer as  4,7,10 C, depending on order of execution of instructions, we can not reorder inside any expression, but we can intermix statements in both expressions. (Same we can change relative order of  statements in two different transactions, but we can no reorder statement in single transaction)

edited by
0 votes
0 votes

$x=4$ is possible, which is straightforward.


If

x:= x + 3

happens first, then

x := x + x + 2

happens, we get $x=10$


If

x := x + x + 2

happens first, then

x:= x + 3

happens, we get $x=7$


Any preemption in the midst of x:= x + 3 or x := x + x + 2 is meaningless, as x would stay 1, since the value is not yet assigned.

Answer:

Related questions