Продолжая тему, начатую в предыдущей статье, в настоящей статье мы рассмотрим взаимодействие уже много-процессорной архитектуры с памятью. Чтобы немного сузить сферу обсуждения, под много-процессорной моделью мы будем понимать несколько ядер(core) на одном кристалле. Таким образом мы не будем рассматривать системы, в которых установлены несколько физических процессоров(ядра тоже есть физические процессоры, просто термины подобраны не очень удачно). Более того, т.к. в общем случае архитектурных отличий между 2-х процессорной системой и, скажем, 16-и процессорной не существует, в настоящей статье мы будем рассматривать только 2-х процессорные системы, подразумевая, естественно, n-процессорные системы. Конечно, тема, которая затронута в настоящей статье является крайне большой, сложной и интересной, и я не претендую на всеобъемлющее раскрытые оной. Целью данной статья является поверхностное раскрытие механизмов, которые стоят за феноменом, породившим довольно сложные примитивы программирование многопроцессорных систем, именуемых барьерами памяти(memory barriers, fences).
Прямое взаимодействие
Итак, по аналогии с предыдущей статьёй, настоящую статью мы начнём с рассмотрения прямого соединения процессора с памятью. Правда, в отличии от предыдущей статьи, здесь мы рассмотрим уже 2 процессора соединённые единой шиной с ОЗУ:
Сразу возникает вопрос: “А будет ли достаточно шины, рассмотренной в предыдущей статье, для подобного соединения?”. Разумеется нет и вот почему: т.к. мы имеем два процессора, подсоединённых к одной и той же шине, мы должны гарантировать, что при начале передачи данных(в память или обратно) только один процессор владеет шиной. Если такой гарантии не будет, то система будет неработоспособной, так как каждый процессор будет отдавать и получать случайные данные, получившиеся в следствии смешения данных от/к разных ЦП. Чтобы решить данную проблему нам достаточно добавить всего один вывод в шину: контроль шины.
Когда процессор хочет прочитать/записать память, он проверяет не выставлен ли сигнал контроля шины, и если нет, тогда оный выставляется и начинается работа с памятью. Если же сигнал уже выставлен, тогда процессор вынужден ждать, пока другой ЦП его погасит и только после этого он сможет начать работу с шиной.
Естественно данная схема ужасна: даже для 2–х процессоров производительность деградирует значительно, что уж говорить, когда процессоров на шине будет больше. Тем не менее, в той или иной степени, данная проблема существует во всех современных конфигурациях, правда везде она так или иначе смягчается различными методами. В идеальном варианте у каждого процессора должно быть отдельное соединение с ОЗУ, и ОЗУ должна мочь работать со всеми ЦП параллельно, но, как и всё параллельное, это добавляет не меньше проблем, чем оно решает. Одним из компромиссных вариантов является NUMA-архитектура, которая представляется собой иерархическую модель памяти, при которой у каждого процессора есть свой(не исключительный!), большой кусок ОЗУ. Мы не будем затрагивать NUMA-архитектуру более, а рассмотрим как мы можем смягчить проблему доступа к шине введением кэш-памяти.
Добавляем кэш-память
Само собой разумеется, что массовые многопроцессорные системы, появившиеся позже массовых однопроцессорных, с “пелёнок” использовали кэш-память, поэтому схема изображённая в предыдущем параграфе никогда не имела места(может в истории и был такой случай, но он явно не был связан с массовыми процессорами). Таким образом реальная современная система выглядит примерно так:
С такой схемой каждый процессор будет занимать шину дольше(считывая по одной кэш-линии за раз), но реже(т.к. кэш отработает по назначению). Как и в случае с однопроцессорной системой, более редкое обращение к памяти улучшает общую производительность системы. К сожаление это лишь смягчает проблему, а не убирает её – если уж процессору всё таки нужна коммуникация с ОЗУ, то весьма вероятна ситуация, при которой ему всё так же придётся ждать шины. С другой стороны подобная схему, конечно же, предпочтительнее прямого соединения, т.к. столкновений за шину будет значительно меньше.
Как и в случае с однопроцессорной схемой, кэш-память не является бесплатным удовольствием – у него тоже есть цена, которая частично описана в предыдущей статье. Но, что ещё хуже, эта цена вырастает для многопроцессорных систем, да вырастает так, что существует мнение, что кэш-память это не спасение, а, в некотором роде, проклятье современных систем(мнение, безусловно, спорное, но заслуживающее внимания).
Давайте рассмотрим какие проблемы кэш-память приносит в многопроцессорные системы. Для этого рассмотрим простейший пример с разделяемой переменной, которая используется в двух потоках, которые, в свою очередь, исполняются на разных ЦП одновременно. Пусть переменная хранит цвет, и, согласно своему адресу, значение переменной будет находится в первой линии кэша.
1. Сначала значение переменной находится только в ОЗУ:
2. Затем оба потока загружают переменную к себе в кэш-память.
3. Затем первый поток меняет переменную на один цвет, тогда как второй поток меняет ту же переменную на другой цвет.
4. Через какое-то время(в зависимости от стратегии кэш-памяти) одно из этих двух значений(цветов) будет записано в память(для простоты примем, что первый ЦП записал своё значение позже второго)
Из вышеприведённых картинок должно быть ясно, что происходит что-то не то. Ведь уже на 3-м шаге два потока, используя одну и ту же переменную, получают разный цвет. После 4-го шага один из потоков победит и его значение станет каноническим(т.к. оно попало в ОЗУ и стало там конечным), но другой ЦП об этом даже не узнает! Он продолжит использовать значение, которое он сам же и выставил, не заботясь ни о ком другом! Это явная и грубая ошибка. Самое последнее значение наш горе-ЦП получит лишь в том случае, если очистит кэш-линию, содержащую разделяемую переменную, и загрузит новое значение из памяти позже.
Разумеется, имея такую проблему, кэш-память становится бесполезной – она просто-напросто не удовлетворяет принципу определённости. Чтобы это исправить, в систему должна быть введена синхронизация между кэш-блоками различных ЦП. Такая синхронизация получила название когерентности кэша и её целью является гарантия того, что если разделяемая переменная(разделяемая линия, в терминах кэша) была изменена, то все заинтересованные ЦП узнают об этом и это произойдёт в конечный отрезок времени. Это отчасти решает проблему, т.к. гарантия синхронности кэшей существует, но, в силу ограничений нашего физического мира, всегда будет окно, когда кэш-блоки различных ЦП могут находится в некогерентном состоянии. Кроме того, синхронизация кэшей снижает общую производительность и добавляет головной боли программистам, как мы увидим это далее. Один из наиболее известных и широко используемых протоколов, используемых для синхронизации кэш-блоков, получил название MESI.
Я написал, что кэш-блоки могут находится в некогерентном состоянии, даже при наличии протокола синхронизации. В общем виде, при наличии протокола синхронизации, такое состояние, конечно же, невозможно. Чтобы такое состояние стало возможным нам нужно ввести дополнительные сущности, которые мы рассмотрим в следующей статье. В рамках же данной статьи будем считать, что такое состояние не может случиться, т.к. когерентность кэша нас полностью защищает.
MESI
MESI получил своё название по первым буквам 4-х состояний: Modified(Изменённое), Exclusive(Эксклюзивное), Shared(Разделяемое), Invalid(Недействительное). Где применяются эти состояния? Каждая линия кэш находится в одном из этих состояний:
- Линия является недействительной, если линия не используется, т.е. ЦП не может использовать данные из этой линии т.к. они либо не были загружены ранее, либо являются устаревшими. Если ЦП запрашивает недействительную линию, то происходит загрузка данных из ОЗУ, другими словами происходит кэш-промах.
- Линия является эксклюзивной, если ранее она была загружена из ОЗУ, полностью совпадает с ОЗУ и ни один другой кэш-блок не содержит этой линии в состоянии отличном от недействительного.
- Линия является модифицированной, если она была изменена ЦП, в не зависимости от того, в каком состоянии линия была до этого(эксклюзивном или разделяемым)
- Линия является разделяемой, если она находится в нескольких кэш-блоках, и в каждом из них она совпадает со значением в ОЗУ. Т.е. это состояние схоже с эксклюзивным, с той лишь разницей, что линия принадлежит сразу нескольким ЦП(кэш-блокам).
Имея вышеозначенные 4-е состояния и некоторый набор сообщений, которые заставляют кэш-линию сменить состояние, не составляет труда реализовать когерентность кэш-блоков. Давайте рассмотрим, как два кэш-блока могут взаимодействовать используя MESI.
В начальном состоянии все линии обоих кэш-блоков находятся в недействительном состоянии:
Затем в первый кэш-блок загружается одна линия из ОЗУ и получается следующая картина:
Следующим шагом во второй кэш-блок загружается та же линия, что была загружена в первый кэш-блок на предыдущем шаге. Кроме того, в первый кэш-блок загружается ещё одна линия:
��еперь первый ЦП решает изменить разделяемую кэш-линию, но и второй решает сделать то же самое! В один шаг этого выполнить не получится т.к. протокол MESI подразумевает обработку таких коллизий(он для этого и был придуман, в конце концов).
Итак, решив изменить разделяемую кэш-линию первый ЦП сначала должен уведомить об этом своих товарищей, т.е. первый ЦП рассылает сообщение, что такая-то кэш-линия должна быть помечена как недействительная. В результате разделяемая кэш-линия во втором кэш-блоке становится недействительной:
Т.к. у нас 2 ЦП, которые одновременно решили, что они хотят менять кэш-линию, то успеть может любой. В нашем случае успел первый. Оба успеть не могут, т.к. шина является последовательной сущностью и кто-то всё равно успеет раньше.
Теперь первый ЦП может изменять разделяемую кэш-линию и он это делает, попутно выставляя её состояние в модифицированное:
Не забываем, что второй процессор тоже хотел изменить свою кэш-линию, но она теперь находится в недействительном состоянии, следовательно происходит кэш-промах и он должен запросить эту линию в ОЗУ, что он и делает. И тут происходит самое интересное: первый ЦП, имея запрашиваемую линию в модифицированном состоянии, отвергает запрос второго ЦП к ОЗУ и вместо этого синхронизирует себя с ОЗУ, таким образом записывая требуемую кэш-линию в память: После этого второй ЦП должен повторить свой запрос и получится следующая картина:
Дальше всё будет происходить по той же схеме, что мы видели ранее, поэтому нет смысла плодить те же картинки ещё раз. На мой взгляд всё должно быть понятно.
Таким образом, используя MESI мы гарантируем, что все ЦП будут знать об изменениях, совершенными другими ЦП. Для этого каждый ЦП отправляет широковещательные сообщения, когда совершает какую-либо операцию над кэш-линией. В то же время все ЦП слушают шину, чтобы быть в курсе всех событий. Так, услышав запрос на чтение кэш-линии, ЦП, содержащий эту линию в эксклюзивном состоянии, изменит её состояние на разделяемое. MESI является довольно простым и элегантным решением, но, как вы можете видеть, это решение создаёт довольно обильный трафик и, следовательно, производительность деградирует. У всего есть цена – кто бы сомневался?
Барьеры памяти
Вооружившись полученными знаниями, предлагаю перейти к реальному(пусть и надуманному) примеру. Пусть мы имеем два потока, в которых мы используем некоторую разделяемую структуру и разделяемый же флаг, который сигнализирует о том, что структура была обновлена. При этом второй поток ждёт, пока флаг будет выставлен. Для простоты примем, что в рассматриваемой нами архитектуре запись и чтение переменной типа bool является атомарной операцией. Код:
bool sharedFlag = false;
long long sharedData = 0;
void thread1()
{
sharedData = 555;
sharedFlag = true;
}
void thread2()
{
while(!sharedFlag);
assert(sharedData == 555);
}Теперь давайте разберёмся, может ли условие sharedData == 555 быть ложным, тем самым заставив assert сработать и остановить нашу программу. Пусть условие будет ложным. Т.к. мы дошли до проверки условия, значит, что sharedFlag выставлен в true(т.к. это продиктовано последовательностью исполнения инструкций), а это, в свою очередь значит, что строчка sharedFlag = true; была исполнена в thread1(). Из этого следует, что и число 555 было записано в sharedData. Принимая во внимание наличие MESI мы имеем гарантию того, что для записи 555 в sharedData ЦП1 сначала убедился в том, что никто другой не содержит этой переменной(линии кэш) и лишь затем записал оное. Таким же образом мы имеем гарантию того, что ЦП2 запросил самое последнее значение sharedData.Так как последним значением является 555, то наше предположение ложно и, следовательно, условие всегда будет истинным. Следовательно, assert никогда не сработает.
И на этом можно было бы расходится, но параграф не зря называется “Барьеры памяти”. К сожалению, ситуация описанная выше является нереалистичной в силу различных оптимизаций и ухищрений, которые могут быть использованы на разных уровнях, для увеличения производительности. В общем случае мы не можем делать никаких предположений о последовательном исполнении инструкций, когда речь идёт о нескольких потоках. Т.е. у нас есть гарантия(на уровне языка), что первый поток видит изменения в следующем порядке:
sharedData = 555;
sharedFlag = true;
Но у нас нет никакой гарантии, что второй поток видит эти изменения в этом же порядке. Это не гарантируется ничем. И сделано это сознательно, чтобы разрешить использование различных оптимизационных техник, которые позволяют коду исполнятся быстрее, а значит делать наших пользователей немного счастливее. Естественно, такое положение вещей не может устраивать заинтересованных людей – компьютер должен быть помощником человека, который исполняет указания, а не делает всё, что ему заблагорассудится. Поэтому, разумеется, у программистов есть средства перехода от хаоса, к вполне детерминированному поведению. Такое поведение достигается за счёт введения барьеров памяти(memory fences, barriers, etc.).
Барьеры памяти, по сути, позволяют указать всем сущностям, которые пытаются оптимизировать код(или его исполнение ), что они должны убрать свои руки и забыть об оптимизации. Важно понимать, что барьеры памяти влияют только на порядок инструкций, т.е. они призваны гарантировать порядок исполнения инструкций относительно памяти(ОЗУ, кэш и т.п.). Поэтому, говоря, что они “отменяют” оптимизацию, нужно понимать, что они отменяют оптимизацию, которая пытается изменить порядок исполнения инструкций, которые взаимодействуют с памятью. Ни на какую другую оптимизацию барьеры памяти не влияют! К примеру, если у нас есть 2 инструкции, которые пишут целое число в память и третья инструкция, которая складывает 2 числа(этих или нет – не важно), то действию барьера могут быть подвержены только первые 2 инструкции; 3-я инструкция барьер памяти просто игнорирует. Естественно, барьеры могут быть как полными, так и частичными, имея ввиду то, что они либо отменяют всю возможную оптимизацию, либо отменяют лишь часть оптимизации, оставляя другую часть в действии.
А зачем тогда вообще нужен MESI, если его наличие ничего не гарантирует? На самом деле гарантирует. Гарантирует ровно то, что было описано ранее. Просто с развитием технологий, развиваются и различные ухищрения, которые могут быть использованы в процессорах. Таким образом, MESI(или его аналог) есть всегда, а вот те оптимизации, которые его “подрывают” не всегда. MESI можно считать базовой гарантией работоспособности кэша, барьеры же нужны для обеспечения строгой гарантии на тех архитектурах, которые могут его подрывать. Это обычная ситуация в мире инженеров – сначала решаем проблему(добавили MESI), это приносит другие проблемы(траффик), начинаем решать проблему траффика – это решение приносит свои проблемы и т.д. Этот процесс практически бесконечен. Решения наслаиваются и становятся всё сложнее. Если же каждый доступ к разделяемой переменной будет осуществляться с использованием полного барьера, то все гарантии MESI будут в силе.
Полный барьер
Для начала давайте рассмотрим, что такое полные барьеры и как они влияют на исполнение нашей простенькой программы:
bool sharedFlag = false;
long long sharedData = 0;
void thread1()
{
sharedData = 555;
full_barrier();
sharedFlag = true;
}
void thread2()
{
while(!sharedFlag);
full_barrier();
assert(sharedData == 555);
}
full_barrier() не является существующей функцией; здесь и далее в статье, всё, что связано с барьерами, будет не частью C++, а просто несуществующими функциями. Таким образом код превращается в псевдокод.
С добавлением этих строчек, наше изначальное доказательство начинает действовать – ведь с помощью барьеров мы гарантировали, что вся возможная оптимизация, которая могла бы поменять местами строчки исполнения была “отключена”.Таким образом мы гарантировали, что assert не сработает.
Чтобы было легче понять принцип работы полных барьеров попробуем прибегнуть к аналогии. Давайте представим, что у нас есть конвейерная лента, по которой едут конверты с инструкциями от начальства(ЦП1):
Как вы можете видеть, у ленты стоит работник(ЦП2), который снимает конверт и исполняет/зачитывает инструкцию, которая там написана. Так как перед работником несколько совершенно одинаковых конвертов, у него нет никаких причин отдавать предпочтения ни одному из них, поэтому он может взять с ленты как ближний к себе конверт, так и дальний, и это ни от чего не зависит(пусть будет так, что дальний доставать не менее удобно, чем ближний). Это идентично ситуации без барьеров – работник не знает, в каком порядке на ленту были положены конверты, а значит и порядок их извлечения не детерминирован. Естественно, что для определенных наборов конвертов порядок не важен, т.к. инструкции могут быть никак не связана друг с другом, но есть и такие последовательности конвертов, порядок извлечения которых необычайно важен. Начальство понимает, что единственный шанс гарантировать порядок, это устранить человеческий фактор. Поэтому они решают добавлять между конвертами, которые должны быть извлечены поочереди, физическую преграду, которая не даёт извлечь конверт идущий вторым, пока первый не будет снят:
Теперь работник физически не может достать второй конверт, пока не вытащит с ленты первый(конвейер умён, и не двигается, пока контейнер не снят). Теперь, между двумя конвертами есть барьер, который гарантирует порядок исполнения инструкций.
Неполные барьеры
Оставим аналогии и вернёмся к нашему коду ещё раз. В нашей первой функции:
void thread1()
{
sharedData = 555;
full_barrier();
sharedFlag = true;
}для корректного исполнения достаточно лишь одной гарантии, что изменения в sharedData видны всем ЦП к тому моменту, как изменяется sharedFlag. Но любая другая оптимизация вовсе не помешает нам, а значит может быть разрешена. Но что за другая оптимизация? Давайте ещё раз уточним, что же такое полный барьер: полный барьер гарантирует, что ни одна операция чтения или записи не может “перепрыгнуть” через барьер:
Картинка выше означает буквально следующее: любая сущность(процессор, компилятор, чёрт рогатый) может изменять порядок инструкций в пределах “блока до” и “блока после”, если это не нарушает целостной картины исполнения в рамках одного потока исполнения(другими словами, если все строчки независимы). Но ни одна инструкция из “блока до” не может быть перенесена в “блок после” и наоборот – между ними, буквально, стена(барьер).
Так вот, исходя из вышесказанного можно увидеть, что полный барьер является чрезвычайно строгим инструментом, который не всегда необходим. К примеру, у нас может быть потребность в том, чтобы только операции записи не пересекали барьера, или наоборот, только операции чтения. Чтобы стало понятнее, давайте разбавим наш пример ещё парой строчек:
int anotherSharedData;
void thread1()
{
sharedData = 555;
int answer = anotherSharedData;
full_barrier();
sharedFlag = true;
if(answer == 42)
...
}
void thread2()
{
while(!sharedFlag);
full_barrier();
anotherSharedData = 42;
assert(sharedData == 555);
}Т.к. мы используем полный барьер, то код в if, совершенно точно, никогда не будет выполнен. Но, на деле, нам не нужен здесь полный барьер, ведь в функции thread1() нам нужно гарантировать только то, что sharedData записана до того, как будем записан sharedFlag. В то же время, на стороне thread2(), нам нужна тоже лишь одна гарантия, что sharedData не будет прочитана до того, как цикл while завершится(те, кто думают, что это и так невозможно – ошибаются). Но если не полный барьер, тогда что? Дело в том, что существуют как минимум 2 типа барьеров памяти(их больше, но на данный момент это не существенно), которые обладают менее строгой гарантией: барьер записи и барьер чтения. Барьер записи можно проиллюстрировать следующим образом:
Как вы можете видеть, при использовании барьера записи оптимизирующие сущности могут перенести чтение данных за барьер, таким образом улучшив производительность Барьер чтения, соответственно, можно проиллюстрировать схожим образом:
Как видно из рисунка, теперь операции чтения не могут выскочить за барьер, тогда как операции записи могут это сделать. Возможно, кому то покажется, что это всё ерунда: ну подумаешь, могут ходить через барьер, что в этом такого? Какой смысл в этих полу-барьерах? Смысл, на самом деле, есть, т.к. забыв обо всех других оптимизациях(компилятора, например) можно сказать совершенно точно, что для некоторых архитектур процессоров неполные барьеры обходятся гораздо дешевле, своих полных собратьев. Поэтому, безусловно, использование неполных барьеров оправданно и на деле весьма часто используется.
Теперь вернёмся к нашему примеру. Очевидно, что для того, чтобы assert гарантировано не сработал, нам достаточно иметь барьер записи в thread1() и барьер чтения в thread2():
int anotherSharedData;
void thread1()
{
sharedData = 555;
int answer = anotherSharedData;
write_barrier();
sharedFlag = true;
if(answer == 42)
...
}
void thread2()
{
while(!sharedFlag);
read_barrier();
anotherSharedData = 42;
assert(sharedData == 555);
}Действительно, теперь запись в sharedData гарантировано выполнится до записи в sharedFlag, а чтения sharedData(в thread2()) будет гарантировано выполнено после чтения sharedFlag, а значит и завершения цикла while. Как говорят математики – что и требовалось доказать. С использованием неполных барьеров мы дали возможность оптимизирующим сущностям больше свободы, а также ослабили нагрузку на ЦП. Кроме того, в качестве бонуса, теперь наш код в if(в thread1()) может отработать, а может и не отработать. Всё зависит от поведения оптимизирующих сущностей – собственно, для этого я и разбавил пример новыми строками, чтобы показать разницу в поведении между полными и неполными барьерами в общем виде.
Пример из жизни
Пример, который мы рассматривали ранее нельзя назвать показательным – более того, он может показаться чрезвычайно надуманным(и наверное так оно и есть), поэтому предлагаю рассмотреть более реальный пример. В качестве примера мы рассмотрим самый известный примитив в программировании многопоточных систем: мьютекс.
Как мы с вами знаем, над любым мьютексом можно выполнить 2 базовых операции: lock и unlock. При этом всё, что находится между этими операциями считается защищённой секцией, т.е. внутри пары lock/unlock мы гарантированно защищены от гонок. Другими словами, всё, что находится внутри блока lock/unlock не может “выйти” за пределы этого блока, в то же время, гарантии не буд��т нарушены, если части внешнего мир “войдут” внутрь блока:
Ничего картинка с описанием не напоминает? Именно, это те же самые барьеры! Правда такие, каких мы ранее не рассматривали. С одной стороны требования слабее, чем при использовании полного барьера, но сильнее, чем при использовании барьеров чтения/записи по отдельности. Т.к. для наших целей подходит только полный барьер, то будем считать, что для реализации мьютекса именно он и используется. Другие типы барьеров, которые лучше подходят для использования в мьютексе, а также то, как барьеры памяти могут быть реализованы на низком уровне, мы рассмотрим в следующей статье.