併發skiplist讀鎖定

Question

我將努力使這個問題儘可能的通用，但我會給出一個簡要介紹了我的實際問題 -

我試圖實現對優先級隊列併發skiplist。每個「節點」都有一個值和一個「前向」節點的數組，其中node.forward [i]表示跳過列表的第i級上的下一個節點。對於寫訪問（即插入和刪除），我用一個自旋鎖（仍然以確定是否是用最好的鎖）

我的問題基本上是，當我需要一個遍歷讀訪問，

node = node.forward[i] 

圍繞這樣的事情需要什麼樣的線程安全性？如果另一個線程在我讀取的同一時間修改node.forward [i]（沒有當前的讀取鎖定機制），會發生什麼情況？

我最初的想法是對索引進行正向的getter和setter一個ReaderWriterLockSLim。在這種情況下是否會有太多不必要的鎖定？

編輯：或者會是最好的，而不是使用我所有的讀取Interlocked.Exchange？

Answer 1

如果另一個線程正在修改node.forward [i]與我讀取的同一時間（沒有當前鎖定機制來讀取），那麼會發生什麼？

這真的取決於執行。當設置「forward」時可以使用Interlocked.Exchange，以防止引用無效（因爲它可以使「set」原子化），但不能保證讀取哪個引用。然而，在一個天真的實現中，任何事情都可能發生，包括獲取不好的數據。

我最初的想法是在Forwarder的索引器的getter和setter上有一個ReaderWriterLockSLim。

這很可能是一個良好的開端。使用ReaderWriterLockSlim進行正確同步收集將非常容易，功能永遠是第一要務。

這可能會是一個很好的起點。

在這種情況下是否會有太多不必要的鎖定？

沒有看到你如何實現它，更重要的是，它是如何被使用，沒有辦法知道。根據您的使用情況，您可以根據需要對進行分析並尋找優化機會。

在附註上 - 您可能需要重新考慮使用node.Forward[i]而不是更多的「鏈接列表」方法。對Forward[i]的任何訪問都可能需要一定程度的同步才能遍歷跳過列表i的步驟，如果node和i之間的任何地方出現node以外的元素之間的任何地方的任何寫入，則所有步驟都需要一些同步來防止錯誤。如果您只向前看一步，則可以（可能）減少所需的同步量。