Multiple threads accessing one variable

Question

I found this question in a textbook I am reading. The solution is given below it as well. I'm having trouble understanding how the minimum could be 2. Why couldn't a thread read 0, all other threads execute and it writes 1? And whether it is 1 or 2, the thread writing last must still complete its own loop?

int n = 0;
int main(int argc, char **argv) {
 for (i = 0; i < 5; i++) {
 int tmp = n;
 tmp = tmp + 1;
 n = tmp;
 }
 return 0;
}

If a single thread ran this application, you would expect the final output to be 5. What if 5 threads ran the same loop in parallel? What are the largest and smallest values n could have? The largest should be selfevident: 25, with 5 increments from 5 threads. However, reasoning about the smallest possible value is more difficult. Hint: n can be less than 5, but it is up to you to figure out why.

Solution:

With five threads running this five-iteration loop and with no protection from concurrent accesses, the lowest value that n can reach is two. Understanding how to reach this result is easiest when working backwards from the final result. For the final output to be two, a thread must have read a value of one from n, incremented it, and then written two. That means that another thread wrote one, implying that it also initially read zero (which is also the starting value for n). This accounts for the behavior of two of the five threads. However, for this behavior to occur the results of the other three threads must have been overwritten. Two valid executions could accomplish this. Either 1) all three threads began and completed execution between the first thread reading zero and writing one, or 2) all three threads began and completed execution between the final thread reading one and writing two. Both execution orderings are valid.

Answer 1

Assuming every thread has a local i (i.e., every thread will run for 5 iterations no matter what), let's try to get 1 as the result. This would mean the last thread to write a value would have to read 0 for n on its 5th iteration. The only way this could happen is if no thread has yet written to n at the start of that thread's 5th iteration, yet for that thread to be on its 5th iteration that thread itself must have written to n, hence it is not possible.

Thus the smallest possible result is 2, which can occur, e.g., as follows: the last thread to write n has completed 4 iterations, then another thread writes 1, the last thread reads the 1 at the start of its 5th iteration, all other threads complete all their iterations before the last thread, and finally the last thread completes its 5th iteration writing the 2.

Disclaimer: I am answering the conceptual question about multithreading – as others have pointed out, the lack of atomicity might lead to undefined behaviour and arbitrary results if the C code presented were used as is. Based on the question's “self-evident” largest number case I'm guessing the textbook's author either doesn't realise this, or is using a C-like pseudo code to illustrate the concept. If the former, then the correct answer would be that the book is wrong, but I think the answer in the latter case is also educational.

Answer 2

Just some insight to add on: Adding, subtracting, etc in C using the + operator is more than just 1 operation. Down in assembly level the + operation is composed of multiple instructions. If multiple threads were to be accessing one variable and there is a bad interleaving of these instructions, the end result could be a horribly incorrect result -> this is another reason why we need things like mutexes, semaphores, and condition variables.