Что такое дедлок?

Дедлок (Deadlock)

Дедлок (взаимная блокировка) — это ситуация в многопоточной программе, когда два или несколько потоков бесконечно ждут друг друга, заблокировав необходимые им ресурсы. В результате все заблокированные потоки не могут продолжить выполнение, и программа зависает.

Классический пример: Проблема философов обедающих

Два потока (философа) и два ресурса (палочки для еды):

public class DiningPhilosophers {
    static class Fork { }
    
    static class Philosopher extends Thread {
        private Fork leftFork;
        private Fork rightFork;
        private String name;
        
        public Philosopher(String name, Fork leftFork, Fork rightFork) {
            this.name = name;
            this.leftFork = leftFork;
            this.rightFork = rightFork;
        }
        
        @Override
        public void run() {
            while (true) {
                synchronized (leftFork) {  // Берет левую палочку
                    System.out.println(name + " взял левую палочку");
                    
                    synchronized (rightFork) { // Ждет правую палочку
                        System.out.println(name + " ест...");
                        try { Thread.sleep(100); } catch (InterruptedException e) { }
                    }
                }
            }
        }
    }
    
    public static void main(String[] args) {
        Fork fork1 = new Fork();
        Fork fork2 = new Fork();
        
        Philosopher p1 = new Philosopher("Философ 1", fork1, fork2);
        Philosopher p2 = new Philosopher("Философ 2", fork2, fork1); // Порядок перевернут!
        
        p1.start();
        p2.start();
        // ДЕДЛОК! p1 ждет fork2, p2 ждет fork1
    }
}

Сценарий дедлока:

1. Философ 1 захватывает fork1 (leftFork)
2. Философ 2 захватывает fork2 (rightFork)
3. Философ 1 ждет fork2, но она занята философом 2
4. Философ 2 ждет fork1, но она занята философом 1
5. Оба зависают навечно!

Четыре условия дедлока (все должны быть выполнены)

1. Mutual Exclusion (Взаимное исключение)

Ресурс может использоваться только одним потоком за раз:

synchronized (lock) { // Только один поток за раз
    // критическая секция
}

2. Hold and Wait (Захват и ожидание)

Поток держит ресурс и ждет другого ресурса:

synchronized (lock1) {
    // Поток держит lock1
    synchronized (lock2) { // И ждет lock2
        // операция
    }
}

3. No Preemption (Нельзя отобрать)

Ресурс нельзя отобрать — только владелец может его отпустить:

// Нельзя принудительно отпустить synchronized блок
// Поток должен закончить блок сам

4. Circular Wait (Циклическое ожидание)

Потоки образуют цикл ожидания: A → B → C → A

Практический пример: Перевод денег между счетами

public class BankAccount {
    private int balance;
    
    public synchronized void withdraw(int amount) {
        balance -= amount;
    }
    
    public synchronized void deposit(int amount) {
        balance += amount;
    }
}

public class MoneyTransfer {
    public static void transfer(BankAccount from, BankAccount to, int amount) {
        synchronized (from) {   // Блокируем счет-отправитель
            synchronized (to) { // Ждем счета-получателя
                from.withdraw(amount);
                to.deposit(amount);
            }
        }
    }
    
    public static void main(String[] args) {
        BankAccount acc1 = new BankAccount();
        BankAccount acc2 = new BankAccount();
        
        Thread t1 = new Thread(() -> transfer(acc1, acc2, 100));
        Thread t2 = new Thread(() -> transfer(acc2, acc1, 100));
        // ДЕДЛОК! t1 ждет acc2, t2 ждет acc1
        
        t1.start();
        t2.start();
    }
}

Решения

1. Упорядочение ресурсов (Lock Ordering)

Всегда захватывай ресурсы в одном порядке:

public static void transfer(BankAccount from, BankAccount to, int amount) {
    BankAccount first, second;
    
    // Всегда берем счета в одном порядке (по hashCode)
    if (from.hashCode() < to.hashCode()) {
        first = from;
        second = to;
    } else {
        first = to;
        second = from;
    }
    
    synchronized (first) {
        synchronized (second) {
            // Теперь нет циклического ожидания!
            if (from == first) {
                from.withdraw(amount);
                to.deposit(amount);
            } else {
                to.withdraw(amount);
                from.deposit(amount);
            }
        }
    }
}

2. Таймауты (Timeout)

Отпусти ресурсы, если не можешь получить второй за отведенное время:

import java.util.concurrent.locks.ReentrantLock;

public class TimeoutTransfer {
    public static void transfer(ReentrantLock lock1, ReentrantLock lock2, int amount) {
        long timeout = 1; // секунда
        TimeUnit unit = TimeUnit.SECONDS;
        
        if (lock1.tryLock(timeout, unit)) {
            try {
                if (lock2.tryLock(timeout, unit)) {
                    try {
                        // Выполняем операцию
                    } finally {
                        lock2.unlock();
                    }
                } else {
                    System.out.println("Не удалось получить lock2, откатываем");
                }
            } finally {
                lock1.unlock();
            }
        } else {
            System.out.println("Не удалось получить lock1, откатываем");
        }
    }
}

3. ReentrantLock с tryLock

import java.util.concurrent.locks.ReentrantLock;

public class SafeTransfer {
    private ReentrantLock lock1 = new ReentrantLock();
    private ReentrantLock lock2 = new ReentrantLock();
    
    public void transfer(int amount) throws InterruptedException {
        while (true) {
            if (lock1.tryLock()) {
                try {
                    if (lock2.tryLock()) {
                        try {
                            // Успешно получили оба лока
                            System.out.println("Передача выполнена");
                            return;
                        } finally {
                            lock2.unlock();
                        }
                    }
                } finally {
                    lock1.unlock();
                }
            }
            // Если не удалось, повторим попытку
            Thread.sleep(10);
        }
    }
}

4. Использование высокоуровневых конструкций

import java.util.concurrent.*;

public class ConcurrentTransfer {
    private final ConcurrentHashMap<Integer, Integer> accounts = new ConcurrentHashMap<>();
    private final Semaphore semaphore = new Semaphore(1);
    
    public void transfer(int fromId, int toId, int amount) throws InterruptedException {
        semaphore.acquire();
        try {
            accounts.merge(fromId, -amount, Integer::sum);
            accounts.merge(toId, amount, Integer::sum);
        } finally {
            semaphore.release();
        }
    }
}

5. Используй Queue вместо синхронизации

import java.util.concurrent.*;

public class QueueBasedTransfer {
    private final BlockingQueue<Transaction> queue = new LinkedBlockingQueue<>();
    private final ExecutorService executor = Executors.newSingleThreadExecutor();
    
    public QueueBasedTransfer() {
        executor.submit(() -> {
            while (true) {
                try {
                    Transaction tx = queue.take();
                    // Обработка без конфликтов
                    processTransaction(tx);
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                    break;
                }
            }
        });
    }
}

Обнаружение дедлока

JStack — инструмент для диагностики:

jstack <pid>

Вывод покажет потоки в состоянии ожидания с указанием, какие локи они удерживают и ждут.

Резюме

• Дедлок — это ситуация, когда потоки бесконечно ждут друг друга
• Четыре условия должны быть выполнены одновременно
• Решения: упорядочение ресурсов, таймауты, высокоуровневые конструкции (Lock, Queue)
• Best practice: избегай вложенной синхронизации, используй конкурентные коллекции
• Тестирование: стресс-тесты помогают найти дедлоки на ранних этапах