Упорядочение памяти описывает порядок доступа ЦП к памяти компьютера. Термин может относиться либо к порядку памяти, сгенерированному компилятором во время компиляции, либо к порядку памяти, сгенерированному ЦП во время выполнения.
В современных микропроцессорах упорядочение памяти характеризует способность ЦП переупорядочивать операции с памятью - это тип выполнения вне очереди. Переупорядочение памяти можно использовать для полного использования пропускной способности шины различных типов памяти, таких как кеши и банки памяти.
На большинстве современных однопроцессоров операции с памятью не выполняются в порядке, указанном программным кодом. В однопоточных программах все операции выполняются в указанном порядке, при этом все неупорядоченное выполнение скрыто от программиста, однако в многопоточных средах (или при взаимодействии с другим оборудованием через шины памяти) это может привести к проблемы. Во избежание проблем в этих случаях можно использовать барьеры памяти.
Большинство языков программирования имеют некоторое представление о потоке выполнения, который выполняет операторы в определенном порядке. Традиционные компиляторы переводят высокоуровневые выражения в последовательность низкоуровневых инструкций относительно счетчика программ на базовом машинном уровне.
Эффекты выполнения видны на двух уровнях: в программном коде на высоком уровне и на машинном уровне с точки зрения других потоков или элементов обработки в параллельном программировании или во время отладки при использовании аппаратного средства отладки с доступом к состоянию машины ( некоторая поддержка этого часто встроена непосредственно в ЦП или микроконтроллер как функционально независимая схема, кроме ядра выполнения, которое продолжает работать, даже когда само ядро остановлено для статической проверки состояния его выполнения). Порядок памяти во время компиляции касается первого и не касается этих других представлений.
Во время компиляции аппаратные инструкции часто генерируются с более высокой степенью детализации, чем указано в коде высокого уровня. Основным наблюдаемым эффектом процедурного программирования является присвоение нового значения именованной переменной.
sum = a + b + c; print(sum);
Оператор печати следует за оператором, который присваивает переменной sum, и, таким образом, когда оператор печати ссылается на вычисляемую переменную, sum
он ссылается на этот результат как на наблюдаемый эффект предыдущей последовательности выполнения. Как определено правилами программной последовательности, когда print
вызов функции ссылается sum
, значение sum
должно быть значением последнего выполненного присваивания переменной sum
(в этом случае непосредственно предыдущий оператор).
На машинном уровне несколько машин могут сложить три числа в одной инструкции, поэтому компилятору придется преобразовать это выражение в две операции сложения. Если семантика языка программы ограничивает компилятор переводом выражения в порядке слева направо (например), то сгенерированный код будет выглядеть так, как если бы программист написал следующие операторы в исходной программе:
sum = a + b; sum = sum + c;
Если компилятору разрешено использовать ассоциативное свойство сложения, он может вместо этого сгенерировать:
sum = b + c; sum = a + sum;
Если компилятору также разрешено использовать коммутативное свойство сложения, он может вместо этого сгенерировать:
sum = a + c; sum = sum + b;
Обратите внимание, что целочисленный тип данных в большинстве языков программирования следует только за алгеброй для математических целых чисел в отсутствие целочисленного переполнения, и что арифметика с плавающей запятой для типа данных с плавающей запятой, доступная в большинстве языков программирования, не является коммутативной в эффектах округления, что дает эффекты порядка выражения, видимого в небольших различиях вычисленного результата (однако небольшие начальные различия могут каскадно превращаться в сколь угодно большие различия в течение более длительного вычисления).
Если программиста беспокоят эффекты целочисленного переполнения или округления в числах с плавающей запятой, ту же программу можно закодировать на исходном высоком уровне следующим образом:
sum = a + b; sum = sum + c;
Многие языки рассматривают границу оператора как точку следования, заставляя все эффекты одного оператора завершаться до выполнения следующего оператора. Это заставит компилятор сгенерировать код, соответствующий выраженному порядку операторов. Однако операторы часто бывают более сложными и могут содержать внутренние вызовы функций.
sum = f(a) + g(b) + h(c);
На машинном уровне вызов функции обычно включает в себя настройку кадра стека для вызова функции, что включает в себя множество операций чтения и записи в машинную память. В большинстве скомпилированных языков, компилятор волен заказать вызовы функций f
, g
и, h
как он находит удобно, что приводит к широкомасштабным изменениям порядка памяти программ. В чистом функциональном языке программирования вызовам функций запрещено иметь побочные эффекты на видимое состояние программы (кроме возвращаемого значения ), и разница в порядке памяти машины из-за порядка вызовов функций не будет иметь значения для семантики программы. В процедурных языках вызываемые функции могут иметь побочные эффекты, такие как выполнение операции ввода-вывода или обновление переменной в глобальной области программы, оба из которых производят видимые эффекты для модели программы.
Опять же, программист, озабоченный этими эффектами, может стать более педантичным в выражении исходной исходной программы:
sum = f(a); sum = sum + g(b); sum = sum + h(c);
В языках программирования, где граница заявление определяется как точка последовательности, вызовов функций f
, g
и h
теперь должен выполнить в этом точном порядке.
Теперь рассмотрим то же суммирование, выраженное косвенным указателем, на таком языке, как C или C ++, который поддерживает указатели :
sum = *a + *b + *c;
Вычисление выражения *x
называется « разыменованием » указателя и включает чтение из памяти в месте, указанном текущим значением x
. Эффекты чтения из указателя определяются архитектурной моделью памяти. При чтении из стандартного хранилища программ нет побочных эффектов из-за порядка операций чтения из памяти. Во встроенном системном программировании очень часто используется ввод-вывод с отображением в память, когда чтение и запись в память запускают операции ввода-вывода или изменения рабочего режима процессора, что является очень заметными побочными эффектами. Для приведенного выше примера предположим, что указатели указывают на обычную программную память без этих побочных эффектов. Компилятор может переупорядочивать эти чтения в порядке программ по своему усмотрению, и при этом не будет никаких видимых для программы побочных эффектов.
Что, если присвоенное значение также является косвенным указателем?
*sum = *a + *b + *c;
Здесь определение языка вряд ли позволит компилятору разбить это на части следующим образом:
// as rewritten by the compiler // generally forbidden *sum = *a + *b; *sum = *sum + *c;
В большинстве случаев это не будет считаться эффективным, а запись указателя может иметь побочные эффекты на видимое состояние машины. Поскольку компилятору не разрешено это конкретное преобразование разделения, единственная запись в ячейку памяти sum
должна логически следовать за тремя чтениями указателя в выражении значения.
Предположим, однако, что программист обеспокоен видимой семантикой целочисленного переполнения и разбивает оператор на программный уровень следующим образом:
// as directly authored by the programmer // with aliasing concerns *sum = *a + *b; *sum = *sum + *c;
Первый оператор кодирует два чтения из памяти, которые должны предшествовать (в любом порядке) первой записи *sum
. Второй оператор кодирует два чтения из памяти (в любом порядке), которые должны предшествовать второму обновлению *sum
. Это гарантирует порядок двух операций сложения, но потенциально создает новую проблему псевдонима адресов: любой из этих указателей потенциально может ссылаться на одно и то же место в памяти.
Например, предположим в этом примере, что *c
и *sum
имеют псевдонимы для одного и того же места в памяти, и перепишем обе версии программы, *sum
заменив обе.
*sum = *a + *b + *sum;
Здесь нет никаких проблем. Исходное значение того, что мы изначально написали, *c
теряется при назначении *sum
, как и исходное значение, *sum
но оно было изначально перезаписано, и это не вызывает особого беспокойства.
// what the program becomes with *c and *sum aliased *sum = *a + *b; *sum = *sum + *sum;
Здесь исходное значение *sum
перезаписывается перед первым обращением, и вместо этого мы получаем алгебраический эквивалент:
// algebraic equivalent of the aliased case above *sum = (*a + *b) + (*a + *b);
который присваивает совершенно другое значение *sum
из-за перестановки оператора.
Из-за возможных эффектов сглаживания выражения указателя трудно переупорядочить без риска видимых программных эффектов. В общем случае может не быть никакого эффекта псевдонима, поэтому код работает нормально, как и раньше. Но в крайнем случае, когда присутствует наложение, могут возникнуть серьезные программные ошибки. Даже если эти крайние случаи полностью отсутствуют при нормальном выполнении, это открывает дверь для злоумышленника, чтобы изобрести вход, где существует псевдоним, что потенциально может привести к уязвимости компьютерной безопасности.
Безопасный переупорядочивание предыдущей программы выглядит следующим образом:
// declare a temporary local variable 'temp' of suitable type temp = *a + *b; *sum = temp + *c;
Наконец, рассмотрим косвенный случай с добавленными вызовами функций:
*sum = f(*a) + g(*b);
Компилятор может выбрать оценку *a
и *b
перед вызовом любой функции, он может отложить оценку *b
до тех пор, пока не будет выполнен вызов функции, f
или он может отложить оценку *a
до тех пор, пока не будет выполнен вызов функции g
. Если функция f
и не g
содержат видимых программных побочных эффектов, все три варианта будут производить программу с одинаковыми видимыми программными эффектами. Если реализация f
или g
содержит побочный эффект любой записи указателя, подверженной наложению имен с указателями a
или b
, три варианта могут привести к различным видимым программным эффектам.
В общем, скомпилированные языки недостаточно подробны в своей спецификации, чтобы компилятор мог формально определить во время компиляции, какие указатели потенциально имеют псевдонимы, а какие нет. Самый безопасный способ действий для компилятора - это предположить, что все указатели потенциально имеют псевдонимы в любое время. Такой уровень консервативного пессимизма имеет тенденцию приводить к ужасным результатам по сравнению с оптимистическим предположением, что никакого псевдонима никогда не существует.
В результате многие компилируемые языки высокого уровня, такие как C / C ++, эволюционировали, чтобы иметь замысловатые и изощренные семантические спецификации относительно того, где компилятору разрешено делать оптимистические предположения при переупорядочении кода в поисках максимально возможной производительности, а где - нет. компилятор должен делать пессимистические предположения при переупорядочении кода, чтобы избежать семантических опасностей.
Безусловно, самый большой класс побочных эффектов в современном процедурном языке связан с операциями записи в память, поэтому правила, касающиеся упорядочивания памяти, являются доминирующим компонентом в определении семантики порядка программ. Переупорядочивание вызовов функций выше может показаться другим соображением, но это обычно сводится к проблемам с внутренними эффектами памяти для вызываемых функций, взаимодействующих с операциями с памятью в выражении, которое генерирует вызов функции.
Современные компиляторы иногда идут дальше с помощью правила «как если бы», в котором разрешается любое переупорядочение (даже между операторами), если оно не влияет на видимые результаты семантики программы. В соответствии с этим правилом порядок операций в переведенном коде может сильно отличаться от указанного в программе. Если компилятору разрешено делать оптимистические предположения о выражениях отдельных указателей, не имеющих перекрытия псевдонимов в случае, когда такое наложение псевдонимов действительно существует (обычно это классифицируется как плохо сформированная программа, демонстрирующая неопределенное поведение ), неблагоприятные результаты агрессивного кода - преобразование оптимизации невозможно угадать до выполнения кода или непосредственной проверки кода. Область неопределенного поведения имеет почти безграничные проявления.
Программист обязан проконсультироваться со спецификацией языка, чтобы избежать написания некорректных программ, в которых семантика потенциально изменяется в результате любой законной оптимизации компилятора. Фортран традиционно возлагает на программиста высокую ответственность за понимание этих проблем, и языки системного программирования C и C ++ не отстают.
Некоторые языки высокого уровня полностью исключают конструкции указателей, поскольку такой уровень бдительности и внимания к деталям считается слишком высоким, чтобы его можно было надежно поддерживать даже среди профессиональных программистов.
Полное понимание семантики порядка памяти считается загадочной специализацией даже среди подгруппы профессиональных системных программистов, которые обычно лучше всего осведомлены в этой предметной области. Большинство программистов соглашаются на адекватное рабочее понимание этих вопросов в рамках обычной области их знаний в области программирования. На вершине специализации в семантике порядка памяти находятся программисты, создающие программные среды для поддержки моделей параллельных вычислений.
Обратите внимание, что нельзя предполагать, что локальные переменные свободны от псевдонимов, если указатель на такую переменную ускользает в «дикую природу»:
sum = f(amp;a) + g(a);
Неизвестно, что функция f
могла сделать с предоставленным указателем a
, включая оставление копии в глобальном состоянии, к которому функция g
позже обращается. В простейшем случае f
записывает новое значение в переменную a
, делая это выражение некорректно определенным в порядке выполнения. f
можно явно предотвратить это, применив квалификатор const к объявлению его аргумента-указателя, сделав выражение четко определенным. Таким образом, современная культура C / C ++ стала в некоторой степени одержима предоставлением квалификаторов const для объявлений аргументов функций во всех жизнеспособных случаях.
C и C ++ позволяют Внутренность f
к типу отбрасывать атрибут константности прочь как опасные целесообразными. Если f
это сделано таким образом, что может нарушить приведенное выше выражение, он не должен в первую очередь объявлять тип аргумента указателя как const.
Другие языки высокого уровня склоняются к такому атрибуту объявления, что составляет строгую гарантию без лазеек для нарушения этой гарантии, предоставляемой в самом языке; все ставки на эту языковую гарантию не действуют, если ваше приложение связывает библиотеку, написанную на другом языке программирования (хотя это считается вопиюще плохим дизайном).
Эти барьеры не позволяют компилятору переупорядочивать инструкции во время компиляции - они не препятствуют переупорядочению со стороны ЦП во время выполнения.
asm volatile("" ::: "memory"); __asm__ __volatile__ ("" ::: "memory");
atomic_signal_fence(memory_order_acq_rel);
__memory_barrier()
_ReadWriteBarrier()
Во многих языках программирования различные типы барьеров могут быть объединены с другими операциями (такими как загрузка, сохранение, атомарное приращение, атомарное сравнение и свопинг), поэтому дополнительный барьер памяти не требуется до или после него (или обоих). В зависимости от целевой архитектуры ЦП эти языковые конструкции будут транслироваться либо в специальные инструкции, либо в несколько инструкций (например, барьер и загрузка), либо в обычные инструкции, в зависимости от гарантий упорядочения памяти оборудования.
Существует несколько моделей согласованности памяти для систем SMP :
На некоторых процессорах
Тип | Альфа | ARMv7 | MIPS | RISC-V | PA-RISC | ВЛАСТЬ | SPARC | x86 | AMD64 | IA-64 | z / Архитектура | |||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
ВМО | TSO | RMO | PSO | TSO | ||||||||||
Заказ грузов может быть изменен после загрузки | Y | Y | зависит от реализации | Y | Y | Y | Y | Y | ||||||
Возможен повторный заказ грузов после складирования | Y | Y | Y | Y | Y | Y | Y | |||||||
Магазины могут быть переупорядочены после магазинов | Y | Y | Y | Y | Y | Y | Y | Y | ||||||
Возможен повторный заказ магазинов после загрузки | Y | Y | Y | Y | Y | Y | Y | Y | Y | Y | Y | Y | Y | |
Атомик можно переупорядочивать с загрузкой | Y | Y | Y | Y | Y | Y | ||||||||
Атомик можно переупорядочить в магазинах | Y | Y | Y | Y | Y | Y | Y | |||||||
Зависимые нагрузки могут быть переупорядочены | Y | |||||||||||||
Непоследовательный конвейер кеширования инструкций | Y | Y | Y | Y | Y | Y | Y | Y | Y | Y |
Модели заказа памяти RISC-V:
Режимы упорядочивания памяти SPARC:
Многие архитектуры с поддержкой SMP имеют специальные аппаратные инструкции для сброса операций чтения и записи во время выполнения.
lfence (asm), void _mm_lfence(void) sfence (asm), void _mm_sfence(void) mfence (asm), void _mm_mfence(void)
sync (asm)
sync (asm)
mf (asm)
dcs (asm)
dmb (asm) dsb (asm) isb (asm)
Некоторые компиляторы поддерживают встроенные команды, которые выдают инструкции аппаратного барьера памяти:
__sync_synchronize
.atomic_thread_fence()
была добавлена команда.MemoryBarrier()
.__machine_r_barrier
, __machine_w_barrier
и __machine_rw_barrier
.