C++ Treiber Stack 和原子 next 指针

Question

“Treiber Stack”通常是最简单的无锁数据结构之一，因此在介绍无锁算法时经常使用它。

我见过许多使用 C++ 原子的 Treiber Stacks 实现。算法本身很简单，所以真正的挑战是处理无锁数据结构的所有其他附带细节，例如提供一些执行安全内存回收的方法、避免 ABA 问题以及以无锁方式分配节点.这可以通过多种方式解决，例如使用原子引用计数、危险指针、counted/tagged 避免 ABA 的指针以及使用无锁内存池。

但是忽略所有这些细节并专注于简单算法本身，我想到的一个问题是我记得的 Treiber Stacks 的每个实现都使用 [=40= 实现了节点 class ]原子下一个指针。例如：

struct Node
{
  T value;
  std::atomic<Node*> next;
};

但是在思考算法之后，我不确定为什么下一个指针需要是原子的。

一般的PUSH算法（忽略无锁分配、安全内存回收、退避、ABA规避等）是：

Node* n = new Node();
Node* front = m_front.load();
n->next.store(front);
while (!m_front.compare_exchange_weak(front, n))
{
  n->next.store(front);
}

一般的 POP 算法（同样，忽略除实际算法逻辑之外的所有细节）是：

Node* front = m_front.load();
Node* next = front->next.load();
while (!m_front.compare_exchange_weak(front, next))
{
  next = front->next.load();
}

这里是 PUSH 算法的真实示例实现：

https://github.com/khizmax/libcds/blob/master/cds/intrusive/treiber_stack.h#L736

所以我不明白为什么下一个指针甚至需要是原子的。大多数 C++ 实现使用 loads/stores 和 next 指针，所以当 reading/writing 到下一个指针时我们不需要任何内存栅栏，但我的想法是它不需要完全是原子的。

据我所知，任何时候都不会同时写入任何节点的next指针。相反，下一个指针可能会同时加载，但我从未看到算法有任何机会同时加载+存储或同时存储+存储。事实上，在 PUSH 算法中，根本不会并发访问 next 指针。

所以在我看来，下一个指针在并发访问时实际上是 "read-only"，所以我不确定为什么有必要让它们成为原子。

然而，我见过的每个 Treiber Stack 的 C++ 实现都使 next 指针成为原子指针。那么我是正确的，还是有某种原因必须使下一个指针成为原子指针？

Answer 1

如果它像您显示的代码一样简单，那您就是对的。 Node 在指向它的指针发布后永远不会被修改。但是您遗漏了清理节点的部分，以便可以对它们进行垃圾收集。（你不能在弹出后 delete ；另一个线程可能仍然有指向它的指针但尚未读取它。这对 RCU 来说也是一个棘手的问题。）

这是您遗漏的函数，在 pop 中的 CAS 成功后调用：

protected:
    void clear_links( node_type * pNode ) CDS_NOEXCEPT
    {
        pNode->m_pNext.store( nullptr, memory_model::memory_order_relaxed );
    }

这是一个 reader 在写入时读取 next 的顺序：

A: Node* front = m_front.load();
                                 B: Node* front = m_front.load();  // same value
A: Node* next = front->next.load();
A: m_front.compare_exchange_weak(front, next) // succeeds, no loop
A: clear_links(front);  // i.e. front->next.store(nullptr);

                                 B: front->next.load();

因此，C++ 未定义行为，就标准合规性而言故事结束。

实际上，大多数 CPU 架构上的非原子负载，或者在最坏的情况下会出现撕裂。（任何 ISA 的 IDK，它会导致除值之外的任何不可预测的内容，但 C++ 保留此选项打开）。

我不确定在任何情况下撕裂值实际上可以使用（放入m_front），因为clear_links()不能运行直到CAS成功之后。如果 CAS 在一个线程中成功，它将在另一个线程中失败，因为它只会尝试使用旧的 front 作为 CAS 的 expected arg 的撕裂 next 值。

在实践中，几乎每个人关心的每个实现都没有额外的成本用于宽松的原子 loads/stores 与指针大小的对象的常规。事实上，如果 .

，这个堆栈非常糟糕

例如在 AVR（使用 16 位指针的 8 位 RISC 微控制器）上，只锁定数据结构会更便宜，而不是让 std::atomic 在这个算法中为每个 load/store 使用锁. （特别是因为没有多核 AVR CPU，所以实现锁的成本可能非常低。）

atomic<> 还让编译器假设一个值可以被另一个线程异步修改。所以它阻止它优化加载或存储，有点像 volatile。（但另见。）我不认为这里有任何需要的地方，也不会发生。

非原子操作按原子获取和释放操作排序，类似于宽松的原子操作，CAS修改front，所以front->nexthas a newfront`所以一个非原子负载无法优化。

将 atomic <Node*> next 替换为 Node *next 后，看看您是否从编译器获得相同的 asm 输出可能是一个有趣的实验。（或者使用仍然具有 load/store 成员函数的 non_atomic 包装器 class，因此您不必修改太多代码）。

我觉得使用宽松的原子存储很不错。您肯定不想以您展示的方式实现它，将 seq_cst 存储作为初始化尚未发布任何指向它的指针的新对象的一部分。那时不需要原子性，但它是免费的（在正常 CPUs 上）所以避免它没有任何好处。 None 的商店或负载可以优化掉。

C++ Treiber Stack 和原子 next 指针

C++ Treiber Stack and atomic next pointers

c++

multithreading

algorithm

atomic

lock-free