🧵 Розділ 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. Пов’язані теми