🧵 Раздел 9 · Вопрос #18

Какие условия необходимы для возникновения deadlock

Для возникновения Deadlock (взаимной блокировки) в любой вычислительной системе необходимо и достаточно одновременное выполнение четырёх условий Коффмана (Coffman Conditions), с...

🧵 Многопоточность 📄 Исходный Markdown

🟢 Junior Level

Краткий ответ для собеседования (30 секунд)

Для возникновения Deadlock (взаимной блокировки) в любой вычислительной системе необходимо и достаточно одновременное выполнение четырёх условий Коффмана (Coffman Conditions), сформулированных Эдвардом Коффманом в 1971 году:

  1. Взаимное исключение (Mutual Exclusion): ресурс неделим и в любой момент времени может удерживаться только одним потоком.
  2. Удержание и ожидание (Hold and Wait): поток, уже удерживающий как минимум один ресурс, запрашивает дополнительные ресурсы, удерживаемые другими потоками.
  3. Отсутствие вытеснения (No Preemption): ресурс не может быть принудительно отобран у удерживающего его потока; освобождение возможно только добровольно самим владельцем.
  4. Циклическое ожидание (Circular Wait): существует замкнутая круговая цепочка потоков ${T_1, T_2, \dots, T_n}$, где $T_1$ ждёт ресурс, занятый $T_2$, $T_2$ ждёт $T_3$, …, а $T_n$ ждёт ресурс, занятый $T_1$.

[!IMPORTANT] Фундаментальный закон: Если нарушить хотя бы одно из четырёх условий Коффмана, возникновение Deadlock становится математически невозможным.

Анализ условий Коффмана в коде Java 21

public class CoffmanConditionsDemo {
    private final Object resourceA = new Object();
    private final Object resourceB = new Object();

    public void threadOneAction() {
        // Условие 1 (Mutual Exclusion): synchronized захватывает монитор монопольно
        synchronized (resourceA) {
            // Условие 2 (Hold and Wait): удерживая resourceA, запрашиваем resourceB
            // Условие 3 (No Preemption): JVM не может принудительно забрать resourceA
            synchronized (resourceB) {
                doWork();
            }
        }
    }

    public void threadTwoAction() {
        synchronized (resourceB) {
            // Условие 4 (Circular Wait): поток 2 ждёт resourceA, замыкая цикл
            synchronized (resourceA) {
                doWork();
            }
        }
    }

    private void doWork() {}
}

🟡 Middle Level

Разрушение условий Коффмана на практике

Каждое из условий Коффмана можно целенаправленно разрушить архитектурными средствами Java:

               Как устранить каждое из условий Коффмана в Java
+--------------------------------------------------------------------------+
| 1. Нарушение Mutual Exclusion:                                           |
|    - Замена блокировок на lock-free структуры (Atomic*, ConcurrentMap).  |
|    - Использование разделяемых замков на чтение: ReadLock.               |
+--------------------------------------------------------------------------+
| 2. Нарушение Hold and Wait:                                              |
|    - Захват всех ресурсов сразу «пакетом» через tryLock():               |
|      если второй ресурс недоступен, немедленно освободить первый!         |
+--------------------------------------------------------------------------+
| 3. Нарушение No Preemption:                                              |
|    - Использование ReentrantLock.tryLock(timeout) или lockInterruptibly()|
|      для принудительного прерывания зависшего ожидания.                  |
+--------------------------------------------------------------------------+
| 4. Нарушение Circular Wait (САМЫЙ ЭФФЕКТИВНЫЙ СПОСОБ):                   |
|    - Глобальное упорядочивание ресурсов (Global Lock Ordering).          |
|    - Захват блокировок строго по возрастанию ID ресурсов.                |
+--------------------------------------------------------------------------+

Подробный разбор стратегий устранения

1. Разрушение Mutual Exclusion (Взаимное исключение)

Если несколько потоков могут использовать ресурс параллельно без взаимного исключения, Deadlock невозможен.

  • Применение: Разделение операций чтения и записи через ReentrantReadWriteLock или StampedLock. Десятки потоков могут одновременно удерживать readLock(), не блокируя друг друга.
  • Ограничение: Неприменимо для операций записи (мутаций данных).

2. Разрушение Hold and Wait (Удержание и ожидание)

Поток не должен ждать ресурс, удерживая другие:

// Паттерн «Всё или ничего»:
boolean acquiredA = lockA.tryLock();
boolean acquiredB = false;
try {
    if (acquiredA) {
        acquiredB = lockB.tryLock();
    }
    if (acquiredA && acquiredB) {
        // Успех: оба ресурса захвачены
        process();
    }
} finally {
    if (!acquiredB && acquiredA) {
        lockA.unlock(); // НЕМЕДЛЕННО ОСВОБОЖДАЕМ, если второй не получили!
    } else if (acquiredB) {
        lockB.unlock();
        lockA.unlock();
    }
}

3. Разрушение No Preemption (Отсутствие вытеснения)

В synchronized вытеснение невозможно. Замена на ReentrantLock с таймаутом позволяет сбросить ожидание:

// Если ресурс не освободился за 100 мс, поток отступает
if (lock.tryLock(100, TimeUnit.MILLISECONDS)) {
    try {
        execute();
    } finally {
        lock.unlock();
    }
}

4. Разрушение Circular Wait (Циклическое ожидание)

Самый дешёвый и надёжный промышленный подход — иерархия блокировок по Хавендеру (Havender’s Linear Ordering):

public void transferMoney(Account from, Account to, int amount) {
    // Детерминированный порядок: меньший ID всегда захватывается первым!
    Account first = from.getId() < to.getId() ? from : to;
    Account second = from.getId() < to.getId() ? to : from;

    synchronized (first) {
        synchronized (second) {
            from.debit(amount);
            to.credit(amount);
        }
    }
}

Поскольку все потоки системы захватывают блокировки в строго одинаковом порядке, цикл в графе ожидания математически не может сформироваться.

🔴 Senior Level

Теория графов: Wait-For Graph (WFG) и Resource Allocation Graph (RAG)

В академической теории распределённых систем взаимные блокировки анализируются через направленные двудольные графы распределения ресурсов (RAG):

       Resource Allocation Graph (RAG)           Wait-For Graph (WFG)
          [ R1 ] ───────> ( T1 )                    ( T1 ) ◄───────┐
            ▲               │                         │            │
            │               │                         │            │
            │               v                         v            │
          ( T2 ) <─────── [ R2 ]                    ( T2 ) ────────┘
     (T2 ждёт R1,     (R2 занят T2,               (Цикл в графе WFG
      R1 занят T1)     T1 ждёт R2)                 означает Deadlock)
  1. Если каждый ресурс имеет ровно одну копию (Single-unit resources): наличие цикла в графе зависимостей потоков (WFG) является необходимым и достаточным условием взаимной блокировки.
  2. Если ресурсы имеют множественные копии (Multi-unit resources): наличие цикла является лишь необходимым, но не достаточным условием (ситуация анализируется матричным алгоритмом банкира Дейкстры / Banker’s Algorithm).

Задача об обедающих философах (Dijkstra, 1965)

Классическая иллюстрация всех четырёх условий Коффмана:

  • 5 философов сидят за круглым столом. Между каждой парой лежит одна вилка (всего 5 вилок).
  • Для еды философу требуются две соседние вилки (левая и правая).
                            Философ 1
                          /           \
                     Вилка 1         Вилка 5
                      /                 \
               Философ 2               Философ 5
                  |                       |
               Вилка 2                 Вилка 4
                   \                     /
                  Философ 3 ── Вилка 3 ── Философ 4

Иллюстрация условий:

  1. Mutual Exclusion: вилку может взять только один философ.
  2. Hold and Wait: каждый философ берёт левую вилку и держит её, ожидая правую.
  3. No Preemption: никто не может силой вырвать вилку у соседа.
  4. Circular Wait: если все 5 философов одновременно возьмут левую вилку, они замкнут кольцо ожидания правой вилки — наступает Deadlock.

Решение Дейкстры (Нарушение Circular Wait):

Один из философов (например, последний) назначается «левшой» и берёт сначала правую вилку, а затем левую, тогда как все остальные берут сначала левую. Цикл мгновенно разрывается.

Анализ ложных дедлоков (False Deadlocks)

В современных распределённых микросервисных архитектурах средства мониторинга APM часто рапортуют о «дедлоках», которые таковыми не являются:

Тип зависания Реальный статус Потребление CPU Это Deadlock?
Deadlock потоков Java BLOCKED на мониторах 0% ✅ Да
Deadlock пула БД (HikariCP) WAITING на getConnection() 0% ❌ Нет (Resource Starvation)
Зависание на сетевом I/O RUNNABLE в сокете ОС 0% ❌ Нет (Network Hang / Socket Timeout)
Длительная GC-пауза (STW) Все потоки остановлены на Safepoint 100% (потоки GC) ❌ Нет (GC Pause)

🎯 Шпаргалка для интервью

1. 30-секундный эссенс (Elevator Pitch)

Deadlock возникает тогда и только тогда, когда одновременно выполняются 4 условия Коффмана: взаимное исключение (Mutual Exclusion), удержание и ожидание (Hold and Wait), отсутствие принудительного вытеснения (No Preemption) и цикличность ожидания (Circular Wait). Нарушение любого одного условия гарантирует защиту от дедлока. В промышленной разработке чаще всего разрушают циклическое ожидание через строгий глобальный порядок захвата замков (Lock Ordering по ID ресурса) или устраняют отсутствие вытеснения через ReentrantLock.tryLock(timeout).

2. 4 каверзных вопроса с глубокими ответами

Вопрос 1: Какое из четырёх условий Коффмана проще и надёжнее всего нарушить на практике в промышленном Enterprise-коде?

Ответ: Проще и надёжнее всего нарушить четвёртое условие — циклическое ожидание (Circular Wait) посредством введения глобального порядка захвата блокировок (Lock Ordering).
Обоснование:

  • Нарушить Mutual Exclusion для операций модификации данных невозможно без нарушения согласованности.
  • Нарушение Hold and Wait (проверка tryLock всех ресурсов сразу) усложняет код и может вызывать Livelock.
  • Введение детерминированного порядка (например, захватывать ресурсы строго по возрастанию их первичных ключей в БД или id сущностей) полностью устраняет возможность формирования цикла в графе зависимостей с нулевым оверхедом по производительности.

Вопрос 2: Разрушает ли использование ReentrantReadWriteLock условие взаимного исключения (Mutual Exclusion)?

Ответ: Частично. Для читающих потоков (readLock()) условие взаимного исключения действительно разрушается, так как множество потоков могут одновременно владеть замком на чтение без ожидания. Однако для пишущих потоков (writeLock()) блокировка остаётся строго монопольной. Более того, при попытке повышения блокировки (Lock Upgrading) из readLock в writeLock внутри одного потока гарантированно возникает Deadlock, если два потока одновременно удерживают замок на чтение и пытаются запросить замок на запись.

Вопрос 3: Как задача об обедающих философах (Dining Philosophers) иллюстрирует условия Коффмана и в чём заключается решение по Дейкстре?

Ответ: Задача моделирует 5 процессов, конкурирующих за 5 разделяемых ресурсов (вилок), расположенных по кругу. Условия Коффмана проявляются в том, что вилка неделима (Mutual Exclusion), философ держит одну и ждёт вторую (Hold and Wait), отобрать вилку нельзя (No Preemption), и все берут сначала левую вилку, замыкая кольцо (Circular Wait).
Решение Дейкстры разрушает Circular Wait: вводится асимметрия, при которой один философ меняет порядок взятия вилок (сначала берёт правую, затем левую) или вилки нумеруются от 1 до 5, и каждый обязан брать вилку с меньшим номером первой.

Вопрос 4: Что произойдёт, если попытаться нарушить условие No Preemption в synchronized через вызов Thread.interrupt()?

Ответ: Условие No Preemption не будет нарушено. Поток, ожидающий входа в монитор synchronized (инструкция monitorenter), находится в состоянии Thread.State.BLOCKED. Это состояние является аппаратно непрерываемым в Java: вызов thread.interrupt() выставит флаг прерывания, но не прервёт ожидание и не выбросит InterruptedException. Поток продолжит ожидать монитор. Нарушить No Preemption можно только переходом на ReentrantLock с вызовом lockInterruptibly().

3. Типичные ошибки и Red Flags

❌ “Для дедлока достаточно любых трёх условий Коффмана из четырёх.”
Правильно: Все 4 условия обязаны выполняться одновременно. Если хотя бы одно условие отсутствует, Deadlock невозможен.

❌ “Использование volatile защищает от условий Коффмана.”
Правильно: volatile обеспечивает только видимость в кешах процессора, но не гарантирует взаимного исключения для составных операций и вообще не имеет отношения к механизмам блокировок.

❌ “Если в коде нет ключевого слова synchronized, условия Коффмана не применимы.”
Правильно: Условия Коффмана универсальны для любых ресурсов: пулов соединений с БД (HikariCP), потоков ввода-вывода, очередей сообщений и даже файловых блокировок ОС.

4. Связанные вопросы