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

Что такое deadlock (взаимная блокировка)

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

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

🟢 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, когда два потока одновременно захватывают один замок, не могут взять второй, одновременно отпускают первый и повторяют это бесконечно.

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