有可能卡在 compare_exchange 的循环中吗？

Question

考虑这段代码（来自 'C++ concurrency in action' [第二版]：第 212 页）：

void LockFreeStack::pop (stack_data& result)
{
    Node* old_head = head.load();
    while(!head.compare_exchange_weak(old_head, old_head->next))
        ;
    result = old_head->data;
}

我认为有可能线程一执行 pop() 并且在执行第一行（加载 head）之后时间切片发生在线程二上，它正在执行 push(T&)。所以现在 head 原子变量的值不等于 old_head 并且 while 循环不会中断。
是吗？

Answer 1

假设 head 是 std::atomic<Node*> 那么代码是正确的，因为当 compare_exchange_weak 失败时它将变量的当前值加载到它的第一个参数中，在 compare_exchange_weak 调用 old_head 将始终包含 head.

的当前值

该代码大致相当于在没有原子的情况下执行以下操作：

Node* old_head = head;
while (true)
{
  std::unique_lock lock(mutex);
  if (old_head == head)
  {
     head = old_head->next;
     break;
  }
  else
  {
     old_head = head;
  }
}

因此，对 pop 的并发调用是安全的，不应永远阻塞（除非其他线程不断调用 pop 并以某种方式总是在当前线程有机会之前设置值）。

Answer 2

正如@Alan Birtles 已经解释的那样，您不会陷入 while 循环。但是，请务必注意，您的代码很可能会遇到 ABA 问题。考虑以下场景：

堆栈看起来像这样：A->B->C（即头指向 A）
线程1加载头部（即A的地址）和A的下一个指针（B），但在执行CAS之前，它是打断了。
线程 2 弹出 A，然后 B，然后压入 A，即堆栈现在看起来像这样：A->C
线程 1 恢复并愉快地将头部从 A 更新为 B -> boom!

有几种可能的解决方案可以避免 ABA 问题，例如标记指针或并发内存回收方案。

有可能卡在 compare_exchange 的循环中吗？

It is possible to getting stuck in the compare_exchange's loop?

c++

atomic

gcc9