C++中的无锁栈弹出实现

Question

在C++ Concurrency in Action, 2e, 作者描述了一个无锁线程安全链表实现。现在，他正在描述 pop() 方法以及如何以一种类似于 "garbage-collector" 的方法安全地删除节点，以确保没有其他线程在同一实例上调用 pop。这是 pop 的一些代码：

#include <atomic>
#include <memory>

template<typename T>
class lock_free_stack
{
private:
    std::atomic<unsigned> threads_in_pop;
    void try_reclaim(node* old_head);
public:
    std::shared_ptr<T> pop()
    {
        ++threads_in_pop;
        node* old_head=head.load();
        while(old_head &&
              !head.compare_exchange_weak(old_head,old_head->next));
        std::shared_ptr<T> res;
        if(old_head)
        {
            res.swap(old_head->data);
        }
        try_reclaim(old_head);
        return res;
    }
};

重要的是，每次调用 pop() 时，计数器都会自动递增。然后，try_reclaim 函数将递减所述计数器。这是 try_reclaim 的实现：

void try_reclaim(node* old_head)
{
    if(threads_in_pop==1) //#1
    {
        node* nodes_to_delete=to_be_deleted.exchange(nullptr);
        if(!--threads_in_pop) //#2
        {
            delete_nodes(nodes_to_delete);
        }
        else if(nodes_to_delete)
        {
            chain_pending_nodes(nodes_to_delete);//#3
        }
        delete old_head; //#4 THIS IS THE PART I AM CONFUSED ABOUT
    }
    else
    {
        chain_pending_node(old_head);
        --threads_in_pop;
    }
}

这里调用的其他函数的实现是无关紧要的（它们只是将节点添加到要删除的节点链中），所以我省略了它们。我在代码中感到困惑的部分是#4（已标记）。在这里，作者对传入的old_head调用了delete。但是，他为什么不在删除old_head之前检查此时threads_in_pop是否仍然为零？他在第 2 行和第 1 行中仔细检查以确保另一个线程当前不在 pop() 中，那么他为什么不在继续删除 old_head 之前再次检查？难道另一个线程不可能在#3 之后立即调用 pop()，从而增加计数器，并且当第一个线程到达#4 时，threads_in_pop 将不再为零吗？

也就是说，当代码到达#4 时，threads_in_pop 不可能是，例如，2？在那种情况下，他怎么能安全地删除 old_head 呢？有人可以解释一下吗？

Answer 1

调用 try_reclaim 的线程刚刚从堆栈中删除了 old_head。

class 确保任何 old_head 的其他用途必须在来自其他线程的 pop 调用中，因此如果线程发现没有其他并发调用，则它知道它是 old_head 指针的独占持有者。然后，只要它不发布该指针以便它可以从另一个线程中获取，它就可以在它到达它时删除它。

因此实施是安全的。你问的问题："Why doesn't he check [again]" 说明你想的不对。再次检查不会证明任何事情，因为如果另一个线程有可能进入 pop 并使用 old_head，那么它可能总是发生在你检查之后！

Answer 2

你有以下（简化的）序列，所有原子操作顺序一致：
++threads_in_pop -> head.cmpxchg -> threads_in_pop.load() -> delete old_head

所以我们先去掉当前的head，然后查看threads_in_pop的个数。假设我们有两个线程 T1 和 T2，它们在堆栈上进行操作。如果 T1 在 try_reclaim 中执行 threads_in_pop.load() (#1) 并看到 1，这意味着 T2 尚未执行增量 (++threads_in_pop)，即 T1 是唯一可以拥有的线程那时对 old_head 的引用。但是，T1 已经从列表中删除了 old_head，因此任何进入 pop 的线程都将看到更新后的头部，因此其他线程不可能再获得对 old_thread 的引用。因此删除 old_head.

是安全的

检查 #2 是必要的，以避免释放刚刚添加到 to_be_released 列表的节点在这个线程已经执行它的 pop，但是其他线程可能仍然持有一个参考。考虑以下情况：

T1执行pop，即将执行nodes_to_delete=to_be_deleted.exchange(nullptr);
T2 开始 pop 并读取 head
T3 开始 pop 并读取 head，看到与 T2 相同的值
T2 完成弹出并将 old_head 添加到列表
注意：T3 仍然引用现在属于 to_be_deleted 列表
T1 现在执行 nodes_to_delete=to_be_deleted.exchange(nullptr);

T1 现在有一个 nodes_to_delete 列表，其中包含对 T3 仍可访问的节点的引用。这就是为什么检查 #2 是必要的，以防止 T1 释放该节点。

C++中的无锁栈弹出实现

Lock-free stack pop implementation in C++

c++

concurrency

multithreading

lock-free

data-structures