Lock-free алгоритм

Lock-free алгоритм — это класс алгоритмов параллельного программирования, обеспечивающий прогресс системы в целом (системный прогресс) без использования традиционных блокировок (мьютексов, семафоров). В отличие от блокирующих алгоритмов, где приостановка одного потока может заблокировать всю систему, lock-free алгоритмы гарантируют, что по крайней мере один поток в системе продолжает выполнение за конечное число шагов, независимо от состояния других потоков. Основой lock-free алгоритмов являются атомарные операции (например, Compare-And-Swap, CAS), которые позволяют нескольким потокам безопасно изменять общие данные без взаимного исключения.

История

Идеи неблокирующей синхронизации начали развиваться в 1970-х годах. В 1977 году Лесли Лэмпорт предложил концепцию регистров, которые могут быть прочитаны и записаны несколькими процессами без блокировок. В 1980-х годах Морис Херлихи и другие исследователи заложили теоретические основы wait-free и lock-free алгоритмов. В 1993 году Джон Меллор-Крамми и Майкл Скотт опубликовали одну из первых практических реализаций — lock-free очередь (MS-queue). В 1995 году был предложен алгоритм Hazard Pointer, который решил проблему безопасного освобождения памяти в lock-free структурах. Развитие многоядерных процессоров в начале 2000-х годов стимулировало практическое применение lock-free алгоритмов в высоконагруженных системах.

Классификация

Lock-free алгоритмы являются подклассом более широкой категории неблокирующих алгоритмов. В иерархии неблокирующих алгоритмов выделяют три уровня гарантий прогресса:

Обструкция-free (Obstruction-free)

Самый слабый уровень: поток может быть заблокирован другим потоком, но если поток работает в изоляции (другие потоки приостановлены), он завершит операцию за конечное число шагов. На практике используется редко.

Lock-free

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

Wait-free

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

Принципы работы

Основой lock-free алгоритмов является использование атомарных операций, которые выполняются неделимо (атомарно) относительно других потоков. Ключевая операция — Compare-And-Swap (CAS), которая атомарно сравнивает значение в памяти с ожидаемым и, при совпадении, заменяет его на новое. CAS реализована в виде инструкции процессора (например, CMPXCHG на x86).

Типичный цикл lock-free операции выглядит следующим образом:

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

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

Проблемы и решения

Проблема ABA

Классическая проблема lock-free алгоритмов, связанная с CAS. Если поток читает значение A, затем другой поток меняет его на B, а затем обратно на A, то CAS может ошибочно считать, что данные не изменились. Решение: использование тегов (tagged pointers) или версий (например, в Java — AtomicStampedReference). В C++11 для этой цели используется std::atomic с меткой или std::atomic_compare_exchange_strong с двойным словом.

Управление памятью

В lock-free структурах данных поток может удалить узел, который в этот момент читает другой поток. Это приводит к висячим указателям. Для решения этой проблемы применяются:

• Hazard Pointers: каждый поток объявляет, какие указатели он использует в данный момент. Другие потоки не могут освободить память, пока указатель «опасен».
• Epoch-Based Reclamation (EBR): память освобождается только после того, как все потоки, работавшие в момент удаления, завершили свои операции.
• Reference counting: подсчёт ссылок на узлы, но с атомарными операциями.

Производительность

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

Примеры lock-free структур данных

Lock-free стек (Treiber stack)

Один из простейших lock-free алгоритмов, предложенный Р. Трайбером в 1986 году. Стек реализован как односвязный список с атомарным указателем на вершину. Операция push: читает текущую вершину, создаёт новый узел, указывающий на неё, и пытается CAS-ом заменить вершину. Операция pop: читает вершину, читает следующий узел, пытается CAS-ом заменить вершину на следующий.

Lock-free очередь (MS-queue)

Предложена Меллор-Крамми и Скоттом в 1993 году. Очередь использует два указателя: на голову и на хвост. Операция enqueue добавляет узел в конец, используя CAS для атомарного обновления указателя next последнего узла и указателя хвоста. Операция dequeue удаляет узел с головы.

Lock-free хеш-таблица

Реализуется на основе lock-free списков (bucket) или с использованием техники split-ordered lists. Поддерживает параллельные вставку, удаление и поиск без блокировок.

Применение

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

• Операционные системы: планировщики, очереди задач, менеджеры памяти (например, в ядре Linux).
• Базы данных: транзакционные системы, кэши (например, Memcached, Redis).
• Высоконагруженные веб-серверы: обработка запросов, пулы соединений.
• Библиотеки параллельного программирования: Java java.util.concurrent (ConcurrentLinkedQueue, ConcurrentHashMap), C++ std::atomic и библиотеки libcds, folly.
• Финансовые системы: биржевые движки, где критична скорость обработки ордеров.

Критика

Несмотря на преимущества, lock-free алгоритмы имеют ограничения:

• Сложность разработки и отладки: ошибки (например, проблема ABA) трудно воспроизвести и исправить.
• Проблемы с управлением памятью: требуется дополнительная инфраструктура (hazard pointers, EBR), что усложняет код и может снижать производительность.
• Неэффективность при высокой конкуренции: CAS-циклы могут приводить к «живым блокировкам» (livelock), когда потоки постоянно перезапускают операции, не продвигаясь.
• Отсутствие гарантий справедливости: некоторые потоки могут «голодать» (не получать доступа к данным) в течение длительного времени.

В современных системах часто используется гибридный подход: блокирующие алгоритмы для критических секций с высокой конкуренцией и lock-free для операций с низкой вероятностью конфликтов.

Источники

• Herlihy M., Shavit N. «The Art of Multiprocessor Programming» (2008)
• Maurice Herlihy, «Wait-Free Synchronization» (1991)
• John M. Mellor-Crummey, Michael L. Scott, «Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors» (1991)
• R. K. Treiber, «Systems Programming: Coping with Parallelism» (1986)
• Paul E. McKenney, «Is Parallel Programming Hard, And, If So, What Can You Do About It?» (2011)