TIFR CSE 2010 | Part B | Question: 28

Question

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:

• A. $\{4\}$
• B. $\{8\}$
• C. $\{4, 7, 10\}$
• D. $\{4, 7, 8, 10\}$
• E. $\{4, 7, 8\}$

Comments

here it is given that the evaluation of variable x is not atomic . so we can consider to take different values of x in a single statement , which make the answer
'c'

---

PPT on Cobegin

Answer 1

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

Comments

since both process are concurrent then why this:

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

---

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

It will give value 44.

Why is it so?

---

$\underline{\mathbf{Conclusion}}$

So, according to me there are $\mathbf 4$ cases in the nut-shell.

1. When $1^{st}$ runs, and then $2^{nd}$ Ans is $10$
2. When $2^{nd}$ runs, and then $1^{st}$ runs.  Ans is $7$

3. When first and second both run in parallel and final write is done by the second.  Answer $=4$

4. when second and first both runs in parallel and final write is done by the first. Answer $ = 4$

Answer 2

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)

Comments

There can be multiple read for x in a block..

---

actually within an expression x can have 2 different values as per question,

---

@Arjun, I don't think so. Evaluation of expression is not Atomic - It means that expression evaluation can proceed in parallel. ( I also used same method on 2-3 TIFR questions in recent papers TIFR 2015 & Other one I don't remember ) They had similar code snippets & I get same answers as there key. So I think within expression x can have single value.

---

you have those questions?

---

9. Consider the concurrent program
x:=1;
cobegin
x := x + x + 1 || x := x + 2
coend;
10
Reading and writing of a variable is atomic, but 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
(a) {3}
(b) {7}
(c) {3,5,7}
(d) {3,7}
(e) {3,5}
Answer given is C. TIFR 2012.

---

1 + 1 + 1 = 3
1 + 2 = 3
3 + 1 + 1 = 5
3 + 3 + 1 = 7
3 + 2 = 2

are the possible cases. Variable x can take different value in a block- just that answer is not getting different.

---

In 2015 it's same. Answer is not changing. !

---

In this question also it won't change rt?

---

x  = x + x + 2, Here x can be either 1 or 4. So NO. It adds up to 4, 7 or 10.

---

Is Cobegin-Coend == Parbegin-Parend?

Answer 3

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

i think ans is (4,7,8,10)

Comments

would you share why you think so?