c# - 并发跳表读锁定

Question

我会尽力使这个问题尽可能通用，但我会简要介绍我的实际问题 -

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

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

node = node.forward[i]

对于这样的事情我需要什么样的线程安全？如果另一个线程在我读取的同时修改node.forward[i](没有当前的读取锁定机制)，这里会发生什么？

我最初的想法是在 Forward 索引器的 getter 和 setter 上使用 ReaderWriterLockSLim。这种情况下会不会有太多不必要的锁定？

编辑:或者最好使用 Interlocked.Exchange 进行所有读取？

Answer 1

If another thread is modifying node.forward[i] at exactly the same time that I read (with no current locking mechanism for read), what can happen here?

这实际上取决于实现。可以使用Interlocked.Exchange当以可以防止引用无效的方式设置“前进”时(因为它可以使“设置”原子)，但不能保证您将读取哪个引用。然而，如果实现简单，任何事情都可能发生，包括获取不良数据。

My initial thought is to have a ReaderWriterLockSLim on the getter and setter of the indexer for Forward.

这可能是一个很好的起点。使用 ReaderWriterLockSlim 制作正确同步的集合相当容易，并且功能始终是第一要务。

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

Will there be too much unnecessary locking in this scenario?

如果不看看如何实现它，更重要的是，不看看它会如何使用，就无法知道它的情况。根据您的使用情况，您可以分析并寻找优化机会如果有必要。

附带说明 - 您可能需要重新考虑使用 node.Forward[i] 而不是此处更多的“链接列表”方法。对 Forward[i] 的任何访问都可能需要相当多的同步来迭代跳过列表 i 步骤，所有这些都需要一些同步来防止错误，如果除了 node 之外，node 和 i 元素之间的任何位置都存在并发写入。如果您只向前看一步，则可以(可能)减少所需的同步量。