c++ - 简单的无锁堆栈 c++11

Question

我见过几个过于复杂(在我看来很明显)的无锁栈在 C++ 中的实现(使用像 here 这样的标签)，我想出了一个我认为简单但仍然有效的实现。由于我在任何地方都找不到这个实现(我看到 Push 函数的实现与我所做的类似，但不是 Pop)，我猜测它在某些方面是不正确的(很可能在 ABA 案例中失败):

template<typename Data>
struct Element
{
  Data mData;
  Element<Data>* mNext;
};

template<typename Data>
class Stack
{
 public:
  using Obj = Element<Data>;
  std::atomic<Obj*> mHead;

  void Push(Obj *newObj)
  {
    newObj->mNext = mHead.load();
    //Should I be using std::memory_order_acq_rel below??
    while(!mHead.compare_exchange_weak(newObj->mNext, newObj));
  }

  Obj* Pop()
  {
    Obj* old_head = mHead.load();
    while (1)
    {
      if (old_head == nullptr)
        return nullptr;
      //Should I be using std::memory_order_acq_rel below??
      if(mHead.compare_exchange_weak(old_head, old_head->mNext)) ///<<< CL1
        return old_head;
    }
  }
};

我假设 Push 和 Pop 的调用者将负责内存分配和释放。另一种选择是使上述 Push 和 Pop 私有(private)方法并具有新的公共(public)函数，这些函数将负责内存分配并在内部调用这些函数。我相信这个实现中最棘手的部分是我用“CL1”标记的那一行。我认为它是正确的并且在 ABA 案例中仍然有效的原因如下:

假设 ABA 案例确实发生了。这意味着“CL1”处的 mHead 将等于 old_head，但它们指向的对象实际上与我将 mHead 分配给它时 old_head 最初指向的对象不同。但是，我认为即使它是一个不同的对象我们仍然可以，因为我们知道它是一个有效的“头部”。 old_head 指向与 mHead 相同的对象，因此它是堆栈的有效头部，这意味着 old_head->mNext 是有效的下一个头部。所以，将 mHead 更新为 old_head->mNext 仍然是正确的!

总结:

1. 如果 mHead != old_head(另一个线程抢占了我们并更改了 mHead)-> old_head 更新为新的 mHead，我们再次开始循环。
2. [NON-ABA] 如果 mHead == old_head -> 简单情况，将 mHead 更新为 old_head->next (==mHead->mNext) 并返回 old_head。
3. [ABA] 如果 mHead == old_head -> 如上所述工作。

那么，我的实现是否有效？我错过了什么？

Answer 1

ABA 发生在:

1. 线程 A 读取 old_head->mNext 并在调用 compare_exchange_weak 之前阻塞。
2. 线程 B 弹出当前节点并压入一些其他节点，然后将原始节点压回堆栈。
3. 线程 A 解除阻塞，成功完成 compare_exchange_weak，因为 mHead 具有相同的值，但将陈旧的 mNext 值存储为新的 mHead.

See this answer for more details ，您同时遇到问题 #2(mNext 上的数据竞争)和问题 #3 (ABA)。