Atomic shared_ptr用于无锁单链表

Question

我想知道是否有可能为任何"常见"架构(如x64或ARMv7/ARMv8)创建无锁,线程安全的共享指针.

在cppcon2014上关于无锁编程的讨论中,Herb Sutter提出了一个无锁定单链表的(部分)实现.实现看起来很简单,但它依赖于shared_ptr标准库中不存在或使用专用std::atomic...函数的原子实现.这一点尤为重要,因为单个push/pop调用可能会调用多个原子加载/存储和compare_exchange操作.

我看到的问题(我认为谈话中的一些问题是朝着相同的方向)是因为这是一个实际的无锁数据结构,那些原子操作本身就必须是无锁的.我不知道任何标准库实现std::atomic...的无锁功能 - 至少有一个简短的google/SO搜索 - 我也没有找到如何实现无锁专业化的建议std::atomic<std::shared_ptr>.

在我浪费时间之前,我想问:

• 你知道吗,如果有可能写一个无锁的原子共享指针呢？
• 是否已经有任何我忽略的实现 - 理想情况 - 甚至与您期望的实现兼容std::atomic<std::shared_ptr>？对于所提到的队列,它尤其需要CAS操作.
• 如果无法在当前体系结构上实现此功能,那么与锁定保护的"普通"链接列表相比,您是否看到Herb实现中的任何其他好处？

---

供参考,这里是来自Herb Sutter的代码(可能包含来自我的错别字):

template<class T> 
class slist {
    struct Node { T t;  std::shared_ptr<Node> next; };
    std::atomic<std::shared_ptr<Node>> head;        
public:
    class reference{
        std::shared_ptr<Node> p;
    public:
        reference(std::shared_ptr<Node> p_){}
        T& operator*(){ return p->t; }
        T* operator->(){ return &p->t; }
    };
    auto find(T t) const {
        auto p = head.load();
        while (p && p-> != t) {
            p = p - next;
        }
        return reference(move(p));
    }
    void push_front(T t) {
        auto p = std::make_shared<Node>();
        p->t = t;
        p->next = head;
        while (!head.compare_exchange_weak(p->next, p)) {}
    }
    void pop_front() {
        auto p = head.load();
        while (p && !head.compare_exchange_weak(p, p - next)) { ; }
    }
};

注意,在此实现中,a的单个实例shared_ptr可以由多个不同的线程访问/修改.它可以被读取/复制,重置甚至删除(作为节点的一部分).所以这不是关于多个不同的shared_ptr对象(管理同一个对象)是否可以被多个线程使用而没有竞争条件 - 这对于当前实现已经是正确的并且是标准所要求的 - 但它是关于对单个指针的并发访问实例,对于标准共享指针 - 没有比原始指针上的相同操作更多的线程安全.

---

解释我的动机:
这主要是一个学术问题.我不打算在生产代码中实现我自己的锁定免费列表,但我发现这个主题很有趣,乍一看,Herb的演示似乎是一个很好的介绍.然而,在考虑这个问题和@ sehe对我的答案的评论时,我记得这个话题,再看看它并意识到如果它的原始操作需要锁定,那么调用Herb的实现无锁是没有多大意义的(他们目前正在做什么).所以我想知道,这只是对当前实现的限制还是设计中的一个根本缺陷.

Answer 1

我将其添加为答案，因为评论太长了：

需要考虑的事情。是无锁的shared_ptr并不需要实现无锁/无等待的数据结构。

Sutter 在他的演讲中使用 shared_ptr 的原因是因为编写无锁数据结构最复杂的部分不是同步，而是内存回收：当节点可能被其他线程访问时，我们不能删除它们，所以我们必须泄漏它们并在以后回收。无锁 shared_ptr 实现本质上提供了“免费”内存回收，并使无锁代码的示例变得可口，尤其是在有时间限制的演示的上下文中。

当然，将无锁 atomic_shared_ptr 作为标准的一部分将是一个巨大的帮助。但这不是为无锁数据结构进行内存回收的唯一方法，还有一种天真的实现，即维护要在执行中的静止点删除的节点列表（仅适用于低争用场景）、危险指针、滚动 -您自己的原子引用计数使用拆分计数。

至于性能，@mksteve 是正确的，无锁代码不能保证优于基于锁的替代方案，除非它运行在提供真正并发的高度并行系统上。它的目标是实现最大的并发性，因此我们通常得到的是以执行更多工作为代价的线程更少的等待。

PS 如果您对此感兴趣，您应该考虑看看 Anthony Williams 的 C++ Concurrency in Action。它用了一整章来编写无锁/无等待代码，这提供了一个很好的起点，介绍了无锁堆栈和队列的实现。

Answer 2

可以编写无锁共享 ptr，因为唯一需要更改的是计数。ptr 本身仅被复制，因此这里不需要特别注意。删除时，这必须是最后一个实例，因此其他线程中不存在其他副本，因此没有人会同时增加。
但话虽如此， std::atomic> 将会是一个非常特殊的东西，因为它不完全是一个原始类型。

我见过一些无锁列表的实现，但没有一个是共享指针的。这些容器通常有特殊用途，因此关于它们的使用（何时/谁创建/删除）存在协议，因此不需要使用共享指针。
此外，共享指针带来的开销与我们最初将我们带入无锁域的低延迟目标背道而驰。

所以，回到你的问题——我认为这是可能的，但我不明白为什么要这样做。
如果您确实需要类似的东西，那么refCount成员变量会更好。

我认为 Herb 的具体实现没有任何具体的好处，也许除了学术上的好处之外，但无锁列表有明显的没有锁的动机。它们通常用作队列或只是在对锁过敏的线程之间共享节点集合。
也许我们应该问赫伯..赫伯？你在听么？

编辑： 根据下面的所有评论，我实现了一个无锁单链表。该列表相当复杂，以防止共享指针在访问时被删除。它太大了，无法在这里发布，但主要思想如下：
- 主要思想是将删除的条目存储在单独的位置 - 垃圾收集器 - 以使它们无法被以后的操作访问。
- 原子引用计数在进入每个函数（push_front、pop_front和front）时递增，并在退出时自动递减。当版本计数器递减至零时，版本计数器会递增。全部集中在一条原子指令中。
- 当共享指针需要被擦除时，在pop_front中，它被推入 GC。每个版本号都有一个 GC。GC是使用更简单的无锁列表实现的，只能使用push_front或pop_all。我创建了 256 个 GC 的循环缓冲区，但也可以应用其他一些方案。
- 版本的 GC 在版本增量时刷新，然后共享指针删除持有者。
因此，如果你调用 pop_front，没有任何其他运行，引用计数将增加到 1，前端共享 ptr 被推入 GC[0]，引用计数回到零并且版本为 1，GC[0] 被刷新 - 它减少我们弹出的共享 ptr 并可能删除它拥有的对象。

现在，创建一个无锁的shared_ptr。我相信这是可行的。以下是我想到的想法：
- 您可以使用指向持有者的指针的低位来获得某种自旋锁，因此只有在锁定它之后才能取消引用它。您可以对 inc/dec 等使用不同的位。这比锁定整个事物要好得多。
这里的问题是共享 ptr 本身可以被删除，因此它包含的任何内容都必须提供一些来自外部的保护，例如链接列表。
- 您可以拥有一些共享指针的中央注册表。这不会遇到上述问题，但在不偶尔出现延迟峰值的情况下进行扩展将是一项挑战。

总而言之，我目前认为整个想法没有实际意义。如果您发现其他一些不会遇到大问题的方法 - 我会非常想知道:)
谢谢！