c++ - 如何防止此无锁堆栈函数中的未定义行为和 ABA 问题？

Question

我目前正在使用 C++11 开发无锁单链表，我的 popFront() 函数有问题——或者我至少应该说我知道它在某些情况下会出现问题。

无论如何，这就是我目前拥有的:

std::shared_ptr<T> popFront(void)
{
    auto p = atomic_load(&head);
    while(p && !atomic_compare_exchange_weak(&head, &p, p->next))
    {}
    return p ? p->data : std::shared_ptr<T>();
}

注意 head 是 shared_ptr 类型。

但是，我预计会出现一些问题。第一种情况是两个线程都在执行popFront()，它们都读取相同的head，一个线程先完成。在第二个线程完成之前，调用者删除了所指向的对象，因此第二个线程现在正在处理已删除的内存。第二个问题是经典的 ABA 问题。

这个链表背后的想法是让它是无锁的，所以我想避免在这个函数中强加锁。不幸的是，我不确定如何解决这些问题。如有任何建议，我们将不胜感激。

Answer 1

设计无ABA问题的无锁队列有很多解决方案。

这article应该提供一些见解，并且可以找到解决此问题的一些通用工具 here .

现在，关于您提到的问题:

Before the second thread finishes, the caller deletes the object that was being pointed to, so the second thread is now working with deleted memory

是的，这是可能发生的，一个解决方案是使用 tagged pointers : 在 32 位架构上，最后 2 ( or more) 位未被使用，因此它们可用于标记，而在 64 位架构上，我们至少有 3 个未使用的位。

因此我们可以将指针设置为逻辑删除，但不能通过设置指针的一些未使用位来物理删除它，如下所示:

__inline struct node* setTag(struct node* p, unsigned long TAG)
{
    return (struct node*) ((uintptr_t)p | TAG);
}

__inline bool isTagged(struct node* p, unsigned long TAG)
{
    return (uintptr_t)p == (uintptr_t)p &  ~TAG;
}

__inline struct node* getUntaggedAddress(struct node* p, unsigned long TAG)
{
    return (struct node*)((uintptr_t)p &  ~TAG);
}

其中 TAG 最多为 4(对于 32 位架构)，在 64 位架构上最多为 8(2/3 或更多未使用的位，具体取决于计算机架构和字对齐)。

现在在执行 CAS 时，我们忽略标记指针 => 因此仅对有效指针进行操作。

当对队列进行出队时，我们可以执行如下操作:

int dequeue(qroot* root)
{
    qnode* oldHead;

    do
    {
        oldHead = root->head;

        if (isTagged(root->head)) //disregard tagged addresses
            return NULL;

        oldHead = getUntaggedAddress(root->head); //we do a CAS only if the old head was unchanged

    } while (root->head.compare_exchange_strong(oldHead, oldHead->next, std::memory_order_seq_cst));

    return &(oldHead->data);
}

给定

typedef struct qnode
{
    std::atomic<qnode*> next;
    int data;
}qnode;

typedef struct qroot
{
    std::atomic<qnode*> head; //Dequeue and peek will be performed from head
    std::atomic<qnode*> tail; //Enqueue will be performed to tail
}qroot;