并发skiplist读锁定

Question

我会试着让这个问题尽可能通用，但我会简要介绍一下我的实际问题-

我正在尝试为优先级队列实现并发skiplist。每个“节点”都有一个值和一个“转发”节点数组，其中node.forwardi表示跳过列表的第i层上的下一个节点。对于写访问(即插入和删除)，我使用自旋锁(仍然要确定这是否是最好的锁)

我的问题本质上是，当我需要读访问权限进行遍历时，

node = node.forward[i]

在这种情况下，我需要什么样的线程安全？如果另一个线程在我读的同时修改node.forwardi (没有当前的读锁定机制)，这里会发生什么？

我最初的想法是在用于前进的索引器的getter和setter上创建一个ReaderWriterLockSLim。在这种情况下会有太多不必要的锁定吗？

编辑:或者我所有的读操作都使用Interlocked.Exchange是不是最好？

Answer 1

如果另一个线程在我读的同一时间修改node.forwardi (没有当前的读锁定机制)，这里会发生什么？

这真的取决于实现。可以在设置"forward“时使用Interlocked.Exchange，以防止引用无效(因为它可以使"set”成为原子)，但不能保证在读取时会获得哪个引用。然而，对于一个幼稚的实现，任何事情都可能发生，包括获得坏数据。

我最初的想法是在

索引器的getter和setter上设置一个ReaderWriterLockSLim。

这可能是一个很好的起点。使用ReaderWriterLockSlim创建一个正确同步的集合将是相当容易的，并且功能性始终是第一位的。

这可能是一个很好的起点。

在这种情况下会有太多不必要的锁定吗？

没有办法知道你是如何实现它的，更重要的是，它是如何被使用的。根据您的使用情况，您可以在必要时分析和寻找优化机会。

另外，您可能希望重新考虑使用node.Forward[i]，而不是这里更多的“链表”方法。任何对Forward[i]的访问都可能需要相当多的同步来迭代skip list i步骤，所有这些步骤都需要一些同步，以防止在node以外的node和i元素之间存在并发写入时出现错误。如果您只向前看一步，您就可以(潜在地)减少所需的同步量。