Что такое lock-free алгоритмы в многопоточном программировании?

«Что такое lock-free алгоритмы в многопоточном программировании?» — вопрос из категории Алгоритмы и структуры данных, который задают на 10% собеседований Java Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Ответ

Lock-free алгоритмы — это класс алгоритмов для безопасного доступа к общим данным из нескольких потоков, которые гарантируют прогресс системы в целом: если какой-либо поток будет приостановлен (например, из-за вытеснения планировщиком), это не заблокирует выполнение других потоков. Они достигают этого без использования традиционных примитивов блокировки (мьютексов, synchronized-блоков).

Ключевые характеристики:

  • Отсутствие взаимных блокировок (deadlock): Нет захвата блокировок, поэтому deadlock невозможен.
  • Устойчивость к приостановке потока (starvation resistance): Задержка одного потока не останавливает всю систему.
  • Высокая производительность при contention: В условиях высокой конкуренции за ресурсы часто работают быстрее lock- based подходов, так как избегают дорогостоящих переключений контекста и ожидания в очереди.

Основной механизм: Lock-free алгоритмы обычно строятся на атомарных операциях сравнения с обменом (Compare-And-Swap — CAS), предоставляемых процессором (например, java.util.concurrent.atomic).

Пример: Lock-free стек на основе CAS (псевдокод):

import java.util.concurrent.atomic.AtomicReference;

public class LockFreeStack<T> {
    private static class Node<T> {
        final T value;
        Node<T> next;
        Node(T value) { this.value = value; }
    }

    private final AtomicReference<Node<T>> top = new AtomicReference<>();

    public void push(T item) {
        Node<T> newHead = new Node<>(item);
        Node<T> oldHead;
        do {
            oldHead = top.get();          // 1. Читаем текущую вершину
            newHead.next = oldHead;       // 2. Новый узел указывает на старую вершину
        } while (!top.compareAndSet(oldHead, newHead)); // 3. Пытаемся атомарно заменить вершину
        // Если с момента шага 1 вершина не изменилась, CAS успешен.
        // Если изменилась (другой поток добавил элемент), цикл повторяется.
    }

    public T pop() {
        Node<T> oldHead;
        Node<T> newHead;
        do {
            oldHead = top.get();          // 1. Читаем текущую вершину
            if (oldHead == null) return null; // Стек пуст
            newHead = oldHead.next;       // 2. Определяем новую вершину
        } while (!top.compareAndSet(oldHead, newHead)); // 3. Пытаемся атомарно удалить вершину
        return oldHead.value;
    }
}

Важные понятия и ограничения:

  • Lock-free vs Wait-free: Wait-free алгоритмы — более строгий подкласс, гарантирующий прогресс для каждого потока за ограниченное число шагов. Все wait-free алгоритмы lock-free, но не наоборот.
  • Проблема ABA: Классическая проблема при использовании CAS: значение переменной меняется с A на B и обратно на A. Простой CAS не заметит изменения. Решается с помощью меток версий (version stamps) или указателей (Pointer).
  • Сложность: Разработка корректных lock-free структур данных значительно сложнее, чем блокирующих.

Примеры в Java: Классы ConcurrentLinkedQueue, AtomicInteger, AtomicReference реализуют lock-free логику.