对于这些特定的多线程数据结构需求,是否有现有的解决方案?

我觉得你把这个问题弄得太难了。考虑以下几点:

• 看到了吗 Okasaki's Purely Functional Data Structures

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

每个节点包含一个元素(或一个引用)和一个简单的互斥锁。我在这里假设Java,因为它有助于避免节点回收的竞争条件。

搜索列表包括从头部遍历节点,无需获取任何锁(尽管您需要确保线程之间在某个点的可见性—您可以选择这种情况发生的频率—每次搜索一次就足够了)。

要添加项,请执行搜索,直到找到要插入的值的直接前置节点和后续节点,锁定与前一个节点关联的互斥锁,再次检查后续节点(它可能已从您下面更改),然后拼接到新节点。

删除的工作原理类似—找到要删除的节点的前置节点,锁定前置节点,检查它是否仍然是前置节点,并将其从树中取出。

这个结构被分类了(在一定程度上它是正确的-我还没有证明这一点!)。

这种结构显然允许多个读卡器(读卡器从不因任何原因被阻塞)和多个写卡器,尽管尝试操作列表的相同部分的写卡器(例如,两个线程插入具有相同拼接点的节点)将互相等待。

这种结构似乎比较容易推理——基于单个链表,具有相当简单的锁定结构和一些简单的不变量。然而,我没有花超过几分钟的时间来论证它的正确性。以性能为代价,通过使锁定策略更重(插入和删除在迭代过程中锁定每个节点,然后在解锁前一个节点之前锁定后续节点),您可以使推理变得更简单,这样,当您找到拼接点或删除点时,您将锁定两个节点,因此无需“双重检查,需要“回溯”。

你也许可以完全摆脱锁,并使用一个无锁列表,同时保持你的“必须排序”条件,但我还没有深入考虑它-至少我怀疑这将是“难以推理”。

在C++中,结构更为复杂,因为只要读者可能在看它们,就不能依靠GC来保持节点的周围,所以如果读者想删除节点,允许读者以无锁方式运行的简单策略不会飞。您可以通过使读卡器获得每个访问节点的锁来调整它,但这对性能(显而易见)和并发性都很糟糕(因为虽然您可以以某种基本方式拥有多个读卡器和写卡器,但它们再也不能相互传递了,所以实际的并发性受到很大限制)。

另一种方法是在每个节点中使用rwlocks,reader只接受读锁,inserter/deleter接受读锁以找到要处理的位置,然后升级到write。因为读卡器可以传递读卡器,所以货币至少得到了改进,但是写卡器仍然阻止读卡器(因此,在写操作开始的某个节点之前迭代的所有读卡器在操作完成之前将无法迭代通过该节点)。

我想如果你真的想要的话,你可以扩展这种“每节点”的锁定到rb树之类的东西,但这并不容易。特别是,您需要在任何树旋转之前找到某种要锁定的节点,这种节点“足够高”,您可以确保任何想要执行修改的线程也会尝试锁定同一个节点,该修改会影响旋转的正确性。在链表中,这是“前置节点”-在AVL或RB树中,它不是那么简单。

我在中创建了一个无锁数据结构 F# 对我最近的工作有类似的要求。具体来说,这是一个排序字典映射 int 钥匙 内景

我是在 作为类型的值 Map<int, int ref> ref 内景 对的可变引用的键 内景 价值观。读取器同时读取引用以获得当前映射,查找其中的键并取消引用以获得关联的 价值观。写入程序同时读取引用,查找键并原子地增加它(如果存在),或者使用新的键值对创建一个新映射,并使用CAS替换对映射的根引用。

Map 很少见。在我的例子中是这样的,因为大多数写入已经存在的增量计数器,并且在稳定状态下,很少创建新的计数器。