有多个线程数据结构问题的现有解决方案吗？ [英] Is there an existing solution to the multithreaded data structure problem?

问题描述

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

I've had the need for a multi-threaded data structure that supports these claims:

• 允许多个并发读取器和写入器


• 排序


• 很容易解释

实现多个读者和一个作者是很容易，但我真的不会允许多个作家。

Fulfilling multiple readers and one writer is a lot easier, but I really would wan't to allow multiple writers.

我一直在研究这个领域，我知道ConcurrentSkipList（由Lea基于Fraser和Harris的工作），因为它在Java SE 6中实现。我还基于由Herlihy，Lev，Luchangco和Shavit发起的一个普遍正确的可扩展并发跳过
列表。

I've been doing research into this area, and I'm aware of ConcurrentSkipList (by Lea based on work by Fraser and Harris) as it's implemented in Java SE 6. I've also implemented my own version of a concurrent Skip List based on A Provably Correct Scalable Concurrent Skip List by Herlihy, Lev, Luchangco and Shavit.

实现是由那些比我更聪明的人开发的，但我仍然（有点ash愧，因为它是惊人的工作）不得不问这些是如何是并发的多读取器/写入器数据结构的两个唯一可行的实现？

These two implementations are developed by people that are light years smarter then me, but I still (somewhat ashamed, because it is amazing work) have to ask the question if these are the two only viable implementations of a concurrent multi reader/writer data structures available today?

推荐答案

听起来像我自己这么难。请考虑以下内容：

Sounds to me like your making this problem too hard for yourself. Consider the following:

• 它很容易实现许多数据结构的不可变版本，特别是树。不可变数据结构具有的好处是，由于是不可变的，一个线程不能在另一个线程鼻子下修改集合。不变性=无竞争条件=无锁=无死锁。 Awesomeness。

• Its pretty easy to implement immutable versions of many data structures, especially trees. Immutable data structures have the benefit that, by virtue of being immutable, one thread can't modify the collection under another threads nose. Immutability = no race conditions = no locks = no deadlocking. Awesomeness.

请参阅 Okasaki的纯功能数据结构，它提供堆，平衡树，堆栈，队列和一些其他数据结构的ML和Haskell实现。

See Okasaki's Purely Functional Data Structures, which provides ML and Haskell implementations of heaps, balanced trees, stacks, queues, and some other data structures.

线程不能请参阅对在其他线程中进行的不可变数据结构的更改。

Threads can't see changes to an immutable data structure made in other threads. They can, however, notify one another explicitly of changes using message-passing concurrency.

锁定和互斥量过低级别，可变状态几乎是多线程编程的敌人。如果你想想你试图解决的任何问题的不变性和消息传递，那么它会变得1000倍更容易为你。

Locks and mutexes are too low-level, and mutable state is pretty much the enemy of multithreaded programming. If you think about whatever problem your trying to solve in terms immutability and message passing, then it'll become 1000x easier for you.

这篇关于有多个线程数据结构问题的现有解决方案吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！