简单无锁堆栈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的案子确实发生了。这意味着“mHead”的"CL1“将等于old_head，但它们所指向的对象实际上与CL1分配mHead时所指向的对象不同。但是，我认为，即使它是一个不同的对象，我们仍然可以，因为我们知道它是一个有效的“头”。old_head指向与mHead相同的对象，因此它是堆栈的有效头，这意味着old_ head ->mNext是有效的下一个头。所以，将mHead更新到old_head->mNext仍然是正确的！

概括地说：

1. 如果mHead != old_head (另一个线程抢占了我们并更改了mHead)，则-> old_head将被更新为新的mHead，然后我们再次启动循环。
2. 如果mHead == old_head ->简单，则将mHead更新为old_head->next (==mHead->mNext)并返回old_head。
3. 阿坝如果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)。

Answer 2

一般来说，如果数据类型是按位规则的，并且如果仅仅是半正则的(或者相等不是按位)，则不可避免地会受到ABA的影响，实现是正确的。

如果数据类型是按位规则的，那么CAS操作就足够了，例如对于整数。ABA不是问题，因为A等于A，故事的结尾。

Harris算法似乎允许非位正则类型提供一个集合实现，但代价是性能无界，更糟糕的是，它回避了如何分配列表中的节点的问题。这意味着要解决的核心问题是提供一个O(1)无锁分配器，而这种数据结构不存在，因为所涉及的指针只是半正则的。特别是，当指针仅仅将字节数组标识为内存块时，它是规则的；当指针标识链接列表的一个节点时，它不再是规则的，因为指针相等不能确保嵌入的下一个指针是相等的。

周围没有任何可能的工作。我怀疑DCAS是否会有帮助，我也怀疑将固定时间限制放宽到线性约束也会有帮助。

对于不可抢占的线程，一个自旋锁将工作，只要它保护的关键部分是有限制的时间。您可以在MacOS和上获得这些信息。

Answer 3

如果您需要跨平台，此Lf堆栈可以进行跨平台构建，它是内置于

例子：-

int* int_data;
lfstack_t mystack;

if (lfstack_init(&mystack) == -1)
    return -1;

/** Wrap This scope in other threads **/
int_data = (int*) malloc(sizeof(int));
assert(int_data != NULL);
*int_data = i++;
/*PUSH*/
 while (lfstack_push(&mystack, int_data) == -1) {
    printf("ENQ Full ?\n");
}

/** Wrap This scope in other threads **/
/*POP*/
while  ( (int_data = lfstack_pop(&mystack)) == NULL) {
    printf("POP EMPTY ..\n");
}

// printf("%d\n", *(int*) int_data );
free(int_data);
/** End **/

lfstack_destroy(&mystack);