爲什麼我的線程安全字典實現產生數據競爭？

我目前在C＃中實現了一個線程安全的字典，它在內部使用不可變的AVL樹作爲存儲桶。這個想法是在沒有鎖的情況下提供快速讀取訪問，因爲在我的應用程序上下文中，我們只在啓動時向這個字典中添加條目，之後，大多數值都被讀取（但仍有少量的寫入）。爲什麼我的線程安全字典實現產生數據競爭？

我已經構建通過以下方式我TryGetValue和GetOrAdd方法：

public sealed class FastReadThreadSafeDictionary<TKey, TValue> where TKey : IEquatable<TKey> 
{ 
    private readonly object _bucketContainerLock = new object(); 
    private ImmutableBucketContainer<TKey, TValue> _bucketContainer; 

    public bool TryGetValue(TKey key, out TValue value) 
    { 
     var bucketContainer = _bucketContainer; 
     return bucketContainer.TryFind(key.GetHashCode(), key, out value); 
    } 

    public bool GetOrAdd(TKey key, Func<TValue> createValue, out TValue value) 
    { 
     createValue.MustNotBeNull(nameof(createValue)); 
     var hashCode = key.GetHashCode(); 
     lock (_bucketContainerLock) 
     { 
      ImmutableBucketContainer<TKey, TValue> newBucketContainer; 
      if (_bucketContainer.GetOrAdd(hashCode, key, createValue, out value, out newBucketContainer) == false) 
       return false; 

      _bucketContainer = newBucketContainer; 
      return true; 
     } 
    } 

    // Other members omitted for sake of brevity 
}

正如你所看到的，我不TryGetValue使用鎖，因爲reference assignment in .NET runtimes is an atomic operation by design。通過將字段_bucketContainer的引用複製到局部變量，我確信我可以安全地訪問該實例，因爲它是不可變的。在GetOrAdd中，我使用鎖來訪問私人_bucketContainer，所以我可以確保一個值不會創建兩次（即，如果兩個或更多個線程試圖添加一個值，實際上只有一個線程可以創建一個新的ImmutableBucketContainer，因爲它具有附加值的鎖）。

我用Microsoft Chess測試併發性和在我的測試之一，MCUT（微軟併發單元測試）報告數據種族GetOrAdd當我交流與舊的新桶容器：

[DataRaceTestMethod] 
public void ReadWhileAdd() 
{ 
    var testTarget = new FastReadThreadSafeDictionary<int, object>(); 
    var writeThread = new Thread(() => 
           { 
            for (var i = 5; i < 10; i++) 
            { 
             testTarget.GetOrAdd(i,() => new object()); 
             Thread.Sleep(0); 
            } 
           }); 
    var readThread = new Thread(() => 
           { 
            object value; 
            testTarget.TryGetValue(5, out value); 
            Thread.Sleep(0); 
            testTarget.TryGetValue(7, out value); 
            Thread.Sleep(10); 
            testTarget.TryGetValue(9, out value); 
           }); 
    readThread.Start(); 
    writeThread.Start(); 
    readThread.Join(); 
    writeThread.Join(); 
}

MCUT報告以下信息：

23>測試結果：數據爭用 23> ReadWhileAdd（）（上下文=，TestType = MChess）：在GetOrAdd [數據爭]找到數據種族：FastR eadThreadSafeDictionary.cs（68）

這是轉讓_bucketContainer = newBucketContainer;在GetOrAdd。

我的實際問題是：爲什麼分配_bucketContainer = newBucketContainer的競賽條件？當前正在執行的主題TryGetValue總是複製_bucketContainer字段，因此不應該對更新感到困擾（除了複製發生後搜索到的值可能會被添加到_bucketContainer之外，但是這並不重要數據競賽）。並在GetOrAdd，有一個明確的鎖，以防止併發訪問。這是國際象棋中的錯誤還是我錯過了一些非常明顯的東西？

來源

2016-09-22 feO2x

您沒有使用易失性讀取，並且在構建新狀態並將其分配給字段之間可能需要內存屏障。不知道.net 2.0內存模型，但我認爲這兩個在ECMA內存模型中都是必需的。 – CodesInChaos

@CodesInChaos我已經給'TryGetValue'添加了一個'Volatile.Read'調用，它使測試通過（謝謝！）。不過，我不明白爲什麼這是一個問題，因爲'Volatile.Read'只是確保從內存中讀取值，而不是從可能緩存它的CPU寄存器讀取值。由於桶容器本身是不可變的，爲什麼會導致競爭條件？在某些情況下'TryGetValue'可能會使用舊版本，但總體來說，性能應該比'Volatile.Read'好。 – feO2x

我也不明白爲什麼你會在這種情況下得到競爭條件（鑑於C＃語言保證參考讀寫是原子的）。您可能會得到一個陳舊的值（例如，如果引用已在寄存器中更新但尚未複製回主內存），但在使用該字段的上下文中，這不是真正的競爭條件。 –

正如@CodesInChaos在問題的評論中提到的，我錯過了TryGetValue中的易失性讀取。該方法現在看起來是這樣的：

public bool TryGetValue(TypeKey typeKey, out TValue value) 
{ 
    var bucketContainer = Volatile.Read(ref _bucketContainer); 
    return bucketContainer.TryFind(typeKey, out value); 
}

這揮發性讀是必要的，因爲不同的線程訪問該字典可以緩存數據，並從對方，這可能會導致數據爭獨立指令重新排序。另外，運行代碼的CPU體系結構也很重要，例如，默認情況下，x86和x64處理器執行易失性讀取，而對於其他體系結構（如ARM或Itanium），這可能並非如此。這就是爲什麼讀訪問必須與使用內存屏障的其他線程同步的原因，該內存屏障在Volatile.Read內部執行（請注意，lock語句也在內部使用內存屏障）。Joseph Albahari在這裏寫了一篇綜合教程：http://www.albahari.com/threading/part4.aspx

來源

2016-10-16 05:24:33 feO2x

爲什麼我的線程安全字典實現產生數據競爭？

回答

相關問題