Come dimostrare che il modello di blocco a doppio controllo con TrygetValue di Dizionario non è threadSafe

Question

Di recente ho visto alcuni progetti C# che usano un modello a doppio controllo su un Dictionary. Qualcosa come questo:

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

Questo codice non è corretto, poiché il Dictionary può "crescere" la collezione in _cache.Add() mentre _cache.TryGetValue (fuori dalla serratura) sta iterando la collezione. Potrebbe essere estremamente improbabile in molte situazioni, ma è ancora sbagliato.

Esiste un semplice programma per dimostrare che questo codice fallisce?

Ha senso incorporarlo in un test unitario? E se è così, come?

Answer 1

In questo esempio, l'eccezione n. 1 viene lanciata quasi istantaneamente sulla mia macchina:

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

Tuttavia, il comportamento esatto del codice che non è progettato per essere thread-safe è imprevedibile.
Voi non può fare affidamento su di esso. Quindi il codice a doppio controllo è effettivamente rotto.

Non sono sicuro se unità testerò questo, tuttavia, in quanto test di codice concorrente (e farlo bene) è molto più complicato che scrivere il codice concorrente in primo luogo.

Answer 2

Chiaramente il codice non è threadSafe. Ciò che abbiamo qui è un chiaro caso dei pericoli dell'ottimizzazione prematura.

Ricorda, lo scopo del modello di bloccaggio a doppio controllo è migliorare le prestazioni di codice eliminando il costo del blocco. Se la serratura non è contestata, è già incredibilmente economico. Pertanto, il modello di bloccaggio a doppio controllo è giustificato solo nei casi (1) in cui il blocco sarà fortemente contestato o (2) in cui il codice è così incredibilmente Sensibile alle prestazioni che il costo di una serratura non consapevole è ancora troppo alto.

Chiaramente non siamo nel secondo caso. Stai usando un dizionario per l'amor del cielo. Anche senza la serratura faranno ricerche e confronti che saranno centinaia o migliaia di volte più costose dei risparmi di evitare una serratura incontestata.

Se siamo nel primo caso allora capire cosa sta causando la contesa ed eliminalo. Se stai aspettando molto su un blocco, scopri perché è e sostituisci il bloccaggio con un magro lettore-scrittore o ristruttura l'applicazione in modo che non tanti fili sbattono sullo stesso blocco allo stesso modo volta.

In entrambi i casi non vi è alcuna giustificazione per fare tecniche a basso blocco pericolose e sensibili all'implementazione. Dovresti usare solo tecniche a basso blocco in quei casi incredibilmente rari in cui non puoi davvero prendere il costo di una serratura non contestata.

Answer 3

Non penso davvero che tu bisogno Per dimostrare questo, devi solo fare riferimento alle persone al documentazione per Dictionary<TKey, TValue>:

Un dizionario può supportare più lettori contemporaneamente, Finché la raccolta non è modificata. Anche così, elencare attraverso una collezione è intrinsecamente non una procedura di thread-safe. Nel raro caso in cui un'enumerazione si impegna con gli accessi alla scrittura, la raccolta deve essere bloccata durante l'intera enumerazione. Per consentire l'accesso alla raccolta da più thread per la lettura e la scrittura, è necessario implementare la tua sincronizzazione.

In realtà è un fatto ben noto (o dovrebbe essere) che non puoi leggere da un dizionario mentre un altro thread ci sta scrivendo. Ho visto alcuni tipi di domande "bizzarra eretta multi-thread", quindi si è scoperto che l'autore non si rendeva conto che questo non era sicuro.

Il problema non è specificamente correlato al bloccaggio a doppio controllo, è solo che il dizionario non è una classe di thread-safe, nemmeno per uno scenario a reattore singolo/reader singolo.

---

Farò un ulteriore passo avanti e ti mostrerò perché, nel riflettore, questo non è thread-safe:

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

Guarda cosa può succedere se il Resize Il metodo sembra essere in esecuzione mentre anche un lettore chiama FindEntry:

1. Discussione A: aggiunge un elemento, con conseguente ridimensionamento dinamico;
2. Discussione B: calcola l'offset del bucket come (codice hash % bocket count);
3. Discussione A: cambia i secchi per avere una dimensione (primaria) diversa;
4. Discussione B: sceglie un indice di elemento da nuovo Array di secchio al vecchio indice del secchio;
5. Il puntatore del thread B non è più valido.

E questo è esattamente ciò che fallisce nell'esempio di DTB. Inserire una ricerca per una chiave che è noto in anticipo Essere nel dizionario, eppure non viene trovato. Come mai? Perché il FindValue Il metodo scelse quello che pensava fosse il secchio corretto, ma prima ancora che avesse la possibilità di guardare dentro, il filo B cambiava i secchi e ora il filo A sta guardando in un secchio totalmente casuale che non contiene o addirittura porta alla giusta voce.

Morale della storia: TryGetValue non è un'operazione atomica e Dictionary<TKey, TValue> non è una classe thread-safe. Non è solo una scrittura simultanea di cui devi preoccuparti; Non puoi nemmeno avere scritture di lettura simultanea.

In realtà il problema è in realtà molto più profondo di questo, a causa del riordino delle istruzioni da parte del jitter e della CPU, delle cache stantii, ecc. - Non ci sono barriere di memoria qui utilizzate qui - ma questo dovrebbe dimostrare al di là del dubbio che c'è una condizione di gara ovvia se hai un Add invocazione in esecuzione contemporaneamente a TryGetValue invocazione.

Answer 4

Il motivo per cui immagino che questa domanda venga più e più volte:

Pre-2.0, prima dei generici (BG), Hashtable era il contenitore associativo primario in .NET, che fornisce effettivamente alcune garanzie di threading. Da Msdn:
"Hashtable è thread sicuro per l'uso da più thread di lettore e un singolo thread di scrittura. È sicuro per l'uso multi-thread quando solo una delle thread eseguono operazioni di scrittura (aggiornamento), il che consente letture senza blocchi a condizione che gli scrittori sono serializzati per l'hashtable. "

Prima che qualcuno arrivi estremamente Eccitato, ci sono alcune limitazioni.
Vedi ad es Questo post da Brad Abrams, chi possiede Hashtable.
Qualche altro background storico su Hashtable possono essere trovati Qui (... vicino alla fine: "Dopo questa lunga diversione - che dire di Hashtable?").

Perché Dictionary<TKey, TValue> fallisce nel caso sopra:

Per dimostrare che fallisce, è sufficiente trovare un esempio, quindi proverò proprio questo.
Un ridimensionamento avviene man mano che il tavolo cresce.
In ridimensionamento, si verifica un rehash e uno lo vede come le ultime due righe:

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

Il buckets L'array contiene indici nel file entries Vettore. Diciamo che finora abbiamo 10 voci e in questo momento stiamo aggiungendo un nuovo.
Facciamo inoltre finta per il bene della semplicità che non abbiamo e non otterremo collisioni.
Nel vecchio buckets, avevamo indici da 0 a 9 - se non avessimo collisioni.
Ora gli indici nel nuovo buckets Array Run da 0 a 10 (!).
Ora cambiamo il privato buckets campo per indicare i nuovi secchi.
Se c'è un lettore che fa TryGetValue() In questo momento, usa il nuovo secchi per ottenere l'indice, ma quindi usa il nuovo indice da leggere nel vecchio Array di voci, dal momento che entries Il campo indica ancora le vecchie voci.
Una delle cose che si possono ottenere - oltre alle false letture - è amichevole IndexOutOfRangeException.
Un altro modo "fantastico" per farlo è @Aaronaugh's spiegazione. (... ed entrambi possono accadere, ad esempio come in dtb's esempio).

Questo è davvero solo un esempio, Dictonary non è stato progettato e non è mai stato pensato per essere sicuro. È stato progettato per essere veloce, tuttavia, ciò significa che il blocco non si terrà a lungo.

Answer 5

Compreso il codice nella domanda, è possibile testarlo con il seguente codice.

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

}

Questo programma cerca solo di ottenere Create per attraversare la collezione mentre viene "coltivata". Dovrebbe essere eseguito su una macchina con almeno due core (o due processori) e molto probabilmente fallirà dopo un po 'con questa eccezione.

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

L'aggiunta di questo test è difficile poiché si tratta di un test probabilistico e non sai quanto tempo ci vorrà per fallire (se mai). Immagino che potresti scegliere un valore come 10 secondi e lasciarlo funzionare per così tanto tempo. Se non fallisce in quel periodo di tempo, il test passa. Non è il migliore, ma qualcosa. Dovresti anche verificarlo Environment.ProcessorCount > 1 Prima di eseguire il test, altrimenti la probabilità che fallisca è minuscola.