Упорядочение памяти

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

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

Чтобы полностью использовать пропускную способность различных типов памяти, таких как кэши и банки памяти , лишь немногие компиляторы или архитектуры ЦП обеспечивают идеально строгое упорядочение. Среди широко используемых архитектур процессоры x86-64 имеют самый строгий порядок памяти, но все же могут откладывать инструкции по сохранению памяти до тех пор, пока не последуют инструкции по загрузке памяти. На другом конце спектра процессоры DEC Alpha практически не дают гарантий относительно порядка памяти.

Упорядочение памяти во время компиляции

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

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

Общие вопросы заказа программы

Эффекты порядка выполнения программы при оценке выражений

Во время компиляции аппаратные инструкции часто генерируются с более высокой степенью детализации, чем указано в коде высокого уровня. Основным наблюдаемым эффектом процедурного языка программирования является присвоение нового значения именованной переменной.

  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(&a) + g(a); 

Неизвестно, какая функция f можно было бы сделать с предоставленным указателем на a, включая оставление копии в глобальном состоянии, которое функция g более поздние доступы. В простейшем случае f записывает новое значение в переменную a, что делает это выражение неопределенным в порядке выполнения. f этого можно явно избежать, применив квалификатор const к объявлению аргумента-указателя, что сделает выражение четко определенным. Таким образом, современная культура C/C++ стала несколько одержима предоставлением константных квалификаторов для объявлений аргументов функций во всех возможных случаях.

C и C++ позволяют использовать внутренние возможности f для ввода отбрасывать атрибут constness как опасный метод. Если f делает это таким образом, что может нарушить приведенное выше выражение, в первую очередь не следует объявлять тип аргумента указателя как const.

Другие языки высокого уровня склоняются к такому атрибуту объявления, который представляет собой надежную гарантию без лазеек для нарушения этой гарантии, предоставляемой внутри самого языка; все ставки на этот язык не гарантируются, если ваше приложение связывает библиотеку, написанную на другом языке программирования (хотя это считается вопиюще плохим дизайном).

Реализация барьера памяти во время компиляции

См. Также: Барьер памяти.

Эти барьеры не позволяют компилятору переупорядочивать инструкции во время компиляции — они не препятствуют переупорядочению ЦП во время выполнения.

• Любой из этих операторов встроенного ассемблера GNU запрещает компилятору GCC переупорядочивать команды чтения и записи вокруг него:

asm volatile("" ::: "memory");
__asm__ __volatile__ ("" ::: "memory");

• Эта функция C11/C++11 запрещает компилятору переупорядочивать команды чтения и записи вокруг нее:

atomic_signal_fence(memory_order_acq_rel);

• Компилятор Intel C++ (ICC/ICL) использует встроенные функции «полного ограждения компилятора»:

__memory_barrier()

• Компилятор Microsoft Visual C++ (MSVC) поддерживает некоторые встроенные функции только для x86/x64 (все они устарели):

_ReadBarrier()
_WriteBarrier()
_ReadWriteBarrier()

Комбинированные барьеры

Во многих языках программирования различные типы барьеров могут комбинироваться с другими операциями (такими как загрузка, сохранение, атомарное приращение, атомарное сравнение и замена), поэтому дополнительный барьер памяти до или после них (или и того, и другого) не требуется. В зависимости от целевой архитектуры ЦП эти языковые конструкции будут транслироваться либо в специальные инструкции, либо в несколько инструкций (т. е. барьер и загрузка), либо в нормальные инструкции, в зависимости от гарантий аппаратного порядка памяти.

Порядок оперативной памяти

В микропроцессорных системах симметричной многопроцессорной обработки (SMP)

Существует несколько моделей согласованности памяти для SMP -систем:

• Последовательная согласованность (все операции чтения и записи выполняются в порядке)
• Слабая согласованность (допускаются некоторые типы изменения порядка)
  • Загрузки можно переупорядочивать после загрузки (для лучшей работы согласованности кэша, лучшего масштабирования)
  • Грузы можно заказать повторно после магазинов
  • Магазины можно переупорядочить после магазинов
  • Магазины можно переупорядочить после загрузки
• Слабая согласованность (чтение и запись произвольно переупорядочиваются, ограничиваясь только явными барьерами памяти )

На некоторых процессорах

• Атомарные операции можно переупорядочить с помощью загрузок и сохранений.
• Может существовать некогерентный конвейер кэша инструкций, который предотвращает самомодифицирующегося кода без специальных инструкций очистки/перезагрузки кэша инструкций. выполнение
• Зависимые нагрузки можно переупорядочивать (это уникально для Alpha). Если процессор сначала извлекает указатель на некоторые данные, а затем сами данные, он может не получить сами данные, а использовать устаревшие данные, которые он уже кэшировал и еще не признал недействительными. Разрешение этого ослабления упрощает и ускоряет аппаратное обеспечение кэша, но приводит к необходимости установки барьеров памяти для устройств чтения и записи. На оборудовании Alpha (например, многопроцессорных системах Alpha 21264 ) аннулирование строк кэша, отправленное на другие процессоры, по умолчанию обрабатывается ленивым способом, если только обработка не запрашивается явно между зависимыми загрузками. Спецификация архитектуры Alpha также допускает другие формы переупорядочения зависимых загрузок, например, использование спекулятивного чтения данных до знания реального указателя, подлежащего разыменованию.

Упорядочение памяти в некоторых архитектурах

Тип	Альфа	ARMv7	МИПС	РИСК-V		ПА-РИСК	ВЛАСТЬ	СПАРК			х86	AMD64	ИА-64	з/Архитектура
				ВМО	ТСО			РМО	ПСО	ТСО
Загрузки можно переупорядочить после загрузки	И	И	зависеть от выполнение	И		И	И	И					И
Грузы можно заказать повторно после магазинов	И	И		И		И	И	И					И
Магазины можно переупорядочить после магазинов	И	И		И		И	И	И	И				И
Магазины можно переупорядочить после загрузки	И	И		И	И	И	И	И	И	И	И	И	И	И
Atomic можно переупорядочить с помощью нагрузок	И	И		И			И	И					И
Atomic можно повторно заказать в магазинах.	И	И		И			И	И	И				И
Зависимые нагрузки можно переупорядочить	И
Некогерентный кеш/конвейер инструкций	И	И		И	И		И	И	И	И	И		И

Модели заказа памяти RISC-V

ВМО

Слабый порядок памяти (по умолчанию)

ТСО

Общий заказ магазина (поддерживается только с расширением Ztso)

Режимы заказа памяти SPARC

ТСО

Общий заказ магазина (по умолчанию)

РМО

Расслабленный порядок памяти (не поддерживается на последних процессорах)

ПСО

Частичный порядок сохранения (не поддерживается на последних процессорах)

Реализация аппаратного барьера памяти

См. Также: Барьер памяти.

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

• х86 , х86-64

lfence (asm), void _mm_lfence(void)
sfence (asm), void _mm_sfence(void)
mfence (asm), void _mm_mfence(void)

• PowerPC

sync (asm)

• МИПС

sync (asm)

• Итаний

mf (asm)

• ВЛАСТЬ

dcs (asm)

• ARMv7

dmb (asm)
dsb (asm)
isb (asm)

Поддержка компилятором аппаратных барьеров памяти.

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

• ССЗ , версия 4.4.0 и новее, имеет __sync_synchronize.
• Поскольку C11 и C++11 atomic_thread_fence() добавлена ​​команда.
• Компилятор Microsoft Visual C++ имеет MemoryBarrier() макрос в заголовке Windows API (устарело).
• Пакет компиляторов Sun Studio имеет __machine_r_barrier, __machine_w_barrier и __machine_rw_barrier.

См. также

• Модель памяти (программирование)

Дальнейшее чтение

• Модели согласованности общей памяти: руководство Сариты В. Адве и Куроша Гарачорлоо
• Порядок памяти в современных микропроцессорах Пола Маккенни
• Модели слабой и сильной памяти Джеффа Прешинга
• Формальная модель упорядочения памяти ядра, разработанная Джейд Алглав и др.
• Порядок памяти IA (Intel Architecture) на YouTube  – Google Tech Talk, Ричард Л. Хадсон
• Компьютерная архитектура — количественный подход . 4-е издание. Дж. Хеннесси, Д. Паттерсон, 2007. Глава 4.6.