So zeigen Sie, dass das doppeltprüfte Lock-Muster mit dem TrygetValue von Dictionary kein Threadsafe ist

Question

Kürzlich habe ich einige C# -Projekte gesehen, bei denen ein doppelt-überprüfter Lock-Muster auf einem verwendet wird Dictionary. Etwas wie das:

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;
}

Dieser Code ist falsch, da der Dictionary kann die Sammlung in "wachsen" _cache.Add() während _cache.TryGetValue (außerhalb des Schlosses) iteriert über die Sammlung. Es mag in vielen Situationen äußerst unwahrscheinlich sein, ist aber immer noch falsch.

Gibt es ein einfaches Programm, um zu demonstrieren, dass dieser Code fehlschlägt?

Ist es sinnvoll, dies in einen Unit -Test aufzunehmen? Und wenn ja, wie?

Answer 1

In diesem Beispiel wird die Ausnahme Nr. 1 fast sofort auf meine Maschine geworfen:

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";
}

Das genaue Verhalten von Code, das nicht als Thread-Safe ausgelegt ist, ist jedoch unberechenbar.
Du kann sich nicht darauf verlassen. Der Doppelüberprüfungscode ist also tatsächlich unterbrochen.

Ich bin mir jedoch nicht sicher, ob ich dies testen würde, da das Testen des gleichzeitigen Codes (und das richtige Abstand) viel komplizierter ist, als den gleichzeitigen Code überhaupt zu schreiben.

Answer 2

Offensichtlich ist der Code kein Threadsafe. Was wir hier haben, ist ein klarer Fall der Gefahren der vorzeitigen Optimierung.

Denken Sie daran, der Zweck des doppeltprüften Verriegelungsmusters ist es Verbesserung der Leistung Code durch Beseitigung der Kosten des Schlosses. Wenn das Schloss unbestritten ist, ist es schon unglaublich billig. Daher ist das doppelte Überprüfungsmuster nur in den Fällen (1) gerechtfertigt unglaublich leistungsempfindlich, dass die Kosten für ein nicht begründetes Schloss immer noch zu hoch sind.

Offensichtlich sind wir nicht im zweiten Fall. Sie verwenden ein Wörterbuch um Himmels willen. Auch ohne das Schloss werden Nachschläge und Vergleiche durchgeführt, die Hunderte oder tausend Male teurer werden als die Einsparungen bei der Vermeidung eines unbestrittenen Schlosses.

Wenn wir im ersten Fall sind, dann dann Finden Sie heraus, was die Streitigkeiten verursacht, und beseitigen Sie das. Wenn Sie viel auf einem Schloss warten, stellen Sie heraus, warum das ist, und ersetzen Sie die Verriegelung durch ein schlankes Leser-Autor-Lock oder die Anwendung umstrukturieren Zeit.

In beiden Fällen gibt es keine Rechtfertigung dafür, gefährliche, implementierungsempfindliche niedrige Lock-Techniken zu tun. Sie sollten in diesen unglaublich seltenen Fällen, in denen Sie wirklich nicht die Kosten für ein unbestrittenes Schloss erfassen können, nur niedrige Techs-Techniken anwenden.

Answer 3

Ich glaube nicht wirklich, dass du brauchen Um dies zu beweisen, müssen Sie nur Leute an die verweisen Dokumentation für Dictionary<TKey, TValue>:

Ein Wörterbuch kann mehrere Leser gleichzeitig unterstützen, Solange die Sammlung nicht geändert wird. Trotzdem ist die Aufzählung durch eine Sammlung von Natur aus Kein fadensicheres Verfahren. In dem seltenen Fall, in dem eine Aufzählung mit Schreibzugriffs zugänglich ist, muss die Sammlung während der gesamten Aufzählung gesperrt werden. Damit die Sammlung über mehrere Threads zum Lesen und Schreiben zugegriffen werden kann, müssen Sie Ihre eigene Synchronisation implementieren.

Es ist tatsächlich eine bekannte Tatsache (oder sollte sein), die Sie nicht aus einem Wörterbuch lesen können, während ein anderer Thread darauf schreibt. Ich habe hier ein paar "bizarren Multi-Threading-Problemen" gesehen, in denen sich herausstellte, dass der Autor nicht bemerkte, dass dies nicht sicher war.

Das Problem ist nicht speziell mit der doppelten Überprüfung des Sperrens zusammen, es ist nur so, dass das Wörterbuch keine thread-safe Klasse ist, nicht einmal für ein einzelnes/ein-Reader-Szenario.

---

Ich werde noch einen Schritt weiter gehen und Ihnen zeigen, warum in Reflektor dies nicht mit Thread-Sicherheit ist:

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;
}

Schauen Sie sich an, was passieren kann, wenn das passieren kann Resize Die Methode wird ausgeführt, während sogar ein Leser ruft FindEntry:

1. Thread A: fügt ein Element hinzu, was zu einer dynamischen Größenänderung führt.
2. Thread B: Berechnet den Bucket -Offset AS (Hash Code % Bucket Count);
3. Thread A: ändert die Eimer, um eine andere (Prim-) Größe zu haben.
4. Thread B: Wählt einen Elementindex aus dem Neu Eimer -Array am alt Bucket Index;
5. Der Zeiger von Thread B ist nicht mehr gültig.

Und genau das scheitert das Beispiel von DTB. Thread A sucht nach einem Schlüssel, der ist im Voraus bekannt im Wörterbuch zu sein, und doch wird es nicht gefunden. Wieso den? Weil die FindValue Die Methode wählte das, was es für den richtigen Eimer hielt, aber bevor es überhaupt die Chance hatte, nach innen zu schauen, änderte Faden B die Eimer, und jetzt sucht Faden A in einen völlig zufälligen Eimer, der nicht den richtigen Eintrag enthält oder sogar zum richtigen Eintrag führt.

Moral der Geschichte: TryGetValue ist keine atomare Operation und Dictionary<TKey, TValue> ist keine thread-safe Klasse. Es ist nicht nur gleichzeitige Schreibvorgänge, über die Sie sich Sorgen machen müssen. Sie können auch keine gleichzeitigen Leseschreiber haben.

In Wirklichkeit läuft das Problem tatsächlich viel tiefer als dies, da Jitter und CPU, abgestandene Caches usw. erneut angeordnet sind - - hier werden überhaupt keine Speicherbarrieren verwendet - aber dies sollte beweisen, dass dies beweisen sollte zweifelsohne dass es eine offensichtliche Rennbedingung gibt, wenn Sie eine haben Add Aufruf, die zur gleichen Zeit wie a TryGetValue Aufruf.

Answer 4

Der Grund, warum ich denke, dass diese Frage immer wieder auftaucht:

Vor dem 2.0 vor Generika (BG), Hashtable war der primäre assoziative Container in .NET, das tatsächlich einige Gewindegarantien bietet. Aus Msdn:
"Hashtable ist Thread sicher für die Verwendung durch mehrere Leser-Threads und einen einzelnen Schreibphread. Es ist Thread sicher für Multi-Thread-Verwendung, wenn nur einer der Threads Schreibvorgänge (Update) ausgeführt hat, wodurch sperrfreie Lesevorgänge vorgesehen sind, vorausgesetzt, die Autoren werden zum Hashtable serialisiert. "

Bevor jemand bekommt äußerst Aufgeregt, es gibt einige Einschränkungen.
Siehe zB Dieser Beitrag von Brad Abrams, wem gehört Hashtable.
Noch ein historischer Hintergrund auf Hashtable kann gefunden werden Hier (... gegen Ende: "Nach dieser langen Ablenkung - was ist mit Hashtable?").

Warum Dictionary<TKey, TValue> scheitert im obigen Fall:

Um zu beweisen, dass es fehlschlägt, reicht es aus, ein Beispiel zu finden, also werde ich es nur versuchen.
Eine Änderung erfolgt, wenn der Tisch wächst.
In der Größenänderung erfolgt eine Wiederholung und man sieht dies als die letzten beiden Zeilen:

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

Das buckets Array hält Indizes in die entries Array. Nehmen wir an, wir haben bisher 10 Einträge und jetzt fügen wir eine neue hinzu.
Stellen wir uns weiter aus, dass wir nicht Kollisionen erhalten haben und nicht.
Im alten buckets, Wir hatten Indizes von 0 bis 9 - wenn wir keine Kollisionen hatten.
Jetzt die Indizes im neuen buckets Array laufen von 0 bis 10 (!).
Wir ändern jetzt die Privatperson buckets Feld auf die neuen Eimer zeigen.
Wenn es einen Leser macht TryGetValue() In diesem Moment verwendet es die Neu Eimer, um den Index zu erhalten, verwendet dann aber die Neu Index zum Lesen in die alt Einträge Array, seit der entries Feld zeigt immer noch auf die alten Einträge.
Eines der Dinge, die man bekommen kann - neben falschen Lesungen - ist freundlich IndexOutOfRangeException.
Ein weiterer "großartiger" Weg, dies zu bekommen, ist in @Aaronaught's Erläuterung. (... und beide können passieren, zB wie in DTBs Beispiel).

Dies ist wirklich nur ein Beispiel, Diktonary wurde nicht entworfen und nie als fadensicher sein. Es wurde jedoch so konzipiert, dass es schnell ist - das bedeutet, dass das Schloss nicht lange gehalten wird.

Answer 5

Einschließlich des Code in der Frage können Sie ihn mit dem folgenden Code testen.

//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...
    }

}

Dieses Programm versucht nur zu bekommen Create Um die Sammlung zu durchqueren, wird sie "gewachsen". Es sollte auf einer Maschine mit mindestens zwei Kernen (oder zwei Prozessoren) ausgeführt werden und wird mit dieser Ausnahme höchstwahrscheinlich nach einer Weile versagen.

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

Das Hinzufügen dieses Tests ist schwierig, da es sich um einen probabilistischen Test handelt, und Sie wissen nicht, wie lange es dauern wird, bis es scheitert (wenn überhaupt). Ich denke, Sie könnten einen Wert wie 10 Sekunden auswählen und ihn so lange laufen lassen. Wenn es in dieser Zeit nicht scheitert, besteht der Test. Nicht das Beste, aber etwas. Sie sollten das auch überprüfen Environment.ProcessorCount > 1 Vor dem Durchführen des Tests ist die Wahrscheinlichkeit, dass es fehlschlägt, winzig.