Какие знаешь методы решения Deadlock?

Способы решения Deadlock (взаимная блокировка)

Deadlock — это ситуация, когда два или более потока находятся в бесконечном ожидании друг друга, невозможность продолжения работы. Это серьёзная проблема многопоточности. Существует несколько подходов к её решению.

Условия возникновения Deadlock

Для возникновения deadlock необходимо 4 условия (все одновременно):

1. Mutual Exclusion — ресурс не может использоваться несколькими потоками одновременно
2. Hold and Wait — поток удерживает ресурс и ждёт другого
3. No Preemption — ресурс нельзя забрать у потока
4. Circular Wait — циклические зависимости в очереди ресурсов

Классический пример Deadlock

public class DeadlockExample {
    static class Account {
        int id;
        double balance;
        
        Account(int id, double balance) {
            this.id = id;
            this.balance = balance;
        }
    }
    
    // ПРОБЛЕМА: Может произойти deadlock
    static void transferMoney(Account from, Account to, double amount) 
            throws InterruptedException {
        synchronized (from) {
            Thread.sleep(100);  // Имитация операции
            synchronized (to) {
                from.balance -= amount;
                to.balance += amount;
            }
        }
    }
    
    public static void main(String[] args) throws InterruptedException {
        Account account1 = new Account(1, 1000);
        Account account2 = new Account(2, 1000);
        
        // Поток 1: account1 -> account2
        Thread t1 = new Thread(() -> {
            try {
                transferMoney(account1, account2, 100);
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        });
        
        // Поток 2: account2 -> account1 (DEADLOCK!)
        Thread t2 = new Thread(() -> {
            try {
                transferMoney(account2, account1, 100);
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        });
        
        t1.start();
        t2.start();
        // Оба потока зависнут, ожидая друг друга
    }
}

1. Порядок захвата локов (Lock Ordering)

Самый простой и эффективный способ. Все потоки должны захватывать локи в одном порядке:

static void transferMoneyFixed(Account from, Account to, double amount) 
        throws InterruptedException {
    Account first = from.id < to.id ? from : to;
    Account second = from.id < to.id ? to : from;
    
    synchronized (first) {
        synchronized (second) {
            if (from == first) {
                from.balance -= amount;
                to.balance += amount;
            } else {
                from.balance -= amount;
                to.balance += amount;
            }
        }
    }
}

2. Использование ReentrantLock с timeout

Более гибкий способ. Позволяет отказаться от захвата лока если он заблокирован:

static class Account {
    int id;
    double balance;
    ReentrantLock lock = new ReentrantLock();
    
    Account(int id, double balance) {
        this.id = id;
        this.balance = balance;
    }
}

static void transferMoneyWithTimeout(Account from, Account to, 
        double amount, long timeout, TimeUnit unit) 
        throws InterruptedException {
    boolean fromLocked = false;
    boolean toLocked = false;
    
    try {
        fromLocked = from.lock.tryLock(timeout, unit);
        if (!fromLocked) {
            System.out.println("Could not acquire lock on source account");
            return;
        }
        
        toLocked = to.lock.tryLock(timeout, unit);
        if (!toLocked) {
            System.out.println("Could not acquire lock on target account");
            return;
        }
        
        from.balance -= amount;
        to.balance += amount;
        System.out.println("Transfer successful");
    } finally {
        if (toLocked) to.lock.unlock();
        if (fromLocked) from.lock.unlock();
    }
}

3. Иерархия локов (Lock Hierarchy)

Строгое упорядочение захвата ресурсов. Нижестоящие локи всегда захватываются первыми:

static class LockHierarchyAccount {
    private static int globalId = 0;
    private final int lockHierarchyLevel;
    int id;
    double balance;
    ReentrantLock lock = new ReentrantLock();
    
    LockHierarchyAccount(int id, double balance, int hierarchyLevel) {
        this.id = id;
        this.balance = balance;
        this.lockHierarchyLevel = hierarchyLevel;
    }
}

static void transferMoneyHierarchy(LockHierarchyAccount from, 
        LockHierarchyAccount to, double amount) throws InterruptedException {
    if (from.lockHierarchyLevel < to.lockHierarchyLevel) {
        from.lock.lock();
        try {
            to.lock.lock();
            try {
                from.balance -= amount;
                to.balance += amount;
            } finally {
                to.lock.unlock();
            }
        } finally {
            from.lock.unlock();
        }
    } else if (from.lockHierarchyLevel > to.lockHierarchyLevel) {
        to.lock.lock();
        try {
            from.lock.lock();
            try {
                from.balance -= amount;
                to.balance += amount;
            } finally {
                from.lock.unlock();
            }
        } finally {
            to.lock.unlock();
        }
    } else {
        throw new IllegalArgumentException("Cannot transfer between accounts with same hierarchy");
    }
}

4. Atomic переменные (Lock-Free)

Избегаем локов полностью. Используем атомарные операции для состояния без синхронизации:

static class AtomicAccount {
    int id;
    AtomicReference<Long> balance;
    
    AtomicAccount(int id, long initialBalance) {
        this.id = id;
        this.balance = new AtomicReference<>(initialBalance);
    }
    
    void transfer(AtomicAccount to, long amount) {
        boolean success = false;
        while (!success) {
            long fromBalance = this.balance.get();
            long toBalance = to.balance.get();
            
            if (fromBalance < amount) return;  // Недостаточно средств
            
            success = this.balance.compareAndSet(fromBalance, fromBalance - amount) &&
                      to.balance.compareAndSet(toBalance, toBalance + amount);
        }
    }
}

5. CopyOnWriteArrayList и ConcurrentHashMap

Использование thread-safe коллекций вместо ручной синхронизации:

// Вместо synchronized List
List<Transaction> transactions = new CopyOnWriteArrayList<>();

// Вместо synchronized Map
Map<Integer, Account> accounts = new ConcurrentHashMap<>();

// Безопасные операции
accounts.putIfAbsent(1, new Account(1, 1000));
accounts.computeIfPresent(1, (key, account) -> {
    account.balance += 100;
    return account;
});

6. Timeout и обработка исключений

Обнаружение и восстановление из deadlock ситуации:

static void transferMoneyWithRecovery(Account from, Account to, 
        double amount) throws InterruptedException {
    while (true) {
        try {
            transferMoneyWithTimeout(from, to, amount, 1, TimeUnit.SECONDS);
            break;  // Успех
        } catch (InterruptedException e) {
            System.out.println("Retrying transfer...");
            Thread.sleep(100);  // Экспоненциальная задержка
        }
    }
}

7. Обнаружение Deadlock (Debugging)

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

// JConsole, VisualVM, JProfiler
// Или программно:
ThreadMXBean bean = ManagementFactory.getThreadMXBean();
long[] deadlockedThreads = bean.findDeadlockedThreads();
if (deadlockedThreads != null && deadlockedThreads.length > 0) {
    System.out.println("Deadlock detected!");
    ThreadInfo[] infos = bean.getThreadInfo(deadlockedThreads);
    for (ThreadInfo info : infos) {
        System.out.println(info);
    }
}

Рекомендации

1. Минимизируй время под локом — захватывай лок как можно позже
2. Избегай вложенных локов — если возможно
3. Используй высокоуровневые конструкции — java.util.concurrent вместо synchronized
4. Тестируй многопоточность — стресс-тесты выявляют deadlocks
5. Мониторь потоки — используй JMX для отслеживания

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