Необходимы ли отношения синхронизации, чтобы избежать дублирования вызова функции?
Рассмотрим этот пример:
#include <iostream>
#include <atomic>
#include <random>
#include <thread>
int need_close(){
random_device rd;
std::mt19937 gen(rd());
uniform_int_distribution<int> distribute(0, 2);
return distribute(gen);
}
void invoke(std::atomic<bool>& is_close){
if (is_close.load(std::memory_order::relaxed)){ // #1
return;
}
auto r = need_close();
if (r==0){
is_close.store(true,std::memory_order::relaxed);
}
}
int main(){
std::atomic<bool> is_close{false};
std::thread t1([&](){
for(auto i = 0; i<100000;i++)
invoke(is_close);
});
std::thread t2([&](){
for(auto i = 0; i<100000;i++)
invoke(is_close);
});
t1.join();
t2.join();
}
В этом примере достаточно ли порядка relaxed, чтобы избежать вызова need_close, как только поток увидит это is_close == true (не сразу, но в какой-то момент, когда поток сможет прочитать is_close==true)? В этом примере кажется, что мне не нужна синхронизация, чтобы избежать гонки данных, поскольку в этом примере нет конфликтных действий. Однако из реализации компилятора компилятор может переупорядочить #1 в любое место, следующее за ним, поскольку здесь используется relaxed. Например, если #1 перемещается в какое-то место после точки вызова need_close, need_close всегда будет вызываться снова, даже если is_close установлено значение true, чего не ожидается. Итак, мне интересно, необходим ли Acquire/Release порядок, чтобы избежать переупорядочения кода компилятором, чтобы логика была ожидаемой?
«избегать дублирования вызова» вы имеете в виду оба потока, входящие в функцию одновременно, или просто «вызов функции дважды»? Для последнего есть std::call_once (с встроенной необходимой синхронизацией)
@HolyBlackCat Вы имеете в виду, что компилятор может изменить порядок кода так, что #1 станет бесполезным?
Это возможно даже без перезаказа. Представьте себе, что один поток вызывает need_close() и делает паузу перед установкой флага, затем второй поток входит invoke() и также вызывает need_close().
Ох, что говорит @HolyBlackCat, это безубыточно с memory_order_seq_cst (последовательная последовательность)
@HolyBlackCat Если #1 не переупорядочен, need_close не будет вызываться в какой-то момент после чтения темы close==true. Вместо этого, если компилятор меняет порядок #1, need_close все равно вызывается, даже если поток читает close==true, вот в чем разница.
@MSalters Если переупорядочения нет, поток в конечном итоге увидит значение close==true и не будет вызывать need_close.
Я не понимаю, что вы пытаетесь сказать. Легко продемонстрировать, что это может вызвать need_close() дважды, добавив после него задержку: gcc.godbolt.org/z/68Kn9Khv8
@HolyBlackCat Я имел в виду: достаточно ли порядка relaxed, чтобы need_close не вызывался, как только поток увидит is_close == true? Если компилятор меняет порядок кода, всегда можно вызвать need_close.
@HolyBlackCat gcc.godbolt.org/z/h6a7Ysfa9, в этом примере print не вызывается, как только поток увидит is_close == true.
если is_close.load() истинно, выполняется ранний выход return, поэтому больше ничего в функции не происходит. Это выполняется перед вызовом need_close. Компиляторы не могут просто произвольно перетасовывать строки исходного кода (в любом случае они не оптимизируют это), они должны соблюдать последовательность, чтобы не нарушать однопоточные программы. ЦП может получить и декодировать машинный код для need_close() в тени неверно предсказанной ветки, как в однопоточном коде, но конечный результат должен быть таким, как если бы код выполнялся в программном порядке с is_close.load(), выдающим какое-либо значение.
«как только тред увидит is_close == true» Но это бесполезный вопрос, не так ли? По определению, когда он увидит, что это правда, он не пройдет первым if. Вопрос в том, когда он это увидит.
@HolyBlackCat Питер прочитал мое замешательство. Если первый if переупорядочен в какое-то место после точки вызова need_close() компилятором, need_close будет продолжать вызываться независимо от того, когда поток увидит is_close==true
@PeterCordes О, компилятор также должен подчиняться принципу sequenced-before: первый if нельзя переупорядочить в какое-то место после места вызова need_close(), даже если порядок relaxed позволит компилятору это сделать, верно?
Совершенно уверен, что такое переупорядочение незаконно, независимо от порядка памяти, компилятор этого не сделает. Стандарт формулируется не с точки зрения переупорядочения, а с точки зрения того, когда значение становится видимым для потока. Когда люди говорят о переупорядочении, они обычно имеют в виду ситуации, когда вы выполняете >1 операций чтения/записи подряд, и значения становятся видимыми для другого потока в странном порядке, а затем они говорят, что операции чтения и/или записи были «переупорядочены» относительно друг друга. Но это не то, что происходит*, разные значения становятся видимыми в странном порядке. [1/2]
[2/2] (*По крайней мере, в абстрактной машине стандарта. Возможно, компилятор ДЕЙСТВИТЕЛЬНО переупорядочивает на уровне сборки, но из-за правила «как если бы» вам не нужно об этом беспокоиться, поскольку этого не произойдет, если присутствуют побочные эффекты.)
Забудьте на мгновение о нитях и пусть is_close будет обычным bool. Думаете ли вы теперь, что компилятор может переместить проверку if (is_close) после need_close()? Вы бы точно не стали. То, что в опубликованном случае тип другой и процедура выполняется в потоке, ничего не меняет в отношении такого (запрещенного) переупорядочения.
@xmh0511: Верно, процессор может начать работу need_close(), все еще ожидая значения для is_close.load(relaxed), и пока он в конечном итоге увидит false, он может подтвердить этот путь выполнения как правильный, удаляя эти инструкции. Но если нет, то эта спекулятивно выполненная работа на самом деле является ошибочной спекуляцией. Компилятор мог изменить порядок вещей, только размышляя аналогичным образом, например, безоговорочно выполнять некоторые вычисления во временном, но фактически фиксируя видимые побочные эффекты только после проверки результата is_close.load().
Многопоточность не влияет на однопоточную когерентность. В этом случае ни один поток не может сохранить true, а затем прочитать false на следующей итерации. Но любой поток может прочитать ложь много раз после того, как (в реальном смысле) другой поток сохранит истину. Существуют некоторые (неопределенные) ограничения, согласно которым другой поток должен в конечном итоге увидеть хранилище true у другого, но не делается никаких предположений о том, как быстро это произойдет, особенно при использовании ослабленного порядка памяти.
Ответы 3
Как узнать, можно ли пойти в то отделение, по которому звонят need_close() ? Прочитав значение внутри is_close, невозможно сделать это, не зная этого значения, поэтому компилятор не сможет изменить порядок # 1 после вызова need_close() даже с ослабленными ограничениями порядка, но это не решает вашу проблему.
Упорядочение не предотвратит двойной вызов функции разными потоками, например, между чтением и need_close(), другой поток может выполнить обе операции, поэтому need_close() будет вызываться дважды.
Вы просто не можете предотвратить двойной вызов need_close(). Параллельные вызовы должны быть безопасными, если сделать их логику совместимой с параллельными вызовами или использовать мьютекс.
@DevilishSprits Я не запрещал need_close звонить дважды, я хочу запретить need_close звонить один раз is_close==true. Меня здесь смущает, может ли компилятор изменить порядок первой ветки if после некоторого места, следующего за need_close().
Компилятор не будет переупорядочивать это, но в вашем текущем коде есть TOCTOU, поскольку is_close становится истинным между этими строками из-за действия другого потока.
В комментариях ОП:
Я хочу, чтобы
need_closeне звонили один разis_close==true.
В этом коде нет ничего, что могло бы предотвратить это при любом порядке памяти с переупорядочением выполнения или без него. Это все отвлекающий маневр.
Если в этом смысл исходного вопроса, то ответ — да. Необходима некоторая форма синхронизации.
Совершенно разумно, что оба потока load() принимают значение false и переходят к выполнению need_close() до того, как другой поток выполнит store() из true, ничего не переупорядочивая.
Не имеет значения, сколько времени need_close() потребуется для выполнения, но в этом примере вполне вероятно, что оба потока проводят большую часть своего времени, «преследуя друг друга внутри» need_close(), потому что логически работа need_close(), вероятно, во много раз превышает работу по проверке атомарного флага и зацикливание.
Примечание. Никогда не аргументируйте, что код X всегда (или никогда) будет выполняться быстрее, чем Y, поскольку обычно предполагается, что любой поток можно приостановить в любой момент посредством упреждающей многозадачности. Подобные аргументы представляют собой само понятие состояния гонки.
Простое решение — ввести мьютекс.
Вот некоторое обсуждение расслабленного порядка памяти и потенциально нелогичного поведения, которое оно допускает: https://en.cppreference.com/w/cpp/atomic/memory_orderhttps://en.cppreference.com/w/cpp/atomic/memory_order#Relaxed_ordering
Однако другой поток в конечном итоге сможет увидеть значение (true), сохраненное другим потоком, не так ли? Я думаю, что в то время need_close не будет называться.
см. godbolt.org/z/YWeq36TbK, need_close в ветке через некоторое время не будет вызываться.
@ xmh0511 Будьте очень осторожны при инструментировании std::cout<<: библиотека почти наверняка выполняет операции внутренней синхронизации, которые могут привести к тому, что true станет видимым для другого потока. Нет никакой гарантии, что поведение вашей программы будет таким же, когда вы ее удалите! Допустимое использование ослабленного порядка памяти весьма ограничено, поскольку обычно вам необходимо обеспечить синхронизацию другими способами или вы кодируете состояние гонки без определенного вывода.
Видимо, на самом деле вы хотели спросить, можно ли вызвать need_close, даже если is_close.load(relaxed) вернуло true, поскольку компилятор переместил проверку позже. Несмотря на ваше редактирование, в заголовке говорится о «дубликативном» вызове, как будто в этом коде было что-то, что в противном случае предотвратило бы его двойной вызов. (Которого, как обсуждается в комментариях и других ответах, нет, вы можете получить несколько вызовов даже с помощью seq_cst.)
Основное правило выполнения процессорами вне порядка выполнения и переупорядочения во время компиляции заключается в том, что однопоточный код не должен нарушаться.
Если is_close.load() истинно, выполняется ранний выход return, поэтому больше ничего в функции не происходит. Это выполняется перед вызовом need_close.
Компиляторы не могут просто произвольно перетасовывать строки исходного кода (во всяком случае, это не то, как они оптимизируют), они должны соблюдать последовательность, чтобы не нарушать однопоточные программы, и правила упорядочения перед многопоточными программами.
ЦП может получить и декодировать машинный код для need_close() в тени неверно предсказанной ветки (что может случиться в однопоточной программе), но конечный результат должен быть таким, как если бы код выполнялся в программном порядке, а is_close.load() произвел что угодно. ценить.
relaxed означает, что значение не должно быть готово до тех пор, пока мы не прочитаем и/или не запишем некоторые другие вещи, но на практике это произойдет из-за спекулятивного выполнения процессором вне очереди (который может отбросить ошибочно предполагаемую работу, когда он откатывается к согласованному состоянию после неверного прогноза), а не за счет того, что компилятор статически переупорядочивает вещи таким образом, чтобы видимые побочные эффекты происходили иначе, чем на абстрактной машине, если другие потоки не выполняются.
Поскольку ваш need_close() имеет видимые побочные эффекты (ввод-вывод в форме построения и чтения из объекта std::random_device), в этом случае компилятор не может сделать ничего полезного без каких-либо условий.
Кто боится большого плохого оптимизирующего компилятора? на LWN рассказывает о некоторых практических примерах переупорядочения во время компиляции, включая некоторые тонкие и интересные, а также о некоторых ограничениях того, что компиляторы не должны делать.
См. также https://preshing.com/20120625/memory-ordering-at-compile-time/ и другие статьи Прешинга, чтобы лучше понять, как об этом думать.
Ха! Я только что добавил комментарий о том, что многопоточность не может нарушить однопоточный код.
@PeterCordes Пожалуйста, посмотрите на этот пример godbolt.org/z/s9G5WzW4K, возможно ли, что need_close все еще вызывается несколько раз в первом потоке после того, как is_close.store(true,std::memory_order::release) установлено как истинное во втором потоке, даже с самым сильным Memory_order seq_cst ?
@xmh0511: Что ты имеешь в виду под «после»? После того, как магазин станет глобально видимым? Нет, потому что это будет означать, что invoke видит это как true.
@PeterCordes После того, как хранилище станет глобально видимым Нет, я имел в виду после выполнения is_close.store(true,std::memory_order::release).
@xmh0511: xmh0511: «выполнено» не является значимым моментом времени с точки зрения порядка и видимости в памяти. Если вы имеете в виду «выполнено», поскольку инструкция сохранения записывает адрес и данные в буфер хранения на типичном современном процессоре, то нет, другие ядра все еще могут иметь строку кэша в состоянии MESI Shared и могут читать старое значение. Только после того, как их копия станет недействительной (в ответ на команду Read For Ownership (RFO) от ядра, пытающегося зафиксировать запись буфера хранилища в своем кеше после того, как хранилище выйдет из буфера переупорядочения), их следующее чтение необходимо будет проверить с другими ядрами. .
@ xmh0511: seq_cst разрешает любое чередование порядка выполнения программы между потоками. Если ваша программа не содержит гонок данных, задержка видимости из-за буфера хранилища или что-то еще неотличимо от того, что просто не произойдет позже. memory_order касается порядка, в котором вещи становятся видимыми для других тредов, и именно так вам следует об этом думать. Внутренние детали ЦП важны только в том случае, если вы пытаетесь понять, как они работают, а также некоторые механизмы, которые могут привести к переупорядочению.
@petercordes, возможно, что эти load все еще читают старое значение (т. е. ложное) после выполнения is_close.store(true,std::memory_order::release) (т. е. инструкция сохранения записывает адрес и данные в буфер хранилища на типичном современном CP), верно?
@xmh0511: На данный момент это все еще текущее значение is_close. Значение is_close не меняется до тех пор, пока его хранилище не зафиксирует кэш L1d. Время записи в буфер хранилища не имеет значения и может даже произойти в результате ошибочного предположения, которое будет отменено и никогда не станет глобально видимым. Это ядро может даже не отправить RFO до тех пор, пока инструкция сохранения не будет удалена из ROB. (Сохранения в буфере хранилища после завершения соответствующей инструкции сохранения называются «постепенными» хранилищами и готовы к фиксации в кэше, как только мы получим эксклюзивное право владения строкой)
@PeterCordes Со стандартной точки зрения, говоря, что у нас есть два потока t1 и t2, порядок модификации такой v0, v1, где v0 создается в результате инициализации атомарного объекта M и v1 создается хранилищем t2, операция сохранения в t2 не произойдет - перед загрузкой в t1, t1 загружается M много раз, возможно, что загрузка в t1 всегда может быть прочитана v0 без нарушения каких-либо правил, определенных в [intro.races], правильно ли я понимаю?
@ xmh0511 Необходимо понимать, что классическая модель архитектуры фон Неймана (VNAM — en.wikipedia.org/wiki/Von_Neumann_architecture) уже давно не работает на любой современной многоядерной платформе. Многоуровневое кэширование на многоядерных процессорах, а также спекулятивное выполнение и гиперпоточность означают, что рассуждения, основанные на VNAM, часто ошибочны, а иногда и совершенно бессмысленны. В стандарте C++ очень четко указано, что расслабленные операции с памятью не являются событиями синхронизации.
@ xmh0511: стандарт ISO C++ имеет две гарантии возможной видимости хранилищ для загрузки в других потоках, но ни одна из них не находится в [intro.races], так что да, это правильно. (Гарантии на самом деле сформулированы как «должны», никаких формальных требований нет, потому что сложно формально выразить наилучшие усилия в системах без жестких гарантий в реальном времени. Зачем устанавливать стоп-флаг с помощью `memory_order_seq_cst`, если вы проверяете его с помощью `memory_order_relaxed` цитирует их из [intro.multithread] и [atomics.order]
@PeterCordes Итак, этот случай также может произойти, даже если мы использовали seq_cst порядок памяти для операций загрузки и сохранения, верно?
@xmh0511: Да, конечно. seq_cst не делает хранилища видимыми для загрузок быстрее, а просто контролирует порядок доступа потоков к общей памяти (или когерентному кешу).
@PeterCordes Спасибо. Я прочитал ваши связанные ответы, iiuc, с точки зрения реализации, загрузка не видела хранилище, которое было в порядке модификации (концепция стандарта С++), из-за возможной задержки, в том случае, если стандарт С++ использует порядок модификации. и никаких нарушений правил в [intro.races], позволяющих этому произойти или выражающих/подразумевающих такую ситуацию.
Нет
memory_orderне позволит этому коду вызыватьneed_close()более одного раза. Также я предлагаю заменитьrand()на что-нибудь другое (что-то потокобезопасное), если ваш вопрос не конкретно об этом.