language-agnostic - 是否有针对这些特定多线程数据结构要求的现有解决方案？

Question

我需要一种支持以下声明的多线程数据结构:

允许多个并发读写器

已排序

关于

很容易推理

实现多位读者和一位作家要容易得多，但是我真的不允许多位作家。

我一直在对该领域进行研究，并且知道ConcurrentSkipList(由Lea根据Fraser和Harris的工作)是在Java SE 6中实现的。我还实现了自己的基于并发跳过列表的版本Herlihy，Lev，Luchangco和Shavit在A Provably Correct Scalable Concurrent Skip List上发表。

这两个实现是由比我聪明的人开发的，但是我仍然(有点(愧，因为这是一件了不起的工作)不得不问一个问题，这是否是并发多读取器/写入器数据结构的两个唯一可行的实现今天有空吗？

Answer 1

在我看来，您觉得这个问题对您自己来说太难了。考虑以下:

实现许多数据结构(尤其是树)的不可变版本非常容易。不可变数据结构的优点在于，由于不可变，一个线程无法在另一个线程的引导下修改集合。不变性=无竞争条件=无锁=无死锁。太棒了

请参阅Okasaki's Purely Functional Data Structures，它提供了堆，平衡树，堆栈，队列和其他一些数据结构的ML和Haskell实现。

线程看不到其他线程中对不可变数据结构所做的更改。但是，它们可以使用消息传递并发性将其他更改明确地通知彼此。

锁和互斥锁的级别太低，可变状态几乎是多线程编程的敌人。如果您考虑尝试通过不变性和消息传递来解决的任何问题，那么对您来说将变得轻松1000倍。