Ответ
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 логику.