Ist es möglich, dass ein Wörterbuch in .Net eine Deadlock-Funktion auslöst, wenn es parallel gelesen und geschrieben wird?

Question

Ich spielte mit TPL und versuchte herauszufinden, wie groß das Durcheinander ist, wenn ich parallel zum selben Wörterbuch lese und schreibe.

So hatte ich diesen Code:

private static void HowCouldARegularDicionaryDeadLock() 
    { 
     for (var i = 0; i < 20000; i++) 
     { 
      TryToReproduceProblem(); 
     } 
    } 

    private static void TryToReproduceProblem() 
    { 
     try 
     { 
      var dictionary = new Dictionary<int, int>(); 
      Enumerable.Range(0, 1000000) 
       .ToList() 
       .AsParallel() 
       .ForAll(n => 
       { 
        if (!dictionary.ContainsKey(n)) 
        { 
         dictionary[n] = n; //write 
        } 
        var readValue = dictionary[n]; //read 
       }); 
     } 
     catch (AggregateException e) 
     { 
      e.Flatten() 
       .InnerExceptions.ToList() 
       .ForEach(i => Console.WriteLine(i.Message)); 
     } 
    } 

Es war ziemlich in der Tat vermasselt, viele Ausnahmen geworfen waren, vor allem über Schlüssel nicht existiert, um nur einige zu Index des Arrays aus gebunden ist.

Aber nach dem Ausführen der App für eine Weile hängt es, und der CPU-Prozentsatz bleibt bei 25%, die Maschine hat 8 Kerne. Also ich nehme an, dass 2 Threads bei voller Kapazität laufen.

Dann lief ich DotTrace darauf und bekam dies:

Es ist meine Vermutung passt, zwei Threads bei 100%.

Beide die FindEntry-Methode von Dictionary ausführen.

Dann lief ich die App wieder, mit DotTrace, diesmal das Ergebnis ist etwas anders:

Diesmal ein Thread FindEntry, das andere Insert läuft.

Meine erste Intuition war, dass es totgesperrt ist, aber dann dachte ich, es könnte nicht sein, es gibt nur eine gemeinsame Ressource, und es ist nicht gesperrt.

Also wie soll das erklärt werden?

ps: Ich suche nicht, um das Problem zu lösen, könnte es behoben werden, indem Sie ein ConcurrentDictionary verwenden, oder indem Sie parallele Aggregation durchführen. Ich suche nur eine vernünftige Erklärung dafür.

Answer 1

Sieht aus wie eine Race-Bedingung (nicht ein Deadlock) - was, wie Sie kommentieren, den vermischten internen Zustand verursacht.

Das Wörterbuch ist nicht Thread-sicher, so dass gleichzeitige Lese- und Schreibvorgänge in denselben Container aus separaten Threads (auch wenn es nur einen einzigen gibt) nicht sicher ist.

Sobald die Race-Bedingung getroffen wird, wird es undefiniert, was passieren wird; in diesem Fall scheint das eine Endlosschleife zu sein.

Wenn ein Schreibzugriff erforderlich ist, ist im Allgemeinen eine Form der Synchronisation erforderlich.

Answer 2

Ihr Code führt also Dictionary.FindEntry aus. Es ist nicht ein Deadlock - ein Deadlock passiert, wenn zwei Threads auf eine Weise blockieren, die sie aufeinander warten lassen, um eine Ressource freizugeben, aber in Ihrem Fall erhalten Sie zwei scheinbar endlose Schleifen. Die Threads sind nicht gesperrt.

Schauen wir uns diese Methode in der reference source einen Blick:

private int FindEntry(TKey key) { 
    if(key == null) { 
     ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); 
    } 

    if (buckets != null) { 
     int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF; 
     for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) { 
      if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i; 
     } 
    } 
    return -1; 
} 

am for Schleife Werfen Sie einen Blick. Die Inkrement Teil ist i = entries[i].next, und raten Sie mal: entries ist ein Feld, das in der Resize method aktualisiert wird. next ist ein Bereich der inneren Entry struct:

public int next;  // Index of next entry, -1 if last 

Wenn Ihr Code die FindEntry Methode nicht verlassen kann, ist die wahrscheinlichste Ursache wäre Sie verwirren die Einträge in einer solchen Art und Weise geschafft haben, dass sie eine unendliche produzieren Reihenfolge, wenn Sie die Indizes, die auf das Feld next zeigen, folgen.

Was die Insert method, hat es eine sehr ähnliche for Schleife:

for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next) 

---

Da die Dictionary Klasse dokumentiert ist nicht Thread zu sein, bist du im Bereich der undefinierten Verhalten sowieso.

eine ConcurrentDictionary oder ein Verriegelungsmuster verwendet, wie beispielsweise ein ReaderWriterLockSlim (Dictionary threadsicher ist für die gleichzeitige nur liest) lock oder eine einfache alte löst das Problem gut.