0

I found an example of a race condition that I was able to reproduce under g++ in linux. What I don't understand is how the order of operations matter in this example.

int va = 0;

void fa() {
    for (int i = 0; i < 10000; ++i)
        ++va;
}

void fb() {
    for (int i = 0; i < 10000; ++i)
        --va;
}

int main() {
    std::thread a(fa);
    std::thread b(fb);
    a.join();
    b.join();
    std::cout << va;
}

I can undertand that the order matters if I had used va = va + 1; because then RHS va could have changed before getting back to assigned LHS va. Can someone clarify?

sornbro
  • 243
  • 3
  • 12
  • 3
    Not sure what needs clarifying. You say yourself that it's a race. Races introduce undefined behavior. Anything can happen. – SergeyA Sep 04 '19 at 18:09
  • Both threads are trying to modify `va` **at the same time**, even inside for-loops. Who wins? Unknow, so the final value of `va` can be anything. – Ripi2 Sep 04 '19 at 18:11
  • 2
    I suspect that you believe that the increment and decrement operations are atomic. They’re not. – molbdnilo Sep 04 '19 at 18:13
  • Even if the operation is atomic, without synchronization there's no guarantee if or when changes to `va` are actually pushed to a place that other threads can see them. For example, `va` may very well stored in a register. – François Andrieux Sep 04 '19 at 18:13
  • 1
    BTW, optimizer are allowed to change those method as `va += 10000;`, `va += 10000;`, reducing even more "chances" to see race effect. – Jarod42 Sep 04 '19 at 18:15
  • Note that a data race is a static property of a program. It’s not a behaviour. – molbdnilo Sep 04 '19 at 18:17
  • Note that in general order matters also if you would properly synchonize access. Assume one thread would do `va = 0;` and the other `va = 1;` then even in a correct code (no data race) you do not necessarily know what thread comes first – 463035818_is_not_an_ai Sep 04 '19 at 18:28

3 Answers3

5

The standard says (quoting the latest draft):

[intro.races]

Two expression evaluations conflict if one of them modifies a memory location ([intro.memory]) and the other one reads or modifies the same memory location.

The execution of a program contains a data race if it contains two potentially concurrent conflicting actions, at least one of which is not atomic, and neither happens before the other, except for the special case for signal handlers described below. Any such data race results in undefined behavior.

Your example program has a data race, and the behaviour of the program is undefined.

What I don't understand is how the order of operations matter in this example.

The order of operations matters because the operations are not atomic, and they read and modify the same memory location.

can undertand that the order matters if I had used va = va + 1; because then RHS va could have changed before getting back to assigned LHS va

The same applies to the increment operator. The abstract machine will:

  • Read a value from memory
  • Increment the value
  • Write a value back to memory

There are multiple steps there that can interleave with operations in the other thread.

Even if there was a single operation per thread, there would be no guarantee of well defined behaviour unless those operations are atomic.

Note outside of the scope of C++: A CPU might have a single instruction for incrementing an integer in memory. For example, x86 has such instruction. It can be invoked both atomically and non-atomically. It would be wasteful for the compiler to use the atomic instruction unless you explicitly use atomic operations in C++.

Community
  • 1
  • 1
eerorika
  • 232,697
  • 12
  • 197
  • 326
4

The important idea here is that when c++ is compiled it is "translated" to assembly language. The translation of ++va or --va will result in assembly code that moves the value of va to a register, then stores the result of adding 1 to that register back to va in a separate instruction. In this way, it is exactly the same as va = va + 1;. It also means that the operation va++ is not necessarily atomic.

See here for an explanation of what the Assembly code for these instructions will look like.

In order to make atomic operations, the variable could use a locking mechanism. You can do this by declaring an atomic variable (which will handle synchronization of threads for you):

std::atomic<int> va;

Reference: https://en.cppreference.com/w/cpp/atomic/atomic

fendall
  • 524
  • 2
  • 8
  • imho your first part is slightly misleading. UB can result in assembly that looks fine one day but not the other day – 463035818_is_not_an_ai Sep 04 '19 at 18:24
  • @formerlyknownas_463035818 I've tried to make this more clear by emphasizing that the c++ operation is non-atomic because the underlying assembly instructions perform the get and set separately. – fendall Sep 04 '19 at 18:37
  • actually only now I understand what you are saying ;) +1 – 463035818_is_not_an_ai Sep 04 '19 at 18:38
  • It is not relevant whether or not the increment instructions of the underlying architecture are atomic. They may or may not be, but a data race in the C++ memory model is still undefined behavior of which the optimizer will make use accordingly. Also, instruction sets like x86 have instructions that increment a memory location directly without loading into a register. – user17732522 Sep 18 '22 at 18:38
4

First of all, this is undefined behaviour since the two threads' reads and writes of the same non-atomic variable va are potentially concurrent and neither happens before the other.

With that being said, if you want to understand what your computer is actually doing when this program is run, it may help to assume that ++va is the same as va = va + 1. In fact, the standard says they are identical, and the compiler will likely compile them identically. Since your program contains UB, the compiler is not required to do anything sensible like using an atomic increment instruction. If you wanted an atomic increment instruction, you should have made va atomic. Similarly, --va is the same as va = va - 1. So in practice, various results are possible.

Brian Bi
  • 111,498
  • 10
  • 176
  • 312