Неблокирующий алгоритм

Неблокирующий алгоритм (англ. non-blocking algorithm) — это алгоритм параллельных вычислений, в котором задержка, остановка или сбой одного потока выполнения не приводит к задержке, остановке или сбою других потоков. В отличие от алгоритмов, использующих блокировки (мьютексы, семафоры), неблокирующие алгоритмы гарантируют, что система в целом продолжает прогрессировать, даже если один из её потоков приостановлен планировщиком операционной системы или находится в состоянии гонки. Ключевой характеристикой является отсутствие взаимных блокировок (deadlock) и гарантированное выполнение хотя бы одним потоком полезной работы за конечное число шагов.

История

Концепция неблокирующего программирования возникла как ответ на проблемы, связанные с использованием традиционных блокировок в многопоточных системах. В 1970-х годах были разработаны первые аппаратные инструкции для атомарных операций, такие как Test-and-Set (TAS) и Compare-and-Swap (CAS). В 1990-х годах, с ростом числа процессоров в системах и развитием симметричной многопроцессорной обработки (SMP), интерес к неблокирующим алгоритмам значительно возрос.

В 1993 году Морис Херлихи (Maurice Herlihy) опубликовал фундаментальную работу, в которой доказал, что для построения неблокирующих алгоритмов общего назначения необходима аппаратная поддержка атомарных операций, таких как CAS или Load-Link/Store-Conditional (LL/SC). Он также показал, что простых операций чтения и записи недостаточно. В 2000-х годах неблокирующие алгоритмы стали широко применяться в ядрах операционных систем, базах данных и высоконагруженных серверных приложениях.

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

Неблокирующие алгоритмы делятся на три основных класса по степени гарантии прогресса:

Wait-free (без ожидания)

Алгоритм, в котором любой поток гарантированно завершит свою операцию за конечное число шагов, независимо от действий других потоков. Это самый строгий класс, обеспечивающий максимальную предсказуемость, но часто требующий сложной реализации и дополнительной памяти. Примеры: некоторые реализации очередей (queue) на основе CAS.

Lock-free (без блокировок)

Алгоритм, в котором хотя бы один поток в системе гарантированно завершит свою операцию за конечное число шагов. Другие потоки могут испытывать задержки (например, из-за повторных попыток), но система в целом прогрессирует. Это наиболее распространённый класс неблокирующих алгоритмов. Примеры: стеки (stack) на основе CAS, счётчики ссылок (reference counting) в сборщиках мусора.

Obstruction-free (без препятствий)

Алгоритм, в котором поток гарантированно завершит свою операцию, если он работает в изоляции (то есть другие потоки не конкурируют с ним за ресурсы). При наличии конкуренции поток может бесконечно долго пытаться выполнить операцию. Этот класс требует дополнительных механизмов для разрешения конфликтов (например, отката и повторной попытки). Используется реже, чем lock-free, в основном в экспериментальных или специализированных системах.

Основные принципы и механизмы

Атомарные операции

Неблокирующие алгоритмы опираются на аппаратно-поддерживаемые атомарные операции, которые выполняются неделимо. Наиболее распространённые:

• Compare-and-Swap (CAS) — атомарно сравнивает значение в памяти с ожидаемым и, если они равны, заменяет его на новое. Возвращает старое значение.
• Load-Link/Store-Conditional (LL/SC) — пара инструкций: LL считывает значение, а SC записывает новое, только если память не была изменена другим потоком с момента LL.
• Fetch-and-Add (FAA) — атомарно прибавляет заданное значение к ячейке памяти и возвращает старое значение.
• Test-and-Set (TAS) — атомарно устанавливает значение в 1 и возвращает предыдущее значение.

Циклическая проверка (retry loop)

Большинство lock-free алгоритмов используют цикл, в котором поток пытается выполнить операцию с помощью CAS. Если CAS не удаётся (из-за конкуренции), поток повторяет попытку, считывая обновлённые данные. Это называется активным ожиданием (busy-waiting), но в отличие от блокировки, оно не удерживает ресурсы и позволяет другим потокам прогрессировать.

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

Проблема, известная как ABA-проблема, возникает, когда значение в памяти изменяется с A на B и обратно на A, что может привести к ложному успеху CAS. Для её решения используются:

• Метки (tagged pointers) — добавление счётчика версий к указателю.
• Double Compare-and-Swap (DCAS) — атомарная операция над двумя ячейками памяти.
• Сборка мусора с отслеживанием ссылок (Hazard Pointers, RCU) — техники, позволяющие безопасно освобождать память, пока на неё ссылаются другие потоки.

Применение

Ядра операционных систем

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

Базы данных и системы управления транзакциями

В системах управления базами данных (СУБД) неблокирующие алгоритмы применяются для реализации изоляции транзакций и управления конкурентным доступом. Например, многоверсионное управление конкурентным доступом (MVCC) часто использует lock-free структуры для создания и чтения версий записей, что позволяет читателям не блокировать писателей и наоборот.

Высоконагруженные серверы

В веб-серверах, кэшах (например, Redis) и системах обмена сообщениями (например, Kafka) неблокирующие алгоритмы используются для реализации очередей, хеш-таблиц и счётчиков. Это критически важно для обеспечения низкой задержки и высокой пропускной способности при большом числе параллельных запросов.

Реализации коллекций в языках программирования

Современные языки программирования (Java, C++, Go) предоставляют библиотеки с неблокирующими структурами данных. Например, в Java класс java.util.concurrent.ConcurrentLinkedQueue реализован на основе lock-free алгоритма, а в C++ стандартная библиотека включает std::atomic и std::atomic_flag для построения собственных неблокирующих структур.

Примеры

Lock-free стек

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

Lock-free очередь Майкла-Скотта

Очередь, предложенная Майклом и Скоттом в 1996 году, использует две атомарные операции: одну для головы (head) и одну для хвоста (tail). Она позволяет нескольким потокам одновременно добавлять и извлекать элементы без блокировок, хотя требует аккуратного управления памятью для предотвращения ABA-проблемы.

Критика и ограничения

Несмотря на преимущества, неблокирующие алгоритмы имеют ряд недостатков:

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

Источники

• Herlihy, M. (1993). "A Methodology for Implementing Highly Concurrent Data Objects". ACM Transactions on Programming Languages and Systems.
• Michael, M. M., & Scott, M. L. (1996). "Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms". Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing.
• McKenney, P. E. (2004). "Exploiting Deferred Destruction: An Analysis of Read-Copy-Update Techniques in Operating System Kernels". PhD thesis, Oregon Graduate Institute.
• Valois, J. D. (1994). "Lock-Free Linked Lists Using Compare-and-Swap". Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing.
• Intel Corporation. (2009). "Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 2A: Instruction Set Reference, A-L".