Happens before

stackoverflow Confusion about happens before relationship in concurrency

Below is an example given in Concurrency in Action , and the author says the assert may fire, but I don't understand why.

#include <atomic>
#include <thread>
#include <assert.h>
std::atomic<bool> x,y;
std::atomic<int> z;
void write_x_then_y()
{
  x.store(true,std::memory_order_relaxed);
  y.store(true,std::memory_order_relaxed);
}
void read_y_then_x()
{
  while(!y.load(std::memory_order_relaxed));
  if(x.load(std::memory_order_relaxed))
  ++z;
}
int main()
{
  x=false;
  y=false;
  z=0;
  std::thread a(write_x_then_y);
  std::thread b(read_y_then_x);
  a.join();
  b.join();
  assert(z.load()!=0);
}

NOTE: read_y_then_x() 中，while(!y.load(std::memory_order_relaxed)); 表明它需要等待 y，即它依赖y

As far as I know, in each single thread, sequenced before also means happens before. So in thread a the store to x happens before y, which means x should be modified before y and the result x.store should be visible before y is modified.

But in this example the author says that the store between x and y could be reordered, why? Does that violate the rule of sequenced before and happens before?

comments

This might explain things about relaxed ordering en.cppreference.com/w/cpp/atomic/memory_order#Relaxed_ordering – Sami Kuhmonen Jul 29 '18 at 13:54

@SamiKuhmonen sequenced before relationship does not prevent reordering? Then what's the usage of sequenced before? – scottxiao Jul 29 '18 at 14:13

x.store happens-before y.store and y.load happens-before x.load - but x.store doesn't happen-before x.load. Happens-before relationship is not necessarily transitive in the presence of relaxed operations; that's kind of their whole point. – Igor Tandetnik Jul 29 '18 at 14:20

NOTE: 上述happens-before relation是从源程序中抽象出来的

@IgorTandetnik but y.store happens before while(!y.load(std::memory_order_relaxed)) , so x.store hapeens before x.load? – scottxiao Jul 29 '18 at 14:21

NOTE: 并不能保证 : y.store happens before while(!y.load(std::memory_order_relaxed))

The conclusion doesn't follow from the premise(前提). Yes, y.store happens-before y.load. No, x.store does not happen-before x.load. You have a sequentially-consistent model of execution in your head - but relaxed operations violate that model; that's why they are called "relaxed", and that's why they are difficult to reason about. – Igor Tandetnik Jul 29 '18 at 14:23

@IgorTandetnik since y.store happens before y.load==true, and happens before relationship is trasitive, why doesn't x.store happens before x.load? – scottxiao Jul 29 '18 at 14:38

Again, happens-before relationship is not in general transitive. In particular, it is not transitive in the presence of relaxed operations. Would it be too much to ask for you to read a comment in full before responding? – Igor Tandetnik Jul 29 '18 at 14:58

The Concurrency in Action says "It’s also a transitive relation: if A inter-thread happens-before B and B inter-thread happens-before C, then A inter-thread happens-before C.". – scottxiao Jul 29 '18 at 15:02

happens-before and inter-thread happens-before are two different relations. Here, y.load does not inter-thread happens-before x.load (since both are on the same thread). – Igor Tandetnik Jul 29 '18 at 15:14

@IgorTandetnik What's the differences between happens before and inter-thread happens before? – scottxiao Jul 29 '18 at 15:41

eel.is/c++draft/intro.multithread#intro.races-10 – Igor Tandetnik Jul 29 '18 at 15:45

@IgorTandetnik Your linkage says they are not different relations, inter-thread happens before belongs to happens before. – scottxiao Jul 29 '18 at 16:14

They are different relations, where one is a subset of the other. The subset is transitive; the superset is not. In particular, if A inter-thread happens-before B and B is sequenced-before C, this doesn't necessarily mean that A happens-before C (even though A happens-before B and B happens-before C). – Igor Tandetnik Jul 29 '18 at 16:23

A

From thread a perspective, it looks as if x.store happens before y.store. However, from thread b perspective, it can look as if they are reordered. https://koheiotsuka701.medium.com/memory-model-basic-d8b5f8fddd5f