Лайвлок
#новичкам

Лайвлок(livelock) — это ситуация в многопоточном программировании, когда потоки не блокируются полностью, как при дедлоке, а продолжают выполняться, но не могут продвинуться в решении задачи из-за постоянной реакции на действия друг друга.

Потоки находятся в состоянии "живой блокировки" — они активны, cpu жжется, но их работа не приводит ни к какому прогрессу.

Лайвлоки не всегда приводят к вечной блокировке потоков. Просто в какие-то рандомные моменты времени условный rps может неконтролируемо вырасти в разы, а то и на порядки.

И так как ситуация сильно зависит от планирования потоков, то воспроизвести ее будет сложно.

Однако у этой проблемы есть характерные черты, облегчающие ее поиск:

🔍 Активное ожидание — потоки постоянно проверяют какие-то условия и крутятся в циклах.
🔍 Взаимозависимость — действия одного потока влияют на условия выполнения другого.
🔍 Неблокирующие алгоритмы - активное ожидание обычно идет за ручку с lockfree алгоритмами.
🔍 Поддавки - при потенциальном конфликте интересов стороны предпочитают уступать.

Аналогия из реальной жизни: вы идете по узкому тротуару и вам навстречу идет человек. Вы хотите разминуться, но отшагиваете вместе в одну и ту же сторону. И вы, как крабики, ходите вместе из стороны в сторону. Рано или поздно вы разойдетесь, но заранее нельзя сказать когда.

К лайвлоку может привести и использование стандартных инструментов. Например, std::scoped_lock, который предназначен для безопасной блокировки нескольких мьютексов. Стандарт требует, чтобы его реализация не приводила к дедлоку. Они используют неопределенную последовательность вызовов методов lock(), try_lock() и unlock(), которая гарантирует отсутствие дедлока. Но не гарантирует отсутствия лайвлока. Алгоритм там примерно такой: попробуй заблокировать столько мьютексов, сколько можешь, а если не получилось, то освободи их и попробуй сначала. Тут есть и циклы, и активное ожидание, и взаимозависимость, и поддавки.

Но компиляторы понимают эту проблему и современные реализации используют разные приемы, типа экспоненциального backoff'а, чтобы все-таки рано или поздно дать шанс одному из потоков полностью захватить все ресурсы.

Вот более "надежный" пример:

std::atomic<bool> lock1 = false;
std::atomic<bool> lock2 = false;

void thread1_work() {
    while (true) {
        // lock lock1
        while (lock1.exchange(true))
            ;
        std::cout << "Thread 1 has acquired lock1, try to acquire lock2..."
                  << std::endl;
        // try to lock lock2
        if (!lock2.exchange(true)) {
            std::cout << "Thread 1 has acquired both locks!" << std::endl;
            lock2 = false;
            lock1 = false;
            break;
        } else {
            // Failed, release lock1 and try again
            std::cout << "Thread 1 failed to acquire lock2, release lock1..."
                      << std::endl;
            lock1 = false;
        }
    }
}

void thread2_work() {
    while (true) {
        // lock lock2
        while (lock2.exchange(true))
            ;
        std::cout << "Thread 2 has acquired lock2, try to acquire lock1..."
                  << std::endl;
        // try to lock lock1
        if (!lock1.exchange(true)) {
            std::cout << "Thread 2 has acquired both locks!" << std::endl;
            lock1 = false;
            lock2 = false;
            break;
        } else {
            // Failed, release lock2 and try again
            std::cout << "Thread 2 failed to acquire lock1, release lock2..."
                      << std::endl;
            lock2 = false;
        }
    }
}

int main() {
    std::jthread t1(thread1_work);
    std::jthread t2(thread2_work);
}

По сути это костыльная и наивная демонстрация принципа работы std::lock с помощью атомарных замков. Каждый поток пытается в своем порядке захватить замки и отпускает захваченный, если не получилось, и идет на следующую попытку. Можете позапускать этот код у себя и посмотреть, как много попыток захвата потоки будут делать от запуска к запуску.

Unlock your life. Stay cool.

#concurrency