Что такое неблокирующие алгоритмы?

Неблокирующие алгоритмы позволяют нескольким потокам выполнять операции одновременно без необходимости блокирования друг друга. Это достигается за счет использования атомарных операций и предотвращения состояний гонки.

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

• Отсутствие взаимных блокировок (deadlocks): Потоки не ждут друг друга бесконечно.
• Живучесть (liveness): Гарантия того, что некоторая операция в конечном итоге завершится. Существует три уровня живучести:
  • Обструктивное исключение (Obstruction-free): Один поток всегда может выполнить операцию, если он работает в изоляции.
  • Свободное от блокировок исключение (Lock-free): Гарантия того, что по крайней мере один поток выполнит операцию за конечное число шагов (глобальный прогресс).
  • **Свободное от ожидания исклю