Видно ли переупорядочение памяти другим потокам в однопроцессоре?
Обычно в современных архитектурах ЦП используются оптимизации производительности, которые могут привести к неупорядоченному выполнению. В однопоточных приложениях также может происходить переупорядочение памяти, но оно невидимо для программистов, как если бы к памяти обращались в порядке программы. А для SMP на помощь приходят барьеры памяти, которые используются для принудительного упорядочения памяти.
В чем я не уверен, так это о многопоточности в однопроцессоре. Рассмотрим следующий пример: при запуске потока 1 хранилище f может иметь место до магазина в x, Допустим, переключение контекста происходит после f написано, и прямо перед x написано. Теперь поток 2 начинает работать, заканчивает цикл и выдает 0, что, конечно, нежелательно.
// Both x, f are initialized w/ 0.
// Thread 1
x = 42;
f = 1;
// Thread 2
while (f == 0)
;
print x;
Возможен ли описанный выше сценарий? Или есть гарантия, что физическая память выделяется при переключении контекста потока?
Согласно этому вики,
Когда программа работает на однопроцессорной машина, аппаратное обеспечение выполняет
необходимая бухгалтерия, чтобы программа выполнялась так, как будто все
Операции с памятью выполнялись в порядке, указанном
программист (порядок программ), поэтому барьеры памяти не нужны.
Хотя в нем однозначно не упоминаются однопроцессорные многопоточные приложения, он включает этот случай.
Я не уверен, что это правильно / завершено или нет. Обратите внимание, что это может сильно зависеть от аппаратного обеспечения (модель слабой / сильной памяти). Таким образом, вы можете включить оборудование, которое вы знаете, в ответах. Благодарю.
PS. устройства ввода / вывода и т. д. не моя проблема здесь. И это одноядерный однопроцессорный.
редактироватьСпасибо Nitsan за напоминание, мы предполагаем, что здесь нет переупорядочения компилятора (только переупорядочение оборудования), и цикл в потоке 2 не оптимизирован. Опять же, дьявол кроется в деталях.
Решение
В ответ на вопрос C ++ ответ должен состоять в том, что программа содержит гонку данных, поэтому ее поведение не определено. В действительности это означает, что он может напечатать что-то, кроме 42.
Это не зависит от базового оборудования. Как уже указывалось, цикл может быть оптимизирован, и компилятор может переупорядочить назначения в потоке 1, так что результат может возникнуть даже на однопроцессорных машинах.
[Я предполагаю, что под «однопроцессорной» машиной вы имеете в виду процессоры с одним ядром и аппаратным потоком.]Теперь вы говорите, что хотите предположить, что переупорядочивание компилятора или исключение цикла не происходит. После этого мы покинули сферу C ++ и действительно спрашиваем о соответствующих машинных инструкциях. Если вы хотите исключить переупорядочение компилятора, мы, вероятно, можем также исключить любую форму SIMD-инструкций и рассматривать только инструкции, работающие в одном месте памяти одновременно.
Таким образом, по существу, thread1 имеет две инструкции store в порядке store-to-x store-to-f, в то время как thread2 имеет test-f-and-loop-if-not-zero (это может быть несколько инструкций, но включает загрузку из -f) и затем загрузка из-х.
На любой аппаратной архитектуре, которую я знаю или могу себе представить, поток 2 напечатает 42.
Одна из причин заключается в том, что, если инструкции, обрабатываемые одним процессором, не являются последовательно согласованными между собой, вы вряд ли сможете утверждать что-либо о влиянии программы.
Единственное событие, которое может здесь помешать, — это прерывание (как оно используется для запуска преимущественного переключения контекста). Гипотетическая машина, которая хранит все состояние своего текущего состояния конвейера выполнения при прерывании и восстанавливает его по возвращении из прерывания, может дать другой результат, но такая машина непрактична и afaik не существует. Эти операции создадут немало дополнительной сложности и / или потребуют дополнительных избыточных буферов или регистров, и все это без веской причины — кроме как сломать вашу программу. Реальные процессоры либо сбрасывают, либо откатывают текущий конвейер при прерывании, что достаточно для обеспечения последовательной согласованности всех инструкций в одном аппаратном потоке.
И нет проблем с моделью памяти, о которой стоит беспокоиться. Более слабые модели памяти происходят из отдельных буферов и кешей, которые отделяют отдельные аппаратные процессоры от основной памяти или кеша n-го уровня, которые они фактически совместно используют. Один процессор не имеет ресурсов с одинаковым разделением, и нет веских причин использовать их для нескольких (чисто программных) потоков. Опять же, нет причин усложнять архитектуру и тратить ресурсы, чтобы процессор и / или подсистема памяти знали о чем-то вроде отдельных контекстов потоков, если нет отдельных ресурсов обработки (процессоров / аппаратных потоков), чтобы эти ресурсы были заняты.
Другие решения
При строгом упорядочении памяти выполняются инструкции доступа к памяти с точно таким же порядком, как определено в программе, его часто называют «упорядочением программы».
Слабое упорядочение памяти может использоваться, чтобы позволить процессору переупорядочивать доступ к памяти для лучшей производительности, его часто называют «упорядочением процессора».
AFAIK, сценарий, описанный выше НЕ Это возможно в архитектуре Intel ia32, чей процессорный процессор запрещает такие случаи. Соответствующие правила (руководство по разработке программного обеспечения Intel ia-32 Vol3A 8.2 Упорядочение памяти):
записи не переупорядочиваются с другими записями, за исключением потоковых хранилищ, CLFLUSH и строковых операций.
Чтобы проиллюстрировать правило, он приводит пример, подобный этому:
ячейка памяти x, y, инициализированная до 0;
поток 1:
mov [x] 1
mov [y] 1
поток 2:
mov r1 [y]
mov r2 [x]
r1 == 1 и r2 == 0 не допускаются
В вашем примере тема 1 не могу сохранить f перед сохранением x.
@Eric в ответ на ваши комментарии.
инструкция быстрого хранения строк «stosd», может хранить строки не в порядке внутри его операция. В многопроцессорной среде, когда процессор хранит строку «str», другой процессор может наблюдать, как str [1] записывается перед str [0], тогда как логический порядок предполагает запись str [0] перед str [1];
Но эти инструкции не заказываются ни в каких других магазинах. и должен иметь точную обработку исключений. Когда исключение возникает в середине stosd, реализация может решить отложить его, так что все неупорядоченные подсхемы (не обязательно означающие всю инструкцию stosd) должны фиксироваться перед переключением контекста.
Отредактировано для рассмотрения заявлений, как будто это вопрос C ++:
Даже это рассматривается в контексте C ++. Как я понимаю, стандартный подтверждающий компилятор должен НЕ изменить порядок присваивания х и f в потоке 1.
$ 1.9.14
Каждое вычисление значения и побочный эффект, связанный с полным выражением последовательность перед каждое значение
вычисление и побочный эффект, связанный со следующим полным выражением, которое будет оценено.
На самом деле это не вопрос C или C ++, так как вы явно предполагали, что не нужно переупорядочивать загрузку / сохранение, что вполне допустимо делать компиляторам для обоих языков.
Принимая это предположение ради аргумента, обратите внимание, что цикл в любом случае может никогда не завершиться, если только вы не:
- дать компилятору повод поверить
fможет измениться (например, передав свой адрес какой-то не встроенной функции, которая мог изменить это) - пометить его как изменчивый или
- сделайте это явно атомарным типом и запросите семантику запроса
Что касается аппаратного обеспечения, то ваше беспокойство по поводу того, что физическая память «выделяется» во время переключения контекста, не является проблемой Оба программных потока совместно используют одно и то же оборудование памяти и кэш-память, поэтому здесь нет риска возникновения противоречий независимо от того, какой протокол согласованности / согласованности относится между сердечники.
Скажем, оба магазина были выпущены, и аппаратное обеспечение памяти решает переупорядочить их. Что это на самом деле значит? Возможно, адрес f уже находится в кэше, поэтому он может быть записан немедленно, но хранилище x откладывается до тех пор, пока не будет извлечена эта строка кэша. Ну а читать от х зависит от того же адреса, поэтому либо:
- загрузка не может произойти, пока не произойдет выборка, и в этом случае разумная реализация должна выдать хранилище в очереди до загрузки в очередь
- или загрузка может заглянуть в очередь и получить значение x, не дожидаясь записи
В любом случае, учтите, что приоритет ядра, необходимый для переключения потоков, сам по себе выдаст любые барьеры загрузки / сохранения, необходимые для согласованности состояния планировщика ядра, и должно быть очевидно, что переупорядочение оборудования не может быть проблемой в этой ситуации.
Реальная проблема (которую вы пытаетесь избежать) — это ваше предположение, что нет переупорядочения компилятора: это просто неправильно.
Вам понадобится только забор компилятора. Из документации по ядру Linux на Барьеры памяти (ссылка на сайт):
Барьеры памяти SMP сводятся к барьерам компилятора на однопроцессорных
скомпилированные системы, потому что предполагается, что процессор будет
самосогласованный и правильно упорядочит перекрывающиеся доступы
уважение к себе.
Чтобы расширить это, причина, почему синхронизация не на аппаратном уровне требуется, чтобы:
-
Все потоки в однопроцессорной системе совместно используют одну и ту же память, и, таким образом, нет проблем с когерентностью кэша (таких как задержка распространения), которые могут возникнуть в системах SMP, и
-
Любые неупорядоченные инструкции загрузки / сохранения в конвейере выполнения ЦП будут либо зафиксированы, либо отменены в полном объеме если конвейер очищен из-за преимущественного переключения контекста.
Этот код может никогда не завершиться (в потоке 2), так как компилятор может решить поднять все выражение из цикла (это похоже на использование флага isRunning, который не является энергозависимым).
Тем не менее, вам нужно беспокоиться о 2 типах переупорядочения: компилятор и процессор, оба могут свободно перемещать магазины. Посмотреть здесь: http://preshing.com/20120515/memory-reordering-caught-in-the-act для примера. На данный момент код, который вы описали выше, зависит от компилятора, флагов компилятора и конкретной архитектуры. Цитируемая вики вводит в заблуждение, поскольку может указывать на то, что внутреннее переупорядочение не зависит от процессора / компилятора, а это не так.
Что касается x86, хранилища вне порядка сделаны согласованными с точки зрения выполнения кода в отношении выполнения программы. В этом случае «программный поток» — это просто поток инструкций, которые выполняет процессор, а не что-то ограниченное «программой, выполняющейся в потоке». Все инструкции, необходимые для переключения контекста и т. Д., Считаются частью этого потока, поэтому согласованность поддерживается между потоками.
Переключатель контекста должен сохранять полное состояние компьютера, чтобы его можно было восстановить до возобновления приостановленного потока. Состояния машины включают в себя регистры процессора, но не конвейер процессора.
Если вы предполагаете, что компилятор не переупорядочивается, это означает, что все аппаратные инструкции, которые «на лету» должны быть выполнены до переключения контекста (то есть прерывания), в противном случае они теряются и не сохраняются переключателем контекста. механизм. Это не зависит от аппаратного переупорядочения.
В вашем примере, даже если процессор поменяет две аппаратные инструкции «x = 42» и «f = 1», указатель инструкции уже после второй, и поэтому обе инструкции должны быть завершены до начала переключения контекста. если бы это было не так, поскольку содержимое конвейера и кэша не является частью «контекста», они были бы потеряны.
Другими словами, если прерывание, которое вызывает переключение ctx, происходит, когда регистр IP указывает на инструкцию, следующую за «f = 1», то все инструкции до этой точки должны завершить все свои эффекты.
С моей точки зрения, процессор получает инструкции по одной.
В вашем случае, если «f = 1» был спекулятивно выполнен до «x = 42», это означает, что обе эти инструкции уже находятся в конвейере процессора. Единственный возможный способ запланировать текущий поток — это прерывание. Но процессор (по крайней мере на X86) сбросит инструкции конвейера перед обработкой прерывания.
Так что не нужно беспокоиться о переупорядочении в однопроцессоре.