无锁自由列表栈: 为什么下一个指针不需要是原子的？

Question

无锁栈可以作为一个单向链表实现。这似乎很简单，直到我们不得不考虑节点在被弹出后该如何处理。一种策略是将它们简单地移动到每个栈的LIFO自由列表（从中节点可以被后续推送操作重用），直到所有线程都完成对栈的操作，此时单个线程销毁栈中的所有节点和自由列表中的所有节点。 Boost.Lockfree 使用这种策略。Chris Wellons's C11 implementation 也是如此。我将提到后者，因为它更容易阅读，而且详细信息基本相同，因为C11原子与C++11原子非常相似。

在Wellons的实现中，可以在这里找到所有lstack_node对象都是非原子性的。特别地，这意味着对lstack_node对象的next成员的所有访问都是非原子性的。我无法理解的是：为什么这样的访问永远不会互相竞争？ next成员在lstack.c:30处被读取。它在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的实现会在这样一个基本的方面出错，否则它早就被注意到和修复了。所以我在我的推理中肯定犯了错误。

- Frock Lee

---

也许算法假定机器指针上的原子操作。它将大于指针的结构标记为原子，并且在某些系统上，我可以相信 size_t 是 64，具有 32 位机器字。 - Yakk - Adam Nevraumont

Answer 1

需要翻译的内容如下：

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

在您的假设中，您忽略了两个弹出操作（由两个线程执行）不能同时成功并返回相同的节点这一事实。如果两个线程尝试同时弹出，他们可能会得到相同的节点指针，但其中一个会在compare_and_set原子指令中失败，并带着不同的节点指针循环回来。

这确实要求读/写竞争是“安全”的——即当两个线程之间存在读/写竞争时，读者可能会获得任何值，但不会发生错误（没有陷阱或其他未定义的行为），也不会干扰写入，但这往往是大多数硬件的情况。只要读者在竞争期间不依赖于读取的值，您就可以在事后检测到竞争并忽略该值。

- Chris Dodd

---

只有在节点已经成功从链表中删除后，才能修改下一个节点。在我的例子中，该节点已经从堆栈列表中删除，并且成功执行此操作的线程正在将其添加到空闲列表中（这涉及修改“下一个”）。但是另一个线程仍在读取“下一个”。虽然CAS会失败，但是竞争发生在此之前。 - Frock Lee

是的，但是竞争只意味着它获得了一些值，它将用于原子比较交换中的新值，但由于比较部分失败，该值将被忽略。 - Chris Dodd

问题在于，竞争条件（同时读写同一个内存位置）的存在会导致程序出现未定义的行为。 - Frock Lee

顺便提一下，在C++20中，正确的SeqLock实现使用atomic_ref来避免这种情况。 - mpoeter

atomic或atomic_ref的问题在于它强制你告诉编译器这是4个4字节的块，例如，或者2个8字节的块，可能会强制它在32位机器上执行更昂贵的8字节原子加载，或在64位机器上限制自己。除了一些笨重的参数化类型和适应所选访问宽度与实际数据类型之间的差异之外。当你真正想要的是让它自己选择，就像对于volatile一样。 - Peter Cordes

Answer 2

我刚写了一篇长文，试图解释为什么不能有竞争，直到我仔细研究了Wellson实现的空闲列表后，我得出结论，你是正确的！这里重要的一点是你在问题开头提到的：

这似乎很简单，直到我们考虑弹出节点后该怎么处理。一种策略是将它们简单地移动到每个堆栈LIFO空闲列表中，直到所有线程都完成堆栈操作，此时单个线程销毁堆栈中的所有节点和自由列表中的所有节点。

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

这并不一定意味着boost无锁队列也不正确，但我对boost实现的代码不太了解，无法就此发表资格鉴定的陈述。

FWIW - 这通常称为内存回收问题。这个空闲列表方法是一个简单的解决方案，虽然通常不适用于实际场景。对于实际场景，您可能需要使用像hazard指针或基于时代的回收这样的内存回收方案。您可以查看我的xenium库，其中我实现了几种不同的回收方案以及使用它们的无锁数据结构。关于内存回收问题以及我在xenium中的实现的更多信息，还可以在我的论文C++中无锁数据结构的有效内存回收中找到。

- mpoeter

---

我会更新问题以澄清。对我来说，“自由列表”本质上包含可供重复使用的资源。 - Frock Lee

不错的内容。关于Xenium，我找不到任何有关专利回收算法的信息，这似乎是一个很大的问题，直到最近（例如，我上次查看https://github.com/khizmax/libcds时）。您是否了解专利状态/许可证方面的担忧？ - sehe

@sehe 很遗憾，我不太了解专利状态/许可证。我知道有一个关于危险指针的专利申请，但据我所知已经被放弃了。 - mpoeter