Будут ли две атомарные записи в разные места в разных потоках всегда рассматриваться в одном и том же порядке другими потоками?

Question

Как и в моем предыдущем вопросе, рассмотрим этот код

-- Initially --
std::atomic<int> x{0};
std::atomic<int> y{0};

-- Thread 1 --
x.store(1, std::memory_order_release);

-- Thread 2 --
y.store(2, std::memory_order_release);

-- Thread 3 --
int r1 = x.load(std::memory_order_acquire);   // x first
int r2 = y.load(std::memory_order_acquire);

-- Thread 4 --
int r3 = y.load(std::memory_order_acquire);   // y first
int r4 = x.load(std::memory_order_acquire);

Странный результат r1==1, r2==0 а также r3==2, r4==0 возможно ли в этом случае под модель памяти C++11? Что, если я должен был заменить все std::memory_order_acq_rel от std::memory_order_relaxed?

На x86 такой результат, по-видимому, запрещен, см. Этот вопрос, но я спрашиваю о модели памяти C++11 в целом.

Бонусный вопрос:

Мы все согласны с тем, что с std::memory_order_seq_cst странный результат не будет разрешен в C++11. Теперь Херб Саттер сказал в своем знаменитом atomic<> - говорят 42:30 std::memory_order_seq_cst так же, как std::memory_order_acq_rel но std::memory_order_acquire-нагрузки не могут двигаться раньше std::memory_order_release-writes. Я не вижу, как это дополнительное ограничение в приведенном выше примере предотвратит странный результат. Кто-нибудь может объяснить?

Answer 1

Обновленный¹ код в вопросе (с множеством x а также y поменялся местами в потоке 4) на самом деле проверяет, что все потоки согласились на глобальный порядок хранения

Под моделью памяти C++11, результат r1==1, r2==0, r3==2, r4==0 разрешено и фактически наблюдается на POWER.

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

---

Сноска 1: Первоначально этот вопрос читал оба читателя x затем y, Последовательное последовательное выполнение этого:

-- Initially --
std::atomic<int> x{0};
std::atomic<int> y{0};

-- Thread 4 --
int r3 = x.load(std::memory_order_acquire);

-- Thread 1 --
x.store(1, std::memory_order_release);

-- Thread 3 --
int r1 = x.load(std::memory_order_acquire);
int r2 = y.load(std::memory_order_acquire);

-- Thread 2 --
y.store(2, std::memory_order_release);

-- Thread 4 --
int r4 = y.load(std::memory_order_acquire);

Это приводит к r1==1, r2==0, r3==0, r4==2, Следовательно, это совсем не странный результат.

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

Answer 2

Как говорит ответ @ MWid, очень слабая модель памяти C++11 не требует, чтобы все потоки согласовывали глобальный порядок для магазинов.

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

См. Учебное пособие "Введение в модели расслабленной памяти ARM и POWER", где представлена ​​абстрактная модель этих ISA: ни ARM, ни POWER не гарантируют согласованного глобального порядка хранения, видимого всеми потоками. На самом деле, это возможно на практике на чипах POWER, и, возможно, теоретически на ARM, но, возможно, на реальных реализациях.

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

В компьютерных науках термин для машины, где хранилища становятся видимыми для всех других потоков одновременно (и, следовательно, существует единый глобальный порядок хранилищ), является " атомарным множественным копированием ". Модели памяти TSO в x86 и SPARC обладают этим свойством, но ARM и POWER не требуют его.

---

Современные SMP-машины используют MESI для поддержки единого когерентного домена кэша, чтобы все ядра имели одинаковое представление о памяти. Хранилища становятся глобально видимыми, когда они фиксируются из буфера хранилища в кэш L1d. В этот момент загрузка из любого другого ядра увидит это хранилище. Существует один порядок всех хранилищ, фиксирующих кеширование, потому что MESI поддерживает единый домен когерентности. При наличии достаточного количества барьеров, препятствующих локальному переупорядочению, последовательная последовательность может быть восстановлена.

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

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

Обычно мы думаем о загрузках как об их значении из L1d, но это не тот случай, когда перезагружается последнее хранилище из того же ядра, и данные перенаправляются непосредственно из буфера хранилища. (Пересылка из магазина в загрузку или SLF). Для загрузки даже возможно получить значение, которое никогда не присутствовало в L1d и никогда не будет, даже на сильно упорядоченном x86, с частичным SLF. (См. Мой ответ на инструкции по загрузке невидимого в глобальном масштабе).

Буфер хранилища отслеживает спекулятивные хранилища до того, как инструкция хранилища будет удалена, но также буферизирует не спекулятивные хранилища после того, как они удаляются из части ядра, находящейся вне порядка исполнения (буфер ROB / ReOrder).

Логические ядра на одном физическом ядре совместно используют буфер хранилища. Спекулятивные (еще не выбывшие) хранилища должны оставаться закрытыми для каждого логического ядра. (В противном случае это спровоцировало бы их спекуляцию и потребовало бы отката обоих при обнаружении неправильной спекуляции. Это могло бы нанести ущерб части цели SMT, состоящей в том, чтобы поддерживать ядро ​​занятым, пока один поток остановлен, или восстанавливаться из-за неправильного предсказания ветви),

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

(Я не уверен, что это именно тот механизм HW, который допускает эту странность в POWER, но это правдоподобно).

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

(Абстрактная модель памяти, предложенная в документе ARM/POWER, моделирует это как каждое ядро, имеющее свое собственное кэшированное представление памяти, со связями между кешами, которые позволяют им синхронизироваться. Но в типичном физическом современном оборудовании, я думаю, единственный механизм - между братьями и сестрами SMT, а не между отдельными ядрами.)

---

Обратите внимание, что x86 не может позволить другим логическим ядрам вообще отслеживать буфер хранилища, потому что это нарушит модель памяти TSO в x86 (допустив это странное переупорядочение). В качестве моего ответа на то, что будет использоваться для обмена данными между потоками, выполняющимися на одном ядре с HT? объясняет, что процессоры Intel с SMT (который Intel называет Hyperthreading) статически разделяют буфер хранилища между логическими ядрами.

---

Сноска 1: Абстрактная модель для C++ или asm для конкретного ISA - это все, что вам действительно нужно знать, чтобы рассуждать об упорядочении памяти.

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

Answer 3

Краткий ответ: нет. Стандарт не говорит, что они должны быть, и поэтому они не должны быть. Неважно, можете ли вы или не можете представить конкретный способ, чтобы это произошло.

Answer 4

Странный результат r1==1, r2==0 а также r3==0, r4==2 возможно ли в этом случае под модель памяти C++11?

Да. Модель памяти C++ допускает такой странный результат.

Что, если я должен был заменить все std::memory_order_acq_rel от std::memory_order_relaxed?

Если заменить все memory_order_acquire а также memory_order_release от memory_order_relaxedничего не изменилось для вашего кода.

std::memory_order_seq_cst так же, как std::memory_order_acq_rel но std::memory_order_acquire-нагрузки не могут двигаться раньше std::memory_order_release-writes. Я не вижу, как это дополнительное ограничение в приведенном выше примере предотвратит странный результат.

"acquire-нагрузки не могут двигаться раньше release-writes."показывает один аспект ограничений последовательной согласованности (memory_order_seq_cst).

В модели памяти C++ это только гарантирует, что seq_cst имеет acq_rel семантика и все seq_cst атомарный доступ имеет некоторый "общий порядок" не больше и не меньше. Когда такой "общий порядок" существует, мы не можем получить странный результат, потому что все seq_cst атомарный доступ выполняется как бы в любом чередующемся порядке в одном потоке.

Ваш предыдущий вопрос рассматривает "когерентность" одной атомарной переменной, и этот вопрос требует "согласованности" всех атомных переменных. Модель памяти C++ гарантирует интуитивную когерентность для единственной атомарной переменной даже в самом слабом порядке (relaxed) и "последовательная согласованность" для различных атомарных переменных, если порядок по умолчанию (seq_cst). Когда вы используете явно неseq_cst заказывая атомарный доступ, это может быть странным результатом, как вы указали.