CODEWITHSUNDEEP
c++c++11concurrency
q0987
q0987

Reputation: 35984

why there is no data-race in the following case?

A data race occurs when two threads access the same variable concurrently and at least one of the accesses is a write.

https://isocpp.org/wiki/faq/cpp11-language-concurrency

// start with x==0 and y==0
if (x) y = 1;   // Thread 1 
if (y) x = 1;   // Thread 2

Is there a problem here? More precisely, is there a data race? (No there isn’t).

Why does the original article claim that there is no data race here?

Upvotes: 9

Views: 2121

Answers (5)

Vaughn Cato
Vaughn Cato

Reputation: 64308

Because x and y are both zero, the abstract machine defined by the C++ standard can't write to either memory location, so the only way this could be a problem is if the implementation decided to write to the memory location anyway. For example, if it transformed 

if (x) y = 1;

into

y = 1;
if (!x) y = 0;

This is a potentially valid rewrite under the as-if rule since the observed behavior by any one thread is the same (C++14 1.9 [intro.execution])

The semantic descriptions in this International Standard define a parameterized nondeterministic abstract machine. This International Standard places no requirement on the structure of conforming implementations. In particular, they need not copy or emulate the structure of the abstract machine. Rather, conforming implementations are required to emulate (only) the observable behavior of the abstract machine as explained below.

This would in fact have been a valid rewrite prior to C++11, but since C++11, threads of execution are considered. Because of this, the implementation is not allowed to make changes that would have different observed behavior across threads as long as no data race occurs in the abstract machine.

There's a special note in the C++14 standard that applies here (C++14 1.10 [into.multithread] paragraph 22)

[ Note: Compiler transformations that introduce assignments to a potentially shared memory location that would not be modified by the abstract machine are generally precluded by this standard, since such an assignment might overwrite another assignment by a different thread in cases in which an abstract machine execution would not have encountered a data race. ...

Because of this, the rewrite isn't valid. The implementation has to preserve the observed behavior that x and y are not modified, even across threads. Therefore, there is no data race.

Upvotes: 9

Misgevolution
Misgevolution

Reputation: 845

If x is not set, setting y to 1 doesn't happen and vice versa. So, things here are indeed happening sequentially.

Upvotes: 0

fedepad
fedepad

Reputation: 4609

I found this article written by Hans-J. Boehm illuminating:
http://www.hpl.hp.com/techreports/2009/HPL-2009-259html.html#races

We say that two ordinary memory operations conflict if they access the same memory location (for example, variable or array element), and at least one of them writes to the location.

We say that a program allows a data race on a particular set of inputs if there is a sequentially consistent execution, that is an interleaving of operations of the individual threads, in which two conflicting operations can be executed "simultaneously". For our purposes, two such operations can be executed "simultaneously", if they occur next to each other in the interleaving, and correspond to different threads.

And the article goes on to our point:

Our definition of data race is rather stringent: There must be an actual way to execute the original, untransformed program such that conflicting operations occur in parallel. This imposes a burden on compilers not to "break" programs by introducing harmful data races.

As stated in the article, which report the same example (and others): There's no sequentially consistent execution of this program in which Thread 1 assigns to y, since x and y never become nonzero. Indeed you never satisfy the condition, so no one is writing to the variable that the other thread might be reading.

To understand the difference with the case where a data race exists, try to think about the following example in the article:

y = ((x != 0)? 1 : y)  # Thread 1
y = 2;                 # Thread 2

In this last case it's clear that can happen that y is assigned (write) to by Thread 1 while Thread 2 executes y = 2; (y is written to by Thread 1 no matter what). A data race can happen.

Upvotes: 2

Nicol Bolas
Nicol Bolas

Reputation: 473232

Data races are not static properties of your code. They are properties of the actual state of the program at execution time. So while that program could be in a state where the code would produce a data race, that's not the question.

The question is, given the state of the system, will the code cause a data race? And since the program is in a state such that neither thread will write to either variable, then the code will not cause a data race.

Data races aren't about what your code might do. It's about what they will do. Just as a function that takes a pointer isn't undefined behavior just because it uses the pointer without checking for NULL. It is only UB if someone passes a pointer that really is NULL.

Upvotes: 12

Louis Langholtz
Louis Langholtz

Reputation: 3123

Neither thread will be writing since neither variable is non-zero before the conditionals.

Upvotes: 14

Related Questions