C # / CLR: MemoryBarrier и разорванное чтение

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

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

public struct Sync<T>
    where T : struct
{
    object write;
    T value;
    int version; // incremented with each write

    public static Sync<T> Create()
    {
        return new Sync<T> { write = new object() };
    }

    public T Read()
    {
        // if version after read == version before read, no concurrent write
        T x;
        int old;
        do
        {
            // loop until version number is even = no write in progress
            do
            {
                old = version;
                if (0 == (old & 0x01)) break;
                Thread.MemoryBarrier();
            } while (true);
            x = value;
            // barrier ensures read of 'version' avoids cached value
            Thread.MemoryBarrier();
        } while (version != old);
        return x;
    }

    public void Write(T value)
    {
        // locks are full barriers
        lock (write)
        {
            ++version;             // ++version odd: write in progress
            this.value = value;
            // ensure writes complete before last increment
            Thread.MemoryBarrier();
            ++version;             // ++version even: write complete
        }
    }
}

Не беспокойтесь о переполнении переменной версии, я избегаю этого по-другому. Итак, правильно ли я понимаю и применяю Thread.MemoryBarrier в приведенном выше? Есть ли какие-то препятствия ненужными?


c# concurrency clr memory-barriers concurrent-programming
person naasking    schedule 21.09.2013    source источник
comment
Ваши комментарии и код (информация / версия) не синхронизированы.   -  person Henk Holterman    schedule 21.09.2013

Ответы (2)


arrow_upward
3
arrow_downward

Я внимательно изучил ваш код, и мне он кажется правильным. Одна вещь, которая сразу бросилась в глаза, заключалась в том, что вы использовали установленный шаблон для выполнения операции low-lock. Я вижу, что вы используете version как своего рода виртуальный замок. Четные числа освобождаются, а нечетные числа приобретаются. И поскольку вы используете монотонно увеличивающееся значение для виртуальной блокировки, вы также избегаете проблемы ABA. Однако наиболее важным является то, что вы продолжаете цикл при попытке чтения до тех пор, пока значение виртуальной блокировки не станет таким же до начала чтения по сравнению с после он завершается. В противном случае вы сочтете это неудачным чтением и повторите попытку. Так что да, основная логика выполнена хорошо.

Так что насчет размещения генераторов барьеров памяти? Что ж, все это тоже выглядит неплохо. Требуются все Thread.MemoryBarrier вызовы. Если бы мне пришлось придираться, я бы сказал, что вам нужен еще один в методе Write, чтобы он выглядел так.

public void Write(T value)
{
    // locks are full barriers
    lock (write)
    {
        ++version;             // ++version odd: write in progress
        Thread.MemoryBarrier();
        this.value = value;
        Thread.MemoryBarrier();
        ++version;             // ++version even: write complete
    }
}

Добавленный здесь вызов гарантирует, что ++version и this.value = value не поменяются местами. Теперь спецификация ECMA технически допускает такой вид переупорядочения инструкций. Однако реализация интерфейса командной строки Microsoft и оборудования x86 уже имеет изменчивую семантику записи, поэтому в большинстве случаев в этом нет необходимости. Но, кто знает, возможно, это будет необходимо в среде выполнения Mono, ориентированной на процессор ARM.

Что касается Read вещей, я не могу найти никаких недостатков. Фактически, размещение ваших звонков - это именно то место, где я бы их поместил. Некоторые люди могут задаться вопросом, почему он вам не нужен до первого чтения version. Причина в том, что внешний цикл улавливает случай, когда первое чтение было кэшировано из-за Thread.MemoryBarrier дальше вниз.

Итак, это подводит меня к обсуждению производительности. Неужели это быстрее, чем жесткая блокировка в методе Read? Что ж, я провел довольно обширное тестирование вашего кода, чтобы ответить на этот вопрос. Ответ однозначный: да! Это немного быстрее, чем жесткая блокировка. Я тестировал, используя Guid в качестве типа значения, потому что это 128 бит и поэтому он больше, чем собственный размер слова моей машины (64 бита). Я также использовал несколько разных вариантов количества писателей и читателей. Ваша техника низкого запирания постоянно и значительно превосходила технику жесткого запора. Я даже пробовал несколько вариантов с использованием Interlocked.CompareExchange для безопасного чтения, и все они тоже были медленнее. Фактически, в некоторых ситуациях это было медленнее, чем взятие жесткого замка. Я должен быть честным. Меня это совсем не удивило.

Я также провел довольно серьезное тестирование на валидность. Я создал тесты, которые будут работать довольно долго и ни разу не увидел разорванного чтения. А затем в качестве контрольного теста я настроил метод Read таким образом, чтобы я знал, что он будет неправильным, и снова запустил тест. На этот раз, как и ожидалось, случайным образом стали появляться разорванные чтения. Я переключил код обратно на тот, который у вас есть, и разорванные чтения исчезли; опять же, как и ожидалось. Казалось, это подтвердило то, что я уже ожидал. То есть ваш код выглядит правильно. У меня нет большого разнообразия среды выполнения и аппаратных сред для тестирования (и у меня нет времени), поэтому я не хочу давать ему 100% одобрение, но я действительно думаю, что могу дать вашей реализации два больших пальца вверх сейчас.

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

person Brian Gideon    schedule 30.10.2013
comment
Спасибо за подробный обзор. На самом деле я написал об этом в своем блоге: upperlogics.blogspot .ca / 2013/09 /, и эти функции и некоторые другие, построенные на них, находятся в моей библиотеке Sasa с открытым исходным кодом: sourceforge.net/p/sasa/code/ci/default/tree/Sasa/. Последние версии были переведены на использование VolatileRead / VolatileWrite для ясности. Вы также можете использовать их для реализации примитивов, связанных с загрузкой / условием сохранения. - person naasking; 31.10.2013
comment
@naasking: Посмотрите, сможете ли вы создать операцию LL / SC и опубликовать ее в своем блоге. Я бы хотел посмотреть, что вы придумали. Если у меня будет время, я могу попробовать сам. - person Brian Gideon; 01.11.2013
comment
LL / SC уже присутствует в коде, на который я ссылался выше (внизу страницы). Я также преобразовал часть кода в структуру многократного использования, чтобы упростить API: sourceforge.net/p/sasa/code/ci/default/tree/Sasa.Concurrency/ - person naasking; 01.11.2013

arrow_upward
-1
arrow_downward

Похоже, вам интересна реализация без блокировки / без ожидания. Начнем с этого обсуждения, например: Без блокировки мульти- многопоточность предназначена для настоящих экспертов по многопоточности

person Yury Schkatula    schedule 21.09.2013