Подтвердить что ты не робот

Является ли переупорядочение памяти видимым для других потоков на однопроцессорном компьютере?

Общеизвестно, что современные архитектуры процессоров используют оптимизацию производительности, что может привести к нарушению порядка выполнения. В однопоточных приложениях может также произойти переупорядочение памяти, но оно не должно быть понятным для программистов, как если бы память была доступна в программном порядке. И для 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;

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

В соответствии с этим wiki,

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

Хотя в нем явно не упоминалось однопроцессорное многопоточное приложение, оно включает этот случай.

Я не уверен, что это правильно/закончено или нет. Обратите внимание, что это может сильно зависеть от аппаратного обеспечения (модель слабой/сильной памяти). Поэтому вы можете включить оборудование, которое вы знаете в ответах. Спасибо.

PS. устройства ввода/вывода и т.д. здесь меня не беспокоит. И это одноядерный однопроцессор.

Изменить. Спасибо Nitsan за напоминание. Мы не предполагаем, что здесь нет переупорядочения компилятора (только переупорядочение аппаратного обеспечения), а цикл в потоке 2 не оптимизирован. Again, devil находится в деталях.

4b9b3361

ОТВЕТЫ

Ответ 1

Как вопрос на С++, ответ должен состоять в том, что программа содержит гонку данных, поэтому поведение undefined. На самом деле это означает, что он может печатать что-то другое, чем 42.

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

[Я предполагаю, что с "однопроцессорной" машиной вы имеете в виду процессоры с одним ядром и аппаратным потоком.]

Теперь вы говорите, что вы хотите предположить, что переупорядочение компилятора или исключение цикла не произойдет. При этом мы покинули область С++ и действительно спрашиваем о соответствующих машинных инструкциях. Если вы хотите исключить переупорядочение компилятора, мы, возможно, также исключаем любую форму инструкций SIMD и учитываем только инструкции, работающие в одном месте памяти за раз.

Таким образом, по существу thread1 имеет две инструкции хранения в хранилище-хранилище от-до-x, тогда как thread2 имеет test-f-и-loop-if-not-zero (это может быть несколько инструкций, но включает в себя load-from-f), а затем load-from-x.

На любой аппаратной архитектуре, которую я знаю или могу разумно представить, поток 2 будет печатать 42.

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

Единственное событие, которое может помешать здесь, - это прерывание (как используется для запуска превентивного контекстного переключателя). Гипотетическая машина, которая сохраняет все состояние своего текущего состояния конвейера выполнения при прерывании и восстанавливает его при возврате из прерывания, может привести к другому результату, но такая машина непрактична, а afaik не существует. Эти операции создавали бы некоторую дополнительную сложность и/или требовали бы дополнительных избыточных буферов или регистров, все без уважительной причины - кроме того, чтобы разорвать вашу программу. Настоящие процессоры либо сбрасывают или откатывают текущий конвейер при прерывании, что достаточно, чтобы гарантировать последовательную согласованность для всех инструкций на одном аппаратном потоке.

И нет проблемы с моделью памяти, о которой нужно беспокоиться. Более слабые модели памяти исходят из отдельных буферов и кэшей, которые отделяют отдельные аппаратные процессоры от основной памяти или кеша уровня n, которые они фактически разделяют. Один процессор не имеет одинаково разделенных ресурсов и не имеет оснований для их использования для нескольких (чисто программных) потоков. Опять же нет причин усложнять архитектуру и ресурсы отходов, чтобы заставить подсистему процессора и/или памяти понять что-то вроде отдельных контекстов потоков, если нет отдельных ресурсов обработки (процессоры/аппаратные потоки), чтобы эти ресурсы были заняты.

Ответ 2

Сильное упорядочение памяти выполняет инструкции доступа к памяти с тем же самым порядком, что и в программе, его часто называют "упорядочением программ".

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

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.

@Эрик в ответ на ваши комментарии.

инструкция быстрой записи строки "stosd", может хранить строку не в порядке внутри ее операции. В многопроцессорной среде, когда процессор хранит строку "str", другой процессор может наблюдать, что str [1] записывается до str [0], в то время как логический порядок, предположительно, записывает str [0] перед str [1];

Но эти инструкции не переупорядочиваются с любыми другими магазинами. и должны иметь точную обработку исключений. Когда исключение встречается в середине stosd, реализация может выбрать задержку, чтобы все вспомогательные хранилища вне порядка (не обязательно означающие всю команду stosd) должны были зафиксировать перед контекстным переключателем.

Отредактировано для удовлетворения заявлений, сделанных так, как если бы это был вопрос С++:

Даже это рассматривается в контексте С++. Насколько я понимаю, стандартный подтверждающий компилятор должен НЕ переупорядочить назначение x и f в потоке 1.

$1.9.14 Каждое вычисление значения и побочный эффект, связанные с полным выражением, секвенированы до, каждое значение вычисление и побочный эффект, связанные со следующим полным выражением, которое должно быть оценено.

Ответ 3

Это не вопрос C или С++, поскольку вы явно не предполагали переупорядочения загрузки/хранения, какие компиляторы для обоих языков вполне разрешены.

Допустив это предположение ради аргумента, обратите внимание, что цикл никогда не сможет выйти, если вы не выполните:

  • дает компилятору некоторые причины полагать, что f может измениться (например, передав свой адрес некоторой не-встроенной функции, которая могла бы ее изменить)
  • отметьте его изменчивым, или
  • сделать его явно атомным типом и запросить получить семантику

На аппаратной стороне ваше беспокойство о том, что физическая память "зафиксирована" во время переключения контекста, не является проблемой. Оба программных потока используют одно и то же аппаратное обеспечение и кеш памяти, поэтому нет риска несогласованности там, где существует протокол согласованности/согласованности между ядрами.

Скажите, что оба магазина были выпущены, а аппаратное обеспечение памяти решает переупорядочить их. Что это на самом деле значит? Возможно, адрес f уже находится в кеше, поэтому его можно записать сразу, но хранение x отложено до тех пор, пока не будет выбрана строка кэша. Ну, чтение из x зависит от того же адреса, поэтому либо:

  • загрузка не может произойти до тех пор, пока не произойдет выборка, и в этом случае разумная реализация должна выдать хранилище в очереди перед загрузкой в ​​очередь
  • или загрузка может заглянуть в очередь и извлечь значение x, не дожидаясь записи

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

Реальная проблема (которую вы пытаетесь избежать) - это ваше предположение о том, что переупорядочения компилятора нет: это просто неправильно.

Ответ 4

Вам понадобится только ограждение компилятора. В документах ядра Linux на барьерах памяти (ссылка):

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

Чтобы развернуть это, причина, по которой синхронизация не требуется на аппаратном уровне, такова:

  • Все потоки однопроцессорной системы используют одну и ту же память и, следовательно, отсутствуют проблемы с кэшированием (например, латентность распространения), которые могут возникать в системах SMP, и

  • Любые инструкции по загрузке/хранению вне порядка в конвейере выполнения ЦП будут либо зафиксированы, либо откат в полном объеме, если конвейер будет сброшен из-за превентивного контекстного переключателя.

  • /p >

Ответ 5

Этот код, возможно, никогда не завершится (в потоке 2), поскольку компилятор может решить вытащить все выражение из цикла (это похоже на использование флага isRunning, который не является изменчивым). Тем не менее, вам нужно беспокоиться о двух типах переупорядочений здесь: компилятор и процессор, оба могут свободно перемещать магазины. См. Здесь: http://preshing.com/20120515/memory-reordering-caught-in-the-act для примера. На этом этапе описанный выше код находится во власти компилятора, флагов компилятора и конкретной архитектуры. Процитированные wiki вводят в заблуждение, так как это может свидетельствовать о том, что внутренний переупорядочивание не во власти процессора/компилятора, что не так.

Ответ 6

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

Ответ 7

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

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

В вашем примере, даже если процессор обменивает две аппаратные команды "x = 42" и "f = 1", указатель инструкции уже после второго, и поэтому обе инструкции должны быть выполнены до того, как начнется контекстный переключатель, если бы это было не так, поскольку содержимое конвейера и кеша не являются частью "контекста", они будут потеряны.

Другими словами, если прерывание, вызывающее переключатель ctx, происходит, когда регистр IP указывает на команду, следующую за "f = 1", тогда все инструкции перед этой точкой должны были завершить все их эффекты.

Ответ 8

С моей точки зрения, процессор извлекает инструкции один за другим. В вашем случае, если "f = 1" было спекулятивно выполнено до "x = 42", это означает, что обе эти команды уже находятся в конвейере процессора. Единственный возможный способ запланировать текущий поток - прерывание. Но процессор (по крайней мере, на X86) очистит инструкции по конвейеру перед тем, как обслуживать прерывание. Поэтому не нужно беспокоиться о переупорядочении в однопроцессорном режиме.