atomic-instructions

Атомарные инструкции

Предпосылки: ISA (инструкции, x86 vs ARM), когерентность кешей (MESI, Modified, кеш-линия, invalidate, cache-to-cache transfer).

← SIMD и векторные расширения

Сценарий потерянного инкремента из когерентности кешей оставил открытый вопрос. Два ядра одновременно выполняют counter++, оба читают 5, оба записывают 6, один инкремент исчезает. MESI при этом работает корректно — каждый отдельный store становится виден. Разрыв на один слой выше: последовательность load-add-store — это три инструкции, и между первой и третьей другое ядро успевает вклиниться. Когерентность даёт видимость; неделимости она не даёт.

Закрыть этот разрыв может только сам процессор — тем, что выполнит read-modify-write как одну инструкцию с гарантией: для любого другого ядра операция либо ещё не произошла, либо уже закончилась целиком. Такие инструкции называются атомарными (atomic, от греч. ἄτομος — неделимый).

Когерентность в этой истории выступает дважды. Она обеспечивает возможность неделимости: без механизма, который умеет передавать эксклюзивное владение кеш-линией между ядрами, процессору не на что опереть гарантию. И она же определяет цену: атомарная инструкция — это не только два-три такта в конвейере, это когерентная транзакция, захват линии в Modified, часто cache-to-cache transfer. Та самая цена, которую таблица задержек в когерентности кешей уже зафиксировала, — здесь она становится доминирующим компонентом.

Две реализации одной задачи: LOCK и LL/SC

Неделимость read-modify-write нужна везде, но ISA к этой задаче подходят по-разному. Два основных подхода в массовой практике — префикс LOCK на x86 и пара LL/SC на ARM. Они решают одну и ту же задачу — гарантировать, что между чтением и записью ни одно другое ядро не успеет изменить линию. Разница — в том, как именно они опираются на когерентный протокол.

x86: префикс LOCK

На x86 атомарная read-modify-write-инструкция получается добавлением префикса LOCK к одной из инструкций с явно разрешённым атомарным вариантом: ADD, ADC, AND, OR, SUB, SBB, XOR, XADD, INC, DEC, NEG, NOT, BT/BTR/BTC/BTS, CMPXCHG, CMPXCHG8B/CMPXCHG16B — и только в форме, где адресат в памяти (применение к регистру даёт #UD). XCHG с операндом в памяти залочен по умолчанию, префикс писать не нужно. Семантика: процессор должен захватить нужную кеш-линию в Modified и удерживать её до конца инструкции — никакое другое ядро в этот момент не может ни читать, ни писать.

Под капотом LOCK — та же когерентная транзакция, что и в MESI. Если линия уже в M или E у этого ядра, транзакция локальная: несколько тактов поверх обычной инструкции. Если линия в Shared или у другого ядра — выполняется invalidate (или cache-to-cache transfer), линия переходит в M, инструкция исполняется, и только после этого ядро отпускает линию для других запросов.

Две самые частые LOCK-инструкции:

• LOCK XADD — прочитать значение, прибавить, записать результат, вернуть старое. Одна инструкция вместо трёх шагов.
• LOCK CMPXCHG — прочитать значение, сравнить с ожидаемым, если совпадает — записать новое и вернуть успех; иначе оставить как есть и сообщить о неудаче.

Атомарность на x86 — свойство самой инструкции. Программист выбирает правильную инструкцию, процессор гарантирует остальное.

ARM: LL/SC (Load-Linked / Store-Conditional)

ARM до версии 8.1 не имеет префикса «сделай эту инструкцию атомарной». Атомарность конструируется из пары инструкций с промежуточным состоянием:

• LDXR (load-exclusive) читает значение по адресу и помечает эту кеш-линию как отслеживаемую — на уровне ядра заводится статусный бит на линию (exclusive monitor).
• STXR (store-exclusive) пытается записать новое значение. Запись выполняется успешно только в том случае, если к моменту STXR отслеживаемая линия не была тронута ни одним другим ядром. Иначе STXR ничего не пишет и возвращает неудачу.

Между LDXR и STXR программа выполняет нужное вычисление — прибавляет, сравнивает, решает. Если между ними когерентный протокол фиксирует чужую запись в ту же линию, монитор сбрасывается, STXR отказывает, и код повторяет попытку:

ll_sc_increment(addr):
    повторять:
        old = LDXR(addr)        // читаем и отмечаем линию
        new = old + 1
        успех = STXR(addr, new) // пишем, если линию никто не трогал
        если успех: выйти

Различие с x86 принципиальное: LOCK удерживает линию на время инструкции; LL/SC обнаруживает конфликт постфактум и повторяет. Монитор может сбрасываться не только конкурирующей записью, но и прерыванием, переключением контекста, вытеснением линии — поэтому STXR может отказать и без реальной гонки (spurious failure, ложный отказ). Цикл повтора в LL/SC обязателен не только из-за конкуренции, но и из-за этой особенности.

Exclusive — два разных смысла

«Exclusive» в LDXR — статусный бит на кеш-линии, обозначающий «я слежу за этой линией». «Exclusive» в MESI — состояние кеш-линии «копия только у меня и совпадает с RAM». Это разные вещи. Монитор LDXR не переводит линию в MESI-Exclusive и наоборот: MESI-E и exclusive monitor — две независимые книги учёта, одна — про владение копией, другая — про пометку «не забудь, что ты читал это».

ARMv8.1 LSE: прямые атомарные RMW

С 2016 года, начиная с ARMv8.1-A, в ARM появилось расширение LSE (Large System Extensions) — набор инструкций атомарного read-modify-write, не требующих цикла LL/SC. Вместо пары с повтором — одна инструкция:

• CAS — compare-and-swap одной инструкцией.
• LDADD — загрузить, прибавить, записать (аналог LOCK XADD).
• SWP — атомарный обмен.

На современных серверных ARM — AWS Graviton, Apple M-series, Ampere — LSE поддерживается и используется компиляторами по умолчанию. Модель атомарности на этих процессорах уже ближе к x86: одна инструкция, одна когерентная транзакция, без retry-цикла. LL/SC сохраняется как fallback для старого железа и для операций, где LSE не подходит (например, произвольная функция между чтением и записью — там всё ещё нужен LDXR/STXR с вычислением посередине).

В реальной практике 2020-х ARM-серверный код атомарные счётчики и блокировки строит на LSE; LL/SC остаётся инструментом для более сложных случаев.

CAS: программная абстракция над обоими подходами

LOCK XADD и LOCK CMPXCHG, LL/SC и LSE — это разные реализации одной и той же задачи. Программист редко работает с ними напрямую: компилятор и стандартная библиотека дают абстракцию, не зависящую от ISA. Центральная такая абстракция — CAS (compare-and-swap).

CAS — операция над ячейкой памяти, принимающая три аргумента:

• адрес ячейки,
• ожидаемое значение,
• новое значение.

Семантика: если текущее значение в ячейке совпадает с ожидаемым, CAS записывает новое и возвращает успех; если нет — не трогает ячейку и возвращает неудачу. Вся проверка и запись — одна неделимая операция.

Под капотом CAS транслируется в то, что есть в ISA:

• на x86 — в LOCK CMPXCHG;
• на ARM с LSE — в инструкцию CAS;
• на ARM без LSE — в цикл LL/SC с LDXR, сравнением и STXR.

C++11 std::atomic::compare_exchange_strong, Rust AtomicUsize::compare_exchange, Java AtomicInteger.compareAndSet — все это CAS в разных формах. Программист пишет один вызов, компилятор подставляет подходящую реализацию.

CAS удобен тем, что позволяет атомарно применить произвольную функцию, а не только инкремент. Схема — прочитать текущее значение, посчитать новое, попробовать записать через CAS; если не получилось (кто-то вмешался) — повторить:

atomic_update(addr, fn):
    повторять:
        old = прочитать(addr)
        new = fn(old)
        если CAS(addr, old, new) успешен:
            выйти
        // кто-то изменил addr между чтением и CAS —
        // повторяем с новым значением

Для простых операций (инкремент, побитовое ИЛИ) компилятор обычно выбирает специализированную инструкцию — LOCK XADD на x86, LDADD на ARM LSE. Одна инструкция дешевле, чем CAS-цикл, даже если промахов нет: меньше работы в конвейере.

Цена — это цена когерентной транзакции

Атомарная инструкция в наносекундах не дороже обычной записи — декодер, исполнительный блок, retirement заняты примерно одинаково. Всю разницу создаёт когерентность. Чтобы гарантировать неделимость, процессор должен провести линию через Modified — а это значит либо локальный доступ (если линия уже M или E), либо полный цикл когерентного протокола.

Таблица задержек, разбираемая в цене когерентности, здесь работает как прейскурант атомарных операций:

• Локальный доступ (линия уже в M или E у этого ядра) — порядок L1-hit плюс несколько тактов на саму атомарность.
• Передача линии от другого ядра на этом же сокете (cache-to-cache transfer после invalidate) — десятки наносекунд.
• Cross-socket обращение — сотня наносекунд и больше.

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

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

shared counter = 0
 
поток 0 (Core 0):              поток 1 (Core 1):
  повторить 100M раз:            повторить 100M раз:
    atomic_increment(counter)      atomic_increment(counter)

Если запустить один поток с обычным (неатомарным) инкрементом, 100 миллионов итераций проходят за доли секунды — счётчик всё время в L1 одного ядра, обращения локальны. Два потока с атомарным инкрементом — в десятки раз медленнее. Всё время тратится не на саму инструкцию, а на перелёт кеш-линии между кешами: каждый инкремент переводит линию в Modified у того ядра, которое её в этот момент держит, а следующий инкремент другого ядра вынуждает передать линию к нему.

Грубая оценка: 200 миллионов передач владения × ~50 нс = ~10 секунд. Большую часть этого времени программа ждёт, пока линия доехала по когерентной сети между ядрами и вернулась обратно. Этот эффект — ping-pong — уже обсуждался в когерентности; для атомарных операций он становится базовой моделью стоимости, а не edge-case’ом.

Обычная (неатомарная) запись отчасти скрывает ту же цену за store buffer: ядро кладёт запись в буфер и продолжает выполнение, пока когерентная транзакция идёт в фоне. Для атомарного read-modify-write эта уловка не работает — инструкция обязана дождаться завершения захвата линии, иначе неделимость стала бы фикцией. Поэтому атомарные операции над оспариваемой линией особенно чувствительны к цене когерентности.

Что одна атомарная инструкция не решает

CAS и его родственники гарантируют неделимость для одной ячейки памяти — 4, 8, иногда 16 байт (зависит от ISA и режима). Многие реальные задачи требуют атомарности для нескольких связанных ячеек. Банковский перевод: списать сумму с одного счёта и зачислить на другой. CAS может атомарно обновить первый счёт, но между этим обновлением и вторым другой поток увидит несогласованное состояние — деньги ушли с одного счёта, а на другой ещё не пришли.

Для таких задач нужны программные примитивы синхронизации — мьютексы, семафоры, read-write блокировки. Все они строятся поверх CAS: мьютекс, например, — это обычно CAS-цикл на одном бите, плюс очередь ожидающих в ядре. Атомарная инструкция — строительный материал, не законченное решение.

Отдельное направление — transactional memory: аппаратная поддержка спекулятивного выполнения блока инструкций как одной транзакции, с откатом при конфликте. В x86 существовала реализация Intel TSX (начиная с Haswell) с инструкциями XBEGIN/XEND; после серии уязвимостей и откатов в микрокоде на большинстве процессоров она отключена и в новой практике не используется.

Есть и особый случай — двуместный CAS (double-width CAS): на x86 это LOCK CMPXCHG16B, работающий над двумя смежными 8-байтными словами. Он позволяет атомарно менять пару «указатель + счётчик» — основа борьбы с ABA в lock-free структурах.

См. также

• Упорядочение памяти — атомарная инструкция гарантирует неделимость; какой порядок она гарантирует между собой и остальным кодом — отдельный вопрос модели памяти
• Примитивы синхронизации — мьютексы, семафоры, read-write блокировки, построенные поверх CAS
• Lock-free структуры данных: проблема ABA — CAS видит прежнее значение и считает, что «ничего не изменилось», но контекст между двумя чтениями мог полностью смениться; пара «указатель + счётчик» через двухсловный CAS — классический способ закрытия
• Атомарность команд Redis — в Redis атомарность команды достигается не аппаратной неделимостью, а однопоточным event loop: один исполнитель команд на всё хранилище, никакого чередования; другая ось, другое понятие того же слова

Sources

• John L. Hennessy, David A. Patterson, 2017, Computer Architecture: A Quantitative Approach — Chapter 5: Thread-Level Parallelism, Section 5.5
• Intel, 2024, Intel 64 and IA-32 Architectures Software Developer’s Manual — Volume 2, LOCK prefix; Volume 3, Chapter 8 (Multiple-Processor Management)
• ARM, 2023, ARM Architecture Reference Manual for A-profile architecture — B2.9 Exclusive access instructions (LDXR/STXR); C3.2.9 Atomic instructions (LSE)
• Paul E. McKenney, 2021, Is Parallel Programming Hard, And, If So, What Can You Do About It? — Chapter 5: Counting (атомарные счётчики как каноничный пример цены когерентности)

---

← SIMD и векторные расширения