是否可以实现无锁（等待）的双向链表？

题

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

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

解决方案

一个简单的谷歌搜索，就会发现很多无锁双链表的论文。

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

我不知道在C＃中怎么操作原子是的，但根据该网站

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

其他提示

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

它需要 64 位比较和交换才能运行，而不会出现 ABA 问题。该列表之所以可能，是因为无锁内存管理器.

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

这里有一个纸它描述了一个无锁双向链表。

我们提出了一个并发的脱口水的有效且实用的无锁实现，该实现与现代计算机系统中可用的原子原始原子是不相同的并行访问。以前已知的DEQUE的无锁算法是基于不可用的原子同步基元，只能实现功能的子集，或者不是为脱节访问而设计的。我们的算法基于双重链接列表，并且仅需要单个字比较和折叠...

Ross Bencina 有一些非常好的链接，我刚刚发现了许多论文和源代码示例“关于无锁和无等待算法的一些注意事项".

我不相信这是可能的，因为你有一次性设置多个引用和互锁操作在他们的权力受到限制。

例如，以添加操作 - 如果你插入A和C之间的节点B，则需要设置B->下，B->分组，A->下，和C->分组在一个原子操作。互锁无法处理。预设B的元素甚至没有帮助，因为另一个线程可以决定当你准备“B”做一个插件。

我会更专注于获得在这种情况下，细粒度地锁定，而不是试图消灭它。

读取脚注 - 他们计划拉ConcurrentLinkedList从4.0现有VS2010的最终版本

要

好了，你还没有真正问如何做到这一点。但是，只要你能在C＃中做一个原子的CAS完全有可能。

其实我通过C ++现在双向链表等待空闲列表的实现，我只是工作。

可以编写无锁算法全部大多数架构上的可复制数据结构[1]。但要写出高效的代码是很困难的。

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

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

我要说的是，答案是非常深刻合格“是的，这是可能，但硬”。要实现你问什么，你基本上需要的东西，将编译操作起来，以确保不会发生冲突;正因为如此，这将是很难创建用于该目的的一般实现，它仍然会有些显著的局限性。它可能会更简单，以创建量身定做的精确需求的具体实施，即使这样，也不会以任何方式将“简单”。

许可以下： CC-BY-SA 和归因