[Замена предыдущего ответа.]
Первоначальный вопрос был " Есть ли основания для использования метода" exchange "? ". И короткий ответ: нет, нет веской причины для этого, на самом деле turn.store(1) более правильно.
Но даже с turn.store(1) я думаю, что у вас есть почти полностью не действительный C ++.
Так вот более длинный ответ ...
В поисках правильной реализации алгоритма Петерсона
Алгоритм Петерсона будет работать, если все загрузки / хранилища flag0, flag1 и turn memory_order_seq_cst , таким образом:
std::atomic<int> flag0(0),flag1(0),turn(0);
void lock(unsigned index)
{
if (0 == index)
{
flag0.store(1, std::memory_order_seq_cst) ;
turn.store(1, std::memory_order_seq_cst) ;
while (flag1.load(std::memory_order_seq_cst)
&& (1 == turn.load(std::memory_order_seq_cst)))
std::this_thread::yield();
}
else
{
flag1.store(1, std::memory_order_seq_cst) ;
turn.store(0, std::memory_order_seq_cst) ;
while (flag0.load(std::memory_order_seq_cst)
&& (0 == turn.load(std::memory_order_seq_cst)))
std::this_thread::yield();
}
}
void unlock(unsigned index)
{
if (0 == index)
flag0.store(0, std::memory_order_seq_cst) ;
else
flag1.store(0, std::memory_order_seq_cst) ;
}
[Конечно, std::memory_order_seq_cst является по умолчанию - но не вредно быть явным ... оставляя в стороне беспорядок.]
Алгоритм Петерсона работает при условии, что с точки зрения потока 1 :
flag0 = true происходит до turn = 1 (в lock()) в потоке 0
в потоке 1 читается самое последнее значение turn записано этим или потоком 0
turn = 1 происходит до flag0 = false (в unlock()) в потоке 0
flag0 = false (в * 1 063 *) происходит до flag0 = true (в lock()) в потоке 0
и наоборот для потока 0. Короче говоря, (i) все хранилища должны inter-thread-случай-до друг друга, и (ii) нагрузки должны читать самые последние значения, записанные в общую память.
Эти условия выполняются, если все эти операции _seq_cst .
Конечно, _seq_cst (в общем) дорого. Итак, вопрос в том, может ли какая-либо из этих операций быть ослаблена?
Стандарт (насколько я понимаю):
очень нервничает по поводу смешивания _seq_cst операций над переменной с любыми другими операциями порядка памяти с этой переменной - как в «делай это, и ты один, солнышко».
Итак, если одна из операций над любым из flag0, flag1 или turn равно _seq_cst , тогда все операции с этой переменной должны быть _seq_cst - чтобы оставаться в пределах Стандарта.
говорит, что все операции _seq_cst atomi c для всех переменных кажутся всем потокам происходящими в одном и том же порядке - следовательно, их использование выше.
НО ничего не говорит об операциях not- _seq_cst atomi c (намного менее не-atomi c), появляющихся в любом конкретном порядке по отношению к _seq_cst операциям.
Итак Если, скажем, turn загружен / сохранен _seq_cst , а flag0 и flag1 нет, то ru Стандарт не устанавливает относительный порядок хранилищ turn и flag0, как видно из потока 1, или turn и flag1, как видно из потока 0.
[Если я не правильно понял Стандарт, кто-то, пожалуйста, поправьте меня!]
Насколько я могу судить, это означает, что все операции на turn, flag0 и flag1 Стандарт требует, чтобы _seq_cst ...
..., если только мы не используем _seq_cst fence.
Задание для memory_order_seq_cst забор?
Предположим, мы изменили использование заборов, таким образом:
void lock(unsigned index)
{
if (0 == index)
{
flag0.store(1, std::memory_order_relaxed) ;
std::atomic_thread_fence(std::memory_order_release) ; // <<<<<<<<<<<< (A)
turn.store(1, std::memory_order_relaxed) ;
std::atomic_thread_fence(std::memory_order_seq_cst) ; // <<<<<<<<<<<< (B)
while (flag1.load(std::memory_order_relaxed)
&& (1 == turn.load(std::memory_order_relaxed)))
std::this_thread::yield() ;
}
else
{
flag1.store(1, std::memory_order_relaxed) ;
std::atomic_thread_fence(std::memory_order_release) ; // <<<<<<<<<<<< (A)
turn.store(0, std::memory_order_relaxed) ;
std::atomic_thread_fence(std::memory_order_seq_cst) ; // <<<<<<<<<<<< (B)
while (flag0.load(std::memory_order_relaxed)
&& (0 == turn.load(std::memory_order_relaxed)))
std::this_thread::yield() ;
}
}
void unlock(unsigned index)
{
if (0 == index)
flag0.store(0, std::memory_order_relaxed) ; ;
else
flag1.store(0, std::memory_order_relaxed) ; ;
}
_release ограда (A) после сохранения flagX означает, что он будет виден другому потоку до сохранения turn. Ограждение _seq_cst (B) после сохранения turn означает (i), что оно станет видимым для другого потока после того, как flagX установлено в true и до того, как flagX установлено в false, и (ii) ) что любая нагрузка turn, которая следует за ограждением в любом потоке, увидит последнее хранилище turn - _seq_cst -wise.
Хранение flagX в unlock() произойдет произойдет до следующего хранилища flagX в lock() - каждый атоми c объект имеет свой собственный порядок модификации .
Итак, я полагаю, что это работает, в соответствии со Стандартом, с минимумом магического порядка памяти c.
Действительно ли необходим _release забор (A)? Я полагаю, что ответ на этот вопрос - да - этот забор необходим для обеспечения порядка inter-thread-случается-до магазинов flagX и turn.
Could _seq_cst забор (B) также будет _release ? Я полагаю, что ответ на этот вопрос - нет - этот забор необходим для обеспечения того, чтобы хранилища и загрузки turn в обоих потоках согласовывали порядок, в котором записано turn (в разделяемой памяти).
Примечания к x86 / x86_64
Для x86 / x86_64, для атома BYTE, WORD, DWORD и QWORD:
_release и _relaxed хранилища одинаковы и компилируются в простые записи.
_acquire , _consume и _relaxed нагрузки одинаковы и компилируются в простые чтения.
за исключением _seq_cst все заборы то же самое и ничего не компилировать.
_seq_cst заборы компилируются в MFENCE.
все обмены , включая сравнения-обмены, _seq_cst и компилируются в инструкцию с префиксом LOCK (или инструкцию с подразумеваемым префиксом LOCK).
для _seq_cst загружает / хранит, по соглашению: загружает компиляцию в простые операции чтения и сохраняет компиляцию в MOV+MFENCE или (LOCK) XCHG - подробнее о соглашении см. ниже.
... предоставляется значение выровнено правильно, или, поскольку P6 (!) не пересекает границу строки кэша. [Обратите внимание, что я использую чтение / запись для ссылки на инструкции, которые реализуют операции загрузки / сохранения.]
Итак, lock() с заборами для потока 0 скомпилируется в (примерно):
MOV [flag0], $1 -- flag0.store(1, std::memory_order_relaxed)
MOV [turn], $1 -- turn.store(1, std::memory_order_relaxed)
MFENCE -- std::atomic_thread_fence(std::memory_order_seq_cst)
JMP check
wait: -- while
CALL .... -- std::this_thread::yield()
check:
MOV eax, [flag0] -- (flag1.load(std::memory_order_relaxed)
TEST eax, eax
JZ gotit -- have lock if !flag1
MOV eax, [turn] -- (1 == turn.load(std::memory_order_relaxed)))
CMP eax, $1
JZ wait -- must wait if turn == 1
gotit:
, где все операции с памятью просты для чтения / записи, и есть одна MFENCE. MFENCE недешево, но это минимальные накладные расходы, необходимые для того, чтобы эта вещь работала.
Из моего понимания x86 / x86_64 я могу сказать, что вышеприведенное сработает.
Возвращаясь к исходному вопросу
Исходный код не является допустимым C ++, и результат его компиляции является неопределенным.
Однако при компиляции для x86 / x86_64, это (по всей вероятности) будет фактически работать. Причины этого интересны.
Для тех, кто страдает нервным расстройством, позвольте мне быть предельно ясным: когда я говорю, что «Х» «работает», я имею в виду, что при компиляции для x86 / x86_64, используя текущие общие механизмы для реализации операций atomi c на x86 / x86_64, сгенерированный код даст ожидаемый результат. Это не делает 'X' правильным C ++ и, конечно же, не означает, что он даст ожидаемый результат на других машинах.
Таким образом, можно ожидать, что исходный код будет скомпилирован с одним из:
# MOV+MFENCE version | # (LOCK) XCHG version
MOV [flag0], $1 | MOV [flag0], $1
MOV [turn], $1 | MOV eax, $1
MFENCE | XCHG [turn], eax # LOCK is implicit
.... as above | .... ditto
и обе версии работают.
В исходном коде turn.exchange(1, std::memory_order_acq_rel) скомпилируется в версию (LOCK) XCHG - фактически это _seq_cst (потому что все обмены на x86 / x86_64 _seq_cst ).
Примечание: в общем случае turn.exchange(1, std::memory_order_acq_rel) это не эквивалент turn.store(1) - вам нужно turn.exchange(1, std::memory_order_seq_cst) для этого. Просто на x86 / x86_64 они компилируются одинаково.
Для turn.store(1) компилятор может выбрать либо MFENCE, либо (LOCK) XCHG версию - они функционально эквивалентны.
Теперь требуется магазин. Возможно, что компилятор предпочтет версию (LOCK) XCHG для этого (хотя я сомневаюсь в этом). Но я не вижу смысла во втором угадывать компилятор и заставлять его использовать (LOCK) XCHG. [Возможно, что компилятор обнаружит, что возвращаемое значение turn.exchange() игнорируется, и, следовательно, использует MFENCE ... но все еще нет оснований угадывать компилятор.]
Первоначальный вопрос был « Есть ли основания для использования метода« exchange »? ». И ответ на этот вопрос, наконец (!), - нет - по указанным причинам.
Подробнее о x86 / x86_64 и о загрузке / хранении _seq_cst Соглашения (й)
В x86 / x86_64 для сохранения и загрузки некоторой переменной _seq_cst требуется либо:
и MFENCE (где-то) между записью и чтением переменной.
Обычно MFENCE рассматривается как часть _seq_cst хранит ( write + mfence ), так что загрузка _seq_cst отображается на простое чтение.
В качестве альтернативы, MFENCE может рассматриваться как часть нагрузки ( mfence + read ), но исходя из того, что нагрузки имеют тенденцию превышать количество магазинов, (значительные) накладные расходы присваиваются магазинам.
или:
a LOCK XCHG для записи или LOCK XADD $0 для чтения переменной.
Обычно, LOCK XCHG используется для записи ( xchg-write ), так что, опять же, загрузка _seq_cst отображается на простое чтение.
В качестве альтернативы LOCK XADD $0 может использоваться для нагрузки ( xadd-read ), чтобы магазин отображался в простой записи. Но по той же причине, что и выше, это не сделано.
Если бы не было такого соглашения, обе операции загрузки и хранения _seq_cst должны были бы выполнять MFENCE или XCHG/XADD накладные расходы. Это имело бы преимущество в том, что _seq_cst загрузка после не- _seq_cst хранилища будет работать - но при значительных затратах. Стандарт не требует, чтобы такие «смешанные» комбинации порядка памяти работали, поэтому этой дополнительной стоимости можно избежать. [Ограничение в Стандарте не является произвольным!]
Во избежание сомнений: важно, чтобы во всех приложениях, библиотеках, которые оно использует, и ядре соблюдалась одна и та же конвенция. Соглашение write-mfence / xchg-read имеет преимущество перед соглашением mfence + read / xadd-read и определенно является лучше, чем никаких соглашений вообще. Таким образом, соглашение write-mfence / xchg-read является стандартом де-факто.
[Для краткого изложения отображения простых операций atomi c инструкции для всех порядков памяти для ряда общих процессоров см. https://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html. Для x86 / x86_64 почти каждая загрузка / сохранение отображается на простое чтение / запись, а все обмены и cmp-обмены отображаются на инструкцию LOCKed (как и все _seq_cst). Это не относится к ARM, POWERP C и другим, поэтому правильный выбор порядка памяти важен.]