How std::memory_order_seq_cst works

6
votes

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';
}
3
c++c++11memory-barriersmemory-modelstdatomic
"why this simple example below always prints 3?" Your example does not print anything. – Daniel Langr
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 – Oliv
@Oliv 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? – Minee
@Minee Yes you are correct. – Oliv
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. – Arne Vogel

3 Answers

4
votes

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.

3
votes

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.

0
votes

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