13

最近、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

このコードが失敗することを示す簡単なプログラムはありますか?

これを単体テストに組み込むことは理にかなっていますか? もしそうなら、どのように？

4

5 に答える 5

20

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

ダブルチェック ロック パターンの目的は、ロックのコストを削減してコードのパフォーマンスを向上させることです。ロックが争われていない場合、それはすでに信じられないほど安価です. したがって、二重チェックのロック パターンが正当化されるのは、(1) ロックの競合が激しくなる場合、または (2) コードのパフォーマンスが非常に重要であり、競合しないロックのコストが依然として高すぎる場合のみです。高い。

明らかに、2 番目のケースではありません。あなたは天国のために辞書を使っています。ロックがなくても、競合のないロックを回避することによる節約よりも、数百倍または数千倍のコストがかかるルックアップと比較を行うことになります。

最初のケースの場合は、競合の原因を突き止め、それを排除します。ロックで多くの待機を行っている場合は、その理由を突き止め、ロックをスリムなリーダー/ライター ロックに置き換えるか、アプリケーションを再構築して、同じロックを同時に多くのスレッドが使用しないようにします。時間。

どちらの場合でも、実装に依存する危険なローロック手法を実行する正当な理由はありません。競合していないロックのコストを本当に、本当に負担できない、非常にまれなケースでのみ、ローロック手法を使用する必要があります。

于 2010-04-12T20:37:50.873 に答える
13

この例では、私のマシンで例外 #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";
}

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

ただし、これを単体テストするかどうかはわかりません。並行コードのテスト (およびそれを正しく行うこと) は、最初に並行コードを作成するよりもはるかに複雑だからです。

于 2010-04-12T18:33:22.747 に答える
8

これを証明する必要はないと思います。次のドキュメントDictionary<TKey, TValue>を参照してください。

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

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

この問題は、二重チェックのロックに特に関連するものではありません。単一ライター/単一リーダーのシナリオであっても、辞書がスレッドセーフなクラスではないというだけです。

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

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。

  1. スレッド A: 要素を追加し、動的にサイズ変更します。
  2. スレッド B: バケット オフセットを (ハッシュ コード % バケット数) として計算します。
  3. スレッド A: バケットを別の (プライム) サイズに変更します。
  4. スレッド B:古いバケット インデックスで新しいバケット配列から要素インデックスを選択します。
  5. スレッド B のポインターは無効になります。

そして、これはまさに dtb の例で失敗したものです。スレッド A は、辞書にあることが事前にわかっているキーを検索しますが、見つかりません。なんで？メソッドは正しいバケットと思われるものを選択したため、FindValue内部を確認する前に、スレッド B がバケットを変更し、スレッド A が完全にランダムなバケットを検索しています。エントリ。

話の教訓:TryGetValueはアトミック操作でDictionary<TKey, TValue>はなく、スレッドセーフなクラスでもありません。心配する必要があるのは同時書き込みだけではありません。同時読み書きもできません。

実際には、ジッターや CPU による命令の並べ替え、古いキャッシュなどにより、問題は実際にはこれよりもはるかに深く実行されます。ここで使用されているメモリの障壁はまったくありません。Add呼び出しと同時に実行されている呼び出しがある場合の条件TryGetValue。

于 2010-04-12T18:51:11.070 に答える
3

この質問が何度も出てくると思う理由：

Pre-2.0、Before Generics（BG）Hashtableは、.NETの主要な連想コンテナであり、実際にいくつかのスレッド保証を提供します。MSDNから：
「ハッシュテーブルは、複数のリーダースレッドと単一の書き込みスレッドで使用するためのスレッドセーフです。スレッドの1つだけが書き込み（更新）操作を実行する場合、マルチスレッドでの使用に対してスレッドセーフです。これにより、ロックフリーの読み取りが可能になります。ライターがハッシュテーブルにシリアル化されていること。」

誰かが非常に興奮する前に、いくつかの制限があります。
たとえば、を所有しているBradAbramsからのこの投稿をHashtable参照してください。
に関するいくつかのより歴史的な背景Hashtableがここにあります（...終わり近く：「この長い転換の後-ハッシュテーブルはどうですか？」）。

Dictionary<TKey, TValue>上記の場合に失敗する理由：

それが失敗したことを証明するには、1つの例を見つけるだけで十分なので、それだけを試してみます。
テーブルが大きくなると、サイズ変更が行われます。
サイズ変更時に再ハッシュが発生し、これが最後の2行として表示されます。

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

配列は、配列bucketsへのインデックスを保持しますentries。これまでに10個のエントリがあり、現在、新しいエントリを追加しているとします。
簡単にするために、衝突を起こさなかった、または起こさないというふりをしてみましょう。
以前はbuckets、衝突がなかった場合、0から9までのインデックスが実行されていました。
これで、新しいbuckets配列のインデックスは0から10（！）まで実行されます。ここで、新しいバケットを指すように
プライベートフィールドを変更します。この時点で リーダーが実行している場合、新しいバケットを使用してインデックスを取得しますが、フィールドはまだ古いエントリを指しているため、新しいインデックスを使用して古いエントリ配列に読み込みます。buckets
TryGetValue()entries
誤った読み取り以外に取得できるものの1つは、フレンドリーIndexOutOfRangeExceptionです。
これを取得するもう1つの「優れた」方法は、@Aaronaughtの説明にあります。（...そして、たとえばdtbの例のように、両方が発生する可能性があります）。

これは実際にはほんの一例です。Dictonaryは設計されておらず、スレッドセーフであることを意図したものではありません。ただし、高速になるように設計されています。つまり、ロックが長時間保持されることはありません。

于 2010-04-12T19:48:12.420 に答える
1

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

//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。そうしないと、失敗する可能性が非常に低くなります。

于 2010-04-12T18:42:27.850 に答える