Что такое Compare-and-swap?

Compare-and-Swap (CAS): фундамент неблокирующей синхронизации

Compare-and-Swap (или CAS, также известный как Compare-and-Exchange) — это низкоуровневая атомарная операция, предоставляемая современными процессорами. Это фундамент для построения потокобезопасного кода без использования блокирующих механизмов (mutex, synchronized).

Что такое CAS на концептуальном уровне

CAS — это одна неделимая операция, которая:

1. Сравнивает текущее значение переменной с ожидаемым значением
2. Если они совпадают — заменяет текущее значение на новое значение
3. Если они не совпадают — ничего не делает
4. Возвращает результат операции (успех/неудача)

Вся операция выполняется атомарно — без возможности другого потока вмешаться в середину операции.

Математическое определение

// Псевдокод, показывающий логику CAS
boolean compareAndSwap(AtomicReference<T> ref, T expectedValue, T newValue) {
    // Всё это происходит АТОМАРНО на уровне процессора
    if (ref.get() == expectedValue) {
        ref.set(newValue);
        return true;  // Успешно обновили
    } else {
        return false;  // Значение изменилось, операция не выполнена
    }
}

CAS в Java

В Java CAS доступен через класс Unsafe (низкоуровневый) и через Atomic переменные (рекомендуемый способ):

1. AtomicInteger

import java.util.concurrent.atomic.AtomicInteger;

public class CASExample {
    private AtomicInteger counter = new AtomicInteger(0);
    
    public void demonstrateCAS() {
        // Обычное получение значения
        int current = counter.get();  // например, 10
        
        // CAS операция: если значение всё ещё 10, то установи 11
        boolean success = counter.compareAndSet(10, 11);
        
        if (success) {
            System.out.println("Успешно обновили с 10 на 11");
        } else {
            System.out.println("Значение изменилось, попробуй снова");
        }
    }
}

2. AtomicReference для объектов

import java.util.concurrent.atomic.AtomicReference;

public class UserCache {
    private AtomicReference<User> cachedUser = new AtomicReference<>();
    
    public void updateUserIfNotChanged(User expectedUser, User newUser) {
        // CAS для объектных ссылок
        boolean updated = cachedUser.compareAndSet(expectedUser, newUser);
        
        if (!updated) {
            System.out.println("Кэш был изменён другим потоком");
        }
    }
}

Практический пример: Spin Lock

public class SpinLock {
    private AtomicReference<Thread> owner = new AtomicReference<>(null);
    
    public void lock() {
        Thread currentThread = Thread.currentThread();
        
        // "Вращаемся" пока не захватим лок
        while (!owner.compareAndSet(null, currentThread)) {
            // Активное ожидание (не очень эффективно для долгих ждений)
            Thread.yield();
        }
    }
    
    public void unlock() {
        owner.set(null);
    }
}

Реальный пример: потокобезопасный счётчик

public class CASCounter {
    private AtomicInteger count = new AtomicInteger(0);
    
    public void increment() {
        int current;
        int next;
        
        // Повторяем, пока CAS не удастся
        do {
            current = count.get();
            next = current + 1;
        } while (!count.compareAndSet(current, next));
        // CAS может не удаться, если другой поток изменит значение
    }
    
    // Внутри AtomicInteger это делается оптимизированнее
    // но логика одна и та же
}

// Сравни с synchronized версией:
public class SynchronizedCounter {
    private int count = 0;
    
    public synchronized void increment() {
        count++;  // Просто, но может быть медленнее при большой конкуренции
    }
}

Как CAS работает на уровне процессора

На современных процессорах (x86, ARM) есть инструкции:

// Для x86:
// CMPXCHG - Compare and Exchange
// Выполняется атомарно с помощью LOCK префикса

// На Java уровне через Unsafe:
private static final Unsafe unsafe = Unsafe.getUnsafe();
private static final long valueOffset;

static {
    try {
        valueOffset = unsafe.objectFieldOffset(
            AtomicInteger.class.getDeclaredField("value")
        );
    } catch (Exception e) {
        throw new Error(e);
    }
}

public final boolean compareAndSet(int expect, int update) {
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    // Это вызывает CMPXCHG на процессоре
}

CAS vs Synchronized

Когда CAS лучше (Optimistic Locking)

// ХОРОШО использовать CAS: мало конкуренции на один объект
public class LowContentionCounter {
    private AtomicInteger count = new AtomicInteger(0);
    
    public void increment() {
        count.incrementAndGet();  // Работает быстро при мало конкуренции
    }
}

// Характеристики:
// + Нет блокировки потоков
// + Нет context switching (дешевле)
// + Лучше для high throughput сценариев
// - Может быть медленнее при высокой конкуренции (много retries)

Когда Synchronized лучше (Pessimistic Locking)

// ХОРОШО использовать synchronized: высокая конкуренция
public class HighContentionCounter {
    private int count = 0;
    
    public synchronized void increment() {
        count++;  // Просто ждём, не тратим CPU на retry
    }
}

// Характеристики:
// + Простая логика
// + Лучше при высокой конкуренции (не вращаемся в цикле)
// - Дороже (context switching)
// - Может привести к deadlocks

Сложный пример: неблокирующая очередь

public class LockFreeQueue<T> {
    private static class Node<T> {
        final T value;
        AtomicReference<Node<T>> next = new AtomicReference<>();
        
        Node(T value) {
            this.value = value;
        }
    }
    
    private AtomicReference<Node<T>> head;
    private AtomicReference<Node<T>> tail;
    
    public LockFreeQueue() {
        Node<T> sentinel = new Node<>(null);
        head = new AtomicReference<>(sentinel);
        tail = new AtomicReference<>(sentinel);
    }
    
    public void enqueue(T value) {
        Node<T> newNode = new Node<>(value);
        
        while (true) {
            Node<T> lastNode = tail.get();
            Node<T> nextNode = lastNode.next.get();
            
            if (lastNode == tail.get()) {  // Double-checked locking
                if (nextNode == null) {
                    // Пытаемся добавить узел в конец
                    if (lastNode.next.compareAndSet(null, newNode)) {
                        // Успешно добавили, обновляем tail
                        tail.compareAndSet(lastNode, newNode);
                        return;
                    }
                } else {
                    // Кто-то уже добавил узел, обновляем tail и повторяем
                    tail.compareAndSet(lastNode, nextNode);
                }
            }
        }
    }
    
    public T dequeue() {
        while (true) {
            Node<T> firstNode = head.get();
            Node<T> lastNode = tail.get();
            Node<T> nextNode = firstNode.next.get();
            
            if (firstNode == head.get()) {
                if (firstNode == lastNode) {
                    if (nextNode == null) {
                        return null;  // Пуста
                    }
                    tail.compareAndSet(lastNode, nextNode);
                } else if (nextNode != null) {
                    T value = nextNode.value;
                    // Пытаемся переместить head
                    if (head.compareAndSet(firstNode, nextNode)) {
                        return value;
                    }
                }
            }
        }
    }
}

Проблемы и ограничения

1. ABA Problem

// ПРОБЛЕМА: A -> B -> A (значение вернулось!)
private AtomicReference<Node> node = new AtomicReference<>(nodeA);

// Поток 1: читает A
Node expected = node.get();  // A

// Поток 2: A -> B -> A (быстро вернулось)

// Поток 1: пытается CAS
node.compareAndSet(expected, newNode);  // успешно! но логика нарушена

// РЕШЕНИЕ: используй versioned CAS
AtomicStampedReference<Node> node = new AtomicStampedReference<>(nodeA, 0);
node.compareAndSet(expected, newNode, expectedStamp, newStamp);

2. CPU контенция

// При высокой конкуренции потоки пересчитывают друг друга
while (!atomic.compareAndSet(old, new)) {
    // МНОГО потоков здесь тратят CPU
    old = atomic.get();
}

Заключение

CAS — это основной механизм построения высокопроизводительного параллельного кода без традиционных блокировок. Используется внутри:

• AtomicInteger, AtomicLong, AtomicReference
• ConcurrentHashMap
• java.util.concurrent коллекции
• Reactive фреймворки

Примеры такие сложные не потому что CAS сложный, а потому что правильная параллельная программа всегда сложна. Но когда она нужна для производительности — CAS это мощный инструмент.