Какие знаешь проблемы CAS?

Проблемы CAS (Compare-And-Swap)

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

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

// Псевдокод
boolean CAS(Object obj, long offset, Object expectedValue, Object newValue) {
    if (memory[offset] == expectedValue) {
        memory[offset] = newValue;
        return true;
    }
    return false;
}

В Java реализуется через AtomicInteger, AtomicReference и т.д.:

AtomicInteger counter = new AtomicInteger(0);
boolean success = counter.compareAndSet(0, 1); // Если счётчик = 0, установить 1

1. ABA Problem (Проблема ABA)

Это классическая проблема CAS. Если значение изменилось A → B → A, CAS подумает, что ничего не произошло, хотя на самом деле было изменение.

AtomicInteger value = new AtomicInteger(10); // A = 10

// Поток 1: читает значение
int readValue = value.get(); // readValue = 10

// Поток 2: A(10) -> B(20) -> A(10)
value.set(20);
value.set(10); // Вернули в исходное состояние

// Поток 1: пытается CAS
value.compareAndSet(10, 30); // Успех! Но состояние объекта могло измениться

Классический пример с очередью (stack):

class LockFreeStack {
    static class Node {
        int value;
        Node next;
        Node(int v, Node n) { value = v; next = n; }
    }
    
    AtomicReference<Node> top = new AtomicReference<>();
    
    void pop() {
        while (true) {
            Node oldTop = top.get();
            if (oldTop == null) return;
            
            Node newTop = oldTop.next;
            // Проблема: между get() и compareAndSet()
            // другой поток мог удалить oldTop.next, вернуть его в pool,
            // и переиспользовать его! ABA!
            if (top.compareAndSet(oldTop, newTop)) {
                return;
            }
        }
    }
}

Решение: использовать AtomicStampedReference с версионированием:

AtomicStampedReference<Node> top = new AtomicStampedReference<>(null, 0);

void pop() {
    while (true) {
        int[] stamp = new int[1];
        Node oldTop = top.get(stamp);
        if (oldTop == null) return;
        
        Node newTop = oldTop.next;
        // Версия меняется, даже если значение вернулось в исходное состояние
        if (top.compareAndSet(oldTop, newTop, stamp[0], stamp[0] + 1)) {
            return;
        }
    }
}

Ор использовать AtomicMarkableReference (версия ABA с boolean флагом):

AtomicMarkableReference<Node> top = new AtomicMarkableReference<>(null, false);

2. Contention (Высокое соперничество)

CAS работает хорошо при низком соперничестве. Когда много потоков одновременно пытаются изменить одно значение, CAS превращается в spinlock (вращение в цикле).

AtomicInteger counter = new AtomicInteger(0);

// Много потоков пытаются увеличить счётчик
ExecutorService executor = Executors.newFixedThreadPool(100);
for (int i = 0; i < 100000; i++) {
    executor.submit(() -> {
        while (true) {
            int current = counter.get();
            if (counter.compareAndSet(current, current + 1)) {
                break; // Успех
            }
            // Иначе — повторить (spinlock)
        }
    });
}

Проблемы:

• CPU жрет — активное ожидание в цикле
• Cache invalidation — постоянная синхронизация кэшей между ядрами
• Performance cliff — при достижении критического количества потоков производительность резко падает

Решение: использовать LongAdder вместо AtomicLong при высоком соперничестве:

// Плохо при высоком соперничестве
AtomicLong counter = new AtomicLong(0);
counter.incrementAndGet();

// Хорошо: распределяет нагрузку между ячейками
LongAdder counter = new LongAdder();
counter.increment();
long result = counter.sum();

3. Несо-транзакционность (Multiple CAS Problem)

CAS работает атомарно только для одного поля. Если нужно изменить несколько полей атомарно, CAS недостаточно.

class Transfer {
    AtomicLong fromAccount = new AtomicLong(1000);
    AtomicLong toAccount = new AtomicLong(0);
    
    void transfer(long amount) {
        // CAS для fromAccount
        while (!fromAccount.compareAndSet(fromAccount.get(), fromAccount.get() - amount)) {}
        
        // Между двумя CAS другой поток может вмешаться!
        // Деньги исчезнут!
        
        // CAS для toAccount
        while (!toAccount.compareAndSet(toAccount.get(), toAccount.get() + amount)) {}
    }
}

Решение: использовать ReentrantLock для нескольких операций:

class Transfer {
    private ReentrantLock lock = new ReentrantLock();
    long fromAccount = 1000;
    long toAccount = 0;
    
    void transfer(long amount) {
        lock.lock();
        try {
            fromAccount -= amount;
            toAccount += amount;
        } finally {
            lock.unlock();
        }
    }
}

4. Memory Visibility Issues (Видимость памяти)

Поддержание корректной видимости памяти при использовании CAS сложно. Если неправильно использовать happen-before отношения, можно получить data race.

class DataHolder {
    AtomicReference<Data> data = new AtomicReference<>();
    int metadata; // Обычное поле!
    
    void update() {
        Data newData = new Data();
        data.set(newData); // CAS видит новые данные
        metadata = 42; // Но это может быть невидимо другим потокам!
    }
}

Решение: убедиться, что все полезные данные либо в Atomic переменной, либо правильно синхронизированы.

5. Garbage Collection Pressure

Lock-free код часто создает больше временных объектов, что увеличивает нагрузку на GC.

// Lock-free подход: много временных объектов
while (!casSuccessful) {
    int current = value.get();
    int newValue = compute(current); // Новый объект в памяти
    casSuccessful = value.compareAndSet(current, newValue);
}

6. Сложность понимания и отладки

Lock-free код намного сложнее для понимания и отладки. Race conditions могут проявляться редко и непредсказуемо.

Когда использовать CAS

✅ Используй:

• Много читателей, мало писателей
• Низкое соперничество
• Высокопроизводительные системы
• AtomicInteger, AtomicReference для простых случаев
• LongAdder для счётчиков при высоком соперничестве

❌ НЕ используй:

• Сложные операции с несколькими полями
• Высокое соперничество (используй блокировки)
• Когда производительность не критична
• Если код не будет поддерживаться

CAS — мощный инструмент, но требует глубокого понимания многопоточности.