Краткий ответ

Lock-free гарантирует, что система в целом будет продвигаться: за конечное число шагов хотя бы один поток завершит операцию. Отдельный поток при этом может бесконечно проигрывать гонку CAS и голодать. Wait-free сильнее: каждая операция каждого потока завершается за заранее ограниченное число шагов, независимо от конкуренции.

Исторический контекст

Эти свойства появились как критерии прогресса для алгоритмов, которым нужно работать без взаимных блокировок. Блокировки могут привести к взаимной блокировке, приоритетной инверсии или длительному ожиданию владельца, поэтому для некоторых задач используют атомарные операции вроде CAS.

Однако отсутствие явного lock само по себе не означает сильную гарантию прогресса. Важен анализ всего алгоритма: сколько раз поток может повторять попытку и зависит ли его завершение от успеха других потоков.

Постановка проблемы

Типичный CAS-цикл читает значение, вычисляет новый результат и пытается заменить старое значение. Если другой поток успел изменить поле, CAS завершается неудачей, и первый поток повторяет попытку.

При высокой конкуренции такой цикл обычно продолжает продвигать систему, потому что успешный CAS какого-либо потока означает прогресс. Но конкретный поток может постоянно проигрывать более быстрым или многочисленным конкурентам. Это риск непредсказуемой задержки и голодания.

Подробное решение

Упрощённая форма lock-free операции выглядит так:

import java.util.concurrent.atomic.AtomicInteger;

class Counter {
    private final AtomicInteger value = new AtomicInteger();

    int increment() {
        int observed;
        do {
            observed = value.get();
        } while (!value.compareAndSet(observed, observed + 1));
        return observed + 1;
    }
}

Если CAS не удался, это означает, что значение уже изменил другой поток. При корректной реализации такой успешный конкурентный CAS считается прогрессом системы, поэтому алгоритм является кандидатом на lock-free-реализацию. Но число повторов для конкретного вызова не ограничено.

Wait-free-алгоритм должен иметь верхнюю границу числа собственных шагов. Простого повторения CAS для этого недостаточно: при постоянных конфликтах цикл может выполняться неограниченно долго. Для wait-free-проектирования применяют, например, заранее ограниченное число попыток, помощь другим операциям или структуры, в которых каждый поток гарантированно получает обслуживание.

Важно различать прогресс системы и гарантию задержки отдельного запроса. Lock-free подходит, когда важна общая пропускная способность и допустимы редкие длинные задержки. Wait-free нужен, когда требуется предсказуемое время завершения, например в системах с жёсткими требованиями к latency.

Термины lock-free и wait-free не гарантируют отсутствия всех проблем. Они не устраняют логические ошибки, ABA-проблему, переполнение счётчиков или некорректную публикацию связанных данных. Кроме того, планировщик, остановка потока или паузы сборщика мусора могут повлиять на фактическое время ответа.

Ситуация из практики

Сервису требуется выдавать уникальные последовательные номера запросов. Вариант с synchronized прост и обычно легче проверяется, но конкурирующие потоки могут блокироваться, а задержка зависит от владельца монитора. Вариант с AtomicLong устраняет явную блокировку и обычно даёт хорошую пропускную способность, но его CAS-цикл не становится wait-free.

LongAdder здесь не подходит: он оптимизирован для конкурентного накопления статистики, а не для выдачи каждому вызову уникального следующего номера. Разбиение счётчика на независимые диапазоны может снизить конкуренцию, но усложняет порядок номеров и восстановление после сбоев.

Для обычного сервиса выбран AtomicLong: нужна уникальность, а не жёсткая граница задержки каждой операции. Если же система требует гарантированного верхнего предела времени ответа, следует не объявлять CAS-цикл wait-free без доказательства, а выбрать специально спроектированный bounded-протокол либо изменить требование к глобальной последовательности.

Что кандидаты часто упускают

Может ли lock-free операция голодать?

Да. Lock-free гарантирует прогресс хотя бы одного потока, но не справедливость. Один поток может многократно читать устаревшее значение и каждый раз проигрывать CAS. Если отсутствие голодания важно, нужны дополнительные механизмы справедливости или другой алгоритм; сама атомарность этого не обеспечивает.

Является ли любой CAS-цикл wait-free, если значение в итоге меняется?

Нет. Изменение значения кем-то другим доказывает прогресс системы, но не ограничивает число неудачных попыток конкретного потока. Для wait-free необходимо доказать конечную верхнюю границу шагов каждой операции при любом расписании потоков.

Означает ли lock-free отсутствие блокировок в реализации Java?

Не обязательно. Это свойство алгоритма и его прогресса, а не только отсутствие слова synchronized. Использование атомарного API часто позволяет построить lock-free-алгоритм, но нужно учитывать реализацию конкретной операции, возможные внутренние механизмы платформы и весь окружающий код. Если операция вызывает блокирующий компонент, общая процедура уже не получает чистую lock-free-гарантию.