这些特定的多线程数据结构需求是否有现成的解决方案？

Question

这些特定的多线程数据结构需求是否有现成的解决方案？

language-agnosticdata-structuresconcurrencyparallel-processingbinary-tree

9

我需要一个支持以下要求的多线程数据结构：

允许多个并发读取者和写入者
已排序
易于理解

实现多个读取者和一个写入者比较容易，但我真的想允许多个写入者。

我一直在研究这个领域，我知道ConcurrentSkipList（由Lea基于Fraser和Harris的工作实现）因其在Java SE 6中的实现而闻名。我还根据Herlihy、Lev、Luchangco和Shavit的A Provably Correct Scalable Concurrent Skip List实现了自己版本的并发跳表。

这两种实现是由比我聪明得多的人开发的，但我仍然（有点惭愧，因为这是惊人的工作）不得不问这两种实现是否是当今唯一可行的并发多读/写数据结构的实现？

- thr

3个回答

3

好的，您已经提到了我通常建议的并发跳表，但除了上述三个特定要求之外，我认为一个简单的带有每个节点互斥锁的链表就可以胜任：每个节点包含一个元素（或引用）和一个简单的互斥锁。我会假设这里使用Java，因为它有助于避免节点回收时的竞态条件问题。

通过从头部迭代节点搜索列表，无需获取任何锁（虽然您需要在某个时候确保线程间的可见性 - 您可以选择多频繁进行此操作 - 每次搜索可能已足够）。

要添加一个条目，请执行搜索，直到找到要插入值的直接前驱和后继节点，锁定与先前节点相关联的互斥锁，再次检查后继节点（它可能在您的下面更改），然后拼接新节点。

删除类似地工作-找到要删除的节点的前驱节点，锁定前驱节点，检查它仍然是前驱节点，并将其从树中取出。

该结构是排序的（在正确的范围内 - 我尚未证明！）。

该结构清楚地允许多个读取器（读取器永远不会由于任何原因而被阻塞），以及多个编写器，尽管尝试操作列表的同一部分（例如，插入具有相同拼接点的节点的两个线程）的编写器将等待彼此。

该结构似乎相对容易推理 - 基于单个链接列表，具有相当简单的锁定结构和几个简单的不变量。我没有花费更多时间来思考其正确性，但是您可以通过使锁定策略更加沉重（代价是性能）来使其更易于推理-在迭代期间为每个节点插入和删除锁定每个节点，然后在解锁前趋节点之前锁定后继节点-以这种方式，找到拼接或删除点时，您将同时锁定两个节点，因此不需要“双重检查，回溯”。

您可能可以完全消除锁定并使用无锁链表，同时保持“必须排序”的条件，但我尚未深入思考它-至少我认为这将是“更难推理的”。

在C ++中，由于不能指望GC将节点保留在读取器可能正在查看它们的时间段内，因此允许读取器以无锁方式漫游的简单策略行不通，如果您要删除节点。您可以通过使读取器获取每个访问的节点的锁来调整它，但这会对性能（显然）和并发性（因为尽管您可以以某种基本方式拥有多个读取器和编写器，但它们不能再相互传递，因此实际并发性受到严重限制）造成影响。

另一种选择是在每个节点中使用rwlocks，只有读取器需要获取读取锁定，插入/删除者需要获取读取锁定以找到要处理的位置，然后升级为写入。尽管读取器可以相互传递，但并发性仍得到改善，但写入者仍会阻止读取器（因此，在某些节点上开始写入操作之前迭代在该位置之前的所有读取器将无法迭代超过该节点，直到操作完成）。

现在，所有这些都说了（呼！），我应该提到除了“易于理解”之外，这种结构似乎在每个方面都比并发跳表差，可能稍微少用一点内存（也许）。特别是它没有对数（N）搜索行为。它不是完全无锁定的（写入者在某些情况下可能等待其他写入者）。就并发性而言，我甚至不确定它是否更容易理解，尽管底层结构很简单。

我认为，如果您真的想要，您可以将这种“每个节点”锁定扩展到类似于rb-tree的东西，但这并不容易。特别是，您需要在任何树旋转之前找到要锁定的某个节点，该节点“足够高”，以便您可以确信任何想要执行影响旋转正确性的修改的线程也将尝试锁定相同的节点。在链接列表中，这是“前导节点”-在AVL或RB树中并不那么简单。

- BeeOnRope

@BeeOnRope：感谢您的惊人回应，虽然我希望我能给您更多的赞，但我仍然必须说，使用普通的链表并为每个节点使用互斥锁的想法会很快降低性能，因为搜索/更新/插入时间为O(n)。我真的需要O(log n)来进行搜索/插入/更新，这基本上只剩下跳表或二叉树。我尝试使用锁实现多读/写二叉树，但由于旋转而变得非常复杂。 - thr

如果您可以取消要求值已排序的要求（或者如果需要排序访问的频率不够高以至于需要时进行完整排序就足够了），那么具有分段锁的哈希映射表将非常有效，可能比并发跳表表现更好。请问为什么并发跳表不能满足您的需求呢？ - BeeOnRope

0

最近我在工作中创建了一个无锁数据结构，使用F#。具体来说，这是一个有序字典，将int键映射到int值，其中值是计数器，并且两个基本操作是增加与给定键关联的计数和获取当前键值对数组。

我在F#中实现了这个数据结构，它是类型Map<int, int ref> ref的值，这是一个可变引用，指向不可变映射，将int键映射到可变引用 int 值。阅读者同时读取引用以获取当前映射，在其中查找键并解引用以获取关联的int值。写入者同时读取引用，在其中查找键，如果存在则原子地增加它，否则创建一个带有新键值对的新映射，并使用CAS替换根引用到映射。

这个设计依赖于原子读写引用的能力（.NET保证），但只有在对Map的更新很少时才有效率。在我的情况下，大多数写操作都会增加已经存在的计数器，在稳定状态下，创建新计数器的情况很少。

- J D

一个单一的写入者可以安全地更新它...他说他想允许多个写入者同时更新结构。 - Seun Osewa

@Seun：你说得完全正确。我不知道当我写下原始答案时在想什么，所以我已经用一些希望不是无意义的废话来替换它。;-) - J D

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Juliet · Accepted Answer

听起来你把这个问题想得太难了。考虑以下几点：

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

请参见 Okasaki 的 Purely Functional Data Structures，其中提供了堆、平衡树、栈、队列和其他一些数据结构的 ML 和 Haskell 实现。
线程无法看到其他线程对不可变数据结构所做的更改。但是，它们可以使用消息传递并发显式地通知彼此进行更改。

锁和互斥量太低级，并且可变状态基本上是多线程编程的敌人。如果你用不可变性和消息传递来思考要解决的任何问题，那么它将变得轻松1000倍。