正确使用compare_exchange_weak

Question

const int SIZE = 20; 
struct Node { Node* next; };

std::atomic<Node*> head (nullptr);
void push (void* p)
{
    Node* n = (Node*) p;
    n->next = head.load (); 
    while (!head.compare_exchange_weak (n->next, n));
}
void* pop ()
{
    Node* n = head.load (); 
    while (n &&
          !head.compare_exchange_weak (n, n->next));

    return n ? n : malloc (SIZE);
}

void thread_fn()
{
    std::array<char*, 1000> pointers;

    for (int i = 0; i < 1000; i++) pointers[i] = nullptr;

    for (int i = 0; i < 10000000; i++)
    {   
        int r = random() % 1000;

        if (pointers[r] != nullptr) // allocated earlier
        {   
            push (pointers[r]);
            pointers[r] = nullptr;
        }   
        else
        {   
            pointers[r] = (char*) pop (); // allocate

            // stamp the memory
            for (int i = 0; i < SIZE; i++)
                pointers[r][i] = 0xEF;
        }   
    }   
}


int main(int argc, char *argv[])
{
    int N = 8;

   std::vector<std::thread*> threads;
   threads.reserve (N);

   for (int i = 0; i < N; i++)
       threads.push_back (new std::thread (thread_fn));

   for (int i = 0; i < N; i++)
       threads[i]->join();
}

compare_exchange_weak的这种用法有什么问题？上面的代码使用clang++ (MacOSX) 5次中就有1次崩溃。

崩溃时的head.load()将具有“0xEFEFEFEFEEF”。pop就像malloc，而push就像是免费的。每个线程(8个线程)从head随机分配或释放内存

Answer 1

它可能是一个很好的无锁分配器，但是出现了ABA-problem：

A：假设某个thread1执行pop()，将head的当前值读入n变量，但紧接着线程被抢占，并发thread2执行完整的pop()调用，即从head读取相同的值并成功执行compare_exchange_weak。

B：现在，n在thread1中引用的对象不再属于该列表，可以由thread2修改。因此，n->next通常是垃圾:从它读取可以返回任何值。例如，它可以是0xEFEFEFEFEF，其中前5个字节是thread2写入的stamp (EF)，最后3个字节仍然是来自nullptr的0。(Total value以小端字节序的方式进行数值解释)。看起来，由于head值已更改，thread1将使其compare_exchange_weak调用失败，但是...

A：Concurrent thread2 push()es导致指针返回列表。因此，thread1看到head的初始值，并成功执行compare_exchange_weak，这会将不正确的值写入head。列表已损坏。

请注意，这个问题不仅仅是可能的，其他线程可以修改n->next的内容。问题是n->next 的值不再与列表耦合。因此，即使它没有被并发地修改，它也会变得无效(对于替换head)，例如，当其他线程从列表中取回2个元素，但push()只返回其中的第一个元素时。(因此n->next将指向第二个元素，该元素不再属于列表。)