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

~5 минут · 2 примера · 3 вопроса

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

Взаимоблокировка (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 невозможен.
  • Стратегии: предотвращение, избегание, обнаружение, игнорирование.
  • Практичное правило: захватывать замки всегда в одном порядке — нет кругового ожидания.

Проверь себя

Три вопроса по уроку. Ответы никуда не идут — это для тебя.

1Сколько условий Коффмана должно выполняться одновременно для возможности взаимоблокировки?

2Какое условие нарушается, если всегда захватывать замки в одном фиксированном порядке?

3Что такое «страусиная политика» в отношении взаимоблокировок?

Следующий урок
16 · Обнаружение и избегание deadlock Открыть урок 16
Урок 14: Мьютексы и семафоры