CS Notes

memory-ordering

14 min read

Модель памяти

← Синхронизация | Lock-free структуры →

Мьютекс и CAS (Compare-And-Swap) дают корректный параллельный доступ к данным. Но каждый мьютекс стоит 10-20 нс: захват, запись, освобождение. На горячем пути с миллионами операций в секунду эта цена заметна. Иногда задача проще: один поток записывает данные и выставляет флаг, второй поток крутится в цикле на флаге и читает данные. Две обычных записи, две обычных чтения — казалось бы, мьютекс здесь избыточен.

// Поток A                              // Поток B
atomic_store_explicit(&data, 42, memory_order_relaxed);
atomic_store_explicit(&ready, true, memory_order_relaxed);
                                        while (!atomic_load_explicit(&ready, memory_order_relaxed)) { /* spin */ }
                                        printf("%d\n", atomic_load_explicit(&data, memory_order_relaxed));

Допустим, все операции атомарные (нет torn read/write, нет UB), но используют самый слабый ordering — Relaxed. На x86 программа обычно выведет 42. На ARM — может вывести 0. Оба потока работают с разными адресами, каждая операция атомарна — но система не гарантирует, что два потока видят записи в том же порядке, в каком их выполнил автор. Без указания правильного ordering (Acquire/Release) атомарность каждой операции не означает упорядоченности между ними.

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

Две проблемы, не одна

Первая проблема — разорванное чтение/запись (torn read/write). 64-битное значение на 32-битном процессоре записывается двумя инструкциями: сначала младшие 4 байта, потом старшие. Между ними другой поток может прочитать половину старого значения и половину нового. Результат — число, которого никогда не существовало.

Вторая проблема — порядок видимости (visibility ordering). Даже если каждая отдельная запись атомарна (не разорвана), нет гарантии, что другой поток увидит две записи в том же порядке. Поток A выполнил data = 42; ready = true;, но поток B может увидеть ready == true и data == 0.

Это разные проблемы с разными решениями. Relaxed атомарность решает первую. Acquire/Release решает вторую. Модель памяти (memory model) — контракт между программистом и системой: если программист явно попросит гарантии, система их обеспечит. Если не попросит — система вольна переставлять операции как угодно ради производительности.

Проблема 1: разорванное чтение

На 64-битном процессоре обычная запись uint64_t выполняется одной инструкцией mov и аппаратно атомарна для выровненных адресов. Но на 32-битной платформе (ARMv7, старые x86) 64-битное значение записывается двумя 32-битными инструкциями:

// ARMv7: запись uint64_t по адресу [r0]
str r2, [r0]        // младшие 32 бита
str r3, [r0, #4]    // старшие 32 бита

Между двумя str может произойти прерывание, и другой поток, запущенный на том же ядре, прочитает адрес [r0] в промежуточном состоянии: младшая половина новая, старшая — старая.

Пример: поток A записывает 0x0000_0001_0000_0000 поверх 0x0000_0000_FFFF_FFFF. Поток B читает между двумя str и видит 0x0000_0000_0000_0000 — число, которое A никогда не записывал.

Поток A                      Поток B
-------                      -------
str r2, [r0]                 (младшие: 0x00000000)
                             load [r0]  -->  0x0000_0000_0000_0000
str r3, [r0, #4]             (старшие: 0x00000001)

Решение — Relaxed атомарность. AtomicU64 с Ordering::Relaxed (в Rust) или atomic_load_explicit(..., memory_order_relaxed) (в C) гарантирует ровно одно: операция не будет разорвана. На 64-битном процессоре компилятор выберет одну инструкцию mov. На 32-битном — пару ldrexd/strexd (ARM) или lock cmpxchg8b (x86-32), которые аппаратно атомарны.

Relaxed не даёт ничего сверх этого. Никаких гарантий о порядке видимости. Никаких барьеров. Это минимальный контракт: «операция целостна, но когда и в каком порядке её увидят другие потоки — не определено».

Проблема 2: порядок видимости

Теперь каждая запись атомарна — torn read исключён. Вернёмся к исходному сценарию, но с атомарными типами и Relaxed:

use std::sync::atomic::{AtomicBool, AtomicI32, Ordering::Relaxed};
 
static DATA: AtomicI32 = AtomicI32::new(0);
static READY: AtomicBool = AtomicBool::new(false);
 
// Поток A
DATA.store(42, Relaxed);
READY.store(true, Relaxed);
 
// Поток B
while !READY.load(Relaxed) {}
let value = DATA.load(Relaxed);
// value может быть 0!

Оба store атомарны, оба load атомарны. Разорванных чтений нет. Но поток B может увидеть READY == true и DATA == 0. Почему?

Две причины, каждая из которых достаточна по отдельности.

Переупорядочивание компилятором

Компилятор видит два store в разные адреса: DATA и READY. Между ними нет зависимости по данным — значение READY не зависит от значения DATA. Компилятор вправе переставить их местами, если сочтёт это более эффективным (например, ради лучшей конвейеризации). В результате в машинном коде READY.store(true) может оказаться перед DATA.store(42).

Переупорядочивание процессором (store buffer)

Даже если компилятор сохранил порядок, процессор может нарушить его. Обе записи попадают в store buffer (буфер записи) — очередь, в которой ядро процессора «паркует» store, не дожидаясь завершения когерентного протокола. Размер буфера зависит от микроархитектуры: 56 записей в Intel Skylake, 72 в Alder Lake P-core; на ARM и RISC-V размеры другие. Запись DATA = 42 и запись READY = true попадают в разные кеш-линии. Каждая запись ждёт своего RFO (Request For Ownership) — запроса на получение кеш-линии в состоянии Modified. RFO для READY может завершиться раньше, чем RFO для DATA, если линия с READY уже ближе к нужному состоянию. Тогда READY = true выйдет из store buffer в кеш раньше, чем DATA = 42.

Ядро 0 (поток A)
┌──────────────────────────────────┐
│  store DATA=42    --\            │
│  store READY=true --+--> store   │ --> кеш L1
│                      |   buffer  │
│                      |   [READY] │ --> RFO завершён, READY=true в кеше
│                      |   [DATA]  │ --> RFO ещё в пути...
└──────────────────────────────────┘
 
Ядро 1 (поток B)
  load READY --> true  (из кеша, уже видно)
  load DATA  --> 0     (запись 42 ещё в store buffer ядра 0)

Поток B видит READY == true, читает DATA — и получает устаревшее значение 0. Данные ещё не покинули store buffer ядра 0.

На x86 store-store переупорядочивание не происходит: записи выходят из store buffer строго в порядке программы. Эту модель часто называют TSO (Total Store Order), хотя формально x86 не специфицирован как TSO — детали в dropdown ниже. Поэтому сценарий с data/ready работает на x86 даже с Relaxed. Но на ARM, RISC-V и Power — не работает: эти архитектуры разрешают store-store reordering.

Модель памяти: контракт, а не описание железа

Код должен работать на любой платформе. Рассчитывать на TSO-гарантии x86 — значит получить баг при портировании на ARM (серверы Graviton на AWS, Apple Silicon, Android). Модель памяти — это контракт между программистом и системой (компилятор + процессор): «по умолчанию система переставляет всё, что может. Если нужны гарантии — запроси их явно. Система обеспечит минимальный набор барьеров для текущей платформы.»

Язык запросов — Ordering в Rust, memory_order в C/C++. Три уровня: Relaxed, Acquire/Release, SeqCst.

Release: гарантия для записи

Release (освобождение) привязывается к store — записи, которая служит сигналом. Контракт: всё, что поток записал до Release-store, гарантированно станет видимым до того, как другой поток увидит сам Release-store.

В терминах store buffer: Release запрещает записям, сделанным до него, «перепрыгивать» через него в store buffer. На ARM это реализуется инструкцией stlr (store-release): она не выходит из store buffer, пока все предыдущие записи не завершены. Фактически stlr работает как односторонний забор: предыдущие записи не могут переместиться за неё, но последующие могут переместиться перед ней.

На x86 TSO store-store порядок и так гарантирован аппаратно. Release-store компилируется в обычный mov — барьер нужен только на уровне компилятора (запрет на переупорядочивание инструкций при оптимизации). Стоимость: 0 нс дополнительных затрат на x86.

Acquire: гарантия для чтения

Acquire (захват) привязывается к load — чтению сигнала. Контракт: всё, что поток прочитает после Acquire-load, гарантированно увидит данные, записанные отправителем до парного Release-store.

На ARM это инструкция ldar (load-acquire): чтения, которые идут после ldar в программе, не могут быть выполнены процессором раньше ldar. На x86 load-load порядок гарантирован TSO, поэтому Acquire — снова только компиляторный барьер.

Acquire + Release = happens-before

Release и Acquire работают в паре. Когда поток B выполняет Acquire-load и видит значение, записанное потоком A через Release-store, возникает отношение happens-before («выполняется-до»): всё, что A сделал до Release, гарантированно видно B после Acquire.

use std::sync::atomic::{AtomicBool, AtomicI32, Ordering};
 
static DATA: AtomicI32 = AtomicI32::new(0);
static READY: AtomicBool = AtomicBool::new(false);
 
// Поток A
DATA.store(42, Ordering::Relaxed);       // (1)
READY.store(true, Ordering::Release);    // (2) Release: (1) видно до (2)
 
// Поток B
while !READY.load(Ordering::Acquire) {}  // (3) Acquire: видит (2)=true
let value = DATA.load(Ordering::Relaxed);// (4) гарантированно 42

Почему DATA.store и DATA.load используют Relaxed? Им не нужна собственная упорядоченность — гарантию обеспечивает пара Release/Acquire на READY. Release в точке (2) запрещает записи (1) перепрыгнуть вперёд. Acquire в точке (3) запрещает чтению (4) выполниться раньше. Вместе они дают: если B увидел READY == true, то DATA уже 42.

Это ровно тот паттерн, который используют мьютексы внутри: unlock содержит Release (все записи внутри критической секции зафиксированы до отпускания замка), lock содержит Acquire (все чтения после захвата замка увидят актуальные данные). Acquire/Release — тот же механизм, только без взаимного исключения.

Тот же код на C:

#include <stdatomic.h>
 
atomic_int data = 0;
atomic_bool ready = false;
 
// Поток A
atomic_store_explicit(&data, 42, memory_order_relaxed);
atomic_store_explicit(&ready, true, memory_order_release);
 
// Поток B
while (!atomic_load_explicit(&ready, memory_order_acquire)) {}
int value = atomic_load_explicit(&data, memory_order_relaxed);
// value == 42, гарантировано

SeqCst: глобальный порядок

Acquire/Release создают happens-before между двумя потоками: отправителем и получателем. Но когда три и более потока должны договориться о порядке событий, Acquire/Release недостаточно.

Классический пример — алгоритм Деккера (Dekker’s algorithm). Два потока устанавливают свои флаги и проверяют чужой:

// Поток A                        // Поток B
flag_a = true;                    flag_b = true;
if (!flag_b) {                    if (!flag_a) {
    // критическая секция             // критическая секция
}                                 }

С Acquire/Release оба потока могут войти в критическую секцию. Поток A записывает flag_a (Release) и читает flag_b (Acquire), но Release-store + Acquire-load на разных переменных не создают happens-before между A и B. Каждый поток может увидеть свой флаг поднятым, а чужой — ещё нет.

SeqCst (sequentially consistent) — самая строгая модель. Все SeqCst-операции во всех потоках выстраиваются в единый глобальный порядок, согласованный между всеми наблюдателями. Если поток A выполнил SeqCst-store flag_a = true до SeqCst-load flag_b, и поток B выполнил SeqCst-store flag_b = true до SeqCst-load flag_a, то хотя бы один из них увидит чужой флаг поднятым.

На x86 SeqCst-store требует полного барьера, запрещающего store-load reorder (единственное переупорядочивание, которое TSO допускает). Конкретная реализация зависит от компилятора: GCC (GNU Compiler Collection) генерирует mov + mfence (memory fence — барьер, ожидающий опустошения store buffer), LLVM/Clang — xchg (атомарный обмен, который неявно содержит full barrier и часто быстрее mfence на современных процессорах). Стоимость: 10-40 нс на операцию. На ARM SeqCst использует dmb ish (data memory barrier, inner shareable) — полный барьер, 5-20 нс.

Стоимость гарантий

Каждый уровень ordering добавляет ограничения, и эти ограничения имеют цену в наносекундах:

Ordering        Гарантия                x86 (TSO)       ARM (Weak)
─────────────────────────────────────────────────────────────────────
Relaxed         нет torn read/write     ~0 нс           ~0 нс
                нет гарантий порядка    (обычный mov)   (обычный ldr/str)
 
Acquire/        happens-before между    ~0 нс           ~1-3 нс
Release         парой потоков           (компилятор.    (ldar/stlr)
                                         барьер)
 
SeqCst          глобальный порядок      ~10-40 нс       ~5-20 нс
                для всех потоков        (mov + mfence)  (ldr/str + dmb ish)

На x86 разница между Relaxed и Acquire/Release — ноль наносекунд. TSO и так гарантирует store-store и load-load порядок; Release и Acquire сводятся к запрету оптимизаций компилятора. Но SeqCst дорогой: mfence сбрасывает store buffer и ждёт завершения всех записей.

На ARM каждый уровень стоит реальных наносекунд. stlr (Release) ждёт завершения предыдущих записей. ldar (Acquire) запрещает спекулятивное выполнение последующих чтений. dmb ish (SeqCst) — полный забор в обе стороны.

x86 TSO и ARM: почему портативный код всё равно нужен

x86 работает в модели Total Store Order: записи одного ядра выходят из store buffer строго в порядке программы, чтения не переупорядочиваются относительно друг друга. Единственное разрешённое переупорядочивание — store-load: store может оказаться «после» следующего за ним load, потому что store уходит в store buffer, а load выполняется спекулятивно. Поэтому Release на x86 бесплатен (store-store порядок гарантирован), но SeqCst дорогой (mfence блокирует store-load reorder).

ARM использует weak ordering: процессор может переупорядочивать любые пары операций — store-store, load-load, store-load, load-store — если между ними нет зависимости по данным. Каждый барьер — реальная инструкция, которая ограничивает это поведение.

Переупорядочивание      x86 TSO     ARM
────────────────────────────────────────
store-store             нет         да
load-load               нет         да
store-load              да          да
load-store              нет         да

Код, который работает на x86 без явных барьеров, ломается на ARM. Серверы AWS Graviton (ARM), Apple Silicon, мобильные устройства — все используют weak ordering. Портативный код пишется под слабейшую модель и явно указывает нужные гарантии. На x86 Acquire/Release бесплатны (компилятор генерирует обычные mov, TSO и так обеспечивает нужный порядок). SeqCst на x86 остаётся дорогим — mfence блокирует store-load reorder, который TSO допускает. На ARM каждый уровень ordering стоит реальных наносекунд, но обеспечивает корректность.

Когда какой ordering использовать

Relaxed — когда порядок не важен. Счётчики метрик, статистика, генерация уникальных ID через fetch_add. Поток инкрементирует requests_total — не имеет значения, в каком порядке другие потоки увидят это обновление. Важно только, чтобы значение не было разорвано.

static COUNTER: AtomicU64 = AtomicU64::new(0);
 
// Любой поток
COUNTER.fetch_add(1, Ordering::Relaxed);
 
// Поток мониторинга: значение может отставать, но не разорвано
let total = COUNTER.load(Ordering::Relaxed);

Acquire/Release — когда один поток передаёт данные другому через сигнал. Паттерн «записал данные, поднял флаг» — producer/consumer, инициализация, publish. Мьютексы внутри используют именно Acquire/Release.

SeqCst — когда три и более потока должны согласовать порядок. Алгоритм Деккера, Петерсона, любые ситуации, где корректность зависит от глобально согласованного порядка. Также разумный выбор по умолчанию, когда нет уверенности в правильности более слабого ordering: лучше заплатить 10-40 нс, чем получить баг, который воспроизводится раз в неделю только на ARM.

На практике подавляющее большинство lock-free кода использует Acquire/Release. Relaxed — для счётчиков. SeqCst — редко, в специфических алгоритмах или как страховка.

От барьеров к lock-free структурам

Модель памяти даёт инструменты для корректной публикации данных между потоками без мьютекса. Но паттерн flag + data — простейший случай. Реальные задачи сложнее: очередь, где несколько producer и consumer одновременно добавляют и извлекают элементы, стек, где push и pop конкурируют за вершину. Мьютекс сериализует доступ и становится узким местом: при 64 потоках и 1M операций в секунду contention на мьютексе убивает пропускную способность. Lock-free структуры данных решают эту задачу: корректность без блокировок, используя только CAS и правильные ordering.

См. также

  • Ruby memory model — GVL даёт sequential consistency между Ruby-инструкциями, но не между отдельными bytecode: @counter += 1 разбивается на read/compute/write и допускает потерю обновлений

Sources

← Синхронизация | Lock-free структуры →

Graph View

Backlinks