È possibile che un dizionario in .Net causi un blocco morto durante la lettura e la scrittura in parallelo?

Question

Stavo giocando con TPL, e ho cercato di scoprire quanto grande potessi fare leggendo e scrivendo sullo stesso dizionario in parallelo.

Così ho avuto questo codice:

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

E 'stato abbastanza incasinato in effetti, ci sono stati un sacco di eccezioni sollevate, per lo più di chiave non esiste, un paio su indice fuori limite di array.

Ma dopo aver eseguito l'applicazione per un po ', si blocca, e la percentuale di CPU rimane al 25%, la macchina ha 8 core. Quindi presumo che siano 2 thread in esecuzione a piena capacità.

Poi corsi dotTrace su di esso, e ha ottenuto questo:

Si abbina la mia ipotesi, due thread in esecuzione al 100%.

Entrambi eseguono il metodo FindEntry del dizionario.

Poi ho eseguito l'applicazione di nuovo, con dotTrace, questa volta il risultato è leggermente diverso:

Questa volta, un thread è in esecuzione FindEntry, l'altro Inserisci.

La mia prima intuizione era che è morto bloccato, ma poi ho pensato che non poteva essere, c'è solo una risorsa condivisa, e non è bloccata.

Quindi, come dovrebbe essere spiegato?

ps: Non sto cercando di risolvere il problema, potrebbe essere risolto utilizzando un ConcurrentDictionary o facendo un'aggregazione parallela. Sto solo cercando una spiegazione ragionevole per questo.

Answer 1

Sembra una condizione di competizione (non una situazione di stallo) - che, come si commenta, causa lo stato interno incasinato.

Il dizionario non è thread-safe, quindi le letture e le scritture simultanee nello stesso contenitore da thread separati (anche se ce ne sono poche come una) non sono sicure.

Una volta colpita la condizione della gara, diventa indefinito ciò che accadrà; in questo caso ciò che sembra essere un ciclo infinito di qualche tipo.

In generale, una volta richiesto l'accesso in scrittura, è necessaria una forma di sincronizzazione.

Answer 2

Quindi il codice è in esecuzione Dictionary.FindEntry. È non un deadlock: un deadlock si verifica quando due thread bloccano in un modo che li fa attendere l'un l'altro per rilasciare una risorsa, ma nel tuo caso stai ricevendo due loop apparentemente infiniti. I thread non sono bloccati.

Diamo uno sguardo a questo metodo nel reference source:

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

Date un'occhiata al ciclo for. L'incremento parte è i = entries[i].next e indovina cosa: entries è un campo che viene aggiornato nel Resize method. next è un campo di quella interna Entry struct:

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

Se il codice non può uscire dal metodo di FindEntry, la causa più probabile sarebbe che sei riuscito a rovinare le voci in modo tale da produrre un infinito sequenza quando si seguono gli indici puntati dal campo next.

Per quanto riguarda il Insert method, ha una molto simile for ciclo:

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

---

Come la classe Dictionary è documentata per essere non threadsafe, sei nel regno del comportamento non definito in ogni caso.

Utilizzando una o un motivo di bloccaggio ConcurrentDictionary come un ReaderWriterLockSlim (Dictionary è thread-safe per letture simultanee) o un semplice vecchio lock ben risolve il problema.