Неблокирующие алгоритмы позволяют нескольким потокам выполнять операции одновременно без необходимости блокирования друг друга. Это достигается за счет использования атомарных операций и предотвращения состояний гонки.
Ключевые характеристики:
- Отсутствие взаимных блокировок (deadlocks): Потоки не ждут друг друга бесконечно.
- Живучесть (liveness): Гарантия того, что некоторая операция в конечном итоге завершится. Существует три уровня живучести:
- Обструктивное исключение (Obstruction-free): Один поток всегда может выполнить операцию, если он работает в изоляции.
- Свободное от блокировок исключение (Lock-free): Гарантия того, что по крайней мере один поток выполнит операцию за конечное число шагов (глобальный прогресс).
- Свободное от ожидания исключение (Wait-free): Гарантия того, что каждый поток выполнит операцию за конечное число шагов (индивидуальный прогресс).
Примеры в Java:
java.util.concurrent.atomic пакет (например, AtomicInteger, AtomicReference).- Некоторые реализации коллекций из
java.util.concurrent (например, ConcurrentHashMap).
Атомарные операции, такие как Compare-and-Swap (CAS), являются основой неблокирующих алгоритмов.
java