c++multithreadingatomicrelaxed-atomics

A Minimum Ordering Requirement


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

Solution

  • 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.