What should be the minimum value when the two threads are executed concurrently

Question

int count=0;
void *thfunc()
{
    int ctr=0;
    for(ctr=0;ctr<100;ctr++)
    count++;
}

If *thfunc() is executed by two threads concurrently in a uniprocessor system, what will be the minimum value of count when both threads complete their execution? Assume that count++ is performed by using three instructions:(1) Read value of count from memory to a CPU register R,(2) Increment R,(3) Store the value in memory.

(a) 200

(b) 2

(c) 100

(d) None of the above

According to me, the answer should be 100. I cant find any execution sequence in which the count value can go down below 100. But my manual says that the answer is 2.

Can anyone please tell me what I am doing wrong? Also, please explain how the answer 2 is obtained?

Thanks in advance!

Answer 1

Here's a tricky interleaving. R1,R2 denote the independent logical registers used by the threads, while count is the shared variable in memory.

• Thread 1 starts its first iteration, performing only a read. count=0, R1=0, R2=?
• Thread 2 performs 99 iterations. count=99, R1=0, R2=99
• Thread 1 completes its first iteration (increment and write). count=1, R1=1, R2=99
• Thread 2 starts iteration #100, performing only a read. count=1, R1=1, R2=1
• Thread 1 performs the other 99 iterations. count=100, R1=100, R2=1
• Thread 2 completes its iteration #100 (increment and write). count=2, R1=100, R2=2
• Both threads now exit, having completed their execution.

So, the sequence is something like

rX = read by thread X
iX = local increment by thread X
wX = write by thread X

r1,
r2,i2,w2,r2,i2,w2,...,r2,i2,w2,  (99 full iterations)
i1,w1,
r2,
r1,i1,w1,r1,i1,w1,...,r1,i1,w1,  (99 full iterations)
i2,w2