Конкурентность и атомики

C++ Concurrency in action [2020] Anthony Wiliams

Rust Atomics and Locks [2023] Mara Bos

Средняя и хорошая книги об основах

Поводом глубже погрузиться в тему конкурентности стал пойманный мной баг в крейте thingbuf (issue). После этого я прикупил книгу C++ Concurrency in Action, и параллельно начал читать онлайн Rust Atomics and Locks.

Изначально хотел написать свою SCSP-очередь с переиспользованием слотов 🚲. Но после прочтения понял, что ну его. Лучше починить заведенный баг.

Memory ordering

Я уже освещал тему атомиков, но после чтения книг появилось, что добавить.

Внутри одного потока всегда сохраняется программный порядок (sequenced-before) независимо от Ordering. То есть в рамках одного потока операции ведут себя так, как будто выполняются строго последовательно (при отсутствии других потоков, изменяющих те же данные).

static RELAXED: AtomicI64 = AtomicI64::new(0);
fn one_tread_only() {
  let t0 = RELAXED.load(Ordering::Relaxed);
  RELAXED.store(1, Ordering::Relaxed);
  let t1 = RELAXED.load(Ordering::Relaxed);
  assert_eq!(t0, 0);
  assert_eq!(t1, 1);
}

При Relaxed операции разных потоков не связаны отношением happens-before. Однако для каждой атомарной переменной существует *лобальный modification order — единый порядок всех её записей, общий для всех потоков. Это означает, что если поток однажды прочитал значение атомарной переменной, он не может позже прочитать более старое значение этой же переменной. При этом разные потоки могут одновременно наблюдать разные значения.

static RELAXED: AtomicI64 = AtomicI64::new(0);
thread1: { for i in 1..=1_000_000 { RELAXED.store(i, Ordering::Relaxed); } };
thread2: {
  let mut last = 0;
  while last !=1_000_000 {
    let t = RELAXED.load(Ordering::Relaxed);
    if t < last {
        panic!("impossible: saw RELAXED go backwards: {} -> {}", last, v);
    }
    last = t;
}}

Acquire/Release позволяют установить отношение happens-before между потоками. Если поток 1 выполнил N произвольных записей в память, а затем записал значение в атомарную переменную с Release, то все предыдущие записи становятся видимыми другим потокам после синхронизации. Если поток 2 прочитает эту же атомарную переменную с Acquire и увидит запись, сделанную потоком 1, то между потоками возникает отношение happens-before. В этом случае поток 2 гарантированно увидит все N записей, сделанные потоком 1 до Release.

static mut DATA: u64 = 0;
thread1: {
    A.store(SOME_VAL, Relaxed); // можно и Release 
    unsafe { DATA = SOME_VAL2 }; // Safety: thread2 не может читать DATA до установки B
    B.store(SOME_VAL, Release); 
}
thread2: {
    while B.load(Acquire) != SOME_VAL { }
    let a = A.load(Relaxed); // можно и Acquire
    assert!(a == SOME_VAL); // OK
    assert!(unsafe { DATA } == SOME_VAL2); // из-за Acquire/Release, безопасно читать DATA
}

spawn и join потоков создают отношение happens-before, аналогичное Release/Acquire, влияя на Relaxed операции над атомиками.

На основе этого отношения можно написать примитивный мьютекс:

static mut DATA: u64 = 0;
static LOCKED: AtomicBool = AtomicBool::new(false);

fn f(new_val: u64) {
    if LOCKED.swap(true, Acquire) == false {
        // Safety: мы владеем эксклюзивным доступом к DATA
        unsafe { DATA = new_val };
        LOCKED.store(false, Release);
    }
}

Ordering::SeqCst это Acquire/Release плюс глобальный порядок операций. Если поток записал или прочитал значение атомарной переменной с SeqCst, другие потоки будут наблюдать эти операции в одном и том же глобальном порядке (при условии, что они тоже используют SeqCst).

На практике SeqCst для большинства алгоритмов не нужен. Если требуется строгая синхронизация, лучше использовать Relaxed операции и добавить явный std::sync::atomic::fence(Ordering::SeqCst).

Атомики в ассемблере

В седьмой главе книги по Rust разбирается ассемблер, стоящий за атомиками, и различия между инструкциями на ARM, RISC и x86. Это самая интересная глава всей книги, потому что она отражает, чем на самом деле являются memory ordering и атомики.

x86

Если использовать Relaxed ordering с load/store, то ассемблер обычной операции не отличается от операции с атомиком: mov dword ptr [rdi], 0.

Для операций Read-Modify-Write (add, sub, and, not, or, xor) на x86 используется lock-префикс: lock add dword ptr [rdi], 10. Эта инструкция подходит, если не нужно знать значение переменной до изменения. Если старое значение требуется, используется CAS-цикл:

# x.fetch_or(10, Relaxed)
mov eax, dword ptr [rdi]
.L1:
  mov ecx, eax
  or ecx, 10
  lock cmpxchg dword ptr [rdi], ecx
  jne .L1

Есть и специализированные инструкции для некоторых операций, например, xadd, bts, btr, btc, которые можно использовать с lock-префиксом.

Вишенка на торте: на x86 load и read-modify-write операции генерируют одинаковый ассемблер как для Relaxed, так и для SeqCst. store одинаков для Relaxed и Release, но отличается для SeqCst:

# x.store(0, SeqCst)
xor eax, eax
xchg dword ptr [rdi], eax

Т.е. если пишешь код на x86 с SeqCst для load или модификаций, то он не будет отличаться от Relaxed. Поэтому при ревью кода можно быть чуть менее строгим к избыточному SeqCst. Делать так постоянно всё же не стоит, но знать стоимость ordering полезно.

Как следствие, std::sync::atomic::fence на x86 разворачивается в ничто во всех случаях, кроме SeqCst. В последнем случае появляется инструкция mfence.

ARM

Если использовать Relaxed ordering с load/store, то обычные и атомарные операции также выглядят одинаково: str wzr, [x0].

Для операций Read-Modify-Write ARM использует пару инструкций load-linked / store-conditional (LL/SC):

# x.fetch_add(10, Relaxed)
.L1:
  ldxr w8, [x0]
  add w9, w8, #10
  stxr w10, w9, [x0]   # не сохранит, если значение изменилось после ldxr
  cbnz w10, .L1        # stxr пишет 0 при успехе, иначе 1

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

Если нужно отменить отслеживание ldxr, компилятор добавляет инструкцию clrex.

В новых версиях ARM появились и специализированные атомарные инструкции (fetch_add, fetch_max и другие), которые работают быстрее.

На ARM memory ordering влияет на выбор инструкций гораздо сильнее, чем на x86. Различаются инструкции:

Ordering	Load	Store	Exclusive Load	Exclusive Store	Meaning
Relaxed	ldr	str	ldxr	stxr	load/store register, load/store exclusive register
Acquire	ldar	—	ldaxr	—	load-acquire register, load-acquire exclusive register
Release	—	stlr	—	stlxr	store-release register, store-release exclusive register

Для SeqCst используются комбинации Acquire, Release и AcqRel в зависимости от операции. Именно поэтому на ARM важно различать Relaxed и более строгие ordering.

Как следствие, std::sync::atomic::fence на ARM генерирует реальные инструкции: Acquire → dmb ishld, остальные варианты → dmb ish.

C++ Concurrency in action

Книга занимает около 640 страниц, но по факту примерно половина — это приложение с распечаткой cppreference. Реально полезного текста около 300 страниц.

Начинается все с классического введения в многопоточность C++. Разбираются потоки, разные виды мьютексов (mutex, shared_mutex, recursive_mutex), RAII-обёртки (lock_guard, unique_lock, scoped_lock), а также работа с несколькими мьютексами через std::lock. Есть и менее очевидные вещи, например, инициализация через once_flag и call_once как альтернатива статическим переменным.

Дальше подробно разбираются высокоуровневые механизмы синхронизации: условные переменные, latch, barrier, future-механизмы вместе с std::promise и std::packaged_task.

Сравнение C++ с Rust

В Rust нет прямых аналогов std::future, так как в C++ это, по сути, контейнер для передачи результата. В Rust используют каналы, spawn_blocking или полноценный async/await runtime. При этом сами Rust-фьючерсы — это ленивый state machine, которому требуется executor.

В C++ нормальный then-chaining и операции вроде when_all / when_any появятся только в C++26 вместе с std::execution. В Rust подобные вещи (select, join_all) уже давно есть в async-экосистеме.

Некоторые примитивы совпадают:

• std::latch можно сравнить с crossbeam::WaitGroup
• std::barrier есть в стандартной библиотеке Rust (std::sync::Barrier)

Интересности

Самый сильный раздел — разработка собственных concurrent-структур данных. Автор постепенно усложняет примеры: сначала блокирующие структуры (stack, queue, hash_map, linked_list) с увеличением числа мьютексов. Например, в списке мьютекс размещается прямо в каждой ноде.

Дальше книга переходит к lock-free структурам: стеку и очереди. Эта часть заметно сложнее: я её не осилил и прочитал только поверхностно. Для реализации RCU приводятся два подхода: hazard pointers и подсчёт ссылок. Выглядит это, как минималистичный сборщик мусора, где удаление элементов откладывается до момента, когда ни один поток больше не работает с ними.

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

В книге обсуждаются общие принципы разработки конкурентного кода:

• распределение работы: пулы воркеров (с механизмом work-stealing), организация пайплайнов, распределение работы в рекурсивных алгоритмах с ограничением общего числа потоков
• кэш: если данные лежат слишком близко, можно получить false sharing на одной и той же линии. Если слишком далеко — ухудшается locality. Если хочется пощупать эти эффекты руками, рекомендую лабораторные data_packing и false_sharing из курса perf-ninja
• конкуренция за ресурсы: когда потоков много, стоит помнить, что кэш у ядра общий, и потоки на одном ядре будут его делить. Переключения контекста никуда не исчезают
• безопасность исключений: для этого хорошо подходят std::packaged_task и std::async. Без них обеспечить корректную обработку исключений в собственном пуле потоков будет довольно сложно

Rust Atomics and Locks

Книга хорошо объясняет фундаментальные механизмы синхронизации и постепенно показывает, как из атомиков строятся более сложные примитивы.

Иногда интересные детали встречаются в самых неожиданных местах. Пример скрытой синхронизации: в Rust println! всегда потокобезопасен: внутри используется std::io::Stdout::lock(). Отключить это нельзя. Если нужно писать в stdout без этого лока, остаётся путь через libc::write.

В C++ еще больше нюансов в стандартном вводе-выводе: для ускорения отключают синхронизацию через sync_with_stdio(false), а также разрывают связь cin и cout с помощью cin.tie(nullptr), чтобы ввод не флашил вывод автоматически. В Rust таких механизмов по умолчанию нет, поведение проще и прозрачнее.

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

let v: Mutex<Vec<i32>> = init();
if let Some(item) = v.lock().unwrap().pop() {
 process(item);
} // lock dropped after the whole if
if v.lock().unwrap().pop() == Some(42) { // lock dropped after condition
  call();
}

В книге рассматривается механизм thread::park / unpark. Это «условная переменная для бедных»: он работает только между конкретными потоками и требует явного доступа к thread_handle.

Отдельный большой блок посвящён атомикам и CAS-циклам. Материал читается легко: сначала вводится базовый паттерн compare-and-swap, а такие вещи, как гонки, переупорядочивание операций и ABA-проблема, лишь обозначаются. Подробное обсуждение появляется позже. Такой подход позволяет не перегружать первые главы и держать фокус на основной идее.

Для CAS-loop в Rust есть удобная обёртка fetch_update: внутри она реализует тот же цикл сравнения и замены, а пользователю остаётся только передать функцию, описывающую переход из текущего значения в новое.

Дальше книга переходит к простым примитивам: spinlock, каналы и Arc. Про Arc я уже писал раньше, и даже реализовывал. Кажется, этот пример был в The Rustonomicon. В книге он разобран подробнее и довольно интересный.

В финальных главах автор сравнивает примитивы синхронизации в разных операционных системах и показывает, как реализовать собственные Mutex, Condition Variable и RwLock. Я добавил эти реализации в свой учебный репозиторий.

Bonus

В статье про атомики не упомянул, что есть отличная браузерная игра The Deadlock Empire, посвящённая конкурентности и типичным ошибкам многопоточности. В ней ты игрешь за злого планировщика потоков, который приводит программу к дедлокам, гонкам данных и другим сбоям.

Знаю еще пару игр: Human Resource Machine и 7 Billion Humans, в которых через задачки моделируются аспекты параллельного и офисного «многопоточного» труда, но сам до них я пока так и не добрался, только положил в Steam‑wishlist.

Дополнительно можно почитать статью на хабре Введение в атомики. C++.