Java Interview Questions

Главная / Все ответы / Многопоточность

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

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

Представьте банкомат: 4. Если да — снимает 200, новый баланс 800 5. Если нет (кто-то уже снял) — отменяет операцию, нужно попробовать снова

Russian Многопоточность Исходный Markdown
Версии по языкам: English Russian Ukrainian

Junior уровень

Базовое понимание

CAS (Compare-And-Swap) — это атомарная инструкция процессора, которая позволяет обновить значение только если оно не изменилось с момента чтения. Это основа lock-free алгоритмов.

Простая аналогия

Представьте банкомат:

  1. Вы смотрите баланс: 1000 руб
  2. Вы хотите снять 200 руб (ожидаете что будет 800)
  3. Банкомат проверяет: “баланс всё ещё 1000?”
  4. Если да — снимает 200, новый баланс 800
  5. Если нет (кто-то уже снял) — отменяет операцию, нужно попробовать снова

Ключевое отличие от synchronized: CAS — это optimistic подход (попробуй, если не вышло — повтори). synchronized — pessimistic подход (заблокируй и делай, никто не помешает).

Как работает CAS

// CAS принимает 3 параметра:
// 1. Адрес в памяти
// 2. Ожидаемое значение
// 3. Новое значение

boolean CAS(address, expectedValue, newValue) {
    if (memory[address] == expectedValue) {
        memory[address] = newValue;
        return true;  // Успех!
    }
    return false; // Не удалось — значение изменилось
}

Пример с AtomicInteger

AtomicInteger counter = new AtomicInteger(0);

counter.incrementAndGet(); // Внутри:
// 1. Прочитать текущее значение (current = 0)
// 2. Вычислить новое (next = 1)
// 3. CAS: если value == 0, установить 1
//    Если CAS не удался — повторить с шага 1

Спин-цикл (Spin-loop)

public final int incrementAndGet() {
    for (;;) { // Бесконечный цикл
        int current = get();        // Прочитать
        int next = current + 1;     // Вычислить
        if (compareAndSet(current, next)) { // CAS
            return next;            // Успех!
        }
        // CAS не удался — кто-то другой обновил значение
        // Идём на следующий круг цикла
    }
}

Когда CAS быстрее блокировок?

Сценарий CAS synchronized
Низкая конкуренция Быстрее (нет блокировки) Медленнее (захват/освобождение)
Средняя конкуренция Быстрее Средне
Высокая конкуренция Медленнее (бесконечные циклы) Быстрее (потоки парковались)

Middle уровень

Алгоритм на уровне железа

На x86 архитектуре CAS реализуется через инструкцию LOCK CMPXCHG:

; rax = expected value
; rcx = new value
; [memory] = actual value in memory

lock cmpxchg [memory], rcx
; Если [memory] == rax:
;   [memory] = rcx      ← Записываем новое значение
;   ZF = 1              ← Флаг успеха
; Иначе:
;   rax = [memory]      ← Загружаем актуальное значение
;   ZF = 0              ← Флаг неудачи

Префикс lock блокирует шину памяти на время операции — другие ядра не могут получить доступ к этой ячейке.

CAS в Java: Unsafe и VarHandle

До Java 9: sun.misc.Unsafe

До Java 9: sun.misc.Unsafe (прямой доступ к памяти, опасен) Java 9+: VarHandle (безопасная замена Unsafe, JEP 193) Примечание: Unsafe всё ещё доступен в Java 9+ через --add-opens, но не рекомендуется.

// Прямой доступ к памяти (не рекомендуется)
Unsafe unsafe = ...;
long offset = ...; // Смещение поля в памяти

int current;
do {
    current = unsafe.getIntVolatile(obj, offset);
} while (!unsafe.compareAndSwapInt(obj, offset, current, current + 1));

Java 9+: VarHandle

// Типизированный и безопасный API
private static final VarHandle VALUE;
static {
    MethodHandles.Lookup l = MethodHandles.lookup();
    VALUE = l.findVarHandle(MyClass.class, "value", int.class);
}

int current;
do {
    current = (int) VALUE.getVolatile(this);
} while (!VALUE.compareAndSet(this, current, current + 1));

Lock-free vs Wait-free

На собеседовании важно различать:

Это иерархия progress guarantee (гарантий прогресса):

  • Wait-free (сильнейшая): КАЖДЫЙ поток завершит операцию за конечное число шагов
  • Lock-free (средняя): ХОТЯ БЫ ОДИН поток завершит операцию за конечное число шагов
  • Obstruction-free (слабейшая): поток завершит, если все остальные приостановлены

Wait-free → Lock-free → Obstruction-free: каждая следующая слабее предыдущей.

Термин Гарантия Пример
Lock-free Хотя бы один поток завершит операцию за конечное время AtomicInteger
Wait-free Каждый поток завершит за конечное число шагов LongAdder.add()
Obstruction-free Поток завершится, если другие не мешают Некоторые STM реализации

STM (Software Transactional Memory) — программная транзакционная память: операции выполняются в транзакции, потом атомарно коммитятся. Альтернативный подход к lock-free программированию.

Exponential Back-off

При высокой конкуренции простой спин-цикл тратит CPU. Решение — паузы:

public int incrementWithBackoff() {
    int backoff = 1;
    for (;;) {
        int current = get();
        int next = current + 1;
        if (compareAndSet(current, next)) {
            return next;
        }
        // CAS не удался — делаем паузу
        Thread.onSpinWait(); // Подсказка процессору

        // `Thread.onSpinWait()` — hint JVM процессору: «я в spin-цикле, можешь оптимизировать». На x86 это PAUSE-инструкция, которая снижает энергопотребление и улучшает производительность spin-цикла.
        Thread.sleep(ThreadLocalRandom.current().nextInt(0, backoff));
        backoff = Math.min(backoff * 2, MAX_BACKOFF); // Экспоненциальный рост
    }
}

ABA Проблема

Время  Поток 1         Поток 2         Стек (head)
──────────────────────────────────────────────────
t1     читает A                        A → B → C
t2                   CAS(A, B)         B → C
t3                   CAS(B, A)         A → C (новое значение!)
t4     CAS(A, D) → УСПЕХ!
       Но стек изменился! B и C потеряны!

Решение: AtomicStampedReference

// Хранит значение + номер версии
AtomicStampedReference<String> ref = new AtomicStampedReference<>("A", 0);

int[] stampHolder = new int[1];
String value = ref.get(stampHolder);
int stamp = stampHolder[0];

// CAS только если и значение И версия совпадают
ref.compareAndSet("A", "D", stamp, stamp + 1);

Когда CAS НЕ подходит

  1. Составные операции: нужно атомарно обновить два поля — CAS работает с одним полем
  2. High contention (100+ потоков): CAS-цикл тратит CPU впустую, лучше LongAdder или Lock
  3. Долгие вычисления: если между read и CAS проходят миллисекунды — CAS будет постоянно fail-ить
  4. ABA проблема: значение изменилось A→B→A, CAS «не заметит» — нужен AtomicStampedReference

Senior уровень

Under the Hood: Memory Ordering

CAS обеспечивает полный memory barrier (StoreLoad):

До CAS:    Все записи гарантированно завершены
CAS:       Атомарное обновление
После CAS: Все чтения видят актуальные данные

На разных архитектурах:

Архитектура CAS реализация Barriers
x86 lock cmpxchg Full barrier (x86 сильно упорядочен)
ARM ldxr/stxr loop Требует dmb инструкции
RISC-V lr.w/sc.w loop Требует fence

Спин-цикл и CPU Saturation

При очень высокой конкуренции потоки могут “крутиться” вечно:

// Проблема: 100 потоков, 1 CAS-переменная
for (;;) {
    int current = get();
    int next = current + 1;
    if (compareAndSet(current, next)) // Все 100 потоков постоянно фейлятся
        return next;
    // CPU на 100%, но прогресса нет!
}

Решения:

  1. Exponential Back-off — пауза между попытками
  2. LongAdder — распределение по ячейкам
  3. Переход к блокировке — если contention слишком высокий

Производительность: CAS vs Mutex

Метрика CAS Mutex (synchronized)
Latency (uncontended) ~5-10 ns ~10-20 ns
Latency (contended) ~100+ ns (spin) ~1000+ ns (park)
CPU usage (contended) 100% (spin-loop) ~0% (parked)
Throughput (low contention) Выше Ниже
Throughput (high contention) Ниже Выше

Критический момент: При сверхвысокой нагрузке мьютекс может быть выгоднее, так как он “паркует” потоки, а не заставляет сжигать CPU.

Реализация AtomicLong на 32-битных системах

// На 32-битной JVM запись long не атомарна!
// long = 64 бита, записывается в два этапа по 32 бита

// AtomicLong гарантирует атомарность через:
// 1. Инструкцию CMPXCHG8B (x86)
// 2. Или внутреннюю блокировку (на старых CPU)

Bus Traffic и Cache Coherence

На многопроцессорных системах частые CAS вызывают:

  1. Cache Line Invalidation — каждое CAS посылает Invalidate всем ядрам
  2. Bus Traffic — интенсивный обмен по шине межпроцессорной связи
  3. Memory Bandwidth Saturation — шина забита, обычные операции тормозят

Решение: Сегментированные структуры (как ConcurrentHashMap) или LongAdder.

Диагностика

JMC (Java Mission Control)

java -XX:StartFlightRecording=filename=rec.jfr MyApp

События:

  • jdk.ExecutionSample — показывает, где потоки тратят время
  • Если много в compareAndSet → contention

-XX:+PrintAssembly

java -XX:+PrintAssembly -XX:+UnlockDiagnosticVMOptions

Ищите:

lock cmpxchg dword ptr [rax], rcx  # ← Это CAS

Определение contention

// Программная оценка contention
AtomicLong counter = new AtomicLong(0);
long start = System.nanoTime();
for (int i = 0; i < 1_000_000; i++) {
    counter.incrementAndGet();
}
long elapsed = System.nanoTime() - start;
System.out.println("Среднее время: " + (elapsed / 1_000_000) + " ns");
// Много > 10 ns → contention

Best Practices

  1. CAS для простых операций — increment, set, get
  2. Back-off при contention — Thread.onSpinWait() для подсказки CPU
  3. LongAdder для счётчиков — при высокой конкуренции
  4. AtomicStampedReference — когда возможна ABA проблема
  5. Не используйте CAS для долгих операций — переходите к блокировкам
  6. Мониторьте CAS failures — через JFR или профилирование
  7. Избегайте CAS для нескольких полей — используйте synchronized

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

Обязательно знать:

  • CAS = Compare-And-Swap: атомарно сравнивает значение с ожидаемым и записывает новое, если совпало
  • На x86: lock cmpxchg (префикс lock блокирует шину памяти); на ARM: ldxr/stxr; на RISC-V: lr.w/sc.w
  • CAS обеспечивает полный memory barrier (StoreLoad) — все записи до CAS завершены, все чтения после CAS актуальны
  • CAS — это optimistic подход (попробуй/повтори), synchronized — pessimistic (заблокируй и делай)
  • Lock-free (AtomicInteger) vs Wait-free (LongAdder): lock-free = хотя бы один поток завершит; wait-free = каждый поток завершит
  • ABA проблема: значение вернулось A→B→A, CAS не заметит; решение — AtomicStampedReference (значение + версия)
  • При высокой конкуренции CAS-цикл тратит CPU (100%); решение — exponential back-off или переход к LongAdder/Lock

Частые уточняющие вопросы:

  • Когда CAS быстрее synchronized? — При низкой/средней конкуренции (нет overhead на блокировку/парковку)
  • Когда synchronized быстрее CAS? — При высокой конкуренции (100+ потоков): CAS крутится и жжёт CPU, mutex паркует потоки
  • Что делает Thread.onSpinWait()? — Hint JVM процессору «я в spin-цикле»; на x86 = PAUSE инструкция, снижает энергопотребление
  • Чем CAS отличается от volatile? — volatile = только видимость; CAS = видимость + атомарная запись (compare-and-swap)

Красные флаги (НЕ говорить):

  • “CAS всегда быстрее synchronized” — нет, при высокой конкуренции mutex эффективнее
  • “CAS не имеет проблем с памятью” — нет, CAS ставит полный memory barrier, что дорого
  • “ABA проблема — это баг Java” — нет, это фундаментальная проблема CAS-алгоритмов на любом языке
  • “Wait-free и lock-free — одно и то же” — нет, wait-free сильнее: КАЖДЫЙ поток завершит, lock-free — хотя бы ОДИН

Связанные темы:

  • [[8. Что такое Atomic классы]] — все Atomic-классы построены на CAS
  • [[1. В чём разница между synchronized и volatile]] — CAS vs synchronized подходы
  • [[3. Что такое visibility problem]] — CAS обеспечивает полный memory barrier
  • [[7. Что такое reentrant lock]] — AQS использует CAS для захвата state