.NET的无锁和线程安全的IList<T>

Question

有没有一种无锁且线程安全的数据结构可以实现IList？

自然地，我指的是在.NET中没有使用锁原语，而是使用交换操作/原子操作来实现线程安全的实现...

显然，在并发数据结构中似乎没有这样的数据结构...

有人看到过这样的数据结构吗？

我看到一个Java实现的amino-cbbs，称为LockFreeVector，但目前还没有.NET版本。

有什么想法吗？

- damageboy

---

我想您的意思是“无锁”和线程安全，因为List<T>是相当无锁的。您还应该澄清您所说的“无锁”的含义。 - John Saunders

@damageboy 另外一点：他们（氨基酸）正在实现一个链接列表，而不是一个列表。C#中的LinkedList没有实现IList/IList<T>。他们有一个LockFreeVector...但我不认为它是“完全”无锁的。 - xanatos

你需要多完整的实现？我非常怀疑你能找到一个支持随机插入而不锁定的类型（除非你允许自旋，因为那不是真正的“锁定”）。但是，我又知道什么呢？ - Dan Tao

@xantos：我指的是amino的LockFreeVector<T>： http://amino-cbbs.sourceforge.net/java_apidocs/org/amino/ds/lockfree/LockFreeVector.html - damageboy

@damageboy：请注意，基于论文描述的无锁结构的 LockFreeVector<E> 并没有随机 Insert 操作（这是 IList<T> 接口的一部分）。 - Dan Tao

Answer 1

由于整个Parallel.For和Parallel.ForEach类方法，可能在Collections.Concurrent命名空间中缺少实现IList的ConcurrentList。有人可以说，它们可以用来处理任何列表作为Concurrent，以便快速枚举列表并对其项执行操作。

也许通过不提供ConcurrentList，他们意味着或认为如果Parralel.For无法帮助，则需要使用不是IList而是其他类型的集合，如堆栈或队列甚至Bag或Dictionary

我同意这种设计，因为在多线程条件下处理可索引集合听起来很容易出错和糟糕的设计。如果集合随时可以修改并且索引将无效，那么知道项的索引的目的是什么，在存在多个读取器 - 写入器的情况下，对我来说很明显Queue或Stack将是常用的最适合的集合，或者Bag也可以很好地使用。字典也可以使用，因为添加项目到集合不会使其索引无效，如果您需要并行访问列表，则可以使用Parralel.For方法

我发现很奇怪的是——http://msdn.microsoft.com/en-us/library/dd381935.aspx在这里我们可以阅读关于ConcurrentLinkedList类的内容，但我找不到它在System.dll中，只有Bag和BlockingCollection。

我认为你的问题至少有95%的概率符合以下两种情况之一：

1. Parallel类方法比ConcurrentList更好
2. 现有的Concurrent集合将比ConcurrentList更好

我还要说的是，通过不提供ConcurrentList，他们为那些错误地选择ConcurrentList来解决问题的开发者节省了时间，并避免了许多错误，迫使开发者使用现有的Concurrent集合。

- Valentin Kuzub

---

你所引用的页面说，在发布 VS 2010 之前将删除 ConcurrentLinkedList，不要使用它。我同意你写的一切-干得好+1。 - phillip

虽然我确实在很多方面同意你的观点，但我仍然认为需要一个线程安全的IList<T>，就像amino-cbbs中提供的LockFreeVector<T>一样...主要用例（巧合的是，这也是我想要的）是当您有一个List<T>的仅追加修改来自一个/多个线程时，而另外一些线程可能需要以只读方式遍历列表，直到它们开始枚举/处理时的最后已知.Count值...换句话说，我正在寻找与数组等效的只读性能，同时仍然能够进行追加。 - damageboy

Answer 2

我在其他地方无法找到这样的类，所以我自己试着写了一个。

我的ConcurrentList<T>类的源代码可以在GitHub上获取。

它是无锁的、线程安全的（基于我的单元测试，我认为是这样的），并实现了IList<T>。

它不支持Insert、RemoveAt/Remove或Clear。

令我高兴的是，我独立开发的实现与一些软件界内备受尊敬的人士发布的数据结构非常相似。

关于实现本身的简短讨论，请参见我最近的博客文章。

目前，它没有任何文档，考虑到一些代码有多么“棘手”，这有点糟糕:(

如果你看了一眼并发现了错误或其他问题，请务必指出。

无论如何，检查一下可能值得你的时间。如果你这样做了，请告诉我你的想法。

- Dan Tao

---

如果你自己动手实现该功能，我会加1赞的。我也正在将Java版本移植到c#...我看了你的博客文章，仍然会在我的机器上运行你的测试，但主要的好处在于多个读取线程与单个写入/附加线程。这是你应该期望看到性能提升的地方，因为简单愚蠢的“使用lock()”解决方案仍然会针对每个读取操作进行锁定... - damageboy

C# 中是否有 volatile 关键字？在 C 语言中，CAS 的目标需要是 volatile 的，因为 CAS 是否成功是一个运行时决定。 - user82238

@Blank: 关于对齐问题，这是一个非常好的观点。在现代处理器上，对齐要求并不多。（我在其他地方回答了这个问题：https://dev59.com/A0fRa4cB1Zd3GeqP-6Uz#5178935）。.NET框架似乎确保（仍在寻找官方信息）指针对齐。这意味着在x86上，你将获得4字节对齐，在x64上则是8字节对齐。所讨论的代码（原始版本由Dan Tao编写，我的更新版本）都需要达到指针大小的对齐要求。 - damageboy

@damageboy：如果单词CAS内存没有对齐到8个字节，那么CAS指令将出错。 - user82238

我在C语言中编写了一个无锁库 - www.liblfds.org。如果CAS操作数在系统指针长度上未对齐，则二进制文件会崩溃。这主要是当涉及到结构体中的指针时（因此最终会得到未对齐的地址）成为问题。 - user82238

Answer 3

想象一下在多线程环境下如何使用随机访问（由 IList<T> 隐含）可能会出现的情况。如果添加和删除即使是原子操作，也不能真正地做到不可变性，因为它们无法防止第一个线程删除线程2刚要检索的索引处的项目。这就是为什么在 .NET 2.0+ 中 SyncRoot 的东西被移除的原因。

- Mark Sowul

---

我已经考虑过并在Valentin Kuzub在评论中提出这一点时回答了它。唯一有用的情况是仅针对.Add() IList<T>，其中Remove/Insert不适用/允许。这实际上可以并且确实可以大大提高读取器性能，同时仍允许线程安全的追加操作。 - damageboy