What is the minimum and maximum value of Counter when the two threads are executed concurrently?

Question

I'm studying for an exam and have run into a problem that I do not understand. The main program starts two threads that execute the following program concurrently, whenever both threads terminate the program will print the result of counter. I am assuming that the maximum value of counter will be 10? But what will the minimum value be? 1?

The following image shows the pseudocode for the program.

Answer 1

First of all, lets clarify the functional difference between

i = i+1

and

cnt = counter
counter = cnt+1

There is none! Both segments must first read a value from global memory into a register, operate on/with said register and write the result back to global memory. So both execute three instructions; a read, an add, and a write.

With that said, the rest of the problem is an exercise of arranging blocks in a way that one thread "undoes" the work of the other, either for i or for counter.

For the minimum value of counter, see the execution flow below. The grey box represents a single iteration of the loop. The value of counter, after both threads finish, will be 1.

For the maximum value of coutner, see the execution flow below. Again, the grey boxes represent a single iteration of the loops. If all iterations are executed with the alignment shown, at the end, counter will be 20.

Answer 2

While I was initialy convinced by the two previous answers, a colleague of mine showed me the light about this exercise.

He claims that the maximum value of the counter is $65$, not $20$.

As proof, consider the following execution :

• Thread $t$ reads $i = 0$; counter = 0
• Thread $u$ executes $10$ loops in total; counter = 10
• Thread $t$ writes $i = 1$;
• Thread $u$ enters the loop and reads $i = 1$;
• Thread $t$ executes $10$ loops in total; counter = 20
• Thread $u$ writes $i = 2$;
• Thread $t$ enters the loop and reads $i = 2$;
• Thread $u$ executes $9$ loops in total; counter = 29
• Thread $t$ writes $i = 3$;
• …
• Thread $t$ writes $i = 9$;
• Thread $u$ enters the loop and reads $i = 9$;
• Thread $t$ executes $2$ loops in total; counter = 64
• Thread $u$ writes $i = 10$;
• Thread $u$ finishes the loop; counter = 65
• Both tests $i < 10$ are false and both threads exit.

The value $65$ is $10 +10 + 9 + 8 + … + 2 +1$.

Answer 3

The minimum cannot be $0$, because $\text{cnt}\ge0$, and some assignment $\text{counter}=\text{cnt}+1$ will inevitably be performed.

But the minimum can be $1$, as follows:

• the left process executes with $i=0$, until the assignment $\text{cnt = counter;}$ (hence $\text{i}==1$ and $\text{cnt}==0$).

• the right process executes all iterations with $i= 1, \cdots9$ and exits.

• the left process finishes processing and performs the assigment $\text{counter = 0 + 1;}$ and terminates.

Then, unless the incrementation of $i$ is done atomically, the maximum is $20$, as follows:

• both processes execute the $\text{while}$ test and the RHS of the assignment $\cdots=\text i+1$.

• both processes perform the LHS of the assignment, $\text i=\cdots$.

• both processes execute the rest of the loop without overlap.

This way, both loops run $10$ times, for a total of $20$.

If the incrementation is atomic, the maximum is $10$.