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

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

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

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

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

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

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

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

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

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

На самом деле это хорошо известный факт (или должен быть), что вы не можете читать из словаря, пока другой поток записывает в него данные. Я видел несколько вопросов типа "странная проблема многопоточности" здесь на 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. Thread B: Выбирает индекс элемента из new bucket array по old bucket index;
5. Указатель Thread B больше не действителен.

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

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

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

Причина, по которой этот вопрос возникает снова и снова:

До версии 2.0, до появления Generics (B.G.), Hashtable был основным ассоциативным контейнером в .NET, который действительно обеспечивает некоторые гарантии потоков. Из MSDN:
"Hashtable является потокобезопасным для использования несколькими потоками чтения и одним потоком записи. Она безопасна для многопоточного использования, когда только один из потоков выполняет операции записи (обновления), что позволяет читать без блокировки, при условии, что записывающие потоки сериализованы в Hashtable."

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

Почему Dictionary не работает в приведенном выше случае:

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

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

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

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