スレッドセーフな辞書実装でデータ競合が発生するのはなぜですか？

Question

現在、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 
} 

が、私はreference assignment in .NET runtimes is an atomic operation by designのでTryGetValueにロックを使用しないでください。フィールド_bucketContainerの参照をローカル変数にコピーすることにより、インスタンスに安全にアクセスすることができると確信しています。 GetOrAddで私は秘密の_bucketContainerにアクセスするためにロックを使用するので、値が2回作成されないようにすることができます（つまり、2つ以上のスレッドが値を追加しようとしている場合、ロックの）。

[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(); 
} 

：私はテストの同時実行のための Microsoft Chessを使用して、私は、古いものと新しいバケットコンテナを交換したときに私のテストの一つに、MCUT（マイクロソフト同時実行ユニットテスト）が GetOrAddでのデータ競合を報告し

23>試験結果：データ競合 23> ReadWhileAdd（）（コンテキスト=、をTestType = MChess）：GetOrAddで【データ競合]実測データレース：FastR

MCUTは、次のメッセージを報告しますeadThreadSafeDictionary.cs（68）

はGetOrAddです。

私の実際の質問は：_bucketContainer = newBucketContainerは競合状態ですか？現在実行中のスレッドTryGetValueは、常に_bucketContainerフィールドのコピーを作成するので、コピーが行われた直後に検索された値が_bucketContainerに追加される可能性がある点を除いては、更新で悩まされるべきではありません。データ競争）。 GetOrAddには、同時アクセスを防ぐための明示的なロックがあります。これはチェスのバグでしょうか、何か非常に明白なものがありませんか？

Answer 1

質問のコメントで@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ステートメントでもメモリバリアが内部的に使用されます）。ジョゼフ・アルバハリは、ここで、この上で包括的なチュートリアルを書きました：http://www.albahari.com/threading/part4.aspx