How sequentially consistent ordering in c++ define a total order?

Question

I am reading the following example from https://en.cppreference.com/w/cpp/atomic/memory_order#Sequentially-consistent_ordering. And I have a hard time understanding

• under what situation assert(z.load() != 0); will fail.
• why does using memory_order_seq_cst over memory_order_ack_rel make z never be 0.

#include <thread>
#include <atomic>
#include <cassert>
 
std::atomic<bool> x = {false};
std::atomic<bool> y = {false};
std::atomic<int> z = {0};
 
void write_x()
{
    x.store(true, std::memory_order_seq_cst);
}
 
void write_y()
{
    y.store(true, std::memory_order_seq_cst);
}
 
void read_x_then_y()
{
    while (!x.load(std::memory_order_seq_cst))
        ;
    if (y.load(std::memory_order_seq_cst)) {
        ++z;
    }
}
 
void read_y_then_x()
{
    while (!y.load(std::memory_order_seq_cst))
        ;
    if (x.load(std::memory_order_seq_cst)) {
        ++z;
    }
}
 
int main()
{
    std::thread a(write_x);
    std::thread b(write_y);
    std::thread c(read_x_then_y);
    std::thread d(read_y_then_x);
    a.join(); b.join(); c.join(); d.join();
    assert(z.load() != 0);  // will never happen
}

As far as I under, for either read_x_then_y or read_y_then_x, they could observe a state among:

• x = true and y = false
• x = false and y = true
• x = true and y = true
• x = false and y = false

The first 2 cases make z = 1 (eventually 2), the third case makes z = 2, and the last case makes read_x_then_y and read_y_then_x wait until one of `x' and 'y' become true. However, according to the cppreference

This example demonstrates a situation where sequential ordering is necessary. Any other ordering may trigger the assert because it would be possible for the threads c and d to observe changes to the atomics x and y in opposite order.

I don't understand how is that possible. How would the changes to x and y be in the opposite order?

In addition, I am wondering how would the use of memory_order_seq_cst solves the problem. Is it forcing the x.load in read_x_then_y must be executed before y.load?

Answer 1

For read_x_then_y:

void read_x_then_y()
{
    while (!x.load(std::memory_order_seq_cst))
        ;
    if (y.load(std::memory_order_seq_cst)) {
        ++z;
    }
}

The first loop waits until x is loaded as true. Then ++z is executed if y is loaded as true. At this point, y could be either true or false. Both executions are possible.

Likewise, for read_y_then_x, both executions are possible.

What prevents the following?

• read_x_then_y loads x as true but y as false
• read_y_then_x loads y as true but x as false

In this case, the assert would trigger.

The answer is that this is the guarantee sequentially consistent ordering provides. All such atomic operations share a single total modification order. Either the store to x happens first, or the store to y happens first, in this order. All loads will agree on that order.

Release stores and acquire loads provide much less: any stores before the release stores in the same thread are visible to acquire loads in other threads. So all variables stored to by write_x before the store, would be loadable by read_x_then_y after x is loaded. Of course, there are no such stores.

Answer 2

I suggest reading my introduction to memory orders, which explains most of this.

How would the changes to x and y be in the opposite order?

Because by default (in absence of seq_cst) threads only agree on the order of operations on each individual atomic variable. They can disagree on how those operations are interleaved.

So if you remove seq_cst, all threads will merely agree that x and y start as false and are changed to true, but they can disagree which of them is changed first.

In addition, I am wondering how would the use of memory_order_seq_cst solves the problem.

Because for seq_cst operations, all threads agree on how they are interleaved. In other words, there's a single total order (that all threads agree on) in which all seq_cst operations happen.

So if thread read_x_then_y() sees x == true && y == false and does z++, then we've estabilished that x = true "happens before" y = true, so the thread read_y_then_x() has to agree with this observation, and can't see x == false && y == true.