How std::memory_order_seq_cst works

Question

I took the example about std::memory_order_seq_cst from: http://en.cppreference.com/w/cpp/atomic/memory_order

#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
}

This example is also mentioned in the question of Acquire/Release versus Sequentially Consistent memory order.

My question is how it is possible that thread c and thread d see different things? If it is possible, why this simple example below always yields to z=3? For instance, thread b could say "okay I see 0 even though thread a is already done so z becomes 0+1 again"

#include <atomic>
#include <iostream>

std::atomic<int> z = {0};

void increment()
{
    z.fetch_add(1, std::memory_order_relaxed);
}
int main()
{
    std::thread a(increment);
    std::thread b(increment);
    std::thread c(increment);
    a.join(); b.join(); c.join();
    std::cout << z.load() << '\n';
}

Malissamalissia

"why this simple example below always prints 3?" Your example does not print anything. – Fyke

What do you mean by "see different things"? It is hard to imagine what you are looking for. Maybe look for these concepts: modification order and total order – Goldin

@Goldin I mean that it is possible for Thread "c" to see x==1, y==0 and for Thread D to see x==0, y==1. That is what I mean that they see x and y values differently. But I guess I was looking for modification order: "There is a separate order for each atomic object. There is no requirement that these can be combined into a single total order for all objects." As there are two atomic variable here, without the memory std::memory_order_seq_cs a single total order is not guaranteed. Am I correct? – Malissamalissia

@Malissamalissia Yes you are correct. – Goldin

Apart from not containing any printing code, as DanielLangr pointed out, your second example always results in a call to std::terminate() because the threads are destroyed while still joinable. I'm going to fix this for you. – Iormina

@ArneVogel You are right, thank you for the remark. With regards of the printing issue I've already corrected the text. – Malissamalissia

Is that question intended specifically for C++11? Or for any version that supports threads and std::atomic<>? I understand that might want to discuss the specific guarantees of a specific C++ std, I just want to confirm that. – Carisacarissa

Answer 1

So by seeing different things in your comment you mean that Thread C see x==1,y==0 and Thread D see x==0 and y==1. Is that possible with sequential consistency?

Let's suppose this total order (the modification is the transition between this symbolized memory states):

{x==0,y==0} : S0
{x==1,y==0} : S1
{x==1,y==1} : S2

When we say "see" we mean that a thread potentialy performs a load. Two loads can not be performed simultaneously in one thread. So how is it possible that thread C see x==1 then see y==0 and Thread D see x==0 then see y==1? Thread C performs the two loads while the memory is in the state S1, and Thread D see x at state S0, then see y at state S2.

In your example code, what happens is that Thread C load x then load y, and Thread D load y repeatedly until it is true then load x. So after y==1, it is guarenteed that x==1 in this total order.

As said by Minee in its comment, nothing could be expected if in place of sequential consistency memory order were used acquire/release memory order: acquire/release semantic does not imply any total ordering,moreover there are no happens before relation between the store to x and the store to y. So the assertion z.load()!=0 could fire.

Goldin

But this total order guarantee is only valid for the std::memory_order_seq_cst which as you said guarantees the total order. If acquire - release fences are used, as the standard says there is no visibility ordering guarantee between the two variables. Maybe you could add this to get the whole picture. – Malissamalissia

@Malissamalissia A release operation on X by thread A only imply visibility of another thread B does an acquire on X later, and only for the memory operations done in the history of thread A. In fact the release-acquire pair "copies" the history of A to B. The history of thread just started is the history of its creating thread so two threads just started by the same parent already share history. There is nothing to "release" in the first operation of a thread that can be usefully "acquired" by the other. – Carisacarissa

@Minee: Yes, if you only use acq/rel like the answer you linked, IRIW reordering is allowed. (And can happen in real life on some POWER CPUs: Will two atomic writes to different locations in different threads always be seen in the same order by other threads? but it's obscure and doesn't happen on anything else, AFAIK; other HW is multi-copy-atomic). But your question strengthened that to seq_cst and then made some weird claim that disagreement about order is still allowed, which is confusing and wrong with a memory model almost as weak as ISO C++ allows. – Mairamaire

Answer 2

Because read-modify-write operations have special guarantees.

According to the standard [atomics.order] paragraph 11:

Atomic read-modify-write operations shall always read the last value (in the modification order) written before the write associated with the read-modify-write operation.

Arroba

Thank you for this explanation, it helped me to understand. – Malissamalissia

Answer 3

My question is how it is possible that thread c and thread d see different things?

It's allowed in theory, and in practice it might happen, if you have multiple atomic variables and some operations don't have memory_order_seq_cst ordering.

So it is not possible in your code that uses memory_order_seq_cst on all operations (using it on only some operations is dangerous as it can lead to subtle bugs).

For instance, thread b could say "okay I see 0 even though thread a is already done so z becomes 0+1 again"

No.

But in any event, what is allowed on a single atomic variable has nothing to do with memory ordering, which affects the visibility of the rest of memory, and has no effect on the object on which you are operating.

If you have a single atomic variable and no other shared state, the visibility is irrelevant as there is nothing to be made visible.

[Note about the standard description:

The standard implies that in at least in theory, that assertion doesn't hold in all cases for relaxed operations. But the standard is insane on threads: it's ill defined unless my assertion is true.

And anyway, the standard says that in practice the implementations should avoid allowing executions where my assertion is false. And they don't happen anywhere anytime in practice.]

Carisacarissa

But here they do all have seq_cst so IRIW reordering is disallowed: all threads must agree on a global order of operations even across 2 variables x and y. This is an important point, IMO: the OP strengthened the operations vs. the linked answer it was copied from where that is possible with release (including in practice on POWER but probably nothing else): Will two atomic writes to different locations in different threads always be seen in the same order by other threads? – Mairamaire