带有空闲列表的无锁堆栈：为什么下一个指针不需要是原子的？

Question

无锁堆栈可以实现为单链表。这看起来很简单，直到我们必须考虑在弹出节点后如何处理它们。一种策略是简单地将它们移动到每个堆栈的 LIFO 空闲列表（后续的推送操作可以重用该节点），直到最终所有线程都完成了堆栈，此时单个线程会销毁堆栈中的所有节点和所有节点。空闲列表中的节点。Boost.Lockfree使用这种策略。Chris Wellons 的 C11 实现也是如此。我将参考后者，因为它更容易阅读，而且细节基本相同，因为 C11 原子与 C++11 原子非常相似。

在 Wellons 的实现中（可以在 GitHub 上找到），所有lstack_node对象都是非原子的。特别是，这意味着对对象next成员的所有访问lstack_node都是非原子的。我无法理解的是：为什么此类访问从不相互竞争？

该成员在lstack.c:30 处next读取。它写在lstack.c:39。如果这两行可以在同一个对象上同时执行，则该程序包含竞争。这可能吗？对我来说似乎有可能：lstack_node

• 线程 1 调用lstack_pop，它调用pop. 它以原子方式将头节点的值加载到局部变量中orig。现在，orig.node是指向刚刚位于堆栈顶部的节点的指针。（请注意，到目前为止，仅修改了局部变量，因此线程 1 迄今为止所做的任何操作都不可能导致任何其他线程中的 CAS 失败。）同时...
• 线程 2 调用lstack_pop. pop成功并返回node，指向刚刚从堆栈中删除的节点的指针；这与线程 1 中指向的节点相同。orig.node然后它开始调用push以添加node到空闲列表中。自由列表头节点以原子方式加载，并node->next设置为指向自由列表中的第一个节点。
• 哎呀。这与线程 1 中的读取竞争orig.node->next。

难道 Wellons 的实施根本就是错误的吗？我对此表示怀疑。如果他的实现是错误的，那么 Boost 的实现也是错误的，因为修复（在我看来）竞争条件的唯一方法是使next原子化。但我不认为 Boost 的实现可能会在如此基本的方式上出现错误，除非现在已经注意到并修复了它。所以我的推理一定是错误的。

Answer 1

需要注意的关键是，当前链表中的每个节点的 next 字段都是只读的。只有当该节点已成功从链表中删除时，才能修改下一个节点。一旦发生这种情况，删除它的线程“拥有”它，并且没有其他人可以明智地查看它（他们可能会读取一个值，但当它们的compare_and_set失败时，该值将被丢弃。）这样拥有线程就可以安全地修改下一个字段作为将其推送到另一个列表的一部分。

在您的假设中，您忽略了两个弹出（由两个线程完成）不能同时成功并返回相同节点的事实。如果两个线程尝试同时弹出，它们可能会获得相同的节点指针，但其中一个线程会在compare_and_set原子指令中失败，并且会使用不同的节点指针循环返回。

这确实要求读/写竞争是“安全的”——也就是说，当两个线程之间进行读/写竞争时，读取器可能会获得任何值，但不会失败（没有陷阱或其他未定义的行为），并且否则不会干扰写入，但大多数（所有？）硬件上往往都是这种情况。只要读取器不依赖于比赛期间读取的值，您就可以在事后检测比赛并忽略该值。

Answer 2

我只是写了一篇长文试图解释为什么不能有竞争，直到我仔细研究了 Wellson 是如何实现空闲列表的，我得出的结论是你是对的！

这里重要的一点是你在问题一开始提到的：

这看起来很简单，直到我们必须考虑在弹出节点后如何处理它们。一种策略是简单地将它们移至每个堆栈的 LIFO 空闲列表，直到最终所有线程都完成堆栈的操作，此时单个线程会销毁堆栈中的所有节点以及空闲列表中的所有节点。

但这不是 Wellson 实现中的空闲列表的工作原理！相反，它尝试重用空闲列表中的节点，但正如next您所观察到的那样，它也需要是原子的。如果空闲列表已按照您所描述的方式实现，即弹出的节点将被添加到某个空闲列表（未更改，即空闲列表使用与不同的指针next），并且仅在堆栈不再被任何线程使用时才释放， thennext可以是一个普通变量，因为一旦节点被成功推送，它就不会改变。

这并不一定意味着 boost 无锁队列也是不正确的，但我不知道代码是否足够好，无法对 boost 实现做出合格的声明。

FWIW - 这通常称为内存回收问题。这种空闲列表方法是一个简单的解决方案，但通常不适用于现实场景。对于现实场景，您可能希望使用内存回收方案，例如危险指针或基于纪元的回收。您可以查看我的xenium 库，其中我实现了几种不同的回收方案以及使用它们的无锁数据结构。有关内存回收问题和我在 xenium 中的实现的更多信息也可以在我的论文《C++ 中无锁数据结构的有效内存回收》中找到。