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.
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.
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.
The largest should be selfevident: 25, with 5 increments from 5 threads.
Totally and completely wrong. Whatever said this should not ever be listened to (at least about things involving threading), period.
int tmp = n;
tmp = tmp + 1;
n = tmp;
Imagine a CPU that had no increment operation, but had an efficient "add 10" operation and an efficient "subtract nine" operation. On such a CPU, tmp = tmp + 1; could be optimized to tmp += 10; tmp -= 9;. The compiler could also optimize out tmp entirely by operating on n.
So this code could become the equivalent of:
n += 10;
n -= 9;
Now imagine this happens: All five threads add 10, so n is now 50. The first thread reads the 50, the other four threads subtract 9. The first thread subtracts 9 from the 50 it read and writes 41. So when all is done, n is 41.
So what is claimed to be self-evident is utterly false. Whoever wrote that doesn't understand threading in C.
if every thread writes a 1 then the final value cannot magically be something else
Also utterly and completely false. Consider a CPU that writes a 1 by first writing a 0 and then incrementing the value. If this happens on two cores, the final result could be 2. This textbook was written by someone who fundamentally doesn't understand threading and undefined behavior.
(I'm assuming this textbook isn't limited to some special context in which what it's saying is true. For example, it might be using "C-like" code as a form of platform-neutral assembly language and it might be making assumptions about platforms in which aligned integers have specific guarantees. But if that's so, what it's teaching does not translate to C code at all and would only apply to people writing assembly code on CPUs whose rules match the textbook's assumptions.)