---

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 процесору: «я в спін-циклі, можеш оптимізувати». На x86 це PAUSE-інструкція, яка знижує енергоспоживання та покращує продуктивність спін-циклу.
        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 буде постійно фейлитися
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 процесору «я в спін-циклі»; на 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