🧵 Розділ 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. Пов’язані питання