How to make the shared value behave consistently without mutex?

Question

I have the following code. I do not understand why the reader sees inconsistent variable value.

uint64_t get_counter() {
    static uint64_t counter = 0;
    static std::mutex m;
    std::unique_lock l(m);
    return ++counter;
}

auto main() -> int {
    // uint64_t shared = 0;
    std::atomic<uint64_t> shared = 0;

    const auto writer = [&shared]() -> void {
        while (true) {
            shared = get_counter();
            std::this_thread::yield();
        }
    };
    const auto reader = [&shared]() -> void {
        while (true) {
            const uint64_t local = shared;
            if (local > shared) {
                cout << local << " " << shared << endl;
            }
            std::this_thread::yield();
        }
    };

    std::thread w1(writer), w2(writer), r(reader);
    r.join();

    return EXIT_SUCCESS;
}

get_counter is just a helper to generate strictly increasing numbers. In reality it could be replaced by other more useful functions.

Since shared should never go smaller, I expect when if (local > shared) is evaluated, it should never be true. However, I'm getting output like these:

1022 1960
642677 644151
645309 645699
1510591 1512122
1592957 1593959
7964226 7965790
8918667 8919962
9094127 9095161
9116800 9117780
9214842 9215720
9539737 9541144
9737821 9739100
10222726 10223912
11197862 11199348

Looks like local was indeed smaller than shared, but then why the output? Is it caused by some data race? If so, how to fix this without introducing mutex? Can std::atomic_thread_fence be used to help? Does shared have to be a std::atomic?

Answer 1

Seems to me like the following sequence is possible:

 Writer1: get_counter() -> 2
 Writer2: get_counter() -> 3
 Writer2: shared = 3
 Reader: local = shared (3)
 Writer1: shared = 2
 Reader: if (local > shared) // 3 > 2

Since your lock doesn't cover the generation + assignment you have a "race condition" on the write to shared and it can be out of order from the generation, leading to the if firing.

I put race condition in quotes since it's not a data race (since shared is atomic).