简单的无锁堆栈c ++ 11

Question

我已经看到了几个过于复杂的(在我看来很明显)在c ++中使用无锁堆栈的实现(使用像这里的标签),我想出了一个简单但仍然有效的实现.因为我无法在任何地方找到这个实现(我已经看到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私有方法,并使用新的公共函数来处理内存分配并在内部调用这些函数.我相信这个实现中最棘手的部分是我用"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 - > simple case,请将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.

有关详细信息,请参阅此答案,您有问题#2(数据竞争开启mNext)和问题#3(ABA).