Що таке deadlock (взаємне блокування)

Класичний приклад — операція міжбанківського переказу:

🟢 Junior Level

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

Deadlock (взаємне блокування) — це критична ситуація в багатопоточній системі, при якій два або більше потоків нескінченно заблоковані, оскільки кожен із них утримує ресурс, необхідний іншому, і одночасно очікує на звільнення ресурсу, що утримується іншим.

Класичний приклад — операція міжбанківського переказу:

Потік 1 захоплює блокування Рахунку $A$ і намагається захопити Рахунок $B$.
Потік 2 одночасно захоплює Рахунок $B$ і намагається захопити Рахунок $A$.
Результат: жоден потік не може продовжити роботу, вони переходять у стан BLOCKED або WAITING, і система зависає назавжди.

На відміну від баз даних, JVM не вміє автоматично вирішувати взаємні блокування потоків (наприклад, примусово відкочувати одну зі сторін). Вивести потоки зі стану Deadlock у Java без перезапуску застосунку або втручання зовнішнього моніторингу неможливо.

Порівняння: Deadlock проти Livelock проти Starvation

Стан	Поведінка потоків	Утилізація CPU	Причина
Deadlock	Потоки пасивно заблоковані (`BLOCKED`/`WAITING`), очікуючи один одного	0% CPU	Циклічна залежність ресурсів
Livelock	Потоки активні (`RUNNABLE`), безперервно змінюють стан, але корисного прогресу немає	100% CPU	Постійні поступки ресурсом обома потоками
Starvation	Потік готовий до виконання, але планувальник ніколи не дає йому ресурс	Змінна	Несправедливі блокування, пріоритети потоків

Класичний приклад взаємного блокування на Java 21

public class DeadlockDemo {
    private final Object lockA = new Object();
    private final Object lockB = new Object();

    public void executeTask1() {
        synchronized (lockA) {
            System.out.println("Потік 1: утримує lockA, чекає на lockB...");
            sleep(50);
            synchronized (lockB) {
                System.out.println("Потік 1: успішно захопив обидва замки");
            }
        }
    }

    public void executeTask2() {
        synchronized (lockB) {
            System.out.println("Потік 2: утримує lockB, чекає на lockA...");
            sleep(50);
            synchronized (lockA) {
                System.out.println("Потік 2: успішно захопив обидва замки");
            }
        }
    }

    private void sleep(long ms) {
        try { Thread.sleep(ms); } catch (InterruptedException ignored) {}
    }
}

🟡 Middle Level

4 умови Коффмана (Coffman Conditions)

У теорії операційних систем взаємне блокування математично можливе лише при одночасному виконанні чотирьох умов Коффмана (Едвард Коффман, 1971 р.):

                   4 Необхідні умови Deadlock
+-----------------------------+     +-----------------------------+
| 1. Mutual Exclusion         |     | 2. Hold and Wait            |
| Ресурс неподільний: в один  |     | Потік утримує ресурс і      |
| момент часу ним володіє     |     | очікує додатковий.          |
| тільки один потік.          |     |                             |
+--------------+--------------+     +--------------+--------------+
               │                                   │
               v                                   v
+--------------+--------------+     +--------------+--------------+
| 3. No Preemption            |     | 4. Circular Wait            |
| Неможливо примусово         |     | Існує замкнений цикл        |
| відібрати ресурс у потоку.  |     | у графі очікування потоків  |
| Тільки добровільний вихід!  |     | (Потік 1 -> Потік 2 -> ...).|
+-----------------------------+     +-----------------------------+

[!IMPORTANT] Принцип запобігання (Deadlock Prevention): щоб гарантовано виключити можливість виникнення Deadlock, достатньо порушити хоча б одну з чотирьох умов Коффмана! На практиці найчастіше руйнують 4-ту умову (Circular Wait) шляхом суворого впорядкування захоплення ресурсів.

Приховані сценарії Deadlock у реальних застосунках

В Enterprise-системах взаємні блокування рідко виглядають як два очевидні вкладені synchronized-блоки в одному файлі.

1. Deadlock виснаження пулу потоків (Thread Pool Starvation Deadlock)

Виникає, коли задачі, що виконуються в пулі потоків, породжують підзадачі в тому ж самому пулі і синхронно чекають на їхнє завершення:

// Однопотоковий пул
ExecutorService pool = Executors.newFixedThreadPool(1);

pool.submit(() -> {
    System.out.println("Початок виконання батьківської задачі");
    // Батьківська задача відправляє дочірню задачу в ЦЕЙ ЖЕ пул і чекає на неї:
    Future<String> childTask = pool.submit(() -> "Результат дочірньої задачі");
    
    // ФАТАЛЬНИЙ DEADLOCK:
    // Єдиний потік пулу зайнятий очікуванням .get(),
    // а дочірня задача вічно стоїть у черзі workQueue!
    return childTask.get(); 
});

2. Deadlock статичної ініціалізації класів (ClassLoader Deadlock)

Специфікація JVM (JLS §12.4.2) вимагає синхронізації при ініціалізації класів:

Якщо статичний блок class A звертається до class B.
А статичний блок class B звертається до class A.
Два потоки, що вперше завантажують ці класи паралельно, увійдуть у взаємне блокування на внутрішніх моніторах ініціалізації класів JVM!

🔴 Senior Level

Діагностика в Production: `jstack` та `ThreadMXBean`

1. Аналіз через Thread Dump (`jstack`)

JVM автоматично аналізує граф очікування і при формуванні дампа явно виділяє секцію Java-level Deadlock:

Found one Java-level deadlock:
=============================
"Thread-1":
  waiting to lock monitor 0x00007f90c8004b00 (object 0x000000076ad89010, a java.lang.Object),
  which is held by "Thread-2"

"Thread-2":
  waiting to lock monitor 0x00007f90c8005e00 (object 0x000000076ad89000, a java.lang.Object),
  which is held by "Thread-1"

Java stack information for the threads listed above:
===================================================
"Thread-1":
        at com.example.DeadlockDemo.executeTask1(DeadlockDemo.java:12)
        - waiting to lock <0x000000076ad89010> (a java.lang.Object)
        - locked <0x000000076ad89000> (a java.lang.Object)
"Thread-2":
        at com.example.DeadlockDemo.executeTask2(DeadlockDemo.java:23)
        - waiting to lock <0x000000076ad89000> (a java.lang.Object)
        - locked <0x000000076ad89010> (a java.lang.Object)

2. Програмний пошук через JMX `ThreadMXBean`

ThreadMXBean bean = ManagementFactory.getThreadMXBean();
// Знаходить дедлоки як на synchronized моніторах, так і на Lock (AQS Ownable Synchronizers)
long[] deadlockedThreadIds = bean.findDeadlockedThreads();

if (deadlockedThreadIds != null) {
    ThreadInfo[] infos = bean.getThreadInfo(deadlockedThreadIds, true, true);
    for (ThreadInfo info : infos) {
        log.error("Виявлено потік у Deadlock: {} чекає на лок {}, утримуваний {}",
            info.getThreadName(), info.getLockName(), info.getLockOwnerName());
    }
}

[!WARNING] Метод findDeadlockedThreads() виконує повний обхід графа залежностей потоків (алгоритм Тар’яна пошуку циклів, $O(V+E)$). Це високовартісна операція, що вимагає паузи на читання метаданих потоків. Запускати її в безперервному високочастотному циклі в Production категорично заборонено (допустимо запускати фоновим таймером раз на 30–60 секунд).

Архітектурні патерни запобігання

1. Глобальний порядок захоплення (Lock Ordering)

Якщо ресурси завжди захоплюються в однаковому детермінованому порядку в усіх потоках, циклічний граф очікування (Circular Wait) стає фізично неможливим:

public class SafeAccountTransfer {
    // Безпечний переказ грошей між рахунками
    public void transfer(Account from, Account to, int amount) {
        // Впорядковуємо блокування за природним унікальним ID рахунку:
        Account firstLock = from.getId() < to.getId() ? from : to;
        Account secondLock = from.getId() < to.getId() ? to : from;

        synchronized (firstLock) {
            synchronized (secondLock) {
                from.withdraw(amount);
                to.deposit(amount);
            }
        }
    }
}

2. Вирішення колізій ідентифікаторів: Tie-Breaker Lock

Якщо унікального числового ID в об’єктів немає, впорядкування виконують за System.identityHashCode(obj). Проте через принцип Діріхле у двох різних об’єктів у пам’яті може збігтися хеш-код. Для таких рідкісних колізій застосовується замок вирішення нічиєї (Tie-Breaker Lock):

private static final Object tieLock = new Object();

public void transferByIdentity(Object from, Object to) {
    int fromHash = System.identityHashCode(from);
    int toHash = System.identityHashCode(to);

    if (fromHash < toHash) {
        synchronized (from) { synchronized (to) { /* дія */ } }
    } else if (fromHash > toHash) {
        synchronized (to) { synchronized (from) { /* дія */ } }
    } else {
        // Колізія хеш-кодів! Захоплюємо глобальний замок вирішення нічиєї:
        synchronized (tieLock) {
            synchronized (from) {
                synchronized (to) { /* дія */ }
            }
        }
    }
}

3. Використання таймаутів: `ReentrantLock.tryLock()`

Заміна непереривного synchronized на захоплення з таймаутом руйнує умову No Preemption:

public boolean tryTransfer(ReentrantLock lockA, ReentrantLock lockB, long timeout, TimeUnit unit) 
        throws InterruptedException {
    long stopTime = System.nanoTime() + unit.toNanos(timeout);
    while (System.nanoTime() < stopTime) {
        if (lockA.tryLock(50, TimeUnit.MILLISECONDS)) {
            try {
                if (lockB.tryLock(50, TimeUnit.MILLISECONDS)) {
                    try {
                        // Успішно захоплено обидва замки!
                        return true;
                    } finally {
                        lockB.unlock();
                    }
                }
            } finally {
                lockA.unlock(); // Звільняємо перший замок, якщо другий не вдалося захопити!
            }
        }
        // Випадкова затримка (Jitter) для запобігання Livelock
        Thread.sleep(ThreadLocalRandom.current().nextInt(10, 50));
    }
    return false;
}

🎯 Шпаргалка для інтерв’ю

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

Deadlock — стан взаємного перманентного блокування двох і більше потоків, що очікують на ресурси один одного при нульовій утилізації CPU (0%). Виникає суворо при одночасному виконанні 4 умов Коффмана: взаємне виключення, утримання та очікування, відсутність витіснення та циклічність очікування. У Java діагностується через дамп потоків (jstack) та ThreadMXBean. Запобігається порушенням циклічності (детермінований Lock Ordering за ID ресурсу) або використанням ReentrantLock.tryLock(timeout) із випадковим back-off для уникнення Livelock.

2. 4 каверзних питання з глибокими відповідями

Питання 1: У чому різниця між методами `ThreadMXBean.findDeadlockedThreads()` та `findMonitorDeadlockedThreads()`?

Відповідь:

findMonitorDeadlockedThreads() шукає цикли блокувань, побудовані виключно на вбудованих моніторах Java (synchronized).
findDeadlockedThreads() (з’явився в Java 6) аналізує як монітори synchronized, так і власні синхронізатори з пакета java.util.concurrent (блокування ReentrantLock, ReentrantReadWriteLock та інші нащадки AbstractQueuedSynchronizer, що реєструють власників в AbstractOwnableSynchronizer). Він є більш універсальним, але вимагає більше часу на обхід структур пам’яті.

Питання 2: Чому при впорядкуванні блокувань за `System.identityHashCode()` необхідний третій замок вирішення нічиєї (Tie-Breaker Lock)?

Відповідь: Метод System.identityHashCode(obj) повертає 31-бітний хеш, генерований JVM. Згідно з парадоксом днів народження (birthday paradox), у системі із сотнями тисяч об’єктів неминуче виникнуть колізії, коли два абсолютно різних об’єкти в пам’яті отримають однаковий identity hashcode. Якщо для двох об’єктів із рівним хешем спробувати виконати синхронізацію без додаткового замка, порядок їхнього захоплення стане довільним, що поверне можливість взаємного блокування. tieLock серіалізує обробку рідкісних випадків збігу хешів, гарантуючи атомарність входу.

Питання 3: Чи може сигнал `Thread.interrupt()` вивести потік зі стану Deadlock, якщо потоки заблоковані ключовим словом `synchronized`?

Відповідь: Ні, не може. Очікування захоплення монітора в synchronized (на рівні інструкції байткоду monitorenter) є непереривним. Потік перебуває в стані Thread.State.BLOCKED у черзі _cxq/_EntryList. Виклик interrupt() лише виставить прапорець переривання, але потік продовжить спати доти, доки монітор фізично не звільниться. Вивести потік із Deadlock за перериванням можна тільки в тому випадку, якщо синхронізація була побудована на явних замках із підтримкою переривань: Lock.lockInterruptibly().

Питання 4: Як виникає «Thread Pool Starvation Deadlock» і чому збільшення розміру пулу не вирішує проблему кардинально?

Відповідь: Проблема виникає, коли задача $A$, що виконується в пулі, відправляє в цей же пул залежну підзадачу $B$ і блокуюче чекає на неї через future.get(). Якщо одночасно надійде $N$ таких задач (де $N$ — розмір пулу), всі $N$ робочих потоків займуться задачами $A$ і заблокуються на очікуванні. Жоден потік не зможе взяти підзадачі $B$ із черги, і система встане в постійний Deadlock. Просте збільшення пулу лише відсуває поріг відмови: при сплеску навантаження пул будь-якого розміру буде вичерпано. Архітектурне рішення: розділяти пули для батьківських та дочірніх задач, використовувати неблокуючі асинхронні ланцюжки (CompletableFuture.thenCompose()) або переходити на віртуальні потоки (Virtual Threads).

3. Типові помилки та Red Flags

❌ “Deadlock та Livelock — це одне й те саме.”
Правильно: При Deadlock потоки пасивні (BLOCKED/WAITING), не споживають такти процесора (CPU 0%). При Livelock потоки перебувають у статусі RUNNABLE, безперервно спалюють CPU на 100%, поступаючись ресурсами один одному, але система не робить корисного прогресу.

❌ “Якщо в коді виник Deadlock, JVM автоматично викине виняток.”
Правильно: JVM ніколи не викидає винятків при взаємному блокуванні потоків. Потоки висітимуть у пам’яті вічно, доки застосунок не буде перезапущено.

❌ “Використання tryLock() без таймауту рятує від будь-яких проблем.”
Правильно: Наївний цикл із tryLock() без випадкової затримки (back-off / jitter) призводить до переходу з Deadlock у Livelock, коли два потоки одночасно захоплюють один замок, не можуть узяти другий, одночасно відпускають перший і повторюють це нескінченно.