Атомарность записи (multi-copy atomicity)

Атомарность записи (write atomicity) - это свойство протокола когерентности кэшей: запись становится наблюдаемой только после того, как каждая кэшированная копия соответствующей кэш-линии подтвердила её получение, и после этой точки старое значение уже нигде нельзя прочитать. В литературе это также называют store atomicity или multi-copy atomicity (MCA). Определение Адве и Гарачорлу (Adve, Gharachorloo) запрещает операции чтения возвращать только что записанное значение до тех пор, пока все кэшированные копии не подтвердят инвалидацию или обновление, вызванное этой записью.

Протоколы когерентности работают на уровне кэш-линий (обычно по 64 байта), а не отдельных адресов, из-за чего две независимые атомарные операции на одной линии и вызывают конкуренцию в false-sharing-alignment-128.

Три варианта

MCA - строгая форма: ни один процессор не видит запись раньше времени, включая тот, который её выполнил.

Other-multi-copy atomicity (oMCA), в научных статьях также называемая read-own-write-early MCA (rMCA), позволяет пишущему процессору прочитать собственную запись раньше других (обычно через пересылку из своего store buffer), при этом скрывая её от всех остальных ядер до тех пор, пока она не станет глобально видимой. Термин oMCA популяризировали руководства ARM.

Non-multi-copy atomicity (nMCA) позволяет другим процессорам наблюдать запись до того, как будут инвалидированы все копии.

Согласно обзору в shared-memory-consistency-causality, x86 и x86-64, ARMv8-A (ревизия 2017 года), RISC-V, SPARC v9 и IBM z/Architecture относятся к MCA или oMCA; IBM Power, ARMv7, Itanium и GPU NVIDIA на базе PTX - к nMCA. GPU Intel Iris Pro 650 также показал поведение nMCA в тестах моделей памяти. Документация производителей редко говорит об этом прямо, поэтому исследователи создали систематические litmus-тесты (пакет herdtools), чтобы наблюдать за реальным поведением оборудования.

Почему это важно

При наличии атомарности записи любое внешне наблюдаемое переупорядочивание операций с памятью сводится к сугубо локальным эффектам процессора: внеочередному исполнению (out-of-order execution) и буферизации записи (store buffering) внутри одного процессора, а не ситуации, когда записи доходят до разных процессоров в разном порядке. Это исключает целый класс проблем синхронизации. Без атомарности записи восстановление атомарности там, где она требуется алгоритму, ложится на плечи читателя, а способы сделать это либо медленные, либо нетривиальные.

MCA не означает, что само железо внутри устроено консервативно. Архитектуры с этой гарантией могут быть столь же мягкими внутри и использовать спекулятивные вычисления, отменяя работу всякий раз, когда нарушение порядка рискует стать видимым, - ценой сброса конвейера при ошибке спекуляции и роста задержек в хвосте распределения (tail latency). ARM исследовала модель nMCA для ARMv8 (Flowing Model), прежде чем потребовать MCA на уровне архитектуры. Itanium пошёл другим путём: обычные инструкции записи не были атомарными, но специализированные инструкции вроде st.rel были, так что накладные расходы несли только переменные синхронизации.

В моделях памяти языков программирования

Модель памяти C++11, которую в том или ином виде переняли C, Rust, Odin и языки на базе LLVM, намеренно не требует атомарности записи, чтобы её можно было эффективно реализовать на оборудовании с nMCA. Платой за это стал ряд проблем в спецификации: в 2016 и 2017 годах выяснилось, что схемы трансляции компиляторов для Power и ARMv7 нарушают модель, а исправление в C++20 сделало часть трансляций неэффективными на x86. Java с модификатором volatile и Golang с пакетом sync/atomic предоставляют только операции, неявно требующие атомарности записи, благодаря чему их модели устроены проще. Состояние гонки данных (data-race) - это обычный путь, которым программа открывает побочный канал к отсутствующей гарантии, и именно поэтому языки относят гонки данных к неопределённому поведению.

Связанные страницы

• shared-memory-consistency-causality - виртуальная nMCA-машина, выстроенная до каждой гарантии упорядочения
• false-sharing-alignment-128 - трафик когерентности на уровне кэш-линий, измеренный со стороны программного обеспечения
• data-race - условие на уровне программы, при котором более слабый аппаратный порядок операций остаётся скрытым
• art-of-multiprocessor-programming - алгоритмы, корректность которых опирается на эти гарантии