Взаимоблокировки: четыре условия

Когда потоки вежливо ждут друг друга — и в результате не двигается никто.

Взаимоблокировка (deadlock) — ситуация, в которой группа процессов навечно застряла, потому что каждый ждёт ресурс, удерживаемый другим из той же группы.

Аналогия: узкий мост

Две машины въехали на однополосный мост с разных сторон и встретились посередине. Ни одна не может проехать, не сдав назад, но ни одна не хочет сдавать. Обе стоят вечно. Это и есть взаимоблокировка: каждый ждёт, пока уступит другой, а другой ждёт того же.

Классический пример с двумя замками

Поток A захватил замок 1 и ждёт замок 2. Поток B захватил замок 2 и ждёт замок 1. Оба будут ждать вечно:

Поток A:               Поток B:
  lock(замок1)           lock(замок2)
  lock(замок2)  <-- ждёт   lock(замок1)  <-- ждёт
  ...                    ...

Четыре условия Коффмана

Взаимоблокировка возможна только если выполнены одновременно все четыре условия. Убрать любое — и deadlock невозможен:

Условие	Смысл
Взаимное исключение	ресурс не делится — им владеет один процесс
Удержание и ожидание	процесс держит ресурс и ждёт ещё один
Без вытеснения	ресурс нельзя отобрать силой — только владелец отдаёт
Круговое ожидание	есть цикл: A ждёт B, B ждёт C, ..., последний ждёт A

Стратегии борьбы

Есть несколько подходов:

Предотвращение (prevention). Спроектировать систему так, чтобы одно из четырёх условий не выполнялось никогда. Например, против кругового ожидания — захватывать замки всегда в одном фиксированном порядке.
Избегание (avoidance). Перед выдачей ресурса проверять, останется ли система в «безопасном состоянии» (алгоритм банкира). Об этом следующий урок.
Обнаружение и восстановление (detection). Позволить взаимоблокировкам случаться, периодически их искать и разрывать (например, завершив один из процессов). Об этом тоже следующий урок.
Игнорирование («страусиная политика»). Притвориться, что проблемы нет. Звучит несерьёзно, но именно так поступают многие ОС: deadlock'и редки, а борьба дорога — проще перезагрузиться.

Самое практичное правило

В реальном коде против взаимоблокировок чаще всего применяют простое правило: всегда захватывать замки в одном и том же порядке. Тогда круговое ожидание невозможно — а значит, и deadlock. Проверим эту идею на модели.

def acquire(thread, order):
    # пробуем захватывать замки в заданном порядке, проверяя на убывание
    held = []
    for lock in order:
        if held and lock < held[-1]:
            return held, lock  # нарушение порядка -> риск deadlock
        held.append(lock)
    return held, None

# Оба потока берут замки по возрастанию номеров — безопасно
a_held, a_bad = acquire("A", [1, 2])
b_held, b_bad = acquire("B", [1, 2])
print(f"Поток A взял {a_held}, нарушение: {a_bad}")
print(f"Поток B взял {b_held}, нарушение: {b_bad}")

# Поток B берёт в обратном порядке — опасно
b2_held, b2_bad = acquire("B", [2, 1])
print(f"Поток B (обратный порядок) взял {b2_held}, нарушение порядка на замке: {b2_bad}")
print("Вывод: единый порядок захвата устраняет круговое ожидание")

Вывод:

Поток A взял [1, 2], нарушение: None
Поток B взял [1, 2], нарушение: None
Поток B (обратный порядок) взял [2], нарушение порядка на замке: 1
Вывод: единый порядок захвата устраняет круговое ожидание

Итог

Взаимоблокировка — взаимное вечное ожидание процессов из-за удерживаемых ресурсов.
Возможна только при всех четырёх условиях Коффмана одновременно.
Убрать любое из условий — и deadlock невозможен.
Стратегии: предотвращение, избегание, обнаружение, игнорирование.
Практичное правило: захватывать замки всегда в одном порядке — нет кругового ожидания.