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

Question

我需要一个支持这些声明的多线程数据结构:

实现多个读者和一个作家要容易得多,但我真的不想允许多个作家.

我一直在研究这个领域,我知道ConcurrentSkipList(由Lea基于Fraser和Harris的工作),因为它是在Java SE 6中实现的.我还实现了我自己的并发Skip List版本在一个可证明正确的缩放并发跳表由赫利希,列弗,Luchangco和沙维特.

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

Answer 1

在我看来，你让这个问题对自己来说太难了。考虑以下：

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

请参阅Okasaki 的 Purely Function Data Structures，它提供了堆、平衡树、堆栈、队列和其他一些数据结构的 ML 和 Haskell 实现。
线程无法看到其他线程对不可变数据结构所做的更改。然而，他们可以使用消息传递并发性来明确地通知彼此更改。

锁和互斥量太低级，而可变状态几乎是多线程编程的敌人。如果你考虑一下你试图在不变性和消息传递方面解决的任何问题，那么它对你来说会变得容易 1000 倍。