A Minimum Ordering Requirement

143 views Asked by At

Let x and y be two different variables of type std::atomic<int> and assume that the current value of both of them is 1. What is a most relaxed set of ordering requirements so the the following code generates some output? (i.e., what should be used for order1 ... order4?)

// Thread 1
x.store(0, order1);       // A
if(0 == y.load(order2))   // B
  std::cout << '1';       // C
// Thread 2
y.store(0, order3);       // E
if(0 == x.load(order4))   // F
  std::cout << '2';       // G
3

There are 3 answers

3
walnut On BEST ANSWER

You need sequential consistency on all operations.

Release/acquire does not actually impose any ordering here, since there is no store before the release-store or load after the acquire-load, which would be ordered by it.

Relaxed memory ordering on any of the stores, e.g. x.store could cause the stores to become visible in different orders in the two threads. It then does not violate the sequential ordering of the remaining operations to have the relaxed store be visible after the load in the other thread, while the other store still is ordered after its corresponding load in the sequentially consistent total order.

With sequential ordering on all operations output is guaranteed, because there must be a total order of the sequential operations observed the same way in all threads. This order must be consistent with the sequencing order in the threads, i.e. x.store < y.load and y.store < x.load. The only possibilities are:

x.store < y.load  < y.store < x.load
x.store < y.store < x.load  < y.load
x.store < y.store < y.load  < x.load

y.store < x.load  < x.store < y.load
y.store < x.store < y.load  < x.load
y.store < x.store < x.load  < y.load

All of which observe for one of the variables a load after the store, triggering one of the cout statements.

If e.g. x.store is not memory_order_seq_cst, then, while it still needs to be sequenced before y.load in thread 1, it could become visible after x.load in thread 2.

y.load < y.store < x.load would then still satisfy the sequential consistency of the other operations and the modification order of x is trivially satisfied anyway.

0
LWimsey On

#StoreLoad reordering can cause both loads to return the old value, so you need full sequential consistency on all 4 operations to prevent that.

Read up on store buffers to understand what causes this type of reordering.

0
curiousguy On

Two simple rules:

  • as a first action after start of parallelism (start of threads), a release fence or operation doesn't have anything to make visible (in other threads), so nothing is "released" and the release is useless (everything was previously visible and is equally visible by threads started at the same time);
  • as a last action before end of parallelism (end of threads), an acquire fence or operation doesn't have anything to make visible (in that thread) that wouldn't be visible in the common parent thread

Here you have:

x.store(0, order1);       // A
if(0 == y.load(order2))   // B
  • a store at the start
  • a load at the end

so neither acquire nor release semantic can make any difference.