辞書のTryGetValueを使用したダブルチェックロックパターンがスレッドセーフではないことを示す方法

https://stackoverflow.com/questions/2624301

26-09-2019
|

質問

最近、ダブルチェックロックパターンを使用するいくつかのC＃プロジェクトを見てきました Dictionary. 。このようなもの：

private static readonly object _lock = new object();
private static volatile IDictionary<string, object> _cache = 
    new Dictionary<string, object>();

public static object Create(string key)
{
    object val;
    if (!_cache.TryGetValue(key, out val))
    {
        lock (_lock)
        {
            if (!_cache.TryGetValue(key, out val))
            {
                val = new object(); // factory construction based on key here.
                _cache.Add(key, val);
            }
        }
    }
    return val;
}

このコードは間違っています Dictionary コレクションを「成長させる」ことができます _cache.Add() その間 _cache.TryGetValue （ロックの外側）は、コレクションを繰り返しています。多くの状況では非常にありそうもないかもしれませんが、まだ間違っています。

このコードが失敗したことを実証する簡単なプログラムはありますか？

これをユニットテストに組み込むことは理にかなっていますか？もしそうなら、どうですか？

解決

この例では、例外＃1が私のマシンにほぼ即座にスローされます。

var dict = new Dictionary<int, string>() { { 1234, "OK" } };

new Thread(() =>
{
    for (; ; )
    {
        string s;
        if (!dict.TryGetValue(1234, out s))
        {
            throw new Exception();  // #1
        }
        else if (s != "OK")
        {
            throw new Exception();  // #2
        }
    }
}).Start();

Thread.Sleep(1000);
Random r = new Random();
for (; ; )
{
    int k;
    do { k = r.Next(); } while (k == 1234);
    Debug.Assert(k != 1234);
    dict[k] = "FAIL";
}

ただし、スレッドセーフになるように設計されていないコードの正確な動作は 予測不可能な.
君は それに頼ることはできません. 。したがって、ダブルチェックコードは確かに壊れています。

ただし、同時コードをテストする（正しく取得する）テストは、そもそも同時コードを書くよりもはるかに複雑であるため、これを単位テストするかどうかはわかりません。

他のヒント

明らかに、コードはスレッドセーフではありません。ここにあるのは、早期最適化の危険性の明確なケースです。

ダブルチェックされたロックパターンの目的は、 パフォーマンスを改善します ロックのコストを削除することによるコードの。ロックが争われていない場合、それはすでに信じられないほど安いです。したがって、ダブルチェックされたロックパターンは、（1）ロックが激しく争われる場合、または（2）コードがそうである場合にのみ正当化されます。 信じられないほど パフォーマンスに敏感ではないことは、違憲なロックのコストが高すぎることです。

明らかに、私たちは2番目のケースではありません。あなたは天国のために辞書を使用しています。ロックがなくても、争われていないロックを避けることを節約するよりも数百倍または数千倍高価になるルックアップと比較を行うことになります。

最初のケースにいる場合 何が競合を引き起こしているのかを把握し、それを排除する. 。ロックで待っている場合は、それがなぜあるのかを把握し、ロックをスリムな読者用ライターロックに置き換えるか、アプリケーションを再構築して、同じロックを同じロックで叩かないようにアプリケーションを再構築します。時間。

どちらの場合でも、危険な実装に敏感なローロック技術を行う正当性はありません。あなたが本当に、争われていないロックのコストを取ることができない非常にまれなケースでは、ローロックテクニックを使用する必要があります。

私はあなたが本当にそう思わない必要これを証明するには、人々を紹介するだけですのドキュメント Dictionary<TKey, TValue>:

辞書は複数の読者を同時にサポートできます。 コレクションが変更されていない限り。 それでも、コレクションを通して列挙することは本質的にです スレッドセーフ手順ではありません。 列挙が書き込みアクセスと競合するまれなケースでは、列挙全体の間にコレクションをロックする必要があります。 読み書きのために複数のスレッドでコレクションにアクセスできるようにするには、独自の同期を実装する必要があります。

実際には、別のスレッドが書いている間に辞書から読み取ることができないことは、よく知られている事実です（またはそうであるべきです）。ここでいくつかの「奇妙なマルチスレッドの問題」種類の質問を見てきたので、著者がこれが安全ではないことに気付いていないことが判明しました。

問題は、ダブルチェックロックに特に関連するものではありません。辞書がスレッドセーフクラスではなく、単一ライター/シングルリーダーのシナリオでもありません。

さらに一歩進んで、リフレクターで、これがスレッドセーフではない理由を示します。

private int FindEntry(TKey key)
{
    // Snip a bunch of code
    for (int i = this.buckets[num % this.buckets.Length]; i >= 0;
        i = this.entries[i].next)
    // Snip a bunch more code
}

private void Resize()
{
    int prime = HashHelpers.GetPrime(this.count * 2);
    int[] numArray = new int[prime];
    // Snip a whole lot of code
    this.buckets = numArray;
}

どのように起こるかを見てください Resize 1つの読者が電話をかけている間、方法はたまたま実行されています FindEntry:

スレッドA：要素を追加して、動的なサイズ変更をもたらします。
スレッドB：バケットオフセットを計算します（ハッシュコード％バケットカウント）。
スレッドA：バケツを変更して、異なる（プライム）サイズを持っています。
スレッドB：からの要素インデックスを選択します新着でのバケットアレイ年バケットインデックス;
スレッドBのポインターはもはや有効ではありません。

そして、これはまさにDTBの例で失敗するものです。スレッドAはキーを検索します 事前に知られています 辞書にいること、それでも見つかりません。なんで？なぜなら FindValue メソッドは正しいバケツだと思ったものを選びましたが、内部を見る機会さえある前に、スレッドBがバケツを変更し、スレッドAは、正しいエントリに含まれていないか、さらには正しいエントリにつながっていない完全にランダムなバケツを探しています。

この話の教訓： TryGetValue 原子操作ではありません Dictionary<TKey, TValue> スレッドセーフクラスではありません。それはあなたが心配する必要がある単なる同時の書き込みではありません。同時に読み書きを持つこともできません。

実際には、問題はジッターやCPUによる指示の並べ替え、古いキャッシュなどのために、実際にこれよりもはるかに深く動作します。 疑いの余地がありません あなたが持っている場合、明らかな人種状態があること Add aと同時に実行される呼び出し TryGetValue 呼び出し。

The reason I guess this question comes up again and again:

Pre-2.0, Before Generics (B.G.), Hashtable was the primary associative container in .NET, which indeed provides some threading guarantees. From MSDN:
"Hashtable is thread safe for use by multiple reader threads and a single writing thread. It is thread safe for multi-thread use when only one of the threads perform write (update) operations, which allows for lock-free reads provided that the writers are serialized to the Hashtable."

Before anyone gets extremely excited, there are some limitations.
See e.g. this post from Brad Abrams, who owns Hashtable.
Some more historical background on Hashtable can be found here (...near the end: "After this lengthy diversion - What about Hashtable?").

Why Dictionary<TKey, TValue> fails in the above case:

To prove that it fails, it is enough to find one example, so I'll try just that.
A resize happens as the table grows.
On resize, a rehash happens and one sees this as the last two lines:

this.buckets = newBuckets;
//One of the problems here.
this.entries = newEntries;

The buckets array holds indexes into the entries array. Let's say we have 10 entries so far and right now we are adding a new.
Let's further pretend for the sake of simplicity that we did not and will not get collisions.
In the old buckets, we had indexes running from 0 to 9 - if we had no collisions.
Now the indexes in the new buckets array run from 0 to 10(!).
We now change the private buckets field to point to the new buckets.
If there is a reader doing TryGetValue() at this moment, it uses the new buckets to get the index, but then uses the new index to read into the old entries array, since the entries field still points to the old entries.
One of the things one can get - besides false reads - is a friendly IndexOutOfRangeException.
Another "great" way to get this is in @Aaronaught's explanation. (...and both can happen, e.g. as in dtb's example).

This is really just one example, Dictonary was not designed and never meant to be thread-safe. It was designed to be fast, however - that means that the lock will not be held for long.

質問にコードを含めて、次のコードでテストできます。

//using System.Collections.Generic;
//using System.Threading;

private static volatile int numRunning = 2;
private static volatile int spinLock = 0;

static void Main(string[] args)
{
    new Thread(TryWrite).Start();
    new Thread(TryWrite).Start();
}

static void TryWrite()
{
    while(true) 
    {
        for (int i = 0; i < 1000000; i++ )
        {
            Create(i.ToString());
        }

        Interlocked.Decrement(ref numRunning);
        while (numRunning > 0) { } // make sure every thread has passed the previous line before proceeding (call this barrier 1)

        while (Interlocked.CompareExchange(ref spinLock, 1, 0) != 0){Thread.Sleep(0);} // Aquire lock (spin lock)
        // only one thread can be here at a time...

        if (numRunning == 0) // only the first thread to get here executes this...
        {
            numRunning = 2; // resets barrier 1
            // since the other thread is beyond the barrier, but is waiting on the spin lock,
            //  nobody is accessing the cache, so we can clear it...
            _cache = new Dictionary<string, object>(); // clear the cache... 
        }

        spinLock = 0; // release lock...
    }

}

このプログラムはただ取得しようとします Create コレクションが「成長している」ので、コレクションを横断する。少なくとも2つのコア（または2つのプロセッサ）を備えたマシンで実行する必要があり、この例外を除いてしばらくすると失敗する可能性が高いです。

System.Collections.Generic.Dictionary`2.FindEntry(TKey key)

このテストを追加することは、確率的テストであり、失敗するのにどれくらいの時間がかかるかわからないため、困難です。 10秒ほどの値を選択して、それを長く実行させることができると思います。その時間で失敗しない場合、テストは合格します。最高ではありませんが、何か。また、それを確認する必要があります Environment.ProcessorCount > 1 テストを実行する前に、それ以外の場合、失敗する可能性は非常に大きいです。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow