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!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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
Improve this answer
$\endgroup$
2
  • $\begingroup$ Hi @Chi, can you please elaborate a bit more from line 4? It's difficult to follow after that.... $\endgroup$ Commented Jan 4, 2019 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$ Commented Jan 4, 2019 at 17:32

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.