Что делает Compare And Set?

Compare And Set (CAS)

Compare And Set (CAS) — это основная операция для реализации non-blocking синхронизации в многопоточных приложениях на Java. CAS позволяет безопасно обновлять значение переменной без использования блокирующих механизмов (synchronized, Lock), что делает её критически важной для высокопроизводительных систем.

Что делает CAS

Operation Compare And Set выполняет три действия атомарно (неделимо):

1. Сравнивает текущее значение переменной с ожидаемым значением
2. Если значения совпадают — устанавливает новое значение
3. Возвращает true если операция успешна, false если не удалась

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

Как работает CAS на уровне кода

В Java CAS реализована через класс AtomicReference, AtomicInteger, AtomicLong и другие atomic классы:

public class AtomicInteger {
    private volatile int value;
    
    public boolean compareAndSet(int expect, int update) {
        if (this.value == expect) {
            this.value = update;
            return true;
        }
        return false;
    }
}

Практический пример с AtomicInteger

public class CASExample {
    private AtomicInteger counter = new AtomicInteger(0);
    
    public void incrementUsingCAS() {
        int oldValue;
        int newValue;
        
        do {
            oldValue = counter.get();
            newValue = oldValue + 1;
        } while (!counter.compareAndSet(oldValue, newValue));
    }
    
    public static void main(String[] args) throws InterruptedException {
        CASExample example = new CASExample();
        
        Thread t1 = new Thread(() -> {
            for (int i = 0; i < 1000; i++) {
                example.incrementUsingCAS();
            }
        });
        
        Thread t2 = new Thread(() -> {
            for (int i = 0; i < 1000; i++) {
                example.incrementUsingCAS();
            }
        });
        
        t1.start();
        t2.start();
        t1.join();
        t2.join();
        
        System.out.println("Counter: " + example.counter.get());
    }
}

AtomicReference и CAS

CAS работает не только с примитивными типами, но и с объектами:

public class Node {
    public int value;
    public Node next;
    
    public Node(int value) {
        this.value = value;
    }
}

public class LockFreeStack {
    private AtomicReference<Node> head = new AtomicReference<>();
    
    public void push(int value) {
        Node newNode = new Node(value);
        Node oldHead;
        
        do {
            oldHead = head.get();
            newNode.next = oldHead;
        } while (!head.compareAndSet(oldHead, newNode));
    }
    
    public Integer pop() {
        Node oldHead;
        Node newHead;
        
        do {
            oldHead = head.get();
            if (oldHead == null) {
                return null;
            }
            newHead = oldHead.next;
        } while (!head.compareAndSet(oldHead, newHead));
        
        return oldHead.value;
    }
}

Преимущества CAS

• Без блокировок — нет риска deadlock
• Высокая производительность — нет overhead синхронизации
• Масштабируемость — лучше работает на многоядерных системах
• Отсутствие конвоирования — потоки не ждут друг друга

Недостатки и вызовы

• ABA проблема — переменная может измениться с A на B и обратно на A
• Busy-waiting — поток крутится в цикле, требует CPU
• Сложность — код с CAS трудно понимать и тестировать

ABA проблема и решение

Это критическая проблема в CAS алгоритмах. Решение — использовать AtomicStampedReference с версионированием:

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

public void push(Node newNode) {
    int[] stamp = new int[1];
    Node oldHead;
    
    do {
        oldHead = head.get(stamp);
        newNode.next = oldHead;
    } while (!head.compareAndSet(oldHead, newNode, stamp[0], stamp[0] + 1));
}

Где используется CAS

• Concurrent Map — ConcurrentHashMap использует CAS для обновления элементов
• Lock-free стеки и очереди — реализация без блокировок
• Atomic переменные — java.util.concurrent.atomic пакет
• Java Memory Model — основа для volatile гарантий

Вывод

Compare And Set — это фундаментальная операция для lock-free программирования на Java. Она позволяет создавать высокопроизводительные concurrent структуры данных без явной синхронизации. Однако использование CAS требует глубокого понимания многопоточности, race conditions и потенциальных проблем вроде ABA.