0

I was asked this question in an interview recently. The question is if we have a function that takes a reference of int i as parameter and only does i++. There is no any thread synchronizations. Now in main function, we initialize variable i with 0, then we create 7 new threads to run the same function and pass the same variable i, and after all threads are joined, how many possible values the variable i has? Thank you very much!

I tried thinking about the instructions of doing i++. Like load, add and store instructions. Assume we’re using g++ compiler and in Linux OS.

Qixiang Chao
  • 3
  • 2

3 Answers3

1

The code you describe has undefined behavior. The value of i is undefined. If you do compile and run the code and print i on the screen the output could be anything. It could be 42 or "hello world".

Perhaps the question was meant to tease you into considering how many different ways there are to have multiple threads increment i and how that could affect the output. However, when code has undefined behavior, then logical reasoning is futile.

On the other hand, if you care about what actually happens in the compiled code, then the only way to know that is to look at the compiler generated assembly. What the resulting program does is undefined, but it certainly does something. Though you can only know what that is after you compiled it and study the assembly. The C++ standard does not describe what such a program will do and whatever you get is not portable.

463035818_is_not_an_ai
  • 109,796
  • 11
  • 89
  • 185
  • Hi, thank you very much for your answer. Sorry I should have provided more details. What if we declare and assign 0 to variable `i` and pass it to all threads? – Qixiang Chao Apr 02 '22 at 15:15
1

The specific instructions used to increment the variable depends on the instruction set, but unless using some kind of atomic increment, it will break down into load/add/store operations as you are describing.  On x86 that might be done with a single inc instruction, but without locking it will still break down to internal load/add/store operations.

You will want to look at the possible interleaving of those sequences.  The interleaving is caused by interruption of the non-atomic sequences.  Here is one possible such possible interleaving:

thread 1      thread 2
 load   
               load
               add
               store
 add
 store

That sequence will leave the variable incremented only once, by thread 1, because thread 2's increment operation is effectively ignored — thread 1 stores last so "wins".  (Thread 2 started with the wrong value in some sense anyway, so thread 2's store has the same value (+1) as thread 1's store.)

So, on one extreme the answer would be that the variable will be incremented only by one.  On the other extreme, if each thread successfully increments without interruption of that sequence, then the variable would be incremented 7 times.  All intermediate values (incremented by 2-6) are also possible.

Since there is no synchronization at all, we also have to consider the possibility that we observe the original 0 after the joins, though I think this is unlikely due to the natural synchronization of system calls involved in creating threads and joining them.

Erik Eidt
  • 23,049
  • 2
  • 29
  • 53
  • 1
    `join` gives rel/acq synchronization, so you can't see the original `0`. The main thread will synchronize-with each of the threads that terminate, so everything in those threads happens-before main's final read of `i`. (Hypothetically you could see literally anything, since the program had data-race UB. If compiled with `-fsanitize=thread`, that part of main might never be reached because the program aborts; `clang++ -fsanitize=thread` is a conforming C++ implementation, as much as without that option.) – Peter Cordes Apr 03 '22 at 00:40
0

As mentioned in other answers, there is UB.

Also, it is possible to have situations where this number isn't increased at all or incremented a few times (less than 7) or whatever else. Since it's not an atomic variable (the question didn't mention that) - it will yield very unstable/unpredictable results. See/google for "memory model" for more explainations.

Galimov Albert
  • 7,269
  • 1
  • 24
  • 50
  • 1
    It's theoretically possible to have literally anything happen because of data-race UB. But how could you practically have `main` read `i == 0` (not incremented at all) after joining the threads? All of them will have stored a number that's `1` or higher, since they all read a value that was `0` or higher. Pretty sure only values from 1..7 are possible on real hardware. (Values as low as `1` are rather unlikely; all threads having to read the original 0 before any store a new value, but that is in theory possible. Unlike having none of them store, or store a 0.) – Peter Cordes Apr 03 '22 at 00:43
  • Of course, a DeathStation9000 C++ implementation might do `i++` as `i-=2;` `i+=3` or some other thing that involves making a different value temporarily appear in memory, but then results like `-1` would also be possible. I think the question is assuming a "normal" non-atomic increment. If you mean something else, you should be clear about it. – Peter Cordes Apr 03 '22 at 00:48