🧵 Раздел 9 · Вопрос #9

Что такое CAS (Compare-And-Swap)

Инструкция принимает три параметра:

🧵 Многопоточность 📄 Исходный Markdown

🟢 Junior Level

Краткий ответ для собеседования (30 секунд)

CAS (Compare-And-Swap / «Сравни и замени») — это фундаментальная атомарная инструкция современных процессоров, являющаяся аппаратным фундаментом всех неблокирующих (lock-free) структур данных и алгоритмов в Java.

Инструкция принимает три параметра:

  1. Адрес ячейки памяти ($V$)
  2. Ожидаемое значение ($A$, Expected)
  3. Новое значение ($B$, New)

Принцип работы: процессор атомарно на аппаратном уровне сравнивает текущее значение в ячейке $V$ с ожидаемым $A$. Если они равны, процессор записывает туда значение $B$ и возвращает true. Если значение уже изменилось другим потоком, запись не производится, и возвращается false.

CAS реализует оптимистичную модель конкуренции (Optimistic Concurrency): поток не блокирует ресурс заранее, а пытается выполнить модификацию; если возникает конфликт с другим параллельным потоком, операция повторяется в цикле (CAS retry loop).

Оптимистичный против Пессимистичного подхода

Характеристика Пессимистичный (synchronized, ReentrantLock) Оптимистичный (CAS, Atomic*)
Стратегия Заблокировать ресурс перед началом работы Надеяться на отсутствие конфликта, повторить при сбое
Поведение при конкуренции Поток засыпает (паркуется ОС в BLOCKED / WAITING) Поток продолжает крутиться на CPU (Spin-loop)
Затраты при низкой нагрузке Высокие (вход/выход из монитора, системные вызовы) Минимальные (одна аппаратная инструкция)
Затраты при экстремальной нагрузке Умеренные (потоки спят и не жгут процессор) Катастрофические (100% утилизация CPU на холостые попытки)

Пример на Java 21: Неблокирующий стек Трайбера (Treiber Stack)

import java.util.concurrent.atomic.AtomicReference;

public class LockFreeStack<E> {
    private record Node<E>(E item, Node<E> next) {}

    private final AtomicReference<Node<E>> head = new AtomicReference<>(null);

    public void push(E item) {
        Node<E> newHead = new Node<>(item, null);
        Node<E> currentHead;
        do {
            currentHead = head.get();
            newHead = new Node<>(item, currentHead);
            // Атомарно переставляем вершину стека, если она не изменилась
        } while (!head.compareAndSet(currentHead, newHead));
    }

    public E pop() {
        Node<E> currentHead;
        Node<E> nextHead;
        do {
            currentHead = head.get();
            if (currentHead == null) {
                return null;
            }
            nextHead = currentHead.next();
        } while (!head.compareAndSet(currentHead, nextHead));
        return currentHead.item();
    }
}

🟡 Middle Level

Аппаратная реализация на разных процессорных архитектурах

На уровне кремния процессора атомарность CAS реализуется принципиально по-разному в зависимости от архитектуры:

1. CISC (x86-64 / Intel & AMD)

Используется инструкция LOCK CMPXCHG:

; rax = expected value
; rbx = new value
; [rdi] = адрес ячейки в памяти
lock cmpxchg [rdi], rbx
  • Префикс LOCK переводит протокол когерентности кешей (MESI/MOESI) в режим монопольной блокировки кеш-линии (Cache Line Lock).
  • На время выполнения операции никакие другие ядра процессора не могут читать или писать в эту 64-байтную кеш-линию.
  • Если значения равны, флаг ZF (Zero Flag) выставляется в 1, а в память пишется rbx. Иначе ZF = 0, а в регистр rax загружается актуальное значение из памяти.

2. RISC (ARM64, Apple Silicon, RISC-V)

Вместо единой инструкции используется пара инструкций LL/SC (Load-Linked / Store-Conditional):

  • LDXR (Load Exclusive): читает значение и активирует аппаратный монитор эксклюзивного доступа к кеш-линии.
  • STXR (Store Exclusive): пытается записать новое значение. Запись успешна только в том случае, если с момента LDXR ни одно ядро не модифицировало данную кеш-линию.

Иерархия гарантий прогресса (Progress Guarantees)

В многопоточной теории неблокирующие алгоритмы строго классифицируются по силе математических гарантий:

+-----------------------------------------------------------+
| Wait-Free (Сильнейшая гарантия)                           |
| Каждый поток завершает операцию за конечное число шагов  |
| (Пример: LongAdder.add(), ConcurrentLinkedQueue.size())   |
+-----------------------------+-----------------------------+
                              |
+-----------------------------v-----------------------------+
| Lock-Free (Средняя гарантия)                              |
| Хотя бы один поток системы гарантированно завершит шаг    |
| (Пример: AtomicInteger.incrementAndGet(), Treiber Stack)  |
+-----------------------------+-----------------------------+
                              |
+-----------------------------v-----------------------------+
| Obstruction-Free (Слабая гарантия)                        |
| Поток завершит шаг только если все остальные изолированы  |
+-----------------------------------------------------------+

Оптимизация спин-цикла: Thread.onSpinWait()

В наивном цикле while (!compareAndSet(...)) процессор крутится на максимальной частоте, вызывая перегрев, прожиг электроэнергии и сброс конвейера команд (pipeline flush) при выходе из цикла.

В Java 9 был представлен метод Thread.onSpinWait():

public void executeSpinLoop() {
    while (!atomicVar.compareAndSet(expected, updated)) {
        // Подсказка компилятору и CPU о нахождении в спин-цикле
        Thread.onSpinWait(); 
    }
}

Что происходит на уровне ассемблера:

На архитектуре x86 этот вызов транслируется в инструкцию PAUSE:

  1. Приостанавливает исполнение конвейера процессора на ~10-40 тактов.
  2. Предотвращает спекулятивное выполнение ложных инструкций ветвления (Pipeline Clear Penalty).
  3. Снижает энергопотребление ядра процессора в цикле ожидания.

🔴 Senior Level

Проблема ABA и её анатомия в управляемой среде JVM

Суть проблемы:

  1. Поток 1 читает значение переменной: $V = A$.
  2. Поток 1 вытесняется планировщиком ОС.
  3. Поток 2 меняет значение с $A$ на $B$.
  4. Поток 3 (или тот же поток 2) меняет значение с $B$ обратно на $A$.
  5. Поток 1 просыпается и выполняет CAS(address, A, NewValue).
  6. Значение в ячейке равно $A$, CAS завершается успешным возвратом true!
Время      Поток 1            Поток 2               Ячейка V
  │           │                  │                     │
 t1    Читает V (видит A)        │                     A
 t2      (засыпает)              │                     │
 t3           │            Записывает B                B
 t4           │            Записывает A                A
 t5    Просыпается               │                     │
 t6    CAS(A, C) -> УСПЕХ!       │                     C (ABA произошло!)

Почему ABA опасна даже при наличии сборщика мусора (GC)?

Распространённый миф гласит: «В Java сборщик мусора исключает проблему ABA, так как адреса памяти не переиспользуются, пока жива ссылка». Это заблуждение! Проблема ABA актуальна в Java в двух случаях:

  1. Переиспользование объектов (Object Pooling / Node Reuse): если приложение в целях снижения давления на GC переиспользует узлы структур (например, пул буферов в Netty или пулы соединений).
  2. Семантическое состояние узла: объект в памяти остаётся тем же самым по ссылке, но его внутреннее состояние изменилось (например, флаг node.isDeleted успел переключиться из false в true и обратно).

Решение: Версионирование через AtomicStampedReference

// Хранит объект + монотонно возрастающий номер ревизии (stamp)
AtomicStampedReference<Node> head = new AtomicStampedReference<>(initialNode, 0);

int[] stampHolder = new int[1];
Node current = head.get(stampHolder);
int currentStamp = stampHolder[0];

// Обновление пройдёт только если совпадает И ссылка, И номер версии
boolean success = head.compareAndSet(current, newHead, currentStamp, currentStamp + 1);

Деградация шины: Cache Bouncing и Live-Lock под высокой нагрузкой

При одновременной атаке на одну и ту же CAS-переменную со стороны сотен потоков на многопроцессорных NUMA-серверах возникает явление Cache Bouncing (Cache Line Ping-Pong):

+------------+       QPI / UPI Interconnect Bus       +------------+
| CPU Node 0 | <====================================> | CPU Node 1 |
| Core 1..64 |         Шторм сообщений Invalidate      | Core 1..64 |
+------------+                                        +------------+
      │                                                     │
      v                                                     v
[ L1/L2 Cache ] <------ [ Кеш-линия переменной ] ------> [ L1/L2 Cache ]
 (Инвалидирован)                                         (Инвалидирован)
  1. Каждая успешная или неуспешная попытка LOCK CMPXCHG генерирует широковещательный сигнал Invalidate по межпроцессорной шине (Intel UPI / AMD Infinity Fabric).
  2. Кеш-линия непрерывно сбрасывается из локальных L1/L2 кешей ядер одного сокета и передаётся по медленной системной шине в другой сокет.
  3. Полоса пропускания шины памяти оказывается на 100% забита когерентными сообщениями, парализуя работу соседних потоков приложения.
  4. Возникает Live-Lock: ядра процессора загружены на 100%, но ни один поток не может завершить свой CAS-цикл из-за постоянных коллизий.

Архитектурное решение: переход на шардирование состояния (Striped / Partitioned structures) — использование LongAdder или ConcurrentHashMap вместо одиночных CAS-переменных.

Ослабленные CAS-операции: weakCompareAndSet

В Java интерфейс VarHandle и Atomic-классы предоставляют методы:

  • compareAndSet(): полноценный двунаправленный барьер (Full Fence: StoreLoad + Acquire + Release).
  • weakCompareAndSet(): ослабленная версия.

Особенности weakCompareAndSet:

  1. Ложные сбои (Spurious Failures): может вернуть false, даже если текущее значение ячейки в точности равно ожидаемому (типично для архитектур ARM/LL-SC из-за прерываний контекста).
  2. Ослабленный порядок памяти: не накладывает строгих барьеров на соседние операции, позволяя процессору агрессивно переупорядочивать инструкции.
  3. Область применения: идеален внутри циклов while (!weakCompareAndSet(...)), где ложный сбой просто приведёт к следующей итерации, но сэкономит дорогостоящие такты процессора на барьерах памяти.

🎯 Шпаргалка для интервью

1. 30-секундный эссенс (Elevator Pitch)

CAS (Compare-And-Swap) — аппаратная атомарная инструкция процессора (LOCK CMPXCHG на x86, LDXR/STXR на ARM), позволяющая без блокировок ядра ОС проверить и обновить ячейку памяти в один шаг. Она лежит в основе Lock-Free структур данных и пакета java.util.concurrent. CAS реализует оптимистичную конкуренцию через циклы повторных попыток. При умеренной конкуренции CAS быстрее synchronized, но при экстремальной конкуренции приводит к шторму инвалидации кеш-линий (Cache Bouncing) и 100% утилизации CPU, требуя шардирования (LongAdder).

2. 4 каверзных вопроса с глубокими ответами

Вопрос 1: Почему метод weakCompareAndSet() может вернуть false, даже если значение в памяти совпадает с ожидаемым?

Ответ: Метод weakCompareAndSet специфицирован для поддержки RISC-архитектур (ARM, PowerPC), использующих пары инструкций LL/SC (Load-Linked / Store-Conditional). В таких процессорах, если между чтением LL и записью SC происходит любое системное событие ядра (аппаратное прерывание, переключение контекста ОС или даже запись в соседний адрес той же кеш-линии), аппаратный флаг эксклюзивности сбрасывается. Инструкция SC завершается сбоем, и Java-метод возвращает false, несмотря на фактическое равенство значений. Это сделано намеренно для исключения дорогостоящих восстановительных циклов внутри JVM.

Вопрос 2: Какую именно проблему решает инструкция Thread.onSpinWait() внутри процессорного конвейера?

Ответ: При выполнении плотного спин-цикла процессор считает его обычным циклом и агрессивно спекулятивно исполняет инструкции вперёд (Branch Prediction). Когда условие выхода из цикла наконец срабатывает (другой поток завершил CAS), процессору приходится аварийно очищать глубокий конвейер команд (Pipeline Clear / Flushed Pipeline), что вызывает задержку в 30-50 тактов. Инструкция Thread.onSpinWait() транслируется в ассемблерную команду PAUSE, которая вставляет микропаузу в конвейер, предотвращает ошибочные спекулятивные загрузки, исключает штраф сброса конвейера и снижает энергопотребление ядра.

Вопрос 3: Может ли ABA-проблема разрушить логику приложения в Java, если адреса памяти не очищаются сборщиком мусора до тех пор, пока есть ссылки?

Ответ: Да, абсолютно. Сборщик мусора защищает от чтения некорректной сырой памяти (Dangling Pointers), но не защищает от смыслового изменения состояния:

  1. Если приложение использует Object Pooling (пул переиспользуемых объектов для снижения нагрузки на GC), объект может быть возвращён в пул и повторно выдан с тем же адресом в памяти, но уже в совершенно ином бизнес-контексте.
  2. В алгоритмах на графах и узловых структурах: узел $A$ может сохранить тот же адрес и даже то же значение поля value, но его указатели next/prev уже могут быть перелинкованы параллельным потоком в другую цепочку.

Вопрос 4: В каком сценарии производительность CAS-алгоритма падает ниже обычного тяжеловесного synchronized?

Ответ: При сверхвысокой конкуренции на запись сотен потоков за одну переменную (High Contention Write Storm). В таком сценарии:

  • Потоки на CAS непрерывно сбоят, крутясь в бесконечном цикле и утилизируя 100% всех ядер процессора.
  • Протокол когерентности кешей (MESI) непрерывно пересылает сигналы Invalidation по системной шине, вызывая деградацию шины (Bus Saturation).
  • В то же время synchronized (после адаптивного спиннинга) переводит конкурирующие потоки в состояние BLOCKED и паркует их в ОС. Заснувшие потоки не потребляют CPU и не генерируют трафик на шине памяти, позволяя одному активному потоку беспрепятственно выполнять работу.

3. Типичные ошибки и Red Flags

❌ “CAS блокирует ядро процессора навсегда, пока не запишет данные.”
Правильно: CAS — это мгновенная атомарная инструкция, исполняющаяся за единицы-десятки наносекунд. Она блокирует только доступ к конкретной кеш-линии на микроуровне контроллера памяти на время исполнения одной команды.

❌ “CAS-алгоритмы всегда Wait-Free.”
Правильно: Стандартные CAS-алгоритмы являются Lock-Free, но не Wait-Free. Отдельный неудачливый поток может теоретически голодать бесконечно (Starvation), если другие потоки непрерывно успевают совершить CAS раньше него.

❌ “CAS не создаёт барьеров памяти.”
Правильно: Стандартный вызов compareAndSet в Java выставляет полный двунаправленный барьер памяти (Full Fence / StoreLoad), что делает его достаточно дорогостоящей операцией по сравнению с обычной записью.

4. Связанные вопросы