Como mostrar que o padrão de bloqueio verificado duas

Question

Recentemente, vi alguns projetos C# que usam um padrão de bloqueio verificado em um Dictionary. Algo assim:

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

Este código está incorreto, já que o Dictionary pode estar "crescendo" a coleção em _cache.Add() enquanto _cache.TryGetValue (Fora da fechadura) está iterando sobre a coleção. Pode ser extremamente improvável em muitas situações, mas ainda está errado.

Existe um programa simples para demonstrar que esse código falha?

Faz sentido incorporar isso em um teste de unidade? E se sim, como?

Answer 1

Neste exemplo, a exceção nº 1 é jogada quase instantaneamente na minha máquina:

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

No entanto, o comportamento exato do código que não foi projetado para ser seguro para fios é imprevisível.
Você não pode confiar nisso. Portanto, o código de verificação dupla está realmente quebrado.

No entanto, não tenho certeza se, se eu teria uma unidade, como teste de código simultâneo (e acertar) é muito mais complicado do que escrever o código simultâneo em primeiro lugar.

Answer 2

Claramente, o código não é ThreadSafe. O que temos aqui é um caso claro dos riscos de otimização prematura.

Lembre-se, o objetivo do padrão de bloqueio verificado duas vezes é melhorar o desempenho de código eliminando o custo da fechadura. Se a fechadura não for contestada, já é incrivelmente barato. Portanto, o padrão de bloqueio verificado duas vezes é justificado apenas nos casos (1) em que a trava será fortemente contestada, ou (2) onde o código é assim incrivelmente sensível ao desempenho de que o custo de uma trava inconsciente ainda seja muito alta.

Claramente, não estamos no segundo caso. Você está usando um dicionário pelo amor de Deus. Mesmo sem a fechadura, ele fará pesquisas e comparações que serão centenas ou milhares de vezes mais caras do que a economia de evitar uma fechadura incontestada.

Se estamos no primeiro caso, então descobrir o que está causando a contenção e elimine isso. Se você está esperando muito em uma fechadura, descubra por que isso é e substitua o bloqueio por um bloqueio de leitor fino ou reestruture o aplicativo, para que tantos threads não estejam batendo na mesma fechadura na mesma Tempo.

Em ambos os casos, não há justificativa para fazer técnicas perigosas e sensíveis à implementação. Você só deve usar técnicas de baixa trava nos casos incrivelmente raros em que realmente não pode obter o custo de uma fechadura incontestada.

Answer 3

Eu realmente não acho que você precisar Para provar isso, você só precisa encaminhar pessoas para o documentação para Dictionary<TKey, TValue>:

Um dicionário pode suportar vários leitores simultaneamente, desde que a coleção não seja modificada. Mesmo assim, enumerar através de uma coleção é intrinsecamente Não é um procedimento seguro para threads. No caso raro em que uma enumeração afirma com acessos por gravação, a coleção deve ser bloqueada durante toda a enumeração. Para permitir que a coleção seja acessada por vários threads para leitura e escrita, você deve implementar sua própria sincronização.

Na verdade, é um fato bem conhecido (ou deveria ser) que você não pode ler de um dicionário enquanto outro tópico está escrevendo para ele. Eu já vi alguns tipos de perguntas "bizarras de multi-threading" aqui, então onde o autor não percebeu que isso não era seguro.

O problema não está especificamente relacionado ao bloqueio verificado duas vezes, é apenas que o dicionário não é uma classe segura por threads, nem mesmo para um cenário de um único escritor/leitura única.

---

Vou dar um passo adiante e mostrar por que, no refletor, isso não é seguro para fios:

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

Veja o que pode acontecer se o Resize o método passa a ser executado enquanto mesmo um leitor chama FindEntry:

1. Tópico A: adiciona um elemento, resultando em uma redimensionamento dinâmico;
2. Thread B: calcula o deslocamento do balde como (código de hash % contagem de caçambas);
3. Tópico A: Altera os baldes para ter um tamanho (primário) diferente;
4. Tópico B: escolhe um índice de elemento do novo matriz de balde no velho Índice de balde;
5. O ponteiro do Thread B não é mais válido.

E é exatamente isso que falha no exemplo do DTB. Pesquise uma pesquisa por uma chave que é conhecido com antecedência estar no dicionário e, no entanto, não é encontrado. Por quê? Porque o FindValue O método escolheu o que pensava ser o balde correto, mas antes mesmo de ter a chance de olhar para dentro, o Thread B mudou os baldes e agora o Thread A está olhando em algum balde totalmente aleatório que não contém ou mesmo leva à entrada certa.

Moral da história: TryGetValue não é uma operação atômica e Dictionary<TKey, TValue> não é uma classe segura para threads. Não são apenas as gravações simultâneas com as quais você precisa se preocupar; Você também não pode ter write-writos simultâneos.

Na realidade, o problema realmente é muito mais profundo do que isso, devido à reordenação de instruções da instabilidade e da CPU, caches obsoletos etc. - não há barreiras de memória que sejam usadas aqui - mas isso deve provar além de uma dúvida que há uma condição de corrida óbvia se você tiver um Add invocação em execução ao mesmo tempo que um TryGetValue invocação.

Answer 4

A razão pela qual acho que essa pergunta surge repetidamente:

Pré-2.0, antes dos genéricos (BG), Hashtable foi o principal contêiner associativo no .NET, que realmente fornece algumas garantias de rosqueamento. A partir de Msdn:
"A hashtable é segura para uso por vários threads de leitores e um único tópico de escrita. É seguro para o uso de vários thread quando apenas um dos threads executa operações de gravação (atualização), o que permite leituras sem bloqueio, desde que os escritores são serializados para a hashtable. "

Antes que alguém fique extremamente Animado, existem algumas limitações.
Veja por exemplo Este post de Brad Abrams, quem possui Hashtable.
Alguns antecedentes históricos em Hashtable pode ser encontrado Aqui (... perto do final: "Após essa longa desvio - e a hashtable?").

Por que Dictionary<TKey, TValue> falha no caso acima:

Para provar que falha, basta encontrar um exemplo, então tentarei exatamente isso.
Um redimensionamento acontece à medida que a tabela cresce.
Em redimensionamento, uma rehash acontece e vê isso como as duas últimas linhas:

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

o buckets Array mantém índices no entries variedade. Digamos que temos 10 entradas até agora e agora estamos adicionando um novo.
Vamos fingir ainda mais por uma questão de simplicidade que não tenhamos e não obteremos colisões.
No velho buckets, tivemos índices em 0 a 9 - se não tivéssemos colisões.
Agora os índices no novo buckets Array corre de 0 a 10 (!).
Agora mudamos o privado buckets Campo a apontar para os novos baldes.
Se houver um leitor fazendo TryGetValue() Neste momento, ele usa o novo baldes para obter o índice, mas depois usa o novo índice para ler no velho Array de entradas, já que o entries O campo ainda aponta para as entradas antigas.
Uma das coisas que se pode obter - além de falsas leituras - é um amigável IndexOutOfRangeException.
Outra "ótima" maneira de conseguir isso está em @AaronAught's explicação. (... e ambos podem acontecer, por exemplo, como em DTB's exemplo).

Este é realmente apenas um exemplo, o DicTonary não foi projetado e nunca pretendia ser seguro para fios. Foi projetado para ser rápido, no entanto - isso significa que a fechadura não será mantida por muito tempo.

Answer 5

Incluindo o código na pergunta, você pode testá -lo com o código a seguir.

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

}

Este programa apenas tenta obter Create Para atravessar a coleção, pois está sendo "crescido". Ele deve ser executado em uma máquina com pelo menos dois núcleos (ou dois processadores) e provavelmente falhará depois de um tempo com essa exceção.

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

Adicionar esse teste é difícil, pois é um teste probabilístico e você não sabe quanto tempo levará para falhar (se é que alguma vez). Eu acho que você poderia escolher um valor como 10 segundos e deixá -lo correr por tanto tempo. Se não falhar nessa quantidade de tempo, o teste passa. Não é o melhor, mas algo. Você também deve verificar isso Environment.ProcessorCount > 1 Antes de executar o teste, caso contrário, a probabilidade de falhar é minúscula.