Почему приобретает семантику только для чтения, а не для записи? Как LL / SC может приобрести CAS, чтобы захватить блокировку без переупорядочения магазина с критической секцией?

Question

Для начала рассмотрим семантику релиза. Если набор данных защищен спин-блокировкой (мьютекс и т. Д.), Не имеет значения, какая именно реализация используется; пока предположим, что 0 означает, что он свободен, а 1 - занят). После изменения набора данных поток сохраняет 0 для адреса спин-блокировки. Чтобы обеспечить видимость всех предыдущих действий перед сохранением 0 для адреса спин-блокировки, сохранение выполняется с семантикой освобождения, что означает, что все предыдущие чтения и записи должны быть видны другим потокам перед этим сохранением. Это детали реализации, независимо от того, делается ли это с полным барьером или с отметкой об освобождении от одной операции хранения. Это (я надеюсь) понятно без всяких сомнений.

Затем рассмотрим их момент, когда захватывается владение спин-блокировкой. Для защиты от гонки это любая операция сравнения и настройки. При реализации CAS с одной инструкцией (X86, Sparc ...) это объединяет чтение и запись. То же самое для X86 Atomic XCHG. С LL / SC (большинство RISC) это падает до:

1. Считывание (LL) местоположения спин-блокировки, пока оно не покажет свободное состояние. (Может быть оптимизировано с некоторой задержкой процессора.)
2. Запись (SC) значения «занято» (в нашем случае 1). CPU показывает, была ли операция успешной (флаг условия, регистр вывода и т. Д.)
3. Проверьте результат записи (SC) и, если не удалось, перейдите к шагу 1.

Inво всех случаях операция, которая должна быть видимой другим потокам, чтобы показать, что спин-блокировка занята, записывает 1 в ее местоположение, и между этой записью и последующими манипуляциями с набором данных, защищенных спин-блокировкой, должен быть установлен барьер. Чтение этого спин-блокировки ничего не дает схеме защиты, кроме разрешения работы CAS или LL / SC.

Но все реально реализованные схемы позволяют получить модификацию семантики для операций чтения (или CAS), а не записи. В результате для схемы LL / SC потребуется дополнительная заключительная операция чтения с получением на спин-блокировке для фиксации необходимого барьера. Но в типичном выводе такой инструкции нет. Например, если скомпилировать на ARM:

  for(;;) {
    int e{0};
    int d{1};
    if (std::atomic_compare_exchange_weak_explicit(p, &e, d,
          std::memory_order_acquire,
          std::memory_order_relaxed)) {
      return;
    }
  }

, его выходные данные сначала содержат LDAXR == LL +, а затем STXR == SC (без барьера, поэтому нет гарантии, что другие потоки увидят его?) Вероятно, это не мой артефакт, но он генерируется, например, в glibc: pthread_spin_trylock вызывает __atomic_compare_exchange_weak_acquire (и не более барьеров), который попадает во встроенную GCC __atomic_compare_exchange_n с захватом при чтении мьютекса и без освобождения при записи мьютекса.

Кажется, я упустил некоторые основные детали в этом рассмотрении. Кто-нибудь исправит это?

Это также может попасть в 2 подвопроса:

SQ1: В последовательности инструкций, например:

(1) load_linked+acquire mutex_address     ; found it is free
(2) store_conditional mutex_address       ; succeeded
(3) read or write of mutex-protected area

, что предотвращает переупорядочение ЦП (2) и (3), в результате чего другие потоки не увидят, что мьютекс заблокирован?

SQ2: существует ли фактор проектирования, который предполагает использование семантики только для нагрузок?

Видно, что некоторые примеры кода без блокировки, такие как:

поток 1:

var = value;
flag.store(true, std::memory_order_release);

поток 2:

if (flag.load(std::memory_order_acquire)) {
   // We already can access it!!!
   value = var;
   ... do something with value ...
}

, но это должно было быть сделано работать после стиль, защищенный мьютексом, работает стабильно.

Answer 1

Его вывод содержит сначала LDAXR == LL + acquine, затем STXR == SC
(без барьера, поэтому нет гарантии, что другие потоки его увидят?)

А? Магазины всегда становятся видимыми для других потоков;буфер хранилища всегда истощается как можно быстрее. Вопрос только в том, блокировать ли последующие загрузки / сохранения в этом потоке до тех пор, пока буфер хранилища не станет пустым. (Это требуется, например, для магазинов seq-cst pure).

STXR является эксклюзивным и привязанным к LL. Таким образом, он и нагрузка неделимы в глобальном порядке операций, как сторона загрузки и сохранения атомарной операции RMW, точно так же, как x86 делает в одной инструкции с lock cmpxchg.

Атомный RMW может двигаться раньше (потому что накапливающиеся нагрузки могут сделать это, и поэтому могут расслабиться магазины). Но он не может двигаться позже (потому что приобретающие нагрузки не могут сделать это). Следовательно, атомарный RMW появляется в глобальном порядке перед любыми операциями в критической секции и достаточен для снятия блокировки. Ему не нужно ждать более ранних операций, таких как хранилища с отсутствием кэша;это может позволить им перейти в критическую секцию. Но это не проблема.

Однако, если вы использовали , использовали acq_rel CAS, он не сможет взять блокировку до завершения всех предыдущих загрузок / хранилищ (из-за семантики выпускасторона магазина).

Я не уверен, есть ли какая-либо разница в asm между acq_rel и seq_cst для атомарного RMW. Возможно на PowerPC? Не на x86, все RMW являются seq_cst. Не для AArch64: он имеет только расслабленный и последовательный выпуск.

---

LDAR + STR будет выглядеть как x86 cmpxchg без префикс блокировки: получение нагрузки и отдельное хранилище. (За исключением того, что сторона хранилища x86 cmpxchg по-прежнему является хранилищем выпуска (но не последовательным выпуском) из-за модели памяти x86.

---

Другое подтверждение моих рассуждений о том, что mo_acquire для "Успешная сторона CAS достаточна для взятия блокировки:

• https://en.cppreference.com/w/cpp/atomic/memory_order говорит: «Операция lock () на Mutex также является операцией получения»
• pthread_spin_trylock Glibc использует встроенную GCC __atomic_compare_exchange_n в мьютексе только с acqu, а не acq_rel или seq_cst. Мы знаем, что многие умные люди смотрели на glibc. А на платформах, где он не был эффективно усилен до seq-cst asm, возможно, есть ошибкибыло бы замечено, если бы были какие-либо.

---

, что препятствует ЦП против переупорядочения (2) и (3), в результате чего другие потоки не увидят, что мьютекс заблокирован?

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

SQ2: Есть ли фактор проектирования, который предполагает использование семантики только для нагрузок?

Да, учитывайте чистые нагрузки и чистые запасы, а неМРП. Jeff Preshing по семантике acq и rel .

Односторонний барьер релиз-хранилища, естественно, хорошо работает с буфером хранилища на реальных процессорах. Процессоры «хотят» загружаться раньше и запаздывать. Возможно, статья Джеффа Прешинга Барьеры памяти похожи на операции управления исходным кодом - полезная аналогия взаимодействия процессоров с когерентным кешем.

Магазин, который может появиться только раньше, а не позже, в основном потребует очистки буфера хранилища. то есть расслабленное хранилище, за которым следует полный барьер (например, atomic_thread_fence(seq_cst), например, ARM dsb ish или x86 mfence или заблокированная операция). Это то, что вы получаете в магазине seq-cst. Так что у нас более или менее уже есть название для него, и это очень дорого.