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

В предыдущей статье мы рассмотрели простейшую архитектуру современной многопроцессорной системы. Рассматривая оную, мы столкнулись с понятием барьеров памяти, которые в общих чертах и описали. Чего явно недоставало в предыдущей статье, так это подробностей, касательно барьеров памяти. Что за “оптимизирующий сущности”, что на самом деле делает барьер, какие типы барьеров существуют, кроме тех, что были упомянуты? На все эти вопросы настоящая статья и призвана ответить. После прочтения оной у вас должно сложится устойчивое понимание того, что же такое барьеры памяти и почему они необходимы. Не в абстрактном(с этим должна была справиться предыдущая статья), а в максимально приближенном к реальным деталям виде. Почему только “максимально приближенном”? Потому что процессорных архитектур на рынке много и рассмотреть каждую не представляется возможным, поэтому мы рассмотрим максимально общую картину, которая поможет нам лучше понять природу барьеров памяти.

Оптимизирующие сущности

Итак, в предыдущей статье часто упоминались некие “оптимизирующие сущности”, которые придут и испортят наш код. Я сознательно не стал конкретизировать в прошлый раз, чтобы не раздувать и без того не малую статью. Сейчас же настало время рассмотреть некоторые сущности, которые нарушают строгую гармонию, наступившую благодаря появлению когерентности кэша.

Компилятор и внеочередное исполнение

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

int first = 10;
int second = 20;
int third = 0;
first++;//№1 независимая 
second++;//№2 независимая 
third++;//№3 независимая 
third = first + second;//№4 зависит от №1 и №2

строки 1, 2 и 3 независимы и, следовательно, компилятор может исполнить их в любом порядке. Более того, т.к. значение third будет заменено строкой №4, то строка №3 не имеет никакого значения, и компилятор выкинет эту строчку из результирующего кода вообще. Единственная зависимость в вышеприведённом коде это строка №4 – она зависит от значений first и second, следовательно строки №1 и №2 могут быть выполнены в любом порядке, но совершенно точно, они будут выполнены до строки №4. Это гарантирует нам стандарт C++, и компилятор подчиняется.

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

Исходя из вышесказанного уже должно быть понятно, что подобные вольности компилятора и процессора не оставляют никаких шансов для сколь бы то ни было внятного анализа меж-поточного кода. К счастью, как мы уже говорили в предыдущей статье, нас спасают барьеры памяти. В случае компилятора и внеочередного исполнения, барьеры памяти указывают компилятору и ЦП, что они не могут менять порядок инструкций согласно типу барьера(мы рассматривали это в предыдущей статье: компилятор может передвигать инструкции согласно только зелёным стрелкам, хотя на деле, барьер любого типа будет полным для компилятора, скорее всего). Так, воспользовавшись псевдокодом, мы можем превратить предыдущий недетерминированный код во вполне детерминированный, последовательный код, который будет не просто иллюзорно-последовательным,- он именно, что будет последовательным:

int first = 10;
int second = 20;
int third = 0;
first++;//№1 независимая 
full_barrier();
second++;//№2 независимая 
third++;//№3 независимая 
third = first + second;//№4 зависит от №1 и №2

Компилятор всё равно выкинет №3, но все остальное будет выполнено последовательно.

Вопрос на засыпку, как заставить компилятор оставить №3 в покое?

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

Хочется немного уточнить, насчёт внеочередного исполнения,- лично мне не известна архитектура, в которой внеочередное исполнение может помешать детерминированности, поэтому влияние барьеров на внеочередное исполнение это скорее теория, чем практика. В этом просто нет смысла, на тех архитектурах, с которыми я знаком. Если вы знаете другие примеры, я был бы рад комментариям. Компилятор же, напротив, будет “мешать” на любой архитектуре.

Буфер записи

Следующей сущностью, уже подрывающей MESI, является буфер записи(рекомендую освежить знания, если вдруг забыли). Так вот, буфер записи является настоящим тяжеловесом в деле подрыва MESI и вот почему: давайте вспомним, что же происходит, когда процессор желает записать данные в линию кэш, которую он разделяет с другим процессором. Так вот, сначала он отправляет сообщение, чтобы сделать недействительными кэш-линии других процессоров, а сам меняет её состояние в модифицированное, после чего обновляет данные в кэш-линии. Т.к. процессор может не иметь кэш линии в своём распоряжении в текущий момент, он должен будет загрузить её из памяти . Всё это время процессору придётся простаивать; естественно, что это подрывает производительность, поэтому так никто(?) не делает. В процессор добавляют буфер записи, который позволяет оптимизировать процесс. Поэтому процессоры, имеющие буфер записи, поступают по другому:

  1. Пишут данные, которые хотят записать, в буфер записи.
  2. Запрашивают кэш-линию из памяти
  3. Получают кэш-линию из памяти
  4. По наступлению какого-либо события(зависит от процессора) записывают данные из буфера записи в кэш, тем самым инициируя начало протокола MESI.

Так вот, сразу по завершении шага 1 процессор ведёт себя так, как будто вся кэш линия уже записана и, соответственно, ничего не ждёт и работает как ни в чём не бывало. То есть продолжает исполнение следующих инструкций. Это очень удобно, ведь процессор не ждёт ничего и никого, а продолжает заниматься своим делом.

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

int first = 0;
int second = 0;
int third = 0;
...// Много кода
first = 42;
third = 35;
second = 45;

Так уж вышло, что first и second поместились в одну кэш-линию, тогда как third пришлось идти в следующую. Теперь, условившись, что инструкции исполняются в строгом порядке, мы имеем следующую картину:

  1. Процессор помещает “first = 42” в буфер записи.
  2. Процессор помещает “third = 35” в следующую строку буфера записи.
  3. Процессор может поместить “second = 45” в третью строку, но он этого не делает, т.к. first и second лежат в одной кэш линии и было бы логичным совместить их запись.

Таким образом состояние буфера записи, согласно вышеописанным шагам, можно изобразить следующим образом:

Карта состояний буфера записи

Теперь, когда очередь дойдёт до опустошения буфера записи, очевидно, что изменения в second появятся в кэше раньше, чем изменения в third. Безусловно, для самого процессора это не имеет никакого значения, зато имеет огромное значение для его соседей.

Давайте рассмотрим, что это может означать для простых смертных. Пусть у нас есть следующий код:

bool sharedFlag = false;
bool anotherSharedFlag = false;
...
long long sharedData = 0;
 
void thread1()
{
    anotherSharedFlag = true;
    sharedData = 555;
    compiler_full_barrier();
    sharedFlag = true;
}
 
void thread2()
{
    while(!sharedFlag);
    compiler_full_barrier();
    assert(sharedData == 555);
}

Как вы можете видеть, вооружившись знаниями из предыдущего параграфа, мы исключили зловредное влияние компилятора, отменив перестановку инструкций оным. Условимся в следующем:

  • Мы имеем дело с буфером записи, поддерживающем слияние.
  • sharedFlag и anotherSharedFlag находятся в одной линии кэш, тогда как sharedData находится в другой линии кэш.
  • thread1() исполняется на ЦП1, а thread2() на ЦП2.
  • ЦП1 не содержит sharedData и sharedFlag(anotherSharedFlag) в своём кэше, тогда как ЦП2 содержит обе кэш-линии.

Вышеозначенный код может иметь следующую последовательность исполнения:

  1. ЦП1 помещает инструкцию “anotherSharedFlag = true” в буфер записи.
  2. ЦП1 помещает инструкцию “sharedData = 555” в буфер записи.
  3. ЦП1  помещает инструкцию “sharedFlag = true” в буфер записи, помещая её в уже существующую запись с anotherSharedFlag.
  4. ЦП1 решает, что пора бы освободить одну из ячеек буфера записи и, следовательно, записывает кэш-линию, содержащую sharedFlag и anotherSharedFlag.
  5. ЦП1 меняет состояние кэш-линии на “модифицированное” и посылает сигнал ЦП2, чтобы он сделал недействительной линию кэш, содержащую sharedFlag
  6. ЦП2 получает сигнал и делает линию недействительной.
  7. ЦП2 загружает значение sharedFlag для проверки в цикле while. Этот запрос имеет результатом кэш-промах, в результате чего запрос пробрасывается в память, что вынуждает ЦП1 записать значение sharedFlag в память. sharedData всё еще находится в буфере записи!
  8. ЦП2, убедившись, что sharedFlag выставлен в true, прерывает цикл.
  9. ЦП2 загружает значение sharedData для проверки в assert. Т.к. sharedData содержится в кэше ЦП2, то он просто загружает его оттуда.
  10. ЦП2 проверяет значение в assert и он срабатывает, т.к. мы имеем старое значение sharedData!

Карта состояний процессоров

Как можно видеть из вышеописанного примера, введение буфера записи “сломало” MESI, и мы больше не можем говорить о детерминированности поведения, т.к. в одном случае assert сработает, а в другом  нет. У нас нет контроля над этим и всё это зависит лишь от провидения(внешних, по отношению к программисту, сущностей). Разумеется, как мы уже говорил ранее, в данном случае, нас спасут барьеры памяти. Изменяем код на следующий:

bool sharedFlag = false;
bool anotherSharedFlag = false;
...
long long sharedData = 0;
 
void thread1()
{
    anotherSharedFlag = true;
    sharedData = 555;
    full_barrier();
    sharedFlag = true;
}
 
void thread2()
{
    while(!sharedFlag);
    compiler_full_barrier();
    assert(sharedData == 555);
}

Мы изменили compiler_full_barrier() на полноценный full_barrier() в том месте, которое пострадало от введения буфера записи. Полный барьер в буквальном смысле заставляет процессор опустошить буфер записи в том месте, где он встречается. Теперь, как мы можем видеть, и sharedData, и anotherSharedFlag окажутся записанными в кэш-линию до того, как sharedFlag попадёт в буфер записи. Ну а когда sharedFlag попадёт в кэш мы будем абсолютно уверены в том, что кэш содержит последние значения sharedData и anotherSharedFlag, и что соседние процессоры уведомлены об этом. Всё это гарантирует нам правильность исполнения и никогда не срабатывающий assert.

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

Очередь событий

Итак, ещё раз вернёмся к описанию того, что же нужно сделать процессору, чтобы записать данные в разделяемую кэш-линию:  “Сначала ЦП отправляет сообщение, чтобы сделать недействительными кэш-линии других процессоров, соответственно другие процессоры, получившие это сообщение, делают свои кэш-линии недействительными немедленно.”. Мы уже рассмотрели, что с введением буфера записи, процессор освобождается от ожидания и может рассылать свои сообщения с ощутимой задержкой, относительно реального изменения данных. Теперь давайте посмотрим, что же происходит на другой стороне.

  1. ЦП2 тихо-мирно исполняет инструкции своего потока.
  2. ЦП2 получает сообщение от ЦП1.
  3. ЦП2 сломя голову несётся выполнять инструкция, содержащуюся в сообщение от ЦП1.

Надо понимать, что траффик между процессорами может быть весьма существенным и у ЦП2 никаких нервов не хватит постоянно прерывать свои текущие дела и исполнять инструкции от ЦП1. Тем более, что ЦП1, используя буфер записи, отправляет сообщения тогда, когда ему будет удобно, тогда как ЦП2 должен реагировать немедленно. Здесь попахивает нарушением равноправия, а, как мы знаем, Западный мир очень болезненно это воспринимает(ну а современные процессоры это продукт Западного мира, как правило). Чтобы исправить ситуацию, можно рассмотреть параллель из мира людей: если вы большой босс, то вы можете позволить себе секретаря, который будет получать корреспонденцию, отвечать корреспондентам(по необходимости) и передавать вам всю кипу писем тогда, когда вы сочтёте нужным обратить на неё внимание. Так вот, ЦП это тоже большой босс и он тоже может иметь “секретаря”.

Чтобы постоянно не прерывать ЦП на то, чтобы отреагировать на сообщения от других ЦП, вводят специальную сущность – очередь событий. Вся суть её заключается в том, что она агрегирует сообщения от других ЦП, мгновенно отвечая им так, как будто бы сам ЦП исполнил их просьбу(если ответ вообще нужен). При этом, сам ЦП вообще не догадывается, что ему пришло какое-то сообщение. Это позволяет значительно освободить процессор от постоянных “дёрганий”, что даёт ему возможность сосредоточится на своей непосредственной задаче – исполнении инструкций потока.

Название “очередь сообщений” это моё “изобретение”. Я нигде не нашёл канонического именования подобной сущности, но в иностранной литературе вы можете встретить “invalidation queue”, что, на мой взгляд, слишком сужает предназначение оной и не отражает в полной мере настоящее положение дел.

Теперь давайте вернёмся к нашему примеру из параграфа, посвящённого буферу записи(условия те же, что и там):

bool sharedFlag = false;
bool anotherSharedFlag = false;
...
long long sharedData = 0;
 
void thread1()
{
    anotherSharedFlag = true;
    sharedData = 555;
    full_barrier();
    sharedFlag = true;
}
 
void thread2()
{
    while(!sharedFlag);
    compiler_full_barrier();
    assert(sharedData == 555);
}

События могу развиваться следующим образом:

  1. ЦП1 помещает инструкцию “anotherSharedFlag = true” в буфер записи.
  2. ЦП1 помещает инструкцию “sharedData = 555” в буфер записи.
  3. ЦП1 встречает полный барьер и, следовательно, вынужден опустошить буфер записи и записать данные в кэш.
  4. ЦП1 посылает 2 сигнала, касательно 2-х кэш линий, чтобы остальные процессоры сделали эти линии не действительными.
  5. ЦП2 получает оба сигнала и помещает их в очередь событий
  6. ЦП1  записывает “sharedFlag = true” прямиком в кэш, т.к. соответствующая линия уже содержится в оном. Ещё раз посылает сигнал касающийся этой кэш-линии.
  7. ЦП2 ещё раз помещает идентичный сигнал в очередь(возможно отбрасывает новый сигнал, т.к. старый уже есть, это не существенно).
  8. ЦП2 решает, что пришло время освободить одну позицию в очереди событий. Он извлекает одно событие(сигнал касательно линии кэш, содержащей anotherSharedFlag и sharedFlag) и исполняет его. Это приводит к тому, что он вынужден сбросить эту кэш-линию в недействительное состояние.
  9. ЦП2 загружает значение sharedFlag для проверки в цикле while. Этот запрос имеет результатом кэш-промах, в результате чего запрос пробрасывается в память, что вынуждает ЦП1 записать значение sharedFlaganotherSharedFlag) в память.
  10. ЦП2, убедившись, что sharedFlag выставлен в true, прерывает цикл. Сообщение, о том, что кэш-линия содержащая sharedData должна быть переведена в недействительно состояние, всё ещё томится в очереди событий ЦП2!
  11. ЦП2 загружает значение sharedData для проверки в assert. Т.к. он имеет sharedData в своём кэше он просто загружает значение оттуда.
  12. ЦП2 проверяет значение в assert и он срабатывает, т.к. мы имеем устаревшее значение sharedData!

Карта состояний процессоров

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

bool sharedFlag = false;
bool anotherSharedFlag = false;
...
long long sharedData = 0;
 
void thread1()
{
    anotherSharedFlag = true;
    sharedData = 555;
    full_barrier();
    sharedFlag = true;
}
 
void thread2()
{
    while(!sharedFlag);
    full_barrier();
    assert(sharedData == 555);
}

Дело в том, что полный барьер не только заставляет опустошить буфер записи, он также вынуждает процессор опустошить и очередь событий! Именно это заставляет код выше отработать правильно, ведь sharedFlag появляется “в миру” позже sharedData, а это значит, что коль скоро ЦП2  узнал, что sharedFlag выставлен в true и опустошил очередь событий(full_barrier()) , то sharedData гарантировано будет иметь значение 555. Это гарантируется тем, что сигнал касающийся sharedData предшествовал сигналу касающемуся sharedFlag, а это значит, что оба сигнала должны были быть в очереди событий(либо сигнал касательно sharedData  уже был извлечён), когда был извлечён сигнал о sharedFlag. Но последующий полный барьер гарантирует, что очередь пуста, а это значит, что сигнал о sharedData гарантированно был получен ЦП2, что, в свою очередь, вынуждает ЦП2 запросить последнее значение sharedData  из памяти.

Резюме

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

Классификация барьеров

Пришла пора немного структурировать ранее полученные знания о барьерах, чтобы лучше в них ориентироваться. Безусловно, я не могу привести все возможные типы барьеров т.к. это зависит лишь от фантазии инженеров, работающих с той или иной архитектурой. Я приведу лишь наиболее распространённые типы. Для начала давайте расс��отрим 4 комбинации перестановок чтения(load) и записи(store), которые могут быть использованы для запрета этих самых перестановок(этакие мини барьеры, или составные части барьеров):

  • LoadLoad – Все операции чтения, встреченные до барьера должны быть выполнены до операций чтения, находящихся за барьером. Таким образом перестановки между операциями чтения сквозь барьер запрещены. Не влияет на операции записи.
  • LoadStore – Все операции чтения, встреченные до барьера должны быть выполнены до операций записи, находящихся за барьером. Никаких ограничений на перестановку между операциями чтения или операциями записи не накладывается.
  • StoreLoad – Все операции записи, встреченные до барьера, должны быть выполнены до операций чтения, находящихся за барьером. Никаких ограничений на перестановку между операциями чтения или операциями записи не накладывается.
  • StoreStore – Все операции записи, встреченные до барьера, должны быть выполнены до операций записи, находящихся за барьером. Таким образом перестановки между операциями записи сквозь барьер запрещены. Не влияет на операции чтения.

Теперь давайте рассмотрим, что мы можем сконструировать из вышеприведённых частей.

Полный барьер

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

Влияние на оптимизирующие сущности

Компилятор

Запрещает перемещать инструкции, находящиеся до барьера, после него и наоборот.

Буфер записи

Очищает буфер записи, исполняя каждую извлечённую запись.

Очередь событий

Очищает очередь, исполняя каждую извлечённую запись.

Полный барьер

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

Т.к. полный барьер запрещают любые перестановки он, в теории, состоит из всех вышеозначенных блоков: LoadLoad + LoadStore + StoreLoad + StoreStore. Почему недостаточно LoadLoad + StoreStore? Потому что такой барьер не запрещает перестановку между чтением и записью.

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

Барьер записи

Ещё один знакомый нам барьер. Барьер записи предназначен для предотвращения перемещения операций записи сквозь него.

Влияние на оптимизирующие сущности

Компилятор

Запрещает перемещать инструкции записи, находящиеся до барьера, после него и наоборот.

Буфер записи

Очищает буфер записи, исполняя каждую извлечённую запись.

Очередь событий

Не влияет на очередь событий.

Барьер записиКак видно из таблицы выше, барьер записи влияет на буфер записи и не влияет на очередь событий. Это вполне логично, ведь именно буфер записи отвечает за “подтасовку” записи. Таким образом, в примере, который мы использовали ранее, мы заменим full_barrier() в thread1() на write_barrier(), выигрывая, при этом, в производительности, т.к. теперь мы не будет очищать очередь событий тогда, когда нам этого не требуется:

void thread1()
{
    anotherSharedFlag = true;
    sharedData = 555;
    write_barrier();
    sharedFlag = true;
}

В терминах строительных блоков барьер записи является StoreStore барьером. Никаких других гарантий он не даёт.

Барьер чтения

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

Влияние на оптимизирующие сущности

Компилятор

Запрещает перемещать инструкции перемещения, находящиеся до барьера, после него и наоборот.

Буфер записи

Не влияет на буфер записи.

Очередь событий

Очищает очередь, исполняя каждую извлечённую запись.

Барьер чтенияКак и в случае с барьером записи можно увидеть, что барьер записи является “облегчённой” версией полного барьера, которая позволяет снизить нагрузку на система, не трогая буфер записи, когда он не нужен. И наш пример как раз имеет такое место в thread2():

bool sharedFlag = false;
bool anotherSharedFlag = false;
...
long long sharedData = 0;
 
void thread1()
{
    anotherSharedFlag = true;
    sharedData = 555;
    write_barrier();
    sharedFlag = true;
}
 
void thread2()
{
    while(!sharedFlag);
    read_barrier();
    assert(sharedData == 555);
}

Вуаля! Теперь мы имеем ровно те барьеры памяти, который нам жизненно необходимы и не платим ничего сверху. Это действительно может дать значительный прирост производительности на некоторых архитектурах. Да и вообще, любой барьер, который даёт меньше гарантий, как правило, будет давать преимущества на тех архитектурах, которые могут использовать его эффективно.

Барьер для зависимых данных

Давайте представим себе банальную ситуацию:

int first = 0;
int second = 0;
int* pointer = nullptr;
//...

void thread1()
{
    first = 55;
    write_barrier();
    pointer = &first;
}

void thread2()
{
    while(pointer == nullptr)
        ;
    assert(*pointer == 55);
}

Казалось бы, всё здесь нормально – коли pointer не равен нулю, то это означает, что то, на что он указывает должно содержать 55. Ведь мы гарантировали это барьером записи! Так то оно так, да вот не совсем. Как я уже говорил, человеческая логика не всегда работает в отношении компьютеров и для того, чтобы вышеозначенный код работал, на архитектуру процессора должно быть наложено одно ограничение: зависимые обращения к памяти должны исполнятся в строгом порядке. Если вспомнить, что такое указатель, то можно записать вышеозначенный код в thread2() следующим псевдокодом:

condition: 
mov rax, [pointer]
cmp rax, 0
je condition
mov rbx, [rax]
mov rcx, 55
cmp rbx, rcx
jne assert
... 

Зависимые(не все) строчки в коде выше подсвечены. Так вот, чтобы C++ псевдокод из примера выше работал как надо, процессор должен взять на себя обязательства исполнять зависимые инструкции поочередно. Но ведь это же очевидно, как может быть по другому? Разумеется, в рамках одного потока о другом и речи быть не может – иначе это было бы нарушением фундаментальных принципов. Другое дело когда потоков у нас 2. Чтобы понять как может быть нарушено простое правило, давайте рассмотрим вышеозначенный код с немного другой позиции.

Что такое переменная указателя? По сути, это две переменные одна(сам указатель) содержит адрес некой ячейки памяти, другая – та самая ячейка. Блок памяти, в котором содержится указатель и блок памяти, в котором содержится то, на что этот указатель указывает могут находится в разных кэш линиях. Ничего эта ситуация не напоминает?
Исходные условия:

  • У нас есть 2 ЦП, у каждого есть буфер записи и очередь событий
  • pointer и *pointer находятся в разных линиях кэш.
  • thread1() исполняется на ЦП1, а thread2() на ЦП2.
  • ЦП1 содержит first и pointer в своём кэше, тогда как ЦП2 содержит только first.

Следующая последовательность исполнения инструкций может иметь место:

  1. ЦП1 помещает first в буфер записи
  2. ЦП1, встретив барьер записи, опустошает буфер записи и посылает сигнал о недействительности линии кэш, содержащей first, соседним процессорам.
  3. ЦП2 получает сигнал и помещает его в очередь
  4. ЦП1 записывает адрес first в pointer прямиком в кэш, т.к. он имеет эту линию в эксклюзивном состоянии
  5. ЦП2 запрашивает значение pointer в кэше, но получив промах запрашивает оное в памяти. Это вынуждает ЦП1 отклонить этот запрос, записать новое значение pointer в память, после чего ЦП2 получает последнее значение pointer. ЦП2 не имел шанса опустошить очередь событий на данный момент!
  6. ЦП2 прерывает цикл, т.к. видит, что pointer больше не nullptr.
  7. ЦП2 запрашивает значение ячейки, на которую ссылается pointer. Так как по условию first содержится в кэш, а по результатам исполнения сигнал о недействительности томится в очереди, ЦП2 берёт старое значение first из своего кэша.
  8. assert срабатывает!

Если кто ещё не понял, то ситуация абсолютно идентична той, что мы рассматривали в параграфе посвященном очереди событий. Только здесь мы имеем зависимые сущности, тогда как там были сущности независимые. Ну тогда и решение из того параграфа нам подойдёт? Безусловно:

void thread2()
{
    while(pointer == nullptr)
        ;
    read_barrier();
    assert(*pointer == 55);
}

Всё, проблема решена – расходимся. Стоп, к чему тогда весь этот параграф? Дело в том, что абсолютное большинство процессоров гарантируют, что вышеприведенный код будет работать и без барьера чтения, т.к. они гарантируют, что зависимые операции с памятью не могут быть переставлены. Более того, согласно интернету единственным процессором, который этого не гарантирует является DEC Alpha.

Но если все другие гарантируют корректное поведение, тогда получается, что мы зря поставили барьер чтения, который далеко не бесплатен!? Всё верно, поэтому специально для Alpha и его наследников(не приведи Танненбаум) появился специальный барьер – барьер чтения для зависимых данных. Поэтому код выше мы изменим на следующий:

void thread2()
{
    while(pointer == nullptr)
        ;
    read_data_dependency_barrier();
    assert(*pointer == 55);
}

Теперь для всех “нормальных” процессоров read_data_dependency_barrier() превратиться в пустое место, тогда как для Alpha это будет полноценный барьер, который гарантирует корректность исполнения. Можно считать, что данный вид барьера является барьером чтения для тех, кому он нужен(Alpha) и пустой операцией для всех остальных. Поэтому никаких таблиц и картинок для этого барьера не будет – они идентичны оным для барьера чтения.

Зачем рассматривать особенности дышащего на ладан процессора, спросите вы? Затем, что это процессор с наименее строгой моделью памяти, и комитет по стандартизации C++ отталкивался именно от наименее строгой гарантии, разрабатывая модель памяти C++. Более подробно об этом мы поговорим в следующей статье.

Особые барьеры

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

Барьер захвата(acquire)

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

Барьер овладения

Как вы можете видеть данный вид барьера препятствует выходу операций за барьер “вверх”, но не препятствует проникновению оных сверху вниз.

В терминах строительных блоков, данный барьер можно представить как LoadLoad+LoadStore. “Но этого недостаточно!” – может воскликнуть внимательный читатель. Действительно, недостаточно, поэтому данный вид барьера всегда работает в паре.

Барьер освобождения(release)

Данный вид барьера схож со своим собратом. Разница лишь в том, что он не пропускает операции с памятью через барьер “вниз”:

Барьер освобождения

Итак, барьер освобождения не даёт операциям выйти за барьер вниз, но не мешает им заскакивать снизу вверх. Реализация в терминах строительных блоков может быть выполнена с использованием LoadStore+StoreStore.

Теперь давайте представим, что у нас есть следующий код:

acquire_barrier();
sharedData = 10;
sharedDataReady = true;
release_barrier();

На что это похоже? А если совместить картинку двух барьеров и между ними положить код? Правильно, это же мьютекс из прошлой статьи! Действительно, данная пара барьеров формирует между собой критическую секцию. Наличие пары барьеров захвата/освобождения гарантирует, что всё, что было записано до барьера освобождения, будет видно после барьера захвата. Таким образом, получается, что между барьером освобождения и следующим за ним барьером захвата формируется следующая последовательность: LoadLoad+LoadStore+StoreStore, что в свою очередь является почти  полным барьером. Но это только “почти” – не хватает StoreLoad, блока, который, на сколько мне известно, является наиболее затратным в современных процессорах.

Разумеется, мы могли бы использовать пару захвата/освобождения вместо пары барьеров чтения/записи, в используемых нами ранее примерах. Т.е. семантика подходящая, но вот цена выше, т.к. барьеры захвата/освобождения “стоят” дороже. Теперь, я полагаю, должна быть ясна логика выделения этих барьеров в отдельный параграф – они работают только в паре и, по сути, бесполезны поодиночке. Этакий специальный тандем, для реализации мьютексо-подобных сущностей.

Итог

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

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


Полезные материалы, в которых можно почитать про барьеры дополнительно(на английском):