Как показать, что шаблон двойной проверки с блокировкой в ​​словаре TryGetValue не является потокобезопасным - PullRequest
Новая
       48

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

13 голосов
/ 12 апреля 2010

Недавно я видел несколько проектов на 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 ]

20 голосов
/ 13 апреля 2010

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

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

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

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

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

13 голосов
/ 12 апреля 2010

В этом примере исключение # 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";
}

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

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

8 голосов
/ 12 апреля 2010

Не думаю, что вам нужно , чтобы доказать это, вам просто нужно отослать людей к документации для 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: вычисляет смещение сегмента как (хэш-код% количества сегментов);
  3. Тема A: изменяет ведра на другой (простой) размер;
  4. Поток B: выбирает индекс элемента из нового массива сегмента в старом индексе сегмента;
  5. Указатель нити B. больше не действителен.

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

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

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

3 голосов
/ 12 апреля 2010

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

Pre-2.0, Before Generics (B.G.), Hashtable был основным ассоциативным контейнером в .NET, который действительно предоставляет некоторые гарантии многопоточности. От MSDN :
"Hashtable является поточно-ориентированным для использования несколькими потоками считывателей и одним потоком записи. Он является поточно-ориентированным для многопоточного использования, когда только один из потоков выполняет операции записи (обновления), что обеспечивает возможность чтения без блокировок при условии что авторы сериализованы в 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 (!).
Теперь мы изменим приватное поле buckets, чтобы оно указывало на новые сегменты.
Если в данный момент читатель делает TryGetValue(), он использует новые сегменты для получения индекса, но затем использует новый индекс для чтения в old массив записей, так как поле entries по-прежнему указывает на старые записи.
Одна из вещей, которую можно получить - кроме ложных прочтений - это дружелюбие IndexOutOfRangeException.
Другой «замечательный» способ получить это - объяснение @ Aaronaught . (... и то и другое может произойти, например, как в примере dtb ).

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

1 голос
/ 12 апреля 2010

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

//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 перед запуском теста, в противном случае вероятность его сбоя ничтожна.

...