What's wrong with sequental consistency here?

Question

I'm playing with lock-free algorithms in C and C++ and recently stumbled upon a behavior I don't quite understand. If you have the following code, running it will give you something like

reader started
writer started
iters=79895047, less=401131, eq=48996928, more=30496988

Aren't std::atomics are expected to be sequentially-consistent? If so, why does the reader sometimes see b being updated before a? I also tried to do various tricks involving memory fences with no success. The full compilable code can be seen at https://github.com/akamaus/fence_test

What's wrong with the example?

std::atomic<uint> a(0);
std::atomic<uint> b(0);

volatile bool stop = false;

void *reader(void *p) {
    uint64_t iter_counter = 0;
    uint cnt_less = 0,
         cnt_eq = 0,
         cnt_more = 0;

    uint aa, bb;


    printf("reader started\n");

    while(!stop) {
        iter_counter++;
        aa = a.load(std::memory_order_seq_cst);
        bb = b.load(std::memory_order_seq_cst);
        if (aa < bb) {
            cnt_less++;
        } else if (aa > bb) {
            cnt_more++;
        } else {
            cnt_eq++;
        }
    }
        printf("iters=%lu, less=%u, eq=%u, more=%u\n", iter_counter, cnt_less, cnt_eq, cnt_more);

    return NULL;
}

void *writer(void *p) {
    printf("writer started\n");
    uint counter = 0;
    while(!stop) {
        a.store(counter, std::memory_order_seq_cst);
        b.store(counter, std::memory_order_seq_cst);
        counter++;
    }
}

might not be a problem but [volatile should not be used for synchronization](http://stackoverflow.com/questions/2484980/why-is-volatile-not-considered-useful-in-multithreaded-c-or-c-programming) — NathanOliver, Oct 08 '15 at 13:47
Consider: writer writes to `a`, then the reader reads from `a`, then the reader reads from `b`, then the writer writes to `b`. Result: The reader observes `a > b`. Similarly, reader reads from `a`, writer writes to `a`, writer writes to `b`, reader reads from `b`. Result: reader observes `a < b`. — dyp, Oct 08 '15 at 13:47
Put it another way - sequential consistency assures that readers see all the writes already performed. It does not wait for future writes to happen. A similar question from earlier today [Understanding C++ memory model: Different values on different runs](http://stackoverflow.com/questions/33007373/understanding-c-memory-model-different-values-on-different-runs) — Bo Persson, Oct 08 '15 at 13:59

score 4 · Accepted Answer · answered Oct 08 '15 at 13:58

Sequentially consistent memory ordering implies that the modification order (of the atomic objects manipulated with seq cst) observed by all threads is consistent. The program behaves as if all those operations happen interleaved in a single total order. Consider the following cases:

Writer Reader
       a == 0
a = 1
b = 1
       b == 1

Result: aa < bb.

Writer Reader
a = 1
       a == 1
       b == 0
b = 1

Result: aa > bb

With a lock, e.g. a mutex, you can make sure that the operations don't interleave.

What's wrong with sequental consistency here?

1 Answers1