¿Qué son los algoritmos no bloqueantes?

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

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

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

Примеры в Java:

• java.util.concurrent.atomic пакет (например, AtomicInteger, AtomicReference).
• Некоторые реализации коллекций из java.util.concurrent (например, ConcurrentHashMap).

Атомарные операции, такие как Compare-and-Swap (CAS), являются основой неблокирующих алгоритмов.

// Пример использования AtomicInteger
import java.util.concurrent.atomic.AtomicInteger;

public class NonBlockingCounter {
    private final AtomicInteger count = new AtomicInteger(0);

    public int increment() {
        // Атомарно увеличивает значение на 1
        return count.incrementAndGet();
    }

    public int getCount() {
        return count.get();
    }
}