Барьеры и модели памяти – explained

Всем привет! 

Начну с предыстории.

Когда мы в Амазоне планировали переносить сервис с x86/64 на ARM, почему-то никто в нашей команде не поднял тему того, что надо уделить особое внимание работе с многопоточностью и синхронизацией, так как из-за того, что у этих двух архитектур разные модели памяти, могли случиться неожиданные проблемы.

Однако, на тот момент я тоже не знал об этом, и нам повезло, что мы изначально везде использовали модель памяти Sequential Consistency (что это – далее в статье), поэтому все прошло гладко. Теперь, зная про модели памяти и возможные последствия, боюсь представить, что было бы в противном случае.

Как родилась статья

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

Статья основана на материалах лекции Computer Science Center (CSC) с курса “Параллельные вычисления” преподавателя Калишенко Е.Л. Крайне рекомендую ознакомиться со всеми лекциями курса (более структурированного материала по теме я еще не встречал). Благо он в открытом доступе – ссылка.

Что такое барьеры памяти и зачем это все нужно?

Начнем с небольшого описания того, как устроена “условная” архитектура процессора. Почему условная? Потому что может отличаться в зависимости от конкретной реализации, но суть похожа. 

В многопроцессорной среде существует проблема синхронизации данных между ядрами. Для ее решения придумали специальные протоколы, отвечающие за поддержку когерентности кеша. Одним из таких протоколов является MESI, сокращенное от Modified, Exclusive, Shared, Invalid. Если коротко, то протокол определяет состояния, в которых могут находиться линейки кеша процессора и благодаря этому поддерживает их консистентность. Организует работу протокола так называемый брокер сообщений (Broker), который обязуется обеспечивать когерентность кеша. Помимо брокера, есть еще две сущности: 1) Store Buffer и 2) Очередь инвалидации (Invalidate Queue). Store Buffer отвечает за временное хранение линейки кеша процессора после ее модификации. А очередь инвалидации служит для хранения линеек кеша процессора, которые были изменены одним ядром и должны “примениться” на другом. О том, как это работает и зачем нужно, можно почитать Википедию или, опять же, посмотреть лекцию от CSC. 

Например, когда CPU 0 меняет shared данные в своем кеше, они попадают в Store Buffer, и лежат там до тех пор, пока эта линейка кеша не будет “применена” CPU 1. Эти данные попадают в очередь инвалидации CPU 1, позволяя ядру самому решить, когда обновить данные. Теоретически, CPU 0 должно дождаться сигнала, что CPU 1 реально применило изменения, и только после этого продолжить работу. Однако, на практике может произойти так, что для оптимизации работы CPU 1 посылает сигнал Acknowledgment (Ack.), реально не сделав invalidate (то есть не применив последние изменения CPU 0). Рассмотрим на примере, к чему это может привести.

По все тому же протоколу MESI, ядро, исполняющее функцию f(), поменяло переменные a и b, и возможен сценарий, когда изменения a еще находятся в очереди на инвалидацию, и ядро g() не видит этих изменений, поэтому assert(a == 1) падает.

Тут на помощь и приходят барьеры памяти.

Барьеры памяти

Барьер памяти по-простому – это ассемблерная инструкция, которая ставится процессором между операциями чтения/записи. Мнемоника инструкций зависит от архитектуры, но смысл тот же:

• smp_rmb (read memory barrier) – применить все изменения из invalidate queue (чтобы получить актуальные данные из других ядер);

• smp_wmb (write memory barrier) – дождаться всех invalidation ack от других ядер (чтобы удостовериться, что другие ядра применили последние изменения, которые мы им послали);

• smp_mb – применить smp_rmb() и smp_wmb().

Так как существует много архитектур процессоров, и не у всех из них есть store buffer / invalidate queue, для решения проблем синхронизации договорились оперировать теоретическими барьерами памяти в виде X_Y, где X и Y могут принимать одно из двух значений – либо Load, либо Store. 

Смысл у этого такой. Если поставить барьер типа X_Y в любое место кода, – это означает, что все операции типа X до барьера выполнятся гарантированно до всех операций типа Y после барьера. То есть не может быть ситуации, когда операции X спустятся вниз за барьер X_Y, а операции Y поднимутся наверх.

Существует 4 вида барьеров памяти:

Например, барьер LoadLoad означает, что все операции типа "чтение" (Load) до барьера гарантированно будут выполнены до всех операций типа "чтение" (Load) после барьера.

Таким образом, в нашем примере с функциями f() и g() мы могли воспользоваться барьерами памяти, чтобы гарантировать корректное исполнение:

При использовании таких барьеров, мы бы получили гарантию на то, что, когда ядро g() будет читать переменную a, то оно получит актуальные данные a, применив те изменения из очереди инвалидации, которые послало ядро f(). Условно говоря, LoadLoad вызывает инструкцию smp_rmb(), отрабатывающий всю очередь инвалидации. А StoreStore вызывает smp_wmb() и ждет, пока второе ядро не отправит Ack. Но в высокоуровневом коде, например, на Java, мы не ставим барьеры памяти явно. Как быть? Для этого придумано ключевое слово volatile, которое автоматически расставит все нужные барьеры памяти (необходимые ассемблерные инструкции smp) для корректной работы с volatile переменной, что означает, что если эта переменная была изменена в одном ядре, то это изменение будет гарантированно видно другим ядром.

Пару барьеров LoadLoad/LoadStore назвали acquire. А LoadStore/StoreStore – release. А все вместе – acquire/release-семантика.

Названы они так, потому что ни одна операция типа "чтение"/"запись" не будет переупорядочена компилятором за пределы границ, помеченных acquire/release.

Например, в исходном коде JDK эти барьеры явно определены (обратите внимание на объем комментариев над этими строками).

На этом все с барьерами памяти. Посмотрим теперь, что такое модели памяти.

Модели памяти

Модель памяти определяет, какие по умолчанию барьеры памяти гарантирует архитектура процессора и/или компилятор. Их 4.

1. Sequential Consistency – любая операция чтения/записи по умолчанию применяет все барьеры памяти (как если бы в процессоре отсутствовали Store Buffer и Invalidation Queue);

2. Strong-ordered или Total store-ordered (TSO) – применяет acquire и release барьеры для любых операций чтения/записи (пример – x86/64);

3. Weak-ordered – все необходимые барьеры нужно применять вручную (ARMv7);

4. Super-weak – все необходимые барьеры нужно применять вручную + нет гарантий на то, что взаимозависимые строчки кода не будут переупорядочены (Alpha). Например, на такой архитектуре компилятор может переставить строчки таким образом, что следующий код упадет:

Есть давняя статья про барьеры памяти, где указано, какие типы перестановок кода разрешены на каких архитектурах Memory Barriers: a Hardware View for Software Hackers.

Как на практике применять барьеры памяти? 

Зависит от языка. На C++, зачастую, приходится работать с атомиками. Атомики по умолчанию применяют все возможные барьеры памяти для того, чтобы случайно ничего не сломать. Но также дают возможность указывать их самостоятельно. Зачем? Иногда полезно для оптимизации производительности (особенно в системном программировании). На выбор дают:

• Relaxed – не применять никакие барьеры памяти

• Acquire – применить барьеры LoadLoad и LoadStore

• Release – LoadStore + StoreStore

• Sequential Consistency – LoadLoad, LoadStore, StoreLoad, StoreStore

• AcquireRelease – все, кроме StoreLoad

• Consume – StoreLoad

Потренируемся ставить барьеры памяти. В примере ниже в функции f() происходит две записи, поэтому соответствующий теоретический барьер – StoreStore. По табличке определяем, какое ключевое слово ему соответствует – Release. Аналогичным образом понимаем, что для функции g() необходим Acquire.

На Java используем уже упомянутый volatile. Он обеспечивает SequentialConsistency, то есть применение всех барьеров памяти. Начиная с Java 9 появилась возможность явно указывать, какую модель памяти использовать для атомиков.

Вопрос на проверку:

Нужно ли писать volatile для переменных x и y на Java, если код исполняется на архитектуре с моделью памяти Total store-ordered (например, на x86/64). Мы считаем поведение корректным при падении любого из ассерта. Ответ: да, так как TSO не применяет барьер StoreLoad. Без volatile на данной архитектуре следующий код подвержен ошибкам. Почему? Оставляю для размышления. Пишите предположения в комментарии.

Таким образом, возвращаясь к упомянутому в начале переходу с x86/64 на ARM, становится понятно, почему знать про модели памяти полезно. Ведь, если, например, перенести код на C++ на архитектуру с более слабой моделью памяти как есть, возможны “неожиданные” ошибки.

Нужно сказать, что все барьеры памяти принудительно применяются в двух случаях:

    1) При захвате / освобождении любых примитивов синхронизации (иначе мы просто не будем знать реальное состояние мьютекса);

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

Интересный факт

В 2014 году в течение одного года на многих серверах наблюдалось зависание систем, исполняемых на JVM на процессорах, имеющих 8 и более ядер. Ошибка появилась после одного из обновлений Линукса, а именно, реализации фьютекса. Вкратце, произошло так, что когда флаг, проверяющий состояние блокировки, был изменен одним ядром, другое ядро видело его старое значение, и продолжало ожидать разблокировки. Баг был исправлен как раз-таки добавлением упущенного барьера памяти:

Кому интересно, комментарии по этому поводу можно найти здесь.

Выводы

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

2. Портирование кода между архитектурами с различными моделями памяти может быть опасной вещью и требует особого внимания;

3. Java по умолчанию обладает слабой (weak) моделью памяти. Поэтому используем volatile, чтобы обеспечить Sequential Consistency;

4. Модель памяти C++ определяется используемыми моделями в атомиках. Почти всегда нам достаточно дефолтного SeqCst (за исключением, когда нужна супер-производительность).

Спасибо за прочтение! Делитесь мнением и вашим опытом в комментариях 🙂