比赛在哪里？

Question

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

在get返回的值内的下一个指针上有一个竞赛(我相信)。在运行get_and_give的2个线程中不会出现这种情况，因此在其他线程中似乎缺乏顺序一致性，但是我所做的一切都是memory_order_seq_cst，所以我不明白这怎么会是个问题？

有什么主意吗？

Answer 1

我怀疑你遇到了所谓的ABA问题。

来自维基百科

ABA问题发生在同步过程中，当一个位置被读取两次时，两个读取的值都相同，而“值是相同的”被用来表示“没有任何变化”。但是，另一个线程可以在两个线程之间执行读取和更改值，执行其他工作，然后将值改回，从而愚弄第一个线程，使其认为“没有任何变化”，即使第二个线程确实执行了违背该假设的工作。