1

考虑这段代码（来自'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-loop 不会中断。
这是正确的 ？

4

2 回答 2

2

假设head是 astd::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 并且总是在当前线程有机会之前设置值）。

于 2020-03-30T14:27:15.110 回答
1

正如@Alan Birtles 已经解释的那样，您不会被困在 while 循环中。但是，重要的是要注意您的代码很可能会遇到 ABA 问题。考虑以下场景：

  • 堆栈看起来像这样：（A->B->C即，头指向A）
  • 线程 1 加载头（即 的地址A）和A下一个指针（B），但在执行 CAS 之前，它被中断了。
  • 线程 2 pops A， then B，然后 pushes A，即堆栈现在看起来像这样：A->C
  • 线程 1 恢复并愉快地将头部更新A为B->繁荣！

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

于 2020-03-31T13:28:29.987 回答