无锁算法库

Question

有没有一个用C语言（而非C++）编写的实现无锁算法（队列、链表和其他）的库？我查看了一些库，如英特尔的库，但我希望使用通用的库，至少比英特尔的更通用。

- user670324

---

队列，链表等并非算法，它们是数据结构。 - Armen Tsirunyan

但是以无锁方式操纵它们的方法是算法，这样的算法甚至是一个研究的活跃领域，如果我没有记错的话。（虽然可能是一个误导人的领域...） - R.. GitHub STOP HELPING ICE

请注意，链表比队列更高级。队列可以不使用SMR编写。链表几乎不可能（我认为可以做到，我想出了一种理论设计，但它很笨拙，当然，由于它没有使用SMR，因此在后台使用了自由列表进行存储）。 - user82238

Answer 1

请参考剑桥大学的实用无锁数据结构

- Doug Currie

---

听起来很酷。有人使用过这个库吗？ - Karoly Horvath

它实现了多字CAS和软件事务内存，这两者都是软件构造，有点不太实用（即：慢）。然后，它们被用来实现二叉搜索树、红黑树和跳表。可以理解为为了实现树而这样做，因为没有已知的单字CAS无锁平衡树数据结构。跳表也有单字CAS实现。没有队列、栈、普通链表或哈希表。 - llongi

如果跳表是单个CAS，它们如何处理ABA问题？ - user82238

我发现这个库的代码晦涩难懂，而且没有文档，无法直接用于生产环境，即使是读懂它也很费劲 :-) - user82238

乍一看，它们似乎有一个完整的垃圾收集器，至少处理CAS跳表的内存回收，再加上一些标记（我只是快速浏览了代码）。当然，完整的GC解决了内存回收问题，一旦解决了这个问题，ABA就消失了（任何完整的内存回收问题解决方案，例如SMR、RCU等，也解决了ABA。我记得有一个证明在某个地方，但你自己推理出来也很容易）。 - llongi

Answer 2

我已经编写了自己的 Rig，目前有队列、栈和列表，哈希表即将推出。虽然我仍在努力完善它，但它是为公众消费而设计的，API大部分稳定，请使用SVN主干。 :)

我知道的唯一另一个类似于C语言库是liblfds，但我从未使用过它。

- llongi

---

是的，该列表使用了删除位，并且使用Michael Maged的SMR算法回收内存。该代码采用BSD许可证，我只是使用了我能找到的最开放/宽容的许可证。 :) - llongi

嗯——删除位——我给Tim发了电子邮件，他在Sun公司做过这项工作，我怀疑它已经被专利化，并且专利权归Sun（现在是Oracle）所有。Maged的SMR——那是危险指针，对吧？那确实是被专利化的。很抱歉，您选择的BSD许可证无法适用于这些技术。如果有帮助的话，RCU可以在LGPL下使用（我选择了这条路线）。 - user82238

几点说明：1）我发布自己的代码或其他库所使用的许可证与可能实施该代码的技术专利完全无关；2）有趣的是，美国软件专利对我和世界的影响几乎为零；3）我甚至不确定这些专利是否存在，如果存在，它们是否具有任何相关性：在许多情况下，使用指针的未使用位来存储信息是一种广泛使用的技术，而且肯定有比Harris 2001年的论文更早的先例。SMR也是一种相当专业的GC（论文本身就这么说），IBM在背后，他们友好于开源。 - llongi

我不是律师，但在我看来，许可证是针对代码的，定义了它的使用和限制，专利则略有不同。欧盟并不像美国那样承认软件专利，因此仅仅因为一个大公司申请了专利，并不意味着它们会被接受。对于SMR，我只找到了一个专利申请。就个人而言，你是我遇到的第一个如此关注这个问题的开源开发者，我绝对不想欺骗任何人（我有点反感那种指责），只是在我的文化/社交环境中，我们不关心这些。 - llongi

我不会因为我可以而轻易地否认这种可能的索赔，我曾经简单地考虑过这个问题，并得出结论：删除位（使用未使用的指针位进行信息存储）根据先前的技术已经被证明无效（请参见维基百科“标记指针”和LISP机器，这在90年代就已经完成了），而且我甚至不确定这项专利是否存在。对于SMR，有一个专利申请，它并不是一个专利，即使是专利，它也不能简单地阻止任何使用，直到在法庭上得到适当证明才能生效，参见所有的苹果、IBM、HTC等公司之间的诉讼以及所有毫无意义的专利。 - llongi

Answer 3

liblfds

http://www.liblfds.org

具有完整 API 文档的 Wiki，用于提问的论坛，以及供作者发表博客的平台。

独立于平台。可直接在 Windows、Linux、Intel 和 ARM 上使用。

Release 7 将在一个月或两个月内发布。将增加运行时缓存行对齐、退避和 SMR。 （SMR 还支持其他许多 CPU 类型 - 基本上是 GCC 可编译支持原子操作的所有 CPU，例如 SPARC、MIPS、IA64 等）。

此外，没有任何许可证 - 您可以随意使用代码。赚钱吧！它不是 GPL。

- user82238

Answer 4

我目前正在编写一个无锁的库，但它是用C++编写的。这里有一个类似STL的 无锁双向链表。

它使用的内存管理器非常强大（32位CAS无ABA问题），因此我使用它来创建完整的容器集：一个无锁映射/集合（使用跳表），一个无锁包（而不是队列/堆栈）和一个无锁无序映射（使用分割有序列表的哈希表）。

有关双向链表的更多信息，请查看 我对相关问题的回答。

- Qarterd

---

我看了一下内存管理器。它似乎在使用危险指针？之前有关于这种技术被专利的讨论。RCU可在LGPL下使用。 - user82238

内存管理器是一个修改过的LFRM，它将引用计数与危险指针相结合。作者几年前在GPL下发布了LFRM的实现，我已经看到其他库使用直接的SMR并发布了自由许可证，尽管存在危险专利。 - Qarterd

真的，这里的专利情况最好是不明确的，危险指针实际上没有专利，只有一项专利申请。我已经在我的博客https://chtekk.longitekk.com/index.php?/archives/84-Software-patents-WTF.html上跟进了所有这些，并记录了我的想法。再次强调，许可证和专利不是同一回事，它们之间的联系取决于许可证的措辞以及基于谁的依据。有趣的东西。 ;) - llongi

如果获得批准，该专利在我的国家也无效。我会采取“到那时再说”的方法来处理这个问题。 - Qarterd

问题在于，有些用户类别无法使用具有此类许可风险的代码。（虽然 GPL 也基本上消除了商业用户的影响）。 - user82238