Видна ли переупорядочение памяти другим потокам на однопроцессоре?

Часто современные архитектуры ЦП используют оптимизацию производительности, которая может привести к неупорядоченному выполнению. В однопоточных приложениях также может происходить переупорядочение памяти, но оно невидимо для программистов, как если бы доступ к памяти осуществлялся в программном порядке. А для 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++ multithreading memory-barriers
person Eric Z    schedule 06.01.2013    source источник
comment
Если вы запрещаете переупорядочивание компилятора (C ++), хотите ли вы знать, как скомпилированный код (= машинный код) работает на конкретной архитектуре компьютера? Вы должны указать целевую платформу (архитектуру машины) и удалить тег c ++.   -  person yohjp    schedule 08.01.2013
comment
Человек, переупорядочивание компилятора и переупорядочение оборудования - это разные вещи. Когда компилятор установлен, оборудование все еще может переупорядочивать доступ к инструкциям / памяти по своему усмотрению, основываясь на нескольких принципах. Кстати, разные языки могут иметь разные модели памяти, поэтому я хочу сосредоточиться только на C ++. Что вы думаете?   -  person Eric Z    schedule 08.01.2013
comment
Так разве переупорядочение аппаратных инструкций не является другой проблемой, чем операции с памятью (то есть необходимость согласованности кеша, которая не является частью вашего сценария)? Даже с сильной моделью памяти вам все равно нужны барьеры памяти, чтобы предотвратить переупорядочение инструкций.   -  person Chris O    schedule 08.01.2013
comment
1. Да, меня волнует переупорядочение доступа к памяти, а не переупорядочение инструкций. 2. Нет, барьеры памяти не могут помешать переупорядочению инструкций. Команды все еще могут быть переупорядочены, если их привязка к памяти упорядочена. Но в большинстве случаев это вас не волнует, если порядок доступа к памяти соответствует тому, что вам нужно.   -  person Eric Z    schedule 09.01.2013
comment
@EricZ Я также согласен с вами, что такое переупорядочение компилятора / оборудования. Как вы знаете, новый язык C ++ 11 имеет четко определенную модель памяти для многопоточной программы на абстрактной машине. Тем не менее, компилятор C ++ 11 и целевой процессор МОГУТ юридически переупорядочивать любые инструкции с доступом к памяти или оптимизировать их во время компиляции и выполнения, при условии, что переупорядочение компилятора / оборудования соответствовать правилам модели памяти C ++ 11, то есть правилу «как если бы» C ++. ИМО, я боюсь, что игнорирование переупорядочения / оптимизации компилятора может сделать этот вопрос бессмысленным.   -  person yohjp    schedule 09.01.2013
comment
@yohjp, если вы настаиваете, вы всегда можете сделать f изменчивым, чтобы условие цикла не было оптимизировано;) Теперь проблема (вопрос, на котором я хочу сосредоточиться) все еще существует, верно?   -  person Eric Z    schedule 09.01.2013
comment
Если я правильно вас понял, вы имеете в виду только переупорядочение доступа к памяти, выполняемое внутри ЦП? Если да, то я не верю, что переключение контекста возможно между инструкциями, которые уже находятся внутри конвейера ЦП? В этом случае я полагаю, что конвейер будет очищен, и либо все инструкции будут зафиксированы, либо откатятся, что сделает невозможным просмотр неупорядоченного доступа к памяти.   -  person skoy    schedule 09.01.2013
comment
@skoy, да, в этом есть смысл. Просто не могу найти никаких ссылок, подтверждающих это.   -  person Eric Z    schedule 10.01.2013
comment
@EricZ Практически ты прав, но теоретически ошибаешься. Это должно быть atomic<int> (или atomic_int) вместо volatile int для межпотоковой связи в модели памяти C ++ 11 (и C11). См. Атомарную и изменчивую модель памяти C ++ 11, Является ли volatile int в C таким же хорошим, как std :: atomic ‹int› в C ++ 0x?, Почему std :: atomic перегружает каждый метод квалификатором volatile? и т. Д.   -  person yohjp    schedule 10.01.2013

Ответы (8)


arrow_upward
20
arrow_downward

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

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

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

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

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

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

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

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

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

person JoergB    schedule 10.01.2013
comment
все, что он спросил, - распечатает ли поток 2 0. Ответ четко определен, НЕТ. Я сбит с толку, сначала вы говорите: «На самом деле, это означает, что он может печатать что-то другое, кроме 42», затем на любой аппаратной архитектуре, о которой я знаю или могу разумно представить, поток 2 напечатает 42. Итак, что именно является реальностью, что воображение? - person ; 10.01.2013
comment
@arrows: обратите внимание, что утверждение on основано на более конкретном наборе предположений, тогда как другое основано исключительно на высоком уровне языка C ++, где это UB и может привести к тому, что все вы сразу забеременеете хомяками. - person PlasmaHH; 11.01.2013
comment
По правилам C ++ он мог печатать что угодно или делать то, что хомяк. - person JoergB; 11.01.2013
comment
[Повторить попытку, поскольку истекло время ожидания редактирования] По правилам C ++ он может печатать что угодно или делать то же самое. С настоящим компилятором C ++ он может вывести 0 (если это начальное значение x) даже на однопроцессоре (с управляемой прерываниями, вытесняющей многопоточностью) из-за переупорядочения компилятора. С предположениями, которые нам велят сделать (без переупорядочивания компилятора, однопроцессор), ... выведет 42 утверждения. - person JoergB; 11.01.2013

arrow_upward
5
arrow_downward

При строгом упорядочивании памяти команды доступа к памяти выполняются в том же порядке, который определен в программе, это часто называют «упорядочением программ».

Может использоваться более слабое упорядочение памяти, чтобы позволить процессору переупорядочивать доступ к памяти для повышения производительности, это часто называют «упорядочиванием процессора».

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 ++. Как я понимаю, стандартный подтверждающий компилятор НЕ переупорядочивает присвоение x и f в потоке 1.

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

person Community    schedule 09.01.2013
comment
+1 это правда. Еще лучше, если бы вы могли привести пример слабой модели памяти, которая меняет местами STORE при фиксации всех операций с памятью перед переключением контекста потока, как @skoy, упомянутый выше. - person Eric Z; 10.01.2013
comment
Возможно, это делает Itanium, это определенно слабая модель памяти. - person Chris O; 10.01.2013

arrow_upward
2
arrow_downward

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

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

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

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

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

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

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

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

person Useless    schedule 12.01.2013
comment
Вы действительно не читаете мой вопрос, не так ли? Пожалуйста, обратите внимание на комментарии, которые я сделал в этой теме, прежде чем публиковать какой-либо ответ. - person Eric Z; 15.01.2013
comment
Я думал, что рассмотрел как ваше (неверное) предположение о компиляторе, так и вопрос о переупорядочении на уровне оборудования отдельно. Вы что-то еще имели в виду? - person Useless; 15.01.2013
comment
Как я уже сказал в комментариях к своему посту, я не говорю, что оптимизации компилятора не существует, и игнорирую их субъективно. Вместо этого я пытаюсь перейти к сути, просто фокусируясь на проблеме только на переупорядочивании оборудования. При желании вы можете использовать различные способы (например, volatile), чтобы оптимизация компилятора не выходила за рамки ваших ожиданий (например, оптимизировать цикл for). Ваша точка зрения относительно переупорядочивания оборудования имеет смысл, +1. - person Eric Z; 16.01.2013

arrow_upward
2
arrow_downward

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

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

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

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

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

person etherice    schedule 29.05.2013

arrow_upward
1
arrow_downward

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

person Nitsan Wakart    schedule 06.01.2013
comment
Предположим, не происходит переупорядочения компилятора, чтобы сосредоточиться на переупорядочивании оборудования. Только что отредактировал свой пост. - person Eric Z; 06.01.2013

arrow_upward
1
arrow_downward

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

person MJZ    schedule 06.01.2013
comment
Я не следую этому рассуждению, потому что ваши утверждения относительно согласованности между потоками явно неверны на многопроцессорной машине. - person usr; 06.01.2013

arrow_upward
0
arrow_downward

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

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

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

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

person knulp    schedule 10.01.2013

arrow_upward
0
arrow_downward

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

person zhebin jin    schedule 21.07.2015