Deadlock — это ситуация, когда два или более потока навечно блокируют друг друга, каждый ждёт ресурс, который удерживается другим. В отличие от обычной конкурен за ресурсы (где поток просто waits какое-то время), 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 (нет exclusive владения):
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]]