CODEWITHSUNDEEP
c++multithreadingc++11concurrencyatomic
pat
pat

Reputation: 823

Where is the race?

#include <iostream>
#include <atomic>
#include <array>
#include <thread>

template <typename T>
struct node {
    T      value;
    node*  next{nullptr};
};

typedef node<int> node_type;

std::atomic<node_type*> _begin;

node_type* get() {
    node_type* b = _begin;

    while (!_begin.compare_exchange_weak(b, b->next))
        ;

    return b;
}

void give(node_type* v) {
    v->next = _begin;

    while (!_begin.compare_exchange_weak(v->next, v))
        ;
}

void get_and_give() {
    for (int i = 0; i < 1000000; ++i) {
        auto n = get();

        give(n);
    }
}

int main(int argc, const char * argv[])
{
    std::array<node_type, 4> _nodes;

    for (auto & i : _nodes)
        give(&i);

    std::thread t1(get_and_give);
    std::thread t2(get_and_give);
    std::thread t3(get_and_give);

    get_and_give();

    t1.join();
    t2.join();
    t3.join();

    return 0;
}

There is a race (I believe) on the next pointer inside the value returned by get. This does NOT occur with 2 threads running get_and_give, so it seems like its a lack of sequential consistency in the other threads, but everything I do is memory_order_seq_cst, so I don't understand how that could be a problem?

Any ideas!?

Upvotes: 1

Views: 161

Answers (1)

dohashi
dohashi

Reputation: 1841

I suspect you are running into what is known as the ABA problem.

From wikipedia

the ABA problem occurs during synchronization, when a location is read twice, has the same value for both reads, and "value is the same" is used to indicate "nothing has changed". However, another thread can execute between the two reads and change the value, do other work, then change the value back, thus fooling the first thread into thinking "nothing has changed" even though the second thread did work that violates that assumption.

Upvotes: 3

Related Questions