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

---

Junior рівень

Базове розуміння

Deadlock — це не випадковість, а результат математичного поєднання факторів. У 1971 році Едвард Коффман сформулював 4 умови, які мають виконуватися ОДНОЧАСНО для виникнення deadlock. Якщо хоча б одна умова порушена — deadlock неможливий.

4 умови Коффмана

#	Умова	Просте пояснення
1	Mutual Exclusion (взаємне виключення)	Ресурс може зайняти лише один потік. Чому це важливо: якщо ресурс спільний (наприклад, read-only дані), кілька потоків можуть працювати одночасно без очікування
2	Hold and Wait (утримання та очікування)	Потік уже тримає один ресурс і запитує ще один, не відпускаючи перший. Це створює “точку блокування” — потік не рухається вперед, але й не звільняє те, що вже має
3	No Preemption (відсутність витіснення)	JVM чи ОС не можуть примусово забрати ресурс у потоку. synchronized, наприклад, не має таймауту — якщо потік захопив лок, лише він сам може його відпустити
4	Circular Wait (циклічне очікування)	Потоки чекають один одного по колу: T1 чекає ресурс від T2, T2 чекає ресурс від T1. Без кола — deadlock неможливий

Приклад

// Потік 1:
synchronized(resourceA) {   // Захоплює resourceA — Mutual Exclusion: ніхто інший не увійде
    synchronized(resourceB) { // Тримає A, чекає B — Hold and Wait активовано
        // ...
    }
}

// Потік 2:
synchronized(resourceB) {   // Захоплює resourceB — Mutual Exclusion: ніхто інший не увійде
    synchronized(resourceA) { // Тримає B, чекає A — Hold and Wait активовано
        // ...
    }
}

// No Preemption: synchronized не можна "забрати" — лише власник відпустить
// Circular Wait: Потік 1 чекає B (у Потоку 2), Потік 2 чекає A (у Потоку 1) — КОЛО!
// Всі 4 умови виконані = DEADLOCK

Важливий факт

Теоретично, якщо порушити хоча б одну умову — deadlock неможливий. На практиці повне порушення не завжди досяжне: наприклад, Mutual Exclusion не можна порушити для запису у файл або оновлення лічильника. Тому стратегія залежить від типу ресурсу.

---

Коли НЕ варто вивчати умови Коффмана

• Ви пишете однопотоковий додаток — deadlock неможливий без кількох потоків
• Ви використовуєте лише immutable дані та функціональний стиль — немає спільного змінюваного стану, значить немає блокувань
• Ваша команда повністю перейшла на акторну модель (Akka) — актори не використовують спільні блокування за дизайном

Але в реальних Java-проєктах хоча б один synchronized або ReentrantLock завжди є, тому розуміння умов корисне для будь-якого Middle+ розробника.

---

Deadlock vs Livelock vs Starvation

Часто плутають ці поняття:

Проблема	Що відбувається	Приклад
Deadlock	Потоки назавжди заблокували один одного	T1 чекає T2, T2 чекає T1 — повна зупинка
Livelock	Потоки активні, але не просуваються	Двоє людей у коридорі намагаються розійтися, обидва крокують в один бік
Starvation	Потік ніколи не отримує ресурс	Низькопріоритетний потік завжди чекає високопріоритетних

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

---

Middle рівень

Детальний розбір умов

1. Mutual Exclusion (Взаємне виключення)

Ресурс може бути зайнятий лише одним потоком одночасно.

// Mutual Exclusion: synchronized
synchronized(lock) {
    // Лише один потік тут
}

// НЕМАЄ Mutual Exclusion: ReadWriteLock.readLock()
ReadWriteLock rwLock = new ReentrantReadWriteLock();
rwLock.readLock().lock();
// Безліч потоків можуть читати одночасно → deadlock на readLock неможливий!

Як порушити: Використовуйте ресурси зі спільним доступом (ReadLock, Atomic класи, lock-free структури).

2. Hold and Wait (Утримання та очікування)

Потік уже тримає один ресурс і запитує додаткові.

// Hold and Wait:
synchronized(lockA) {
    // Тримаємо lockA
    synchronized(lockB) { // Запитуємо lockB — HOLD AND WAIT
        // ...
    }
}

Як порушити: Запитуйте всі ресурси “одним пакетом”:

// Порушення: запитуємо все або нічого
if (lockA.tryLock() && lockB.tryLock()) {
    try {
        // Обидва захоплені — немає Hold and Wait
    } finally {
        lockB.unlock();
        lockA.unlock();
    }
} else {
    // Не вдалося — нічого не тримаємо
    lockA.unlock(); // Звільняємо якщо встигли
}

3. No Preemption (Відсутність витіснення)

Ресурс може бути звільнений лише добровільно власником.

// No Preemption: synchronized
synchronized(lock) {
    // JVM не може забрати lock у потоку
}

// Порушення: ReentrantLock можна "забрати" через interrupt
lock.lockInterruptibly();
try {
    // Потік можна перервати → lock буде звільнено
} finally {
    lock.unlock();
}

Як порушити: Використовуйте lockInterruptibly() або tryLock(timeout).

4. Circular Wait (Циклічне очікування)

Існує кільцева цепочка: T1 чекає ресурс від T2, T2 від T3, …, Tn від T1.

Потік 1 ──чекає lockB──→ Потік 2
  ▲                       │
  │                       │
  └────чекає lockA─────────┘

Як порушити: Введіть строгий порядок блокувань:

// Завжди захоплюємо у порядку зростання ID
void safeOperation(Resource r1, Resource r2) {
    Resource first = r1.id < r2.id ? r1 : r2;
    Resource second = r1.id < r2.id ? r2 : r1;

    synchronized(first) {
        synchronized(second) {
            // Неможливо створити цикл!
        }
    }
}

Стратегія порушення умов

Умова	Як порушити	Ціна
Mutual Exclusion	Lock-free, ReadLock	Середня
Hold and Wait	tryLock() all or nothing	Низька
No Preemption	lockInterruptibly()	Низька
Circular Wait	Lock Ordering	Найнижча

---

Senior рівень

Under the Hood: Resource Allocation Graph (RAG)

RAG — інструмент аналізу deadlock:

Процеси (P) ───→ Ресурси (R): запит
Ресурси (R) ───→ Процеси (P): призначення

P1 ──запит──→ R2 ──призначення──→ P2
▲                                  │
│                                  │
R1 ◄──призначення── P1 ──запит──→ P2
         │                          │
         └──────── R3 ◄─────────────┘

ЦИКЛ у RAG = Потенційний DEADLOCK

Dynamic Resource Allocation

У складних системах ресурси створюються динамічно (рядки у БД, об’єкти). Як визначити порядок?

// Хешування імен ресурсів для порядку
void safeOperation(Resource r1, Resource r2) {
    int h1 = System.identityHashCode(r1);
    int h2 = System.identityHashCode(r2);

    // Завжди у порядку хешу
    if (h1 < h2) {
        synchronized(r1) { synchronized(r2) { /* ... */ } }
    } else if (h1 > h2) {
        synchronized(r2) { synchronized(r1) { /* ... */ } }
    } else {
        // Колізія хешу — глобальний tie-breaker
        synchronized(globalTieBreaker) {
            synchronized(r1) { synchronized(r2) { /* ... */ } }
        }
    }
}

Lock-free як порушення Mutual Exclusion

// Замість synchronized (Mutual Exclusion):
synchronized(counter) { count++; }

// Використовуємо Atomic (немає ексклюзивного володіння):
AtomicInteger counter = new AtomicInteger(0);
counter.incrementAndGet();
// Немає блокування → немає Mutual Exclusion → немає deadlock!

Try-Lock як порушення Hold and Wait

ReentrantLock lock1 = new ReentrantLock();
ReentrantLock lock2 = new ReentrantLock();

public void safeOperation() {
    while (true) {
        if (lock1.tryLock()) {
            try {
                if (lock2.tryLock()) {
                    try {
                        // Обидва захоплені — робимо роботу
                        return;
                    } finally {
                        lock2.unlock();
                    }
                }
            } finally {
                lock1.unlock(); // Звільняємо перший — порушуємо Hold and Wait
            }
        }
        // Не вдалося — пауза і повтор
        Thread.sleep(10);
    }
}

Діагностика

Thread Dump Analysis

jstack <pid>

"Thread-1" BLOCKED
  - waiting to lock <0x000000076af0c8d0> (Resource B)
  - locked <0x000000076af0c8e0> (Resource A)

"Thread-2" BLOCKED
  - waiting to lock <0x000000076af0c8e0> (Resource A)
  - locked <0x000000076af0c8d0> (Resource B)

За адресами <0x000...> можна знайти конкретні об’єкти у heap через MAT.

False Deadlock

Іноді інструменти моніторингу можуть помилково прийняти довгу операцію за deadlock:

Симптоми "deadlock":
- Потоки BLOCKED довгий час
- Немає прогресу

Але це НЕ deadlock якщо:
- Важкий SQL запит (хвилини)
- GC pause (може бути довгим)
- I/O timeout

Програмна детекція

public class DeadlockDetector {
    public static Optional<DeadlockInfo> detect() {
        ThreadMXBean mxBean = ManagementFactory.getThreadMXBean();
        long[] ids = mxBean.findDeadlockedThreads();

        if (ids != null) {
            return Optional.of(new DeadlockInfo(ids, mxBean));
        }
        return Optional.empty();
    }

    // Warning: дорога операція — не викликати часто!
}

Best Practices

1. Lock Ordering — найнадійніший спосіб (порушує Circular Wait)
2. tryLock(timeout) — порушує Hold and Wait + No Preemption
3. Lock-free структури — порушує Mutual Exclusion
4. Один глобальний лок — порушує Circular Wait (але знижує паралелізм)
5. Thread-specific resources — шардування, незалежні дані
6. Моніторте через ThreadMXBean — але не занадто часто
7. Аналізуйте RAG при проєктуванні — запобігайте на рівні архітектури

---

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

Обов’язково знати:

• 4 умови Коффмана: Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait — всі мають виконуватися ОДНОЧАСНО
• Порушення хоча б однієї умови робить deadlock неможливим
• Lock Ordering (упорядкування блокувань) — порушення Circular Wait — найнадійніший спосіб запобігання
• TryLock порушує Hold and Wait, lockInterruptibly — No Preemption
• Для діагностики: jstack <pid>, ThreadMXBean.findDeadlockedThreads()
• Deadlock vs Livelock vs Starvation: deadlock — повна зупинка, livelock — активність без прогресу, starvation — потік ніколи не отримує ресурс
• Resource Allocation Graph (RAG): цикл у графі = потенційний deadlock

Часті уточнюючі запитання:

• Чи можна порушити Mutual Exclusion? — Так, через lock-free структури (Atomic, ConcurrentHashMap) або ReadWriteLock.readLock()
• Як виявити deadlock у production? — ThreadMXBean.findDeadlockedThreads(), jstack, JFR events, моніторинг BLOCKED потоків
• Що таке false deadlock? — Коли інструменти моніторингу плутають довгу операцію (важкий SQL, GC pause) з deadlock
• Як hashCode-колізія впливає на Lock Ordering? — При збігу identityHashCode двох об’єктів потрібен глобальний tie-breaker (додатковий лок)

Червоні прапорці (НЕ говорити):

• ❌ “Deadlock — це випадкова проблема” — ні, це детермінований наслідок 4 умов
• ❌ “synchronized можна перервати через interrupt()” — synchronized НЕ підтримує interrupt, потрібен ReentrantLock
• ❌ “Deadlock можна обробити всередині JVM без перезапуску” — у більшості випадків deadlock потребує restart JVM
• ❌ “Якщо використовувати ReentrantLock замість synchronized — deadlock неможливий” — ReentrantLock лише дає більше інструментів, але deadlock все ще можливий при неправильному використанні

Пов’язані теми:

• [[20. Як запобігти deadlock]]
• [[21. Що таке race condition]]
• [[22. Як уникнути race condition]]
• [[27. В чому різниця між Thread та Runnable]]
• [[28. Що таке Callable та Future]]