Эта статья — частичный перевод исчерпывающего руководства Дэвида Хоуэлса (David Howells) и Пола Маккени (Paul E. McKenney) распространяемого в составе документации Linux (Documentation/memory-barriers.txt онлайн версия).
Must read для разработчиков ядра/драйверов и очень познавательно для прикладных программистов.
Рассмотрим следующую модель системы:
Каждый процессор выполняет программу, генерирующую последовательность операций доступа к памяти. Абстрактный процессор имеет слабую модель упорядочивания доступа к памяти, так, что фактически операции доступа могут выполняться в произвольном порядке, если при этом не нарушаются причинно-следственные связи заложенные в исполняемом коде. Аналогично, компилятор свободен в организации сгенерированного кода, при условии, что результат выполнения этого кода будет соответствовать исходному тексту программы.
На приведённом рисунке операции с памятью выполняемые процессором наблюдаются остальными компонентами системы, как операции пересекающие границы между этим процессором и системой (обозначенные пунктирными линиями).
Многие устройства имеют управляющий интерфейс в виде набора регистров с определёнными адресами в памяти; порядок доступа к управляющим регистрам важен для правильной работы. Например, сетевой адаптер может иметь набор внутренних регистров, доступ к которым выполняется через регистр адреса (A) и регистр данных (D). Для чтения внутреннего регистра 5 может быть использован следующий код:
этот код может породить следующие последовательности доступа к памяти:
вторая последовательность почти наверняка вернёт неправильный результат, поскольку регистр адреса будет установлен после чтения регистра данных.
Процессор гарантирует, как минимум, следующее:
Кроме того:
Как показано выше, независимые операции доступа к памяти могут выполняться в произвольном порядке, что может стать проблемой для взаимодействия между процессорами или между процессором и внешним устройством. Требуется механизм для указания компилятору и процессору на необходимость соблюдения порядка.
Барьеры доступа к памяти являются таким механизмом. Они приводят к частичному упорядочиванию операций доступа к памяти по обе стороны барьера.
Процессоры и другие системные устройства используют множество приёмов для повышения производительности, в их числе переупорядочивание операций, откладывание и совмещение операций доступа к памяти, раннее чтение данных, предсказание переходов и различные типы кеширования. Барьеры доступа к памяти служат для подавления этих механизмов.
Существует 4 основных типа барьеров:
И пара неявных типов барьеров:
Барьеры доступа к памяти требуются только в случае межпроцессорного взаимодействия, или взаимодействия процессора со внешним устройством. Барьеры доступа к памяти не нужны в коде, который не участвует в таких видах взаимодействия.
Замечание: изложенные гарантии — минимальные. Различные процессорные архитектуры могут давать более сильные гарантии для барьеров, на них, однако, не следует полагаться в архитектурно-независимом коде.
Модель использования барьеров зависимости по данным имеет ряд тонкостей, необходимость которых не всегда очевидна.
Рассмотрим следующую последовательность событий:
В коде присутствует явная зависимость по данным, и создаётся впечатление, что по окончании последовательности Q может быть равен либо &A либо &B, а так же, что (Q == &A) влечёт (D == 1), а (Q == &B) влечёт (D == 4).
Однако, с точки зрения CPU2, P может быть обновлен раньше чем B, в результате чего получится (Q == &B) и (D == 2) (о_О).
Хоть и может показаться, что подобное поведение является нарушением причинно-следственных связей, либо проблемой когерентности, это не так. Такое поведение наблюдается на некоторых типах процессоров (например, DEC Alpha).
Для исправления ситуации требуется барьер зависимости по данным (или более сильный) между чтением адреса и чтением данных по этому адресу:
В таком случае третий исход ((Q == &B) и (D == 2)) невозможен.
Замечание: такая противоестественная ситуация легче всего воспроизводима на машинах с разделённым кешем, когда, например, один кеш-банк обслуживает чётные, а другой — нечётные строки кеша. В случае, когда P и B попадают в строки разной чётности, неравномерность нагрузки на банки кеша может привести к описанному эффекту.
Наличие зависимости по управлению требует использования барьера чтения, барьера зависимости по данным будет недостаточно. Рассмотрим следующий код:
Барьер в этом примере не возымеет желаемого эффекта, поскольку фактически зависимость по данным между (p) и (x = *q) отсутствует, а имеет место зависимость по управлению. Процессор может попытаться предсказать результат.
Что действительно требуется в данной ситуации:
При организации межпроцессорного взаимодействия определённые типы барьеров всегда должны использоваться парно. Отсутствие парности почти наверняка является ошибкой.
Барьер записи должен всегда иметь пару в виде барьера зависимости по данным, барьера чтения или обобщённого барьера доступа к памяти. Аналогично, барьер зависимости по данным и барьер чтения должны иметь пару в виде барьера записи или обобщённого барьера доступа к памяти:
или:
Барьер чтения всегда должен присутствовать, вопрос только в том, какой силы примитив следует для него выбрать.
Замечание: операции записи перед барьером записи обычно имеют парные операции чтения с другой стороны барьера чтения или зависимости по данным и наоборот:
Первый: барьеры записи вносят частичный порядок в операции записи. Рассмотрим следующую последовательность событий:
Эта последовательность достигает системы поддержки когерентности памяти в порядке, который остальные части системы могут наблюдать как неупорядоченный набор записей { ЗАПИСЬ A, ЗАПИСЬ B, ЗАПИСЬ C }, происходящих до неупорядоченного набора записей { ЗАПИСЬ D, ЗАПИСЬ E }:
Второй: барьеры зависимости по данным вносят частичный порядок в зависимые по данным операции чтения. Рассмотрим следующую последовательность событий:
Без барьеров CPU 2 может наблюдать события, производимые CPU 1 в произвольном порядке, не смотря на использование барьера записи CPU 1:
В приведённом примере CPU 2 наблюдает значение B == 7, не смотря на то, что чтение *C (которое должно вернуть B) идёт после чтения C.
Однако, при наличии барьера зависимости по данным между чтением C и чтением *C (т.е. B) на CPU 2,
картина выглядит так:
Третий: барьер чтения частично упорядочивает операции чтения. Рассмотрим следующую последовательность событий:
Без барьеров CPU 2 может наблюдать события, производимые CPU 1 в произвольном порядке, не смотря на использование барьера записи CPU 1:
Однако, при наличии барьера чтения между чтением B и чтением A на CPU 2,
частичный порядок, обеспеченный CPU 1, будет наблюдаем CPU 2 правильно:
Многие процессорные архитектуры могут выполнять чтение из памяти заранее: в случаях, когда процессор видит команду чтения из памяти в конвейере и не использует внешнюю шину для других команд, команда на чтение может быть выдана заранее — даже если поток выполнения команд не добрался до инструкции чтения. Это даёт возможность инструкции чтения завершиться очень быстро, поскольку к моменту её выполнения процессор может уже получить прочитанное из памяти значение.
Может случиться, что прочитанное значение не понадобится — например, если команда перехода встретится раньше команды чтения. В таких случаях прочитанное значение будет отброшено или сохранено в кеше.
Рассмотрим следующий пример:
который может генерировать следующие команды:
Помещение барьера чтения или зависимости по данным перед второй операцией чтения
вынудит процессор пересмотреть заранее прочитанное значение, в зависимости от использованного типа барьера. Если заранее прочитанная область памяти не менялась, значение будет использовано:
однако, если область памяти была перезаписана другим процессором, заранее прочитанное значение будет отброшено и команда чтения будет выдана повторно:
В Linux имеются следующие типы барьеров, действующие на разных уровнях:
Явный барьер компилятора предотвращает перемещение операций доступа к памяти компилятором с одной стороны барьера на другую:
Это единственный барьер уровня компилятора.
Барьер компилятора не оказывает никакого эффекта на поведение процессора, который может переупорядочивать операции доступа к памяти по своему усмотрению.
Следующие 8 функций представляют собой барьеры процессора в Linux:
Все барьеры уровня процессора, за исключением барьера зависимости по данным, включают в себя барьер компилятора.
Замечание: в случае зависимости по данным можно было бы ожидаеть, что компилятор организует инструкции чтения в правильном порядке (например, a[b] сначала прочтёт значение b, а потом — a[b]), однако стандарт языка С не даёт такой гарантии.
При компиляции однопроцессорного ядра, SMP-версии барьеров превращаются в барьеры компилятора, потому что один процессор всегда наблюдает собственные операции с памятью в правильном порядке.
Замечание: SMP-барьеры должны использоваться для управления порядком операций с разделяемой памятью в SMP-системах, но на деле достаточно использования блокирующих примитивов синхронизации.
Безусловные барьеры не следует использовать для управления эффектами SMP, поскольку это приводит к снижению производительности на однопроцессорных системах. Их основная область использования — упорядочивание операций доступа к устройствам ввода/вывода отображаемым в память.
Следующая функция представляет собой барьер записи в область ввода/вывода отображённого в память:
Эта функция является вариантом обязательного барьера записи и обеспечивает частичное упорядочивание операций записи в регион MMIO. Её эффект может простираться вглубь за границу интерфейса между процессором и подсистемой памяти.
То, как операции над кешируемой памятью наблюдаются компонентами системы во многом зависит от кеша, расположенного между процессором и памятью и системы поддержания его когерентности.
С точки зрения рассматриваемых барьеров доступа к памяти, процессорный кеш и система поддержания его когерентности являются частью системной памяти; эффект барьеров доступа к памяти проявляется на границе, изображённой пунктирной линией на диаграмме:
Хотя операции обращения к памяти могут быть выполнены процессором без обращения ко внешней шине, например из кеша, для остальных процессоров системой поддержки когерентности кеша по-прежнему поддерживается видимость того, что межпроцессорное взаимодействие происходит через внешнюю память, посредством миграции строк кеша к которым осуществляется доступ.
Процессорное ядро выполняет инструкции в том порядке, который ему удобен, гарантируя при этом сохранение причинно-следственных связей в выполняемой программе. Некоторые инструкции генерируют запросы чтения или записи, которые помещаются в очередь запросов к подсистеме памяти. Процессорное ядро помещает их в очередь в подходящем порядке и продолжает выполнение, до тех пор пока ему не понадобится получить результат какой-либо из этих инструкций.
Барьеры доступа к памяти контролируют порядок, в котором запросы переходят со стороны процессора на сторону памяти, а так же наблюдаемость эффектов операций, производимых над памятью другими компонентами системы.
Must read для разработчиков ядра/драйверов и очень познавательно для прикладных программистов.
Обобщённая модель доступа к памяти.
Рассмотрим следующую модель системы:
: :
: :
: :
+-------+ : +--------+ : +-------+
| | : | | : | |
| | : | | : | |
| CPU 1 |<----->| Memory |<----->| CPU 2 |
| | : | | : | |
| | : | | : | |
+-------+ : +--------+ : +-------+
^ : ^ : ^
| : | : |
| : | : |
| : v : |
| : +--------+ : |
| : | | : |
| : | | : |
+---------->| Device |<----------+
: | | :
: | | :
: +--------+ :
: :
Каждый процессор выполняет программу, генерирующую последовательность операций доступа к памяти. Абстрактный процессор имеет слабую модель упорядочивания доступа к памяти, так, что фактически операции доступа могут выполняться в произвольном порядке, если при этом не нарушаются причинно-следственные связи заложенные в исполняемом коде. Аналогично, компилятор свободен в организации сгенерированного кода, при условии, что результат выполнения этого кода будет соответствовать исходному тексту программы.
На приведённом рисунке операции с памятью выполняемые процессором наблюдаются остальными компонентами системы, как операции пересекающие границы между этим процессором и системой (обозначенные пунктирными линиями).
Операции со внешними устройствами.
Многие устройства имеют управляющий интерфейс в виде набора регистров с определёнными адресами в памяти; порядок доступа к управляющим регистрам важен для правильной работы. Например, сетевой адаптер может иметь набор внутренних регистров, доступ к которым выполняется через регистр адреса (A) и регистр данных (D). Для чтения внутреннего регистра 5 может быть использован следующий код:
*A = 5;
x = *D;
этот код может породить следующие последовательности доступа к памяти:
1 ЗАПИСЬ *A = 5, x = ЧТЕНИЕ *D
2 x = ЧТЕНИЕ *D, ЗАПИСЬ *A = 5
вторая последовательность почти наверняка вернёт неправильный результат, поскольку регистр адреса будет установлен после чтения регистра данных.
Гарантии.
Процессор гарантирует, как минимум, следующее:
- Операции доступа к памяти, зависящие одна от другой, выполняются в правильном порядке в пределах одного процессора. Иными словами, для кода
Q = P; D = *Q;
процессор сгенерирует такие операции доступа к памяти:
Q = ЧТЕНИЕ P, D = ЧТЕНИЕ *Q
и только в таком порядке. - Записи и чтения в перекрывающиеся участки памяти выполняемые одним процессором сохраняют свой порядок в пределах этого процессора. Иными словами, для кода
a = *X; *X = b;
процессор сгенерирует только такую последовательность доступа к памяти:
a = ЧТЕНИЕ *X, ЗАПИСЬ *X = b
А для кода
*X = c; d = *X;
— только такую:
ЗАПИСЬ *X = c, d = ЧТЕНИЕ *X
Кроме того:
- Не следует полагать, что операции доступа к памяти для независимых чтений и записей будут сгенерированы в каком-то определённом порядке. Иными словами, для кода
X = *A; Y = *B; *D = Z;
может быть сгенерирована одна из следующих последовательностей:
1 X = ЧТЕНИЕ *A, Y = ЧТЕНИЕ *B, ЗАПИСЬ *D = Z 2 X = ЧТЕНИЕ *A, ЗАПИСЬ *D = Z, Y = ЧТЕНИЕ *B 3 Y = ЧТЕНИЕ *B, X = ЧТЕНИЕ *A, ЗАПИСЬ *D = Z 4 Y = ЧТЕНИЕ *B, ЗАПИСЬ *D = Z, X = ЧТЕНИЕ *A 5 ЗАПИСЬ *D = Z, X = ЧТЕНИЕ *A, Y = ЧТЕНИЕ *B 6 ЗАПИСЬ *D = Z, Y = ЧТЕНИЕ *B, X = ЧТЕНИЕ *A - Следует считать, что смежные и перекрывающиеся операции доступа к памяти могут быть объединены или не выполнены вовсе. Иными словами, для кода
X = *A; Y = *(A + 4);
может быть сгенерирована одна из следующих последовательностей:
1 X = ЧТЕНИЕ *A; Y = ЧТЕНИЕ *(A + 4); 2 Y = ЧТЕНИЕ *(A + 4); X = ЧТЕНИЕ *A; 3 {X, Y} = ЧТЕНИЕ {*A, *(A + 4) };
А для кода
*A = X; Y = *A;
— одна из следующих:
1 ЗАПИСЬ *A = X; Y = ЧТЕНИЕ *A; 2 ЗАПИСЬ *A = Y = X;
Что такое барьеры доступа к памяти?
Как показано выше, независимые операции доступа к памяти могут выполняться в произвольном порядке, что может стать проблемой для взаимодействия между процессорами или между процессором и внешним устройством. Требуется механизм для указания компилятору и процессору на необходимость соблюдения порядка.
Барьеры доступа к памяти являются таким механизмом. Они приводят к частичному упорядочиванию операций доступа к памяти по обе стороны барьера.
Процессоры и другие системные устройства используют множество приёмов для повышения производительности, в их числе переупорядочивание операций, откладывание и совмещение операций доступа к памяти, раннее чтение данных, предсказание переходов и различные типы кеширования. Барьеры доступа к памяти служат для подавления этих механизмов.
Разновидности барьеров.
Существует 4 основных типа барьеров:
- Барьеры записи.
Барьеры записи гарантируют, что все операции записи в память, для инструкций предшествующих барьеру, будут выполнены процессором до любой операции записи в память, для инструкций следующих за барьером, с точки зрения остальных компонентов системы.
Барьеры записи упорядочивают только операции записи в память, не следует полагать, что они могут оказывать какой-либо эффект на операции чтения.
Замечание: барьеры записи должны иметь парные барьеры чтения или барьеры зависимости по данным; см. раздел «Парные барьеры в случае SMP».
- Барьеры зависимости по данным.
Барьеры зависимости по данным — это ослабленная версия барьеров чтения. В случаях, когда две операции чтения выполняются таким образом, что вторая операция зависит от результата первой (например, первая операция получает адрес, из которого будет читать вторая), барьер зависимости по данным гарантирует, что данные по адресу второй операции чтения будут актуальными на момент выполнения этой операции.
Барьеры зависимости по данным оказывают эффект только на взаимозависимые операции чтения, не следует полагать, что они могут оказывать эффект на операции записи, независимые или перекрывающиеся операции чтения.
Другие процессоры генерируют последовательности операций записи в память, результаты которых может наблюдать рассматриваемый процессор. Барьер зависимости по данным гарантирует, что при наличии перед барьером операций чтения из адресов, в которые была запись другим процессором, результаты всех остальных операций записи, предшествовавших ей, так же будут доступны процессору проходящему барьер, по окончании его прохождения.
Замечание: зависимость между чтениями должна быть действительно по данным; если адрес второй операции чтения зависит от результата выполнения первой, но не напрямую, а вычисляется на основании результата первого чтения, например, условными операторами, то это зависимость по управлению, и в этом случае следует использовать барьер чтения или барьер доступа. См. раздел «Барьеры зависимости по управлению».
Замечание: барьеры зависимости по данным должны иметь парные барьеры записи; см. раздел «Парные барьеры в случае SMP».
- Барьеры чтения.
Барьер чтения — это барьер зависимости по данным с гарантией, что все операции чтения, для инструкций предшествующих барьеру, будут выполнены процессором до любой операции чтения, для инструкций следующих за барьером, с точки зрения остальных компонентов системы.
Барьеры чтения упорядочивают только операции чтения из памяти, не следует полагать, что они могут оказывать какой-либо эффект на операции записи.
Замечание: барьеры чтения должны иметь парные барьеры записи; см. раздел «Парные барьеры в случае SMP».
- Обобщённые барьеры доступа к памяти.
Барьер доступа к памяти гарантирует, что все операции чтения и записи, для инструкций предшествующих барьеру, будут выполнены до любых операций чтения или записи, для инструкций следующих за барьером, с точки зрения остальных компонентов системы.
Барьеры доступа к памяти упорядочивают как операции чтения, так и записи.
Барьеры доступа к памяти подразумевают барьеры чтения и барьеры записи и могут быть использованы вместо тех и других.
И пара неявных типов барьеров:
- Операции захвата блокировки (LOCK).
Такие операции ведут себя как барьер с односторонней проницаемостью. Они гарантируют, что все операции доступа к памяти, для инструкций следующих за операцией захвата блокировки, будут выполнены после захвата блокировки, с точки зрения остальных компонентов системы.
Операции доступа к памяти, для инструкций предшествующих захвату блокировки, могут быть выполнены как до, так и после её захвата.
Операция захвата блокировки почти всегда должна иметь парную операцию освобождения блокировки.
- Операции освобождения блокировки (UNLOCK).
Такие операции тоже ведут себя как барьер с односторонней проницаемостью. Они гарантируют, что все операции доступа к памяти, для инструкций предшествующих операции освобождения блокировки, будут выполнены до освобождения блокировки, с точки зрения остальных компонентов системы.
Операции доступа к памяти, для инструкций следующих за освобождением блокировки, могут быть выполнены как до, так и после её освобождения.
Гарантируется, что операции захвата и освобождения блокировки не переупорядочиваются.
Использование операций захвата и освобождения блокировки в основном снимает потребность в использовании других типов барьеров доступа к памяти.
Барьеры доступа к памяти требуются только в случае межпроцессорного взаимодействия, или взаимодействия процессора со внешним устройством. Барьеры доступа к памяти не нужны в коде, который не участвует в таких видах взаимодействия.
Замечание: изложенные гарантии — минимальные. Различные процессорные архитектуры могут давать более сильные гарантии для барьеров, на них, однако, не следует полагаться в архитектурно-независимом коде.
Чего барьеры не гарантируют.
- Нет гарантии, что операции доступа к памяти, для инструкций предшествующих барьеру, будут завершены в момент окончания прохождения барьера; условно можно считать, что барьер «проводит черту» в очереди запросов процессора, которую не могут пересекать запросы определённых типов.
- Нет гарантии, что барьер доступа к памяти, выполненный на одном процессоре, окажет какой-либо эффект на другой процессор или другое устройство в системе. Косвенный эффект выражается в наблюдаемой другими устройствами последовательности обращений к памяти, выполняемых этим процессором (см., однако, следующий пункт).
- Нет гарантии, что процессор будет наблюдать эффекты доступа к памяти со стороны других процессоров в правильном порядке, даже если те будут использовать барьеры доступа к памяти, в случае если этот процессор сам не использует соответствующие барьеры (см.раздел «Парные барьеры в случае SMP»).
- Нет гарантии, что никакие промежуточные устройства не будут переупорядочивать обращения к памяти. Механизмы поддержания когерентности процессорного кеша должны передавать эффект от барьеров между процессорами, но могут нарушать их взаимный порядок.
Барьеры зависимости по данным.
Модель использования барьеров зависимости по данным имеет ряд тонкостей, необходимость которых не всегда очевидна.
Рассмотрим следующую последовательность событий:
CPU 1 CPU 2
=============== ===============
{ A == 1, B == 2, C = 3, P == &A, Q == &C }
B = 4;
<барьер записи>
P = &B
Q = P;
D = *Q;
В коде присутствует явная зависимость по данным, и создаётся впечатление, что по окончании последовательности Q может быть равен либо &A либо &B, а так же, что (Q == &A) влечёт (D == 1), а (Q == &B) влечёт (D == 4).
Однако, с точки зрения CPU2, P может быть обновлен раньше чем B, в результате чего получится (Q == &B) и (D == 2) (о_О).
Хоть и может показаться, что подобное поведение является нарушением причинно-следственных связей, либо проблемой когерентности, это не так. Такое поведение наблюдается на некоторых типах процессоров (например, DEC Alpha).
Для исправления ситуации требуется барьер зависимости по данным (или более сильный) между чтением адреса и чтением данных по этому адресу:
CPU 1 CPU 2
=============== ===============
{ A == 1, B == 2, C = 3, P == &A, Q == &C }
B = 4;
<барьер записи>
P = &B
Q = P;
<барьер зависимости по данным>
D = *Q;
В таком случае третий исход ((Q == &B) и (D == 2)) невозможен.
Замечание: такая противоестественная ситуация легче всего воспроизводима на машинах с разделённым кешем, когда, например, один кеш-банк обслуживает чётные, а другой — нечётные строки кеша. В случае, когда P и B попадают в строки разной чётности, неравномерность нагрузки на банки кеша может привести к описанному эффекту.
Барьеры при зависимости по управлению.
Наличие зависимости по управлению требует использования барьера чтения, барьера зависимости по данным будет недостаточно. Рассмотрим следующий код:
q = &a;
if (p)
q = &b;
<барьер зависимости по данным>
x = *q;
Барьер в этом примере не возымеет желаемого эффекта, поскольку фактически зависимость по данным между (p) и (x = *q) отсутствует, а имеет место зависимость по управлению. Процессор может попытаться предсказать результат.
Что действительно требуется в данной ситуации:
q = &a;
if (p)
q = &b;
<барьер чтения>
x = *q;
Парные барьеры в случае SMP.
При организации межпроцессорного взаимодействия определённые типы барьеров всегда должны использоваться парно. Отсутствие парности почти наверняка является ошибкой.
Барьер записи должен всегда иметь пару в виде барьера зависимости по данным, барьера чтения или обобщённого барьера доступа к памяти. Аналогично, барьер зависимости по данным и барьер чтения должны иметь пару в виде барьера записи или обобщённого барьера доступа к памяти:
CPU 1 CPU 2
=============== ===============
a = 1;
<барьер записи>
b = 2; x = b;
<барьер чтения>
y = a;
или:
CPU 1 CPU 2
=============== ===============================
a = 1;
<барьер записи>
b = &a; x = b;
<барьер зависимости по данным>
y = *x;
Барьер чтения всегда должен присутствовать, вопрос только в том, какой силы примитив следует для него выбрать.
Замечание: операции записи перед барьером записи обычно имеют парные операции чтения с другой стороны барьера чтения или зависимости по данным и наоборот:
CPU 1 CPU 2
=============== ===============
a = 1; }---- --->{ v = c
b = 2; } \ / { w = d
<барьер записи> \ <барьер чтения>
c = 3; } / \ { x = a;
d = 4; }---- --->{ y = b;
Примеры операций доступа к памяти с барьерами.
Первый: барьеры записи вносят частичный порядок в операции записи. Рассмотрим следующую последовательность событий:
CPU 1
=======================
ЗАПИСЬ A = 1
ЗАПИСЬ B = 2
ЗАПИСЬ C = 3
<барьер записи>
ЗАПИСЬ D = 4
ЗАПИСЬ E = 5
Эта последовательность достигает системы поддержки когерентности памяти в порядке, который остальные части системы могут наблюдать как неупорядоченный набор записей { ЗАПИСЬ A, ЗАПИСЬ B, ЗАПИСЬ C }, происходящих до неупорядоченного набора записей { ЗАПИСЬ D, ЗАПИСЬ E }:
+-------+ : :
| | +------+
| |------>| C=3 | } /\
| | : +------+ }----- \ -----> События наблюдаемые
| | : | A=1 | } \/ другими компонентами системы
| | : +------+ }
| CPU 1 | : | B=2 | }
| | +------+ }
| | wwwwwwwwwwwwwwww } <--- В этот момент барьер записи
| | +------+ } делает так, что все операции записи предшествующие
| | : | E=5 | } барьеру будут отправлены "наружу" до любой из
| | : +------+ } записей, следующих за барьером
| |------>| D=4 | }
| | +------+
+-------+ : :
|
| Последовательность, в которой события достигают
| подсистемы памяти от CPU 1
V
Второй: барьеры зависимости по данным вносят частичный порядок в зависимые по данным операции чтения. Рассмотрим следующую последовательность событий:
CPU 1 CPU 2
======================= =======================
{ B = 7; X = 9; Y = 8; C = &Y }
ЗАПИСЬ A = 1
ЗАПИСЬ B = 2
<барьер записи>
ЗАПИСЬ C = &B ЧТЕНИЕ X
ЗАПИСЬ D = 4 ЧТЕНИЕ C (возвращает &B)
ЧТЕНИЕ *C (возвращает B)
Без барьеров CPU 2 может наблюдать события, производимые CPU 1 в произвольном порядке, не смотря на использование барьера записи CPU 1:
+-------+ : : : :
| | +------+ +-------+ | Последовательность записей
| |------>| B=2 |----- --->| Y->8 | | наблюдаемая
| | : +------+ \ +-------+ | CPU 2
| CPU 1 | : | A=1 | \ --->| C->&Y | V
| | +------+ | +-------+
| | wwwwwwwwwwwwwwww | : :
| | +------+ | : :
| | : | C=&B |--- | : : +-------+
| | : +------+ \ | +-------+ | |
| |------>| D=4 | ----------->| C->&B |------>| |
| | +------+ | +-------+ | |
+-------+ : : | : : | |
| : : | |
| : : | CPU 2 |
| +-------+ | |
Чтение неверного ---> | | B->7 |------>| |
значения B | +-------+ | |
| : : | |
| +-------+ | |
Чтение Х задерживает---> \ | X->9 |------>| |
обновление наблюдаемого \ +-------+ | |
значения B ----->| B->2 | +-------+
+-------+
: :
В приведённом примере CPU 2 наблюдает значение B == 7, не смотря на то, что чтение *C (которое должно вернуть B) идёт после чтения C.
Однако, при наличии барьера зависимости по данным между чтением C и чтением *C (т.е. B) на CPU 2,
CPU 1 CPU 2
======================= =======================
{ B = 7; X = 9; Y = 8; C = &Y }
ЗАПИСЬ A = 1
ЗАПИСЬ B = 2
<барьер записи>
ЗАПИСЬ C = &B ЧТЕНИЕ X
ЗАПИСЬ D = 4 ЧТЕНИЕ C (gets &B)
<барьер зависимости по данным>
ЧТЕНИЕ *C (reads B)
картина выглядит так:
+-------+ : : : :
| | +------+ +-------+
| |------>| B=2 |----- --->| Y->8 |
| | : +------+ \ +-------+
| CPU 1 | : | A=1 | \ --->| C->&Y |
| | +------+ | +-------+
| | wwwwwwwwwwwwwwww | : :
| | +------+ | : :
| | : | C=&B |--- | : : +-------+
| | : +------+ \ | +-------+ | |
| |------>| D=4 | ----------->| C->&B |------>| |
| | +------+ | +-------+ | |
+-------+ : : | : : | |
| : : | |
| : : | CPU 2 |
| +-------+ | |
| | X->9 |------>| |
| +-------+ | |
Гарантирует, что эффект --> \ ddddddddddddddddd | |
всех операций, предшествующих \ +-------+ | |
записи C наблюдаем последующими ----->| B->2 |------>| |
чтениями +-------+ | |
: : +-------+
Третий: барьер чтения частично упорядочивает операции чтения. Рассмотрим следующую последовательность событий:
CPU 1 CPU 2
======================= =======================
{ A = 0, B = 9 }
ЗАПИСЬ A=1
<барьер записи>
ЗАПИСЬ B=2
ЧТЕНИЕ B
ЧТЕНИЕ A
Без барьеров CPU 2 может наблюдать события, производимые CPU 1 в произвольном порядке, не смотря на использование барьера записи CPU 1:
+-------+ : : : :
| | +------+ +-------+
| |------>| A=1 |------ --->| A->0 |
| | +------+ \ +-------+
| CPU 1 | wwwwwwwwwwwwwwww \ --->| B->9 |
| | +------+ | +-------+
| |------>| B=2 |--- | : :
| | +------+ \ | : : +-------+
+-------+ : : \ | +-------+ | |
---------->| B->2 |------>| |
| +-------+ | CPU 2 |
| | A->0 |------>| |
| +-------+ | |
| : : +-------+
\ : :
\ +-------+
---->| A->1 |
+-------+
: :
Однако, при наличии барьера чтения между чтением B и чтением A на CPU 2,
CPU 1 CPU 2
======================= =======================
{ A = 0, B = 9 }
ЗАПИСЬ A=1
<барьер записи>
ЗАПИСЬ B=2
ЧТЕНИЕ B
<барьер чтения>
ЧТЕНИЕ A
частичный порядок, обеспеченный CPU 1, будет наблюдаем CPU 2 правильно:
+-------+ : : : :
| | +------+ +-------+
| |------>| A=1 |------ --->| A->0 |
| | +------+ \ +-------+
| CPU 1 | wwwwwwwwwwwwwwww \ --->| B->9 |
| | +------+ | +-------+
| |------>| B=2 |--- | : :
| | +------+ \ | : : +-------+
+-------+ : : \ | +-------+ | |
---------->| B->2 |------>| |
| +-------+ | CPU 2 |
| : : | |
| : : | |
Барьер чтения гарантирует -> \ rrrrrrrrrrrrrrrrr | |
что эффект всех операций \ +-------+ | |
предшествующих записи B ---->| A->1 |------>| |
наблюдаем на CPU 2 +-------+ | |
: : +-------+
Барьеры чтения и load speculation.
Многие процессорные архитектуры могут выполнять чтение из памяти заранее: в случаях, когда процессор видит команду чтения из памяти в конвейере и не использует внешнюю шину для других команд, команда на чтение может быть выдана заранее — даже если поток выполнения команд не добрался до инструкции чтения. Это даёт возможность инструкции чтения завершиться очень быстро, поскольку к моменту её выполнения процессор может уже получить прочитанное из памяти значение.
Может случиться, что прочитанное значение не понадобится — например, если команда перехода встретится раньше команды чтения. В таких случаях прочитанное значение будет отброшено или сохранено в кеше.
Рассмотрим следующий пример:
CPU 1 CPU 2
======================= =======================
ЧТЕНИЕ B
ДЕЛЕНИЕ } Команды деления, обычно,
ДЕЛЕНИЕ } совсем не быстро выполняются
ЧТЕНИЕ A
который может генерировать следующие команды:
: : +-------+
+-------+ | |
--->| B->2 |------>| |
+-------+ | CPU 2 |
: :ДЕЛЕНИЕ| |
+-------+ | |
Процессор занят делением, ---> --->| A->0 |~~~~ | |
но заранее выдаёт команду +-------+ ~ | |
на чтение A : : ~ | |
: :ДЕЛЕНИЕ| |
: : ~ | |
По окончании деления процессор --> : : ~-->| |
выполняет команду чтения и : : | |
получает результат немедленно : : +-------+
Помещение барьера чтения или зависимости по данным перед второй операцией чтения
CPU 1 CPU 2
======================= =======================
ЧТЕНИЕ B
ДЕЛЕНИЕ
ДЕЛЕНИЕ
<барьер чтения>
ЧТЕНИЕ A
вынудит процессор пересмотреть заранее прочитанное значение, в зависимости от использованного типа барьера. Если заранее прочитанная область памяти не менялась, значение будет использовано:
: : +-------+
+-------+ | |
--->| B->2 |------>| |
+-------+ | CPU 2 |
: :ДЕЛЕНИЕ| |
+-------+ | |
Процессор занят делением, ---> --->| A->0 |~~~~ | |
но заранее выдаёт команду +-------+ ~ | |
на чтение A : : ~ | |
: :ДЕЛЕНИЕ| |
: : ~ | |
: : ~ | |
rrrrrrrrrrrrrrrr~ | |
: : ~ | |
: : ~-->| |
: : | |
: : +-------+
однако, если область памяти была перезаписана другим процессором, заранее прочитанное значение будет отброшено и команда чтения будет выдана повторно:
: : +-------+
+-------+ | |
--->| B->2 |------>| |
+-------+ | CPU 2 |
: :ДЕЛЕНИЕ| |
+-------+ | |
Процессор занят делением, ---> --->| A->0 |~~~~ | |
но заранее выдаёт команду +-------+ ~ | |
на чтение A : : ~ | |
: :ДЕЛЕНИЕ| |
: : ~ | |
: : ~ | |
rrrrrrrrrrrrrrrrr | |
+-------+ | |
Заранее прочитанное значение ---> --->| A->1 |------>| |
отброшено и прочитано повторно +-------+ | |
: : +-------+
Явные барьеры в ядре.
В Linux имеются следующие типы барьеров, действующие на разных уровнях:
- Барьеры компилятора.
- Барьеры процессора.
- Барьеры записи в области ввода/вывода отображённые в память (MMIO).
Барьеры компилятора.
Явный барьер компилятора предотвращает перемещение операций доступа к памяти компилятором с одной стороны барьера на другую:
barrier();
Это единственный барьер уровня компилятора.
Барьер компилятора не оказывает никакого эффекта на поведение процессора, который может переупорядочивать операции доступа к памяти по своему усмотрению.
Барьеры процессора.
Следующие 8 функций представляют собой барьеры процессора в Linux:
Тип Безусловный Только для SMP
===================== ======================= ===========================
любой доступ mb() smp_mb()
запись wmb() smp_wmb()
чтение rmb() smp_rmb()
зависимость по данным read_barrier_depends() smp_read_barrier_depends()
Все барьеры уровня процессора, за исключением барьера зависимости по данным, включают в себя барьер компилятора.
Замечание: в случае зависимости по данным можно было бы ожидаеть, что компилятор организует инструкции чтения в правильном порядке (например, a[b] сначала прочтёт значение b, а потом — a[b]), однако стандарт языка С не даёт такой гарантии.
При компиляции однопроцессорного ядра, SMP-версии барьеров превращаются в барьеры компилятора, потому что один процессор всегда наблюдает собственные операции с памятью в правильном порядке.
Замечание: SMP-барьеры должны использоваться для управления порядком операций с разделяемой памятью в SMP-системах, но на деле достаточно использования блокирующих примитивов синхронизации.
Безусловные барьеры не следует использовать для управления эффектами SMP, поскольку это приводит к снижению производительности на однопроцессорных системах. Их основная область использования — упорядочивание операций доступа к устройствам ввода/вывода отображаемым в память.
Барьеры записи в области ввода/вывода отображённые в память (MMIO).
Следующая функция представляет собой барьер записи в область ввода/вывода отображённого в память:
mmiowb();
Эта функция является вариантом обязательного барьера записи и обеспечивает частичное упорядочивание операций записи в регион MMIO. Её эффект может простираться вглубь за границу интерфейса между процессором и подсистемой памяти.
Эффекты процессорного кеша.
То, как операции над кешируемой памятью наблюдаются компонентами системы во многом зависит от кеша, расположенного между процессором и памятью и системы поддержания его когерентности.
С точки зрения рассматриваемых барьеров доступа к памяти, процессорный кеш и система поддержания его когерентности являются частью системной памяти; эффект барьеров доступа к памяти проявляется на границе, изображённой пунктирной линией на диаграмме:
<--- CPU ---> : <----------- Память ----------->
:
+--------+ +--------+ : +--------+ +-----------+
| | | | : | | | | +--------+
| Ядро | |Очередь | : | Кеш | | | | |
| CPU |--->|доступа |----->| CPU |<-->| | | |
| | |к памяти| : | | | |--->| Память |
| | | | : | | | | | |
+--------+ +--------+ : +--------+ | | | |
: | Механизм | +--------+
: | поддержки |
: | когерент- | +--------+
+--------+ +--------+ : +--------+ | ности | | |
| | | | : | | | кеша | | |
| Ядро | |Очередь | : | Кеш | | |--->| Устрой-|
| CPU |--->|доступа |----->| CPU |<-->| | | ство |
| | |к памяти| : | | | | | |
| | | | : | | | | +--------+
+--------+ +--------+ : +--------+ +-----------+
:
:
Хотя операции обращения к памяти могут быть выполнены процессором без обращения ко внешней шине, например из кеша, для остальных процессоров системой поддержки когерентности кеша по-прежнему поддерживается видимость того, что межпроцессорное взаимодействие происходит через внешнюю память, посредством миграции строк кеша к которым осуществляется доступ.
Процессорное ядро выполняет инструкции в том порядке, который ему удобен, гарантируя при этом сохранение причинно-следственных связей в выполняемой программе. Некоторые инструкции генерируют запросы чтения или записи, которые помещаются в очередь запросов к подсистеме памяти. Процессорное ядро помещает их в очередь в подходящем порядке и продолжает выполнение, до тех пор пока ему не понадобится получить результат какой-либо из этих инструкций.
Барьеры доступа к памяти контролируют порядок, в котором запросы переходят со стороны процессора на сторону памяти, а так же наблюдаемость эффектов операций, производимых над памятью другими компонентами системы.
