concurrent programming

Question

// prog.c
int x = 0;      // shared variable.

void function(int s) {
    int i=0;   // local to function
    for(i=0;i<s;i++)
        x++;
}
int main() {
    parbegin
        function(8);
        function(13);
    parend
}

note : increment on x can be assumed to be executed in CPU in three steps (load,increment,store)

What is the minimum possible value of x, after completion of the program prog.c ?

Comments

Is the answer 7 ??If yes then let me know..I will explain my approach

---

You explain your answer ! I don't have answer at present :p

---

Sorry corrected..It should be 2

Answer 1

Here u have to assume that increment  operation is a series of three step.

a)Loading the count value into register from memory,

b)incrementing it in the register and

c)storing it back into the memory. as mentioned in the question as well

We should remember that since these are 3 separate steps of a single increment step , we can take preemption in between these 3 sub operations as these are not mentioned to be performing atomically.

Consider 2 processes P1 and P2 calling  function()  in the main().Since they are parallel process we can imagine the two given function calls in the main() as concurrent processes P1 and P2.

Let P1 performs 8 iterations and P2 performs 13 iterations.Let R1 and R2 be the respective registers for storing the value of count.

Initially x = 0.P1 starts the execution.It uses the 2 steps of incrementing x in the first iteration as mentioned earlier.So R1 value = 1.But x = 0 still since value of R1 is not stored.Then we preempt P1 and we run 12 iterations of P2 and performing all the 3 steps of incrementation in each iteration.

Then we preempt P2 and store the value of R1 in x and 1st iteration of P1 is over. Value of x = 1.Now we preempt P1 and run 1st 2 steps of 13th and final iteration in P2.So x value will be incremented to 2 and hence content of R2 = 2.But now we preempt and run the 2nd to 8th and final iteration of P1.With this P1 execution is over and finally we store the value of x from R2.So now value of x = 2 and with this P2 execution is also over.

Hence , minimum achievable value of x which is a shared variable = 2

Comments

:D yes

---

Beautiful explanation

---

Answer is 2.

P1(8) and  p2(13)

P1 will load value of x=0 then P2 will executes 12 Instruction (x=12) and for 13th instruction (just before load) p1 will perform store of Instuction 1 (x=1).

Now P2 will Load and increment x = 2. 

Now p1 will executes its all instuction then finally P2 will store its value.