3
$\begingroup$
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!

$\endgroup$
4
$\begingroup$

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
$\endgroup$
  • $\begingroup$ Hi @Chi, can you please elaborate a bit more from line 4? It's difficult to follow after that.... $\endgroup$ – Abhilash Mishra Jan 4 at 17:29
  • 1
    $\begingroup$ @AbhilashMishra In line 4, thread 2 has to perform its last loop iteration. It starts reading count into its local register R2. Before it increments and store it in memory, thread, thread 1 performs 99 iterations (line 5). Can you point out the part where you need more help? $\endgroup$ – chi Jan 4 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.