c# - 是否可以使用无锁（等待）双向链表？

Question

用 C# 标签问这个问题，但如果可能的话，应该可以用任何语言。

是否可以使用互锁操作实现双向链表以提供无等待锁定？我想插入、添加和删除，无需等待即可清除。

score 16 · Accepted Answer

是的，这是可能的，这是我在 C++ 中实现的类似 STL 的无锁双链表。

它需要 64 位比较和交换才能在没有 ABA 问题的情况下运行。这个列表只有在无锁内存管理器的作用下才有可能。

查看第 12 页的基准。随着争用的增加，列表的性能随着线程数的增加呈线性关系。该算法支持不相交访问的并行性，因此随着列表大小的增加，争用可以减少。

score 11 · Accepted Answer

一个简单的 google 搜索将显示许多无锁双向链表论文。

但是，它们基于原子 CAS（比较和交换）。

我不知道 C# 中的操作有多原子，但根据这个网站

C# 操作仅保证对读取和写入 32 位字段是原子的。没有提到CAS。

score 4 · Accepted Answer

这是一篇描述无锁双向链表的论文。

我们提出了一种高效且实用的无锁并发双端队列实现，该双端队列可不相交并行访问，并使用现代计算机系统中可用的原子原语。以前已知的双端队列无锁算法要么基于不可用的原子同步原语，要么只实现功能的一个子集，要么不是为不相交的访问而设计的。我们的算法是基于一个双向链表，并且只需要一个单词的比较和交换...

Ross Bencina 有一些非常好的链接，我刚刚在大量论文和源代码示例中找到了“关于无锁和无等待算法的一些注释”。

score 2 · Accepted Answer

我不相信这是可能的，因为您必须一次设置多个参考，并且联锁操作的能力有限。

例如，以 add 操作为例 - 如果您在 A 和 C 之间插入节点 B，则需要在一个原子操作中设置 B->next、B->prev、A->next 和 C->prev。联锁处理不了。预设 B 的元素甚至没有帮助，因为另一个线程可能决定在您准备“B”时进行插入。

在这种情况下，我会更多地关注尽可能细粒度的锁定，而不是试图消除它。

score 1 · Accepted Answer

Well you haven't actually asked how to do it. But, provided you can do an atomic CAS in c# it's entirely possible.

In fact I'm just working through an implementation of a doubly linked wait free list in C++ right now.

score 1 · Accepted Answer

1

阅读脚注 - 他们计划在 VS2010 最终版本之前从 4.0 中提取 ConcurrentLinkedList

于 2009-06-15T06:36:30.563 回答

score 1 · Accepted Answer

可以为大多数架构上的所有可复制数据结构编写无锁算法 [1]。但是很难写出有效的。

我为 .Net编写了 Håkan Sundell 和 Philippas Tsigas的无锁双向链表实现。请注意，由于这个概念，它不支持原子 PopLeft。

score 0 · Accepted Answer

FWIW，.NET 4.0 正在添加 ConcurrentLinkedList，这是 System.Collections.Concurrent 命名空间中的线程安全双向链表。您可以阅读文档或描述它的博客文章。

score -1 · Accepted Answer

我会说答案是非常有资格的“是的，有可能，但很难”。要实现您所要求的，您基本上需要将操作编译在一起以确保没有冲突的东西；因此，很难为此目的创建一个通用实现，并且它仍然存在一些重大限制。创建一个针对精确需求量身定制的特定实现可能会更简单，即使那样，它无论如何也不会是“简单”的。

9 回答 9