Какие точные правила в модели памяти C++ предотвращают переупорядочение до операций по приобретению?

Ответ 1

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

N4762, §29.4.2 - [atomics.order]

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

В §6.8.2.1-9 в стандарте также указано, что если хранилище A синхронизируется с нагрузкой B, что-либо упорядочивается до того, как межпоточный "происходит раньше", после того, как последовательность после B.

В вашем втором примере нет связи "synchronizes-with" (и, следовательно, inter-thread бывает раньше), потому что отношения времени выполнения (которые проверяют возвращаемые значения из нагрузок) отсутствуют.
Но даже если вы проверили возвращаемое значение, это не помогло бы, поскольку операции exchange фактически не "выпускают" что-либо (т.е. Операции с памятью не секвенируются до этих операций). Нейтер выполняет операции атомной нагрузки "приобретать" что-либо, так как после нагрузок операции не секвенируются.

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

Если вы хотите исключить результат 0 0 в свой код, все 4 операции должны использовать std::memory_order_seq_cst. Это гарантирует единый общий порядок задействованных операций.

Ответ 2

В исходной версии можно увидеть r1 == 0 && r2 == 0 потому что нет требования, чтобы хранилища распространялись на другой поток до того, как он его прочитал. Это не переупорядочение ни потоков, но, например, чтение устаревших кешей.

Thread 1 cache   |   Thread 2 cache
  x == 0;          |     x == 0;
  y == 0;          |     y == 0;

y.exchange(1, std::memory_order_acq_rel); // Thread 1
x.exchange(1, std::memory_order_acq_rel); // Thread 2

Выпуск по Thread 1 игнорируется Thread 2 и наоборот. В абстрактной машине нет согласованности со значениями x и y на потоках

Thread 1 cache   |   Thread 2 cache
  x == 0; // stale |     x == 1;
  y == 1;          |     y == 0; // stale

r1 = x.load(std::memory_order_relaxed); // Thread 1
r2 = y.load(std::memory_order_relaxed); // Thread 2

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

Без ограничения общности предположим, что Thread 1 выполняется первым.

Thread 1 cache   |   Thread 2 cache
  x == 0;          |     x == 0;
  y == 0;          |     y == 0;

y.exchange(1, std::memory_order_acq_rel); // Thread 1

Thread 1 cache   |   Thread 2 cache
  x == 0;          |     x == 0;
  y == 1;          |     y == 1; // sync 

Выпуск по Thread 1 образует пару с приобретением на Thread 2, а абстрактная машина описывает согласованный y на обоих потоках

r1 = x.load(std::memory_order_relaxed); // Thread 1
x.exchange(1, std::memory_order_acq_rel); // Thread 2
r2 = y.load(std::memory_order_relaxed); // Thread 2

Ответ 3

в выпуске Release-Acquire для создания точки синхронизации между двумя потоками нам нужен некоторый атомный объект M который будет таким же в обеих операциях

Атомная операция A которая выполняет операцию освобождения на атомарном объекте M синхронизируется с атомной операцией B которая выполняет операцию получения на M и принимает свое значение от любого побочного эффекта в последовательности выпуска, возглавляемой A

или более подробно:

Если атомный магазин в потоке A отмечен memory_order_release а атомная нагрузка в потоке B из той же переменной помечена memory_order_acquire, вся память записывается (memory_order_acquire и расслабленная атома), которая произошла - до атомного хранилища с точки зрения потока A, становятся видимыми побочными эффектами в потоке B То есть, как только атомная нагрузка будет завершена, поток B гарантированно увидит, что все потоки A записаны в память.

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

     N = u                |  if (M.load(acquire) == v)    :[B]
[A]: M.store(v, release)  |  assert(N == u)

здесь точка синхронизации на M store-release и load-приобретать (которые принимают значение из store-release!). как результат хранит N = u в потоке A (до хранения-выпуска на M), видимый в B (N == u) после загрузки-получения на том же M

если взять пример:

atomic<int> x, y;
int r1, r2;

void thread_A() {
  y.exchange(1, memory_order_acq_rel);
  r1 = x.load(memory_order_acquire);
}
void thread_B() {
  x.exchange(1, memory_order_acq_rel);
  r2 = y.load(memory_order_acquire);
}

что мы можем выбрать для общего атомного объекта M? скажем, x? x.load(memory_order_acquire); будет содержать точку синхронизации с x.exchange(1, memory_order_acq_rel) (memory_order_acq_rel включает memory_order_release (более сильный) и exchange include store), если x.load нагрузки x.exchange из x.exchange и main будут синхронизированы нагрузками после получения (быть в коде после приобретения ничего не существует) с магазинами до выпуска (но опять же, прежде чем ничего не менять в коде).

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

atomic<int> x, y;
int r1, r2;

void thread_A()
{
    x.exchange(1, memory_order_acq_rel); // [Ax]
    r1 = y.exchange(1, memory_order_acq_rel); // [Ay]
}

void thread_B()
{
    y.exchange(1, memory_order_acq_rel); // [By]
    r2 = x.exchange(1, memory_order_acq_rel); // [Bx]
}

предположим, что r1 == 0.

Все модификации любой конкретной атомной переменной происходят в полном порядке, который является специфическим для этой атомной переменной.

мы имеем 2 модификации y: [Ay] и [By]. потому что r1 == 0 это означает, что [Ay] происходит до [By] в полном порядке модификации y. из этого - [By] прочитанное значение, сохраненное в [Ay]. поэтому у нас есть следующее:

• A записывается в x - [Ax]
• A сделать хранилище-хранилище [Ay] до y после этого (acq_rel include release, exchange include store)
• B загружается из y ([By] значение, сохраненное в [Ay]
• после завершения получения атомной нагрузки (по y) поток B гарантированно увидит, что все нитки A записаны в память до сохранения хранилища (по y). поэтому он рассматривает побочный эффект [Ax] - и r2 == 1

другое возможное решение использует atomic_thread_fence

atomic<int> x, y;
int r1, r2;

void thread_A()
{
    x.store(1, memory_order_relaxed); // [A1]
    atomic_thread_fence(memory_order_acq_rel); // [A2]
    r1 = y.exchange(1, memory_order_relaxed); // [A3]
}

void thread_B()
{
    y.store(1, memory_order_relaxed); // [B1]
    atomic_thread_fence(memory_order_acq_rel); // [B2]
    r2 = x.exchange(1, memory_order_relaxed); // [B3]
}

опять же потому, что все модификации атомной переменной y встречаются в полном порядке. [A3] будет до [B1] или наоборот.

1. если [B1] перед [A3] - [A3] считывает значение, сохраненное в [B1] => r1 == 1.

2. если [A3] до [B1] - [B1] - значение чтения, сохраненное в [A3] и из синхронизации забора ограждения:

Разделительный забор [A2] в потоке A синхронизируется с приобретающим ограждением [B2] в потоке B, если:

• Существует атомный объект y,
• Существует атомная запись [A3] (с любым порядком памяти), которая изменяет y в потоке A
• [A2] секвенирован - до [A3] в потоке A

• Существует атомарное чтение [B1] (с любым порядком памяти) в потоке B

• [B1] считывает значение, записанное в [A3]

• [B1] секвенирован - до [B2] в потоке B

В этом случае все хранилища ([A1]), которые секвенированы, - до [A2] в потоке A, - до всех нагрузок ([B3]) из тех же мест (x), сделанных в потоке B после [B2]

поэтому [A1] (сохранение от 1 до x) будет раньше и будет иметь видимый эффект для [B3] (загрузить форму x и сохранить результат до r2). поэтому будет загружен 1 из x и r2==1

[A1]: x = 1               |  if (y.load(relaxed) == 1) :[B1]
[A2]: ### release ###     |  ### acquire ###           :[B2]
[A3]: y.store(1, relaxed) |  assert(x == 1)            :[B3]

Ответ 4

У вас уже есть ответ на эту проблему. Но я хочу ответить на вопрос о том, как понять, почему это возможно в asm для возможной архитектуры процессора, которая использует LL/SC для атомизации RMW.

Для C++ 11 не имеет смысла запрещать это переупорядочение: для этого потребуется барьер для хранения в этом случае, когда некоторые архитектуры ЦП могут избежать этого.

Это может быть реально с реальными компиляторами на PowerPC, учитывая то, как они отображают C++ 11 заказов памяти на команды asm.

В PowerPC64 функция с обменом acq_rel и загрузкой (используя указатели args вместо статических переменных) компилируется следующим образом с gcc6.3 -O3 -mregnames. Это из версии C11, потому что я хотел посмотреть выход clang для MIPS и SPARC, а настройка clang Godbolt работает для C11 <atomic.h> но не работает для C++ 11 <atomic> когда вы используете -target sparc64.

(источник + asm на Godbolt для MIPS32R6, SPARC64, ARM 32 и PowerPC64.)

foo:
    lwsync            # with seq_cst exchange this is full sync, not just lwsync
                      # gone if we use exchage with mo_acquire or relaxed
                      # so this barrier is providing release-store ordering
    li %r9,1
.L2:
    lwarx %r10,0,%r4    # load-linked from 0(%r4)
    stwcx. %r9,0,%r4    # store-conditional 0(%r4)
    bne %cr0,.L2        # retry if SC failed
    isync             # missing if we use exchange(1, mo_release) or relaxed

    ld %r3,0(%r3)       # 64-bit load double-word of *a
    cmpw %cr7,%r3,%r3
    bne- %cr7,$+4       # skip over the isync if something about the load? PowerPC is weird
    isync             # make the *a load a load-acquire
    blr

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

Таким образом, SC (stwcx.) stwcx. что часть обмена может находиться в буфере хранения и стать глобально видимой после чистой загрузки, которая следует за ней. На самом деле, другое Q & A уже спрашивало об этом, и ответ заключается в том, что мы считаем, что это переупорядочение возможно. "Isync" предотвращает переупорядочение Store-Load на CPU PowerPC?

Если чистая нагрузка - seq_cst, PowerPC64 gcc устанавливает sync перед ld. Создание exchange seq_cst не препятствует переупорядочению. Помните, что C++ 11 гарантирует только единый общий порядок для операций SC, поэтому для гарантии обмена и нагрузки оба должны быть SC для C++ 11.

Таким образом, PowerPC имеет необычное отображение из C++ 11 в asm для атомистики. Большинство систем помещают более тяжелые барьеры в магазины, позволяя seq-cst нагрузкам быть дешевле или только имеют барьер с одной стороны. Я не уверен, что это было необходимо для лидирующей слабой памяти PowerPC, или если был возможен другой выбор.

https://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html показывает некоторые возможные реализации на разных архитектурах. В нем упоминаются несколько альтернатив для ARM.

На AArch64 мы получаем это для исходной версии C++ thread1:

thread1():
    adrp    x0, .LANCHOR0
    mov     w1, 1
    add     x0, x0, :lo12:.LANCHOR0
.L2:
    ldaxr   w2, [x0]            @ load-linked with acquire semantics
    stlxr   w3, w1, [x0]        @ store-conditional with sc-release semantics
    cbnz    w3, .L2             @ retry until exchange succeeds

    add     x1, x0, 8           @ the compiler noticed the variables were next to each other
    ldar    w1, [x1]            @ load-acquire

    str     w1, [x0, 12]        @ r1 = load result
    ret

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

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

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

Но LL/SC не обязательно должна быть настоящей атомной транзакцией, чтобы дать атомарность RMW для этого местоположения.

На самом деле, один ASM swap инструкция может иметь расслабленные или acq_rel семантику. SPARC64 нуждается в инструкциях membar инструкции swap, поэтому в отличие от x86 xchg это не seq-cst самостоятельно. (SPARC имеет действительно хорошую/удобочитаемую мнемонику команд, особенно по сравнению с PowerPC. В общем, что-то более читаемо, чем PowerPC.)

Таким образом, для C++ 11 не имеет смысла требовать, чтобы он это сделал: это повредило бы реализацию на процессоре, который в противном случае не требовал бы барьера для хранения.

Ответ 5

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

Поскольку это симметричный код, достаточно взглянуть только на одну сторону. Поскольку вопрос касается значения r1 (r2), мы начнем с рассмотрения

r1 = x.load(std::memory_order_acquire);

В зависимости от значения r1 мы можем что-то сказать о видимости других значений. Однако, так как значение r1 не проверено - приобретение не имеет значения. В любом случае значение r1 может быть любым значением, которое было когда-либо записано в него (в прошлом или будущем *)). Поэтому это может быть ноль. Тем не менее, мы можем предположить, что он будет равен нулю, потому что нас интересует, может ли результат всей программы быть 0 0, что является своего рода проверкой значения r1.

Следовательно, предполагая, что мы читаем ноль, ТОГДА мы можем сказать, что если этот ноль был записан другим потоком с memory_order_release, то любая другая запись в память, выполненная этим потоком до выпуска хранилища, также будет видна этому потоку. Однако значение нуля, которое мы читаем, является значением инициализации x, а значения инициализации не атомарны - не говоря уже о "выпуске" - и, конечно, не было ничего "упорядоченного" перед ними с точки зрения записи этого значения в память; поэтому мы ничего не можем сказать о видимости других областей памяти. Другими словами, снова "приобретать" не имеет значения.

Таким образом, мы можем получить r1 = 0, и тот факт, что мы использовали функцию приобрести, не имеет значения. То же самое относится и к r2. Таким образом, результат может быть r1 = r2 = 0.

Фактически, если вы предполагаете, что значение r1 равно 1 после получения загрузки, и что это 1 было записано потоком 2 с освобождением порядка памяти (что ДОЛЖНО иметь место, так как это единственное место, где значение 1 когда-либо записывается в x) тогда все, что мы знаем, это то, что все, что записано в память потоком 2 до этого выпуска хранилища, также будет видно для потока 1 (если поток1 прочитал x == 1, таким образом!). Но thread2 НИЧЕГО не записывает перед записью в x, поэтому снова все отношение релиз-получение не имеет значения, даже в случае загрузки значения 1.

*) Тем не менее, при дальнейших рассуждениях можно показать, что определенное значение никогда не может возникать из-за несоответствия модели памяти - но здесь этого не происходит.