Как показать, что шаблон двойной проверки блокировки с TryGetValue словаря не является threadsafe

Недавно я видел несколько проектов C#, которые используют шаблон двойной блокировки на Dictionary. Что-то вроде этого: 

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

Этот код неверен, так как Dictionary может "выращивать" коллекцию в _cache.Add(), в то время как _cache.TryGetValue (вне блокировки) повторяет коллекцию. Это может быть крайне маловероятно во многих ситуациях, но все равно неправильно.

Есть ли простая программа, чтобы продемонстрировать, что этот код не работает?

Имеет ли смысл включить это в модульный тест? И если да, то как?
5 13
c# .net multithreading double-checked-locking

5 ответов:

В этом примере исключение #1 выбрасывается почти мгновенно на моей машине: 

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";
}
Однако точное поведение кода, который не предназначен для потокобезопасности, являетсянепредсказуемым .
Вы не можете полагаться на него. Таким образом, код двойной проверки действительно нарушен.

Я не уверен, что я бы это проверил, хотя, поскольку тестирование параллельного кода (и получение его правильно) намного сложнее, чем написание параллельного кода в первую очередь.

13

Очевидно, что код не является threadsafe. То, что мы имеем здесь, является наглядным примером опасности преждевременной оптимизации.

Помните, что цель дважды проверенного шаблона блокировки состоит в том, чтобыулучшить производительность кода, устранив стоимость блокировки. Если замок не оспаривается, он уже невероятно дешев. Таким образом, дважды проверенный шаблон блокировки оправдан только в случаях (1), когда замок будет сильно оспариваться, или (2), когда код таков невероятно чувствительно к производительности, что стоимость неоспоримого замка все еще слишком высока.

Очевидно, что мы не находимся во втором случае. Ради всего святого, ты пользуешься словарем. Даже без замка это будет делать поиск и сравнение, которые будут в сотни или тысячи раз дороже, чем экономия на обходе безальтернативного замка.

Если мы находимся в первом случае, то Выясните, что вызывает конфликт, и устраните это. Если вы если вы долго ждете блокировки, то выясните, почему это так, и замените блокировку на тонкую блокировку reader-writer-lock или измените структуру приложения так, чтобы не так много потоков одновременно стучали по одной и той же блокировке.

В любом случае нет никакого оправдания для использования опасных, чувствительных к реализации методов низкой блокировки. Вы должны использовать методы низкой блокировки только в тех невероятно редких случаях, когда вы действительно не можете взять на себя стоимость неоспоримого замка.

19

Я действительно не думаю, что вам нужно , чтобы доказать это, вам просто нужно сослаться на документацию для Dictionary<TKey, TValue>:

Словарь может одновременно поддерживать несколько читателей, пока коллекция не изменена. даже в этом случае перечисление через коллекцию само по себе не является потокобезопасной процедурой. в редких случаях, когда перечисление конкурирует с доступом на запись, коллекция должна быть заблокирована в течение всего периода перечисление. Чтобы разрешить доступ к коллекции нескольким потокам для чтения и записи, необходимо реализовать собственную синхронизацию.
На самом деле это хорошо известный факт (или должен быть), что вы не можете читать из словаря, пока другой поток пишет в него. Я видел несколько "странных многопоточных вопросов" здесь, на SO, где оказалось, что автор не понимал, что это небезопасно.

Проблема не в том, чтобы конкретно что касается блокировки с двойной проверкой, то просто словарь не является потокобезопасным классом, даже для сценария с одним писателем/одним читателем.

Я сделаю еще один шаг и покажу вам, почему в Reflector это не потокобезопасно: 

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

Посмотрите, что может произойти, если метод Resize выполняется, когда даже один читатель вызывает FindEntry:

  1. поток A: добавляет элемент, приводящий к динамическому изменению размера;
  2. поток B: вычисляет смещение ковша как (хэш-код % bucket count);
  3. поток а: изменяет размер ведер на другой (основной);
  4. поток B: выбирает индекс элемента из массиваnew bucket в old bucket index;
  5. указатель потока B больше не действителен.

И это именно то, что терпит неудачу в Примере dtb. Поток A ищет ключ, который заранее известен , чтобы быть в словаре, и все же он не найден. Почему? Потому что FindValue метод выбрал то, что он считал правильным ведром, но прежде чем он даже успел заглянуть внутрь, поток B изменил ведра, и теперь поток A ищет в каком-то совершенно случайном ведре, которое не содержит или даже не ведет к нужному входу.

Мораль этой истории: TryGetValue не является атомарной операцией, а Dictionary<TKey, TValue> не является потокобезопасным классом. Вам нужно беспокоиться не только о параллельной записи, но и о параллельной записи на чтение.

В действительности проблема на самом деле работает намного глубже, чем это, из-за переупорядочивания инструкций джиттером и процессором, устаревших кэшей и т. д. - здесь вообще не используются барьеры памяти - но это должно доказать вне всякого сомнения, что существует очевидное условие гонки, если у вас есть Add вызов, выполняемый одновременно с вызовом TryGetValue.

8

Причина, по которой я предполагаю, что этот вопрос возникает снова и снова:

До 2.0, до дженериков (Б. Г.), Hashtable был основным ассоциативным контейнером в .NET, который действительно обеспечивает некоторые гарантии потоковой передачи. От MSDN:
"Hashtable является потокобезопасным для использования несколькими потоками чтения и одним потоком записи. Это потокобезопасно для многопоточного использования, когда только один из потоков выполняет операции записи (обновления), что позволяет выполнять чтение без блокировки при условии, что записи сериализуются в хэш-таблицу."

Прежде чем кто-либо станет чрезвычайно возбужденным, существуют некоторые ограничения.
Смотрите, например, этот пост от Брэда Абрамса , который владеет Hashtable.
Некоторые более исторические сведения о Hashtable можно найти здесь (...ближе к концу: "после этой длительной диверсии-что насчет Hashtable?").

Почему Dictionary<TKey, TValue> терпит неудачу в приведенном выше случае:

Чтобы доказать, что это не удается, это достаточно найти один пример, так что я попробую именно его.
Изменение размера происходит по мере роста таблицы.
При изменении размера происходит перестановка, и мы видим, что это последние две строки: 

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

Массив buckets содержит индексы в массиве entries. Допустим, у нас уже есть 10 записей, и прямо сейчас мы добавляем новую.
Давайте далее для простоты сделаем вид, что у нас не было и не будет столкновений.
В старом buckets у нас были индексы, работающие от 0 до 9 - если бы у нас не было столкновений.
Теперь индексы в новом массиве buckets работают от 0 до 10(!).
Теперь мы изменим поле private buckets, чтобы указать на новые ведра.
Если в данный момент читатель делает TryGetValue(), он использует новые ведра для получения индекса, но затем использует Новый индекс для чтения в массив старых записей, так как поле entries все еще указывает на старые записи.
Одна из вещей, которую можно получить-помимо ложного чтения-это дружелюбный IndexOutOfRangeException.
Еще один "отличный" способ получить это-в объяснении @Aaronaught. (...и то и другое может произойти, например, как в Примере dtb).

Это действительно только один пример, Диктонария не была разработана и никогда не предназначалась для потокобезопасности. Он был разработан, чтобы быть быстрым, однако-это означает, что замок не будет удерживаться долго.
3

Включая код в вопрос, вы можете проверить его с помощью следующего кода.

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

}

Эта программа просто пытается заставить Create пересечь коллекцию по мере ее "выращивания". Он должен быть запущен на машине с по крайней мере двумя ядрами (или двумя процессорами) и, скорее всего, через некоторое время выйдет из строя с этим исключением.

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

Добавление этого теста затруднительно, так как это вероятностный тест, и вы не знаете, сколько времени потребуется, чтобы потерпеть неудачу (если вообще когда-либо). Я думаю, вы могли бы выбрать ... значение, как 10 секунд, и пусть он работает в течение этого времени. Если он не провалится за это время, то тест пройдет. Не самое лучшее, но что-то. Вы также должны проверить, что Environment.ProcessorCount > 1 перед запуском теста, в противном случае вероятность его провала мизерна.

1