Порядок памяти — это порядок доступа ЦП к памяти компьютера . Порядок памяти зависит как от порядка инструкций, сгенерированных компилятором во время компиляции, так и от порядка выполнения ЦП во время выполнения . [1] [2] Однако порядок памяти мало кого волнует за пределами многопоточности и ввода-вывода с отображением в память , поскольку если компилятор или ЦП изменяет порядок любых операций , он должен обязательно гарантировать, что переупорядочивание не изменит вывод обычного однопоточного кода. [1] [2] [3]
Порядок памяти называется сильным или последовательно согласованным , когда порядок операций не может измениться или когда такие изменения не оказывают видимого влияния на какой-либо поток. [1] [4] И наоборот, порядок памяти называется слабым или ослабленным , когда один поток не может предсказать порядок операций, возникающих из другого потока. [1] [4] Многие наивно написанные параллельные алгоритмы терпят неудачу при компиляции или выполнении со слабым порядком памяти. [5] [6] Чаще всего проблема решается путем вставки в программу инструкций барьера памяти . [6] [7]
Для того чтобы полностью использовать пропускную способность различных типов памяти, таких как кэши и банки памяти , лишь немногие компиляторы или архитектуры ЦП обеспечивают идеально сильный порядок. [1] [5] Среди наиболее часто используемых архитектур процессоры x86-64 имеют самый сильный порядок памяти, но все равно могут откладывать инструкции сохранения памяти до окончания инструкций загрузки памяти. [5] [8] С другой стороны, процессоры DEC Alpha практически не дают никаких гарантий относительно порядка памяти. [5]
Большинство языков программирования имеют некоторое понятие потока выполнения, который выполняет операторы в определенном порядке. Традиционные компиляторы транслируют высокоуровневые выражения в последовательность низкоуровневых инструкций относительно счетчика программ на базовом машинном уровне.
Эффекты выполнения видны на двух уровнях: в программном коде на высоком уровне и на уровне машины, как видно из других потоков или элементов обработки в параллельном программировании , или во время отладки при использовании аппаратного средства отладки с доступом к состоянию машины (некоторая поддержка этого часто встроена непосредственно в ЦП или микроконтроллер как функционально независимая схема отдельно от ядра выполнения, которое продолжает работать, даже когда само ядро остановлено для статической проверки его состояния выполнения). Порядок памяти во время компиляции касается первого и не касается этих других представлений.
Во время компиляции аппаратные инструкции часто генерируются с более высокой степенью детализации, чем указано в коде высокого уровня. Основным наблюдаемым эффектом в процедурном языке программирования является присвоение нового значения именованной переменной.
сумма = а + b + с; распечатать(сумма);
Оператор print следует за оператором, который присваивает переменной сумму, и, таким образом, когда оператор print ссылается на вычисляемую переменную, sumон ссылается на этот результат как на наблюдаемый эффект предыдущей последовательности выполнения. Как определено правилами последовательности программ, когда printвызов функции ссылается на sum, значение sumдолжно быть значением последнего выполненного присваивания переменной sum(в данном случае непосредственно предшествующего оператора).
На машинном уровне лишь немногие машины могут сложить три числа вместе в одной инструкции, и поэтому компилятору придется преобразовать это выражение в две операции сложения. Если семантика языка программы ограничивает компилятор в преобразовании выражения слева направо (например), то сгенерированный код будет выглядеть так, как если бы программист написал следующие операторы в исходной программе:
сумма = а + b; сумма = сумма + с;
Если компилятору разрешено использовать ассоциативное свойство сложения, он может вместо этого сгенерировать:
сумма = b + c; сумма = а + сумма;
Если компилятору также разрешено использовать коммутативное свойство сложения, он может вместо этого сгенерировать:
сумма = а + с; сумма = сумма + b;
Обратите внимание, что целочисленный тип данных в большинстве языков программирования следует алгебре для целых чисел математики только при отсутствии целочисленного переполнения , и что арифметика с плавающей точкой для типа данных с плавающей точкой, доступная в большинстве языков программирования, не является коммутативной в эффектах округления, делая эффекты порядка выражения видимыми в небольших различиях вычисленного результата (однако небольшие начальные различия могут перерасти в произвольно большие различия в течение более длительного вычисления).
Если программист обеспокоен переполнением целых чисел или эффектами округления в числах с плавающей точкой, ту же программу можно закодировать на исходном высоком уровне следующим образом:
сумма = а + b; сумма = сумма + с;
Многие языки рассматривают границу оператора как точку последовательности , заставляя все эффекты одного оператора быть завершенными до выполнения следующего оператора. Это заставит компилятор сгенерировать код, соответствующий выраженному порядку операторов. Однако операторы часто более сложны и могут содержать внутренние вызовы функций .
сумма = f(a) + g(b) + h(c);
На уровне машины вызов функции обычно включает в себя настройку стекового фрейма для вызова функции, что включает в себя множество чтений и записей в машинную память. В большинстве компилируемых языков компилятор может свободно упорядочивать вызовы функций f, gи hтак, как он считает удобным, что приводит к масштабным изменениям порядка памяти программы. В чисто функциональном языке программирования вызовам функций запрещено иметь побочные эффекты на видимое состояние программы (кроме возвращаемого значения ), а разница в порядке машинной памяти из-за порядка вызова функций будет несущественной для семантики программы. В процедурных языках вызываемые функции могут иметь побочные эффекты, такие как выполнение операции ввода -вывода или обновление переменной в глобальной области действия программы, оба из которых производят видимые эффекты с моделью программы.
Опять же, программист, обеспокоенный этими эффектами, может стать более педантичным в выражении исходной программы:
сумма = f(a); сумма = сумма + g(b); сумма = сумма + h(c);
В языках программирования, где граница оператора определяется как точка последовательности, функция вызывает f, g, и hтеперь должна выполняться именно в этом порядке.
Теперь рассмотрим то же самое суммирование, выраженное с помощью косвенного указателя, на языке, поддерживающем указатели, например, C или C++ :
сумма = *a + *b + *c;
Оценка выражения *xназывается « разыменованием » указателя и включает чтение из памяти в месте, указанном текущим значением x. Эффекты чтения из указателя определяются моделью памяти архитектуры . При чтении из стандартного хранилища программ побочных эффектов не возникает из-за порядка операций чтения памяти. В программировании встроенных систем очень часто используется отображенный в память ввод-вывод , когда чтение и запись в память запускают операции ввода-вывода или изменения рабочего режима процессора, которые являются весьма заметными побочными эффектами. Для приведенного выше примера предположим на данный момент, что указатели указывают на обычную память программ без этих побочных эффектов. Компилятор может свободно переупорядочивать эти чтения в порядке программы по своему усмотрению, и не будет никаких видимых для программы побочных эффектов.
А что, если присвоенное значение также является косвенным указателем?
*сумма = *а + *b + *c;
В данном случае определение языка вряд ли позволит компилятору разбить это на части следующим образом:
// как переписано компилятором // вообще запрещено *сумма = *а + *b; *сумма = *сумма + *c;
Это не будет считаться эффективным в большинстве случаев, и записи указателей имеют потенциальные побочные эффекты для видимого состояния машины. Поскольку компилятору не разрешено это конкретное преобразование разделения, единственная запись в ячейку памяти sumдолжна логически следовать за тремя чтениями указателей в выражении значения.
Предположим, однако, что программист обеспокоен видимой семантикой целочисленного переполнения и разбивает оператор на части на уровне программы следующим образом:
// как создано непосредственно программистом // с проблемами псевдонимов *сумма = *а + *b; *сумма = *сумма + *c;
Первый оператор кодирует два чтения памяти, которые должны предшествовать (в любом порядке) первой записи в *sum. Второй оператор кодирует два чтения памяти (в любом порядке), которые должны предшествовать второму обновлению *sum. Это гарантирует порядок двух операций сложения, но потенциально вводит новую проблему наложения адресов : любой из этих указателей может потенциально ссылаться на одну и ту же ячейку памяти.
Например, предположим в этом примере, что *cи *sumявляются псевдонимами одной и той же области памяти, и перепишем обе версии программы, *sumзаменяя их.
*сумма = *a + *b + *сумма;
Здесь нет никаких проблем. Исходное значение того, что мы изначально записали как, *cтеряется при присвоении *sum, как и исходное значение , *sumно это было перезаписано изначально, и это не представляет особой проблемы.
// что программа становится с псевдонимами *c и *sum *сумма = *а + *b; *сумма = *сумма + *сумма;
Здесь исходное значение *sumперезаписывается до первого доступа, и вместо этого мы получаем алгебраический эквивалент:
// алгебраический эквивалент псевдонима, приведенного выше *сумма = (*а + *b) + (*а + *b);
который присваивает совершенно другое значение из- *sumза перестановки операторов.
Из-за возможных эффектов псевдонимов выражения указателей трудно переставлять, не рискуя видимыми эффектами программы. В общем случае может не быть никакого псевдонимов, поэтому код, по-видимому, работает нормально, как и раньше. Но в пограничном случае, когда присутствует псевдоним, могут возникнуть серьезные ошибки программы. Даже если эти пограничные случаи полностью отсутствуют при нормальном выполнении, это открывает дверь для злонамеренного противника, чтобы придумать вход, где есть псевдонимы, что потенциально приводит к эксплойту компьютерной безопасности .
Безопасная переупорядоченность предыдущей программы выглядит следующим образом:
// объявить временную локальную переменную 'temp' подходящего типа темп = *а + *б; *сумма = темп + *c;
Наконец, рассмотрим косвенный случай с добавленными вызовами функций:
*сумма = f(*a) + g(*b);
Компилятор может выбрать оценку *aи *bперед вызовом любой функции, он может отложить оценку *bдо вызова функции fили он может отложить оценку *aдо вызова функции g. Если функции fи gсвободны от видимых побочных эффектов программы, все три варианта создадут программу с одинаковыми видимыми эффектами программы. Если реализация fили gсодержит побочный эффект любого указателя write, подлежащего совмещению с указателями aили b, три варианта могут создать различные видимые эффекты программы.
В общем, компилируемые языки недостаточно детализированы в своей спецификации, чтобы компилятор мог формально определить во время компиляции, какие указатели потенциально псевдонимизированы, а какие нет. Самый безопасный курс действий для компилятора — предположить, что все указатели потенциально псевдонимизированы в любое время. Этот уровень консервативного пессимизма имеет тенденцию давать ужасную производительность по сравнению с оптимистичным предположением, что псевдонимизация никогда не существует.
В результате многие высокоуровневые компилируемые языки, такие как C/C++, эволюционировали и стали иметь сложные и изощренные семантические спецификации относительно того, где компилятору разрешено делать оптимистичные предположения при переупорядочении кода в целях достижения максимально возможной производительности, а где компилятору необходимо делать пессимистичные предположения при переупорядочении кода, чтобы избежать семантических опасностей.
Самый большой класс побочных эффектов в современном процедурном языке включает операции записи в память, поэтому правила, касающиеся порядка памяти, являются доминирующим компонентом в определении семантики порядка программы. Переупорядочение вызовов функций выше может показаться другим соображением, но это обычно сводится к проблемам с эффектами памяти, внутренними для вызываемых функций, взаимодействующих с операциями памяти в выражении, которое генерирует вызов функции.
Современные компиляторы иногда идут дальше, используя правило as-if , в котором любое переупорядочивание разрешено (даже между операторами), если это не влияет на видимую семантику программы. Согласно этому правилу, порядок операций в транслируемом коде может сильно отличаться от указанного порядка программы. Если компилятору разрешено делать оптимистичные предположения о том, что отдельные выражения указателей не имеют перекрытия псевдонимов в случае, когда такое перекрытие псевдонимов фактически существует (обычно это классифицируется как плохо сформированная программа, демонстрирующая неопределенное поведение ), неблагоприятные результаты агрессивного преобразования оптимизации кода невозможно предугадать до выполнения кода или прямой проверки кода. Область неопределенного поведения имеет почти безграничные проявления.
Программист должен свериться со спецификацией языка, чтобы избежать написания плохо сформированных программ, семантика которых потенциально изменяется в результате любой допустимой оптимизации компилятора. Fortran традиционно возлагает на программиста большую нагрузку, связанную с знанием этих проблем, а языки системного программирования C и C++ не сильно отстают.
Некоторые языки высокого уровня вообще исключают конструкции указателей, поскольку этот уровень бдительности и внимания к деталям считается слишком высоким, чтобы его можно было надежно поддерживать даже среди профессиональных программистов.
Полное понимание семантики порядка памяти считается скрытой специализацией даже среди субпопуляции профессиональных системных программистов, которые обычно лучше всего информированы в этой предметной области. Большинство программистов довольствуются адекватным рабочим пониманием этих вопросов в рамках обычной области их знаний в области программирования. На самом краю специализации в семантике порядка памяти находятся программисты, которые создают программные фреймворки для поддержки моделей параллельных вычислений .
Обратите внимание, что нельзя считать, что локальные переменные свободны от псевдонимов, если указатель на такую переменную выходит за рамки допустимого:
сумма = f(&a) + g(a);
Невозможно сказать, что функция fмогла бы сделать с предоставленным указателем на a, включая то, что она оставила копию в глобальном состоянии, к которому функция gпозже обращается. В простейшем случае fзаписывает новое значение в переменную a, делая это выражение плохо определенным в порядке выполнения. fможно явно предотвратить это, применив квалификатор const к объявлению своего аргумента указателя, сделав выражение хорошо определенным. Таким образом, современная культура C/C++ стала несколько одержимой предоставлением квалификаторов const к объявлениям аргументов функции во всех возможных случаях.
C и C++ разрешают внутренним частям fотбрасывать атрибут constness как опасный прием. Если fэто делает так, что может сломать выражение выше, то изначально не следует объявлять тип аргумента указателя как const.
Другие языки высокого уровня склоняются к такому атрибуту объявления, представляющему собой надежную гарантию без лазеек для нарушения этой гарантии, предоставляемой самим языком; все ставки на эту языковую гарантию отменяются, если ваше приложение связывает библиотеку, написанную на другом языке программирования (хотя это считается вопиющим плохим проектированием).
Эти барьеры не позволяют компилятору переупорядочивать инструкции во время компиляции, но не предотвращают переупорядочивание, выполняемое процессором во время выполнения.
asm volatile("" ::: "память");__asm__ __volatile__ ("" ::: "память");атомарный_сигнальный_забор(memory_order_acq_rel);
__барьер_памяти()
_ReadBarrier()_WriteBarrier()_ReadWriteBarrier()
Во многих языках программирования различные типы барьеров могут быть объединены с другими операциями (такими как загрузка, сохранение, атомарное приращение, атомарное сравнение и обмен), поэтому не требуется дополнительного барьера памяти до или после него (или обоих). В зависимости от целевой архитектуры ЦП эти языковые конструкции будут транслироваться либо в специальные инструкции, либо в множественные инструкции (т. е. барьер и загрузка), либо в обычную инструкцию, в зависимости от гарантий упорядочения аппаратной памяти.
Существует несколько моделей согласованности памяти для SMP -систем:
На некоторых процессорах
Многие архитектуры с поддержкой SMP имеют специальные аппаратные инструкции для очистки чтения и записи во время выполнения .
lfence (asm), void _mm_lfence(void)sfence (asm), void _mm_sfence (void) [18] mfence (asm), void _mm_mfence(void) [19]
синхронизация (асм)
синхронизация (асм) [20] [21]
мф (асм)
dcs (асм)
дмб (асм)dsb (асм)isb (асм)
Некоторые компиляторы поддерживают встроенные функции , которые генерируют инструкции аппаратного барьера памяти:
__sync_synchronize.atomic_thread_fence()была добавлена команда.MemoryBarrier()макрос в заголовке Windows API (устарело). [25] [13]__machine_r_barrier, __machine_w_barrierи __machine_rw_barrier.Создает барьер, через который компилятор не будет планировать никаких инструкций доступа к данным. Компилятор может размещать локальные данные в регистрах через барьер памяти, но не глобальные данные.