Как показать, что узор с двойной проверкой с помощью TrygetValue словаря не ThreadSafe

StackOverflow https://stackoverflow.com/questions/2624301

Вопрос

Недавно я видел некоторые проекты 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 (за пределами блокировки) итерация по поводу сбора. Это может быть чрезвычайно вряд ли во многих ситуациях, но все еще не так.

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

Есть ли смысл включить это в тест на единицу? И если так, как?

Это было полезно?

Решение

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

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

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

Другие советы

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

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

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

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

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

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

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

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

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

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

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. Указатель Thread B больше не действителен.

И это именно то, что не удается в примере DTB. Нить поиск ключа, который известный заранее быть в словаре, и все же это не найдено. Почему? Поскольку FindValue Метод выбрал то, что он думал, что это правильное ведро, но до того, как он даже имел возможность заглянуть внутрь, нить B поменял ведра, а теперь нить a выглядит в некотором абсолютно случайном ведре, который не содержит или даже привести к правильной записи.

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

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

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

Pre-2.0, до родов (BG), 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 (!).
Теперь мы меняем частные buckets поле, чтобы указать на новые ведра.
Если есть читатель TryGetValue() На данный момент он использует новый ведра, чтобы получить индекс, но затем использует новый индекс для чтения в Старый Массив записей, поскольку entries Поле все еще указывает на старые записи.
Одна из вещей, которые можно получить - помимо ложных читаний - это дружелюбный IndexOutOfRangeException.
Еще один «отличный» способ получить это в @ Аронат объяснение. (... и оба могут произойти, например, как в DTB's. пример).

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top