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

我已经看到了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)方法，并具有新的公用函数，这些公用函数将负责内存分配并在内部调用这些函数。我相信此实现过程中最棘手的部分是我标记为“CL1”的行。我认为这是正确的，但仍然可以在ABA案例中使用的原因如下:

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

总结一下:

如果mHead!= old_head(另一个线程取代了我们并更改了mHead)-> old_head被更新为新的mHead，我们将再次开始循环。

[NON-ABA]如果mHead == old_head->简单情况，请将mHead更新为old_head-> next(== mHead-> mNext)并返回old_head。

[ABA]如果mHead == old_head->则如上所述。

那么，我的实现有效吗？我想念什么？

最佳答案

ABA在以下情况下发生:

线程A在调用old_head->mNext之前读取compare_exchange_weak并进行阻止。

线程B弹出当前节点，将其插入其他节点，然后将原始节点推回堆栈。

线程A解除阻止，成功完成compare_exchange_weak，因为mHead具有相同的值，但将过时的mNext值存储为新的mHead。

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