Livelock и голодание (starvation)

Не всякий «зависший» поток стоит на месте: иногда он бешено работает, но прогресса нет.

Livelock — потоки не заблокированы и активно выполняют действия, но из-за взаимных реакций не продвигаются к цели; голодание (starvation) — поток бесконечно не получает доступ к нужному ресурсу.

Deadlock — это «оба замерли». Livelock — это «оба суетятся, но без толку». Представьте двух людей в узком коридоре: каждый вежливо отходит в ту же сторону, что и другой, они снова сталкиваются, снова отходят — и так бесконечно. Никто не заблокирован, но никто и не проходит.

Откуда берётся livelock

Часто livelock рождается из наивной попытки избежать deadlock: «если не смог взять вторую блокировку — отпущу первую и попробую снова». Если оба потока делают это синхронно, они вечно отпускают и захватывают по кругу.

Поток A: взял l1, не смог l2 -> отпустил l1, ждёт, повторил
Поток B: взял l2, не смог l1 -> отпустил l2, ждёт, повторил
(и так до бесконечности — оба активны, прогресса нет)

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

Голодание

Голодание — когда поток постоянно «оттесняют». Например, при строго приоритетном планировании высокоприоритетные потоки идут без конца, а низкоприоритетный не получает ядра никогда. Или «писатель» не может войти, потому что поток читателей не иссякает.

import random
random.seed(7)

# моделируем backoff: случайная пауза рассинхронизирует попытки
for attempt in range(1, 6):
    backoff = round(random.uniform(0, 1), 2)
    print(f"попытка {attempt}: жду {backoff} перед повтором")

Вывод:

попытка 1: жду 0.32 перед повтором
попытка 2: жду 0.15 перед повтором
попытка 3: жду 0.65 перед повтором
попытка 4: жду 0.07 перед повтором
попытка 5: жду 0.54 перед повтором

Как работает под капотом

Livelock не виден детектору deadlock: потоки не заблокированы, граф ожидания пуст, процессор загружен. Поэтому livelock диагностировать сложнее — программа «жива», но не прогрессирует. Против голодания планировщики применяют старение (aging): чем дольше поток ждёт, тем выше его приоритет, и рано или поздно он получает ядро. Очереди по принципу FIFO тоже гарантируют справедливость.

Частые ошибки

Одинаковый фиксированный backoff у всех. Потоки остаются синхронными — livelock не уходит.
Жёсткие приоритеты без старения. Низкоприоритетные потоки голодают.
Считать высокую загрузку CPU признаком прогресса. При livelock CPU занят, а работа не делается.

Итог

Deadlock — потоки замерли; livelock — потоки активны, но не продвигаются.
Голодание — поток никогда не получает ресурс.
Случайный backoff лечит livelock, рассинхронизируя повторы.
Старение и справедливые очереди спасают от голодания.