Multiple threads accessing one variable

Question

I found this question in the textbook that I am reading. A solution is also provided below. I had problems understanding how minimal could be 2. Why couldn't the thread read 0, all other threads are executed, and it writes 1? And regardless of whether it is 1 or 2, should the last thread record still fill 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 one thread was running this application, you expected the final output to be 5. What if 5 threads were running the same loop in parallel? What are the largest and smallest n values? The biggest being self-confident: 25, with 5 increments from 5 threads. However, the discussion of the smallest possible value is more complicated. Hint: n may be less than 5, but you decide why.

Decision:

With five threads executing this five-period cycle, and without protection against simultaneous accesses, the lowest value that can reach n is two. Understanding how to achieve this result is easiest when working backward from the final result. There must be two for the final output, a stream must read the value of one of n, increase it, and then two is written. This means that another thread wrote one, which means that it also reads zero initially (which is also the starting value for n). This explains the behavior of two of the five threads. However, for this behavior, the results of the other three threads had to be overwritten. You can do two valid executions for this. Either 1) all three threads started and completed execution between the first thread that reads zero and writes one, or 2) all three threads started and execution ended between the final reading of the thread and writing two. Both execution orders are valid.

Answer 1

Assuming each thread has a local i (i.e., each thread will execute for 5 iterations, no matter what), try to get 1 as the result. This would mean that the last thread to write the value would have to read 0 for n at its 5th iteration. The only way this could happen is if the thread has never been written to n at the beginning of this thread of the 5th iteration, but for this thread at the 5th iteration, this thread itself should be written to n , therefore, this is impossible.

Thus, the smallest possible result is 2, which can happen, for example, as follows: the last thread for writing n completed 4 iterations, then the other thread writes 1, the last thread reads 1 at the beginning of its 5th iteration, all other threads complete all iterate to the last thread, and finally, the last thread completes its 5th iteration by writing 2.

Disclaimer I answer a conceptual question about multithreading - as others have pointed out, the lack of atomicity can lead to undefined behavior and arbitrary results if C code is presented, like, Based on the question of the "self-evident" case with the largest number of cases, I assume that the author of the textbook either aware of this, or uses a type C pseudo-code to illustrate the concept. If the former, then the correct answer will be that the book is incorrect, but I think that the answer in the latter case is also educational.

Answer 2

Simple understanding to add: Addition, Subtraction, etc. in C using the + operator is just one operation. Down at the assembly level, operation + consists of several instructions. If multiple threads were supposed to access the same variable, and there was a bad alternation of these instructions, the end result could be a terribly wrong result - this is another reason why we need things like mutexes, semaphores and condition variables.

Answer 3

The largest should be self-help: 25, with 5 increments from 5 threads.

Totally and completely wrong. No matter what they say, this should never happen (at least about things related to flows), period.

  int tmp = n; tmp = tmp + 1; n = tmp; 

Imagine a processor that did not have an increase operation but had an effective add 10 operation and an effective subtract nine operation. On such a processor, tmp = tmp + 1; can be optimized to tmp += 10; tmp -= 9; tmp += 10; tmp -= 9; . The compiler can also fully optimize tmp by working on n .

Thus, this code can become equivalent:

 n += 10; n -= 9; 

Now imagine this happening: all five threads add 10, so n now 50. The first thread reads 50, the other four threads subtract 9. The first thread subtracts 9 from 50, which it reads and writes 41. Therefore, when everything is done, n is 41.

So, that which is claimed to be self-evident, completely false. The one who wrote this does not understand the threads in C.

if each thread writes 1, then the final value cannot be magical with something else

Also completely and completely false. Consider a processor that writes 1, first writing 0, and then increasing the value. If this happens on two cores, the end result may be 2. This tutorial was written by someone who fundamentally does not understand threads and undefined behavior.

(I suppose this tutorial is not limited to any particular context in which what it says is true. For example, it can use the “C-like” code as a form of assembly language, and it can make assumptions about platforms , in which aligned integers have specific guarantees, but if so, what he teaches is not translated into C code at all and will only apply to people who write assembly code on processors whose rules comply with the textbook's assumptions.)

Answer 4

The fact is that the stream uses the same data instance. In addition, it is assumed that all other threads execute at the same execution speed.

Therefore, when each thread rounds the loop (gets to the i++ part of the for ), they all increase i almost simultaneously, so it looks as if the code was written:

  for (i = 0; i < 5; i++, i++, i++, i++, i++) ... 

at least in the last resort, which gives the minimum number of iterations.