Приведи пример DeadLock

# Deadlock в Java: примеры и способы избежания

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

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

public class DeadlockExample {
    
    static class Account {
        private long balance;
        private final Object lock = new Object();
        
        public Account(long balance) {
            this.balance = balance;
        }
        
        public void withdraw(long amount) {
            synchronized(lock) {
                balance -= amount;
            }
        }
        
        public void deposit(long amount) {
            synchronized(lock) {
                balance += amount;
            }
        }
    }
    
    // DEADLOCK СИТУАЦИЯ
    static class Bank {
        public static void transfer(Account from, Account to, long amount) {
            // Поток 1: блокирует from, потом хочет заблокировать to
            synchronized(from.lock) {
                System.out.println(Thread.currentThread().getName() + " locked " + from);
                
                // Имитируем задержку
                try { Thread.sleep(100); } catch (InterruptedException e) {}
                
                synchronized(to.lock) { // Может ждать бесконечно!
                    System.out.println(Thread.currentThread().getName() + " locked " + to);
                    from.withdraw(amount);
                    to.deposit(amount);
                }
            }
        }
    }
    
    public static void main(String[] args) {
        Account account1 = new Account(1000);
        Account account2 = new Account(2000);
        
        // Поток 1: transfer(account1, account2, 100)
        Thread t1 = new Thread(() -> {
            Bank.transfer(account1, account2, 100);
        }, "Thread-1");
        
        // Поток 2: transfer(account2, account1, 200)
        // Обратное направление!
        Thread t2 = new Thread(() -> {
            Bank.transfer(account2, account1, 200);
        }, "Thread-2");
        
        t1.start();
        t2.start();
        
        // Вывод:
        // Thread-1 locked Account@1
        // Thread-2 locked Account@2
        // ... программа зависает (DEADLOCK!)
        // Thread-1 ждёт lock Account@2 (который held Thread-2)
        // Thread-2 ждёт lock Account@1 (который held Thread-1)
    }
}

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

Для Deadlock нужны ВСЕ четыре условия:

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

Поток 1: locked[Lock A] → waiting[Lock B]
                           ↑
Поток 2:                   └→ locked[Lock B] → waiting[Lock A]
                                                    ↓
                            (циклическое ожидание)

Способы избежания Deadlock

1. Избежать циклического ожидания (рекомендуется)

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

static class BankFixed1 {
    // Решение: блокируем объекты в консистентном порядке
    public static void transfer(Account from, Account to, long amount) {
        Account first = from.id < to.id ? from : to;
        Account second = from.id < to.id ? to : from;
        
        synchronized(first.lock) {
            synchronized(second.lock) {
                if (from == first) {
                    from.withdraw(amount);
                    to.deposit(amount);
                } else {
                    to.deposit(amount);
                    from.withdraw(amount);
                }
            }
        }
    }
}

2. Использовать ReentrantLock с timeout

import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.TimeUnit;

static class AccountWithLock {
    private long balance;
    private final ReentrantLock lock = new ReentrantLock();
    
    public boolean transfer(AccountWithLock to, long amount, long timeout, TimeUnit unit) 
            throws InterruptedException {
        
        // Пытаемся заблокировать с timeout
        if (!this.lock.tryLock(timeout, unit)) {
            System.out.println("Could not acquire lock on " + this);
            return false;
        }
        
        try {
            if (!to.lock.tryLock(timeout, unit)) {
                System.out.println("Could not acquire lock on " + to);
                return false;
            }
            
            try {
                this.balance -= amount;
                to.balance += amount;
                return true;
            } finally {
                to.lock.unlock();
            }
        } finally {
            this.lock.unlock();
        }
    }
}

// Использование
AccountWithLock acc1 = new AccountWithLock(1000);
AccountWithLock acc2 = new AccountWithLock(2000);

boolean success = acc1.transfer(acc2, 100, 1, TimeUnit.SECONDS);
if (!success) {
    System.out.println("Transfer timeout, retry...");
}

3. Использовать один общий Lock

static class BankFixed2 {
    private static final Object globalLock = new Object();
    
    public static void transfer(Account from, Account to, long amount) {
        synchronized(globalLock) { // Один lock для всех
            from.withdraw(amount);
            to.deposit(amount);
        }
    }
}

// Минус: производительность упадёт
// Все трансферы будут последовательными

4. Использовать ConcurrentHashMap или других thread-safe структур

import java.util.concurrent.ConcurrentHashMap;

static class BankFixed3 {
    private ConcurrentHashMap<Integer, Long> accounts = new ConcurrentHashMap<>();
    
    public synchronized void transfer(int from, int to, long amount) {
        // ConcurrentHashMap работает без явной синхронизации
        long fromBalance = accounts.get(from);
        if (fromBalance >= amount) {
            accounts.put(from, fromBalance - amount);
            accounts.put(to, accounts.getOrDefault(to, 0L) + amount);
        }
    }
}

5. Использовать StampedLock (Java 8+)

import java.util.concurrent.locks.StampedLock;

static class AccountOptimized {
    private long balance;
    private final StampedLock lock = new StampedLock();
    
    public long getBalance() {
        long stamp = lock.tryOptimisticRead();
        long balance = this.balance;
        if (!lock.validate(stamp)) {
            // Optimistic read failed, retry with pessimistic read
            stamp = lock.readLock();
            try {
                balance = this.balance;
            } finally {
                lock.unlockRead(stamp);
            }
        }
        return balance;
    }
    
    public void transfer(AccountOptimized to, long amount) {
        long fromStamp = lock.writeLock();
        try {
            long toStamp = to.lock.writeLock();
            try {
                this.balance -= amount;
                to.balance += amount;
            } finally {
                to.lock.unlockWrite(toStamp);
            }
        } finally {
            lock.unlockWrite(fromStamp);
        }
    }
}

Обнаружение Deadlock

Вывод Stack Trace (Ctrl+Break в Windows, Ctrl+\ в Linux)

java.lang.Thread.State: BLOCKED
at java.lang.Object.wait(native method)
at BankFixed1.transfer(...)
- waiting to lock Account@1a2b3c (held by Thread-2)

java.lang.Thread.State: BLOCKED
at java.lang.Object.wait(native method)
at BankFixed1.transfer(...)
- waiting to lock Account@2d4e5f (held by Thread-1)

Программный поиск Deadlock

import java.lang.management.*;

public class DeadlockDetector {
    public static void detectDeadlock() {
        ThreadMXBean bean = ManagementFactory.getThreadMXBean();
        long[] threadIds = bean.findDeadlockedThreads();
        
        if (threadIds != null && threadIds.length > 0) {
            System.out.println("DEADLOCK DETECTED!");
            ThreadInfo[] infos = bean.getThreadInfo(threadIds);
            for (ThreadInfo info : infos) {
                System.out.println("Thread: " + info.getThreadName());
                System.out.println("State: " + info.getThreadState());
                System.out.println("Blocked on: " + info.getLockName());
            }
        }
    }
}

Правильный пример: Безопасный трансфер

public class SafeBank {
    static class Account {
        final int id;
        long balance;
        
        Account(int id, long balance) {
            this.id = id;
            this.balance = balance;
        }
    }
    
    // Правильное решение: консистентный порядок блокировки
    public static void transfer(Account from, Account to, long amount) {
        // Порядок на основе ID
        if (from.id < to.id) {
            synchronized(from) {
                synchronized(to) {
                    doTransfer(from, to, amount);
                }
            }
        } else {
            synchronized(to) {
                synchronized(from) {
                    doTransfer(from, to, amount);
                }
            }
        }
    }
    
    private static void doTransfer(Account from, Account to, long amount) {
        from.balance -= amount;
        to.balance += amount;
    }
    
    public static void main(String[] args) throws InterruptedException {
        Account acc1 = new Account(1, 1000);
        Account acc2 = new Account(2, 2000);
        
        Thread t1 = new Thread(() -> {
            for (int i = 0; i < 1000; i++) {
                transfer(acc1, acc2, 1);
            }
        });
        
        Thread t2 = new Thread(() -> {
            for (int i = 0; i < 1000; i++) {
                transfer(acc2, acc1, 1);
            }
        });
        
        t1.start();
        t2.start();
        
        t1.join();
        t2.join();
        
        System.out.println("Success! No deadlock.");
    }
}

Лучшие практики

1. Минимизируй количество locks — лучше один big lock, чем много маленьких
2. Держи locks минимальное время — сокращай critical section
3. Всегда блокируй в одинаковом порядке — если нужны A и B, всегда сначала A
4. Используй timeout — tryLock(timeout) вместо lock()
5. Избегай nested locks — если возможно
6. Используй higher-level конструкции — ReentrantReadWriteLock, Semaphore, ConcurrentHashMap
7. Тестируй многопоточность — используй tools типа Thread Weaver, jcstress

Итог

Deadlock — это серьёзная проблема в многопоточном коде. Главное правило:

Если нужны несколько locks, блокируй их в консистентном порядке или используй более высокоуровневые конструкции, которые это делают за тебя.