阅读《java并发编程实战》第十章

例1： 简单的加锁顺序导致的死锁：

public class LeftRightDeadlock {
    private final Object left = new Object();
    private final Object right = new Object();
    
    public void leftRight() {
        synchronized (left) {
            synchronized (right) {
                System.out.println("do something");
            }
        }
    }
            
    public void rightLeft() {
        synchronized (right) {
            synchronized (left) {
                System.out.println("do something else");
            }
        }
    }
}

例2： 动态加锁顺序，导致的死锁：

class Account {
    private BigDecimal balance = new BigDecimal("1000");

    BigDecimal getBalance() {
        return balance;
    }

    public void debit(BigDecimal amount) {
        this.balance.subtract(amount);
    }

    public void credit(BigDecimal amount) {
        this.balance.add(amount);
    }
}

class InsufficientFundsException extends Exception {
}

public class DynamicTransferDeadlock {
    public static void transfer(Account from, Account to, BigDecimal amount) throws InsufficientFundsException {
        synchronized (from) {
            synchronized (to) {
                if (from.getBalance().compareTo(amount) < 0) {
                    throw new InsufficientFundsException();
                } else {
                    from.debit(amount);
                    to.credit(amount);
                }
            }
        }
    }

    // demo deadlock
    public static void main(String[] args) {
        final int numAccounts = 5;
        final int numTransactions = 20;
        final int numThreads = 20;
        final Random random = new Random();
        final Account[] accounts = new Account[numAccounts];
        for (int i = 0; i < numAccounts; i++) {
            accounts[i] = new Account();
        }
        Runnable transTask = () -> {
            for (int i = 0; i < numTransactions; i++) {
                int from = random.nextInt(numAccounts);
                int to = random.nextInt(numAccounts);
                BigDecimal amount = BigDecimal.valueOf(random.nextInt(1000));
                try {
                    transfer(accounts[from], accounts[to], amount);
                } catch (InsufficientFundsException e) {
                    throw new RuntimeException(e);
                }
            }
        };

        for (int i = 0; i < numThreads; i++) {
            new Thread(transTask).start();
        }
    }
}

运行之后发生死锁，使用jps查看进程号，然后jstack + 进程号打印线程堆栈信息，能看到检测到死锁。原因是：如果账户A 和 B 相互给对方转账，那么就会造成死锁。transfer方法的参数，它传入的参数顺序，影响了加锁的顺序。

例3：通过指定加锁顺序避免死锁

    public static Object tieLock = new Object();

    public static void safeTransfer(Account from, Account to, BigDecimal amount) throws InsufficientFundsException {
        int hashFrom = System.identityHashCode(from);
        int hashTo = System.identityHashCode(to);
        if (hashFrom < hashTo) {
            synchronized (from) {
                synchronized (to) {
                    helperTransfer(from, to, amount);
                }
            }
        } else if (hashFrom > hashTo){
            synchronized (to) {
                synchronized (from) {
                    helperTransfer(from, to, amount);
                }
            }
        } else { // same.
            synchronized (tieLock) {
                synchronized (from) {
                    synchronized (to) {
                        helperTransfer(from, to, amount);
                    }
                }
            }
        }
    }

    private static void helperTransfer(Account from, Account to, BigDecimal amount) throws InsufficientFundsException {
        if (from.getBalance().compareTo(amount) < 0) {
            throw new InsufficientFundsException();
        } else {
            from.debit(amount);
            to.credit(amount);
        }
    }

例4：两个对象之间协作，互相持有对方的锁，造成死锁。比较隐晦，难以发现。

class Point {}
class Image {
    public void drawMarker(Point location) {
        System.out.println("Driver in location: " + location);
    }
}
class Dispatcher {
    private final Set<Taxi> taxis = new HashSet<>();
    private final Set<Taxi> availableTaxis = new HashSet<>();

    public synchronized void notifyAvailable(Taxi taxi) {
        this.availableTaxis.add(taxi);
    }

    public synchronized Image getImage() {
        Image image = new Image();
        for (Taxi t : taxis) {
            image.drawMarker(t.getLocation());
        }
        return image;
    }
}

class Taxi {
    private Point location, destination;
    private final Dispatcher dispatcher;

    public Taxi(Dispatcher dispatcher) {
        this.dispatcher = dispatcher;
    }

    public synchronized Point getLocation() {
        return location;
    }

    public synchronized void setLocation(Point location) {
        this.location = location;
        if (location.equals(destination)) {
            dispatcher.notifyAvailable(this);
        }
    }
}

分析：Taxi的setLocation方法是同步的，需要获取Taxi的锁，然后内部调用dispatch.notifyAvailable()这个也是同步方法，需要获取dispatch实例的锁。

然后Dispatcher的getImage方法，是同步的，先获取dispatch实例的锁，然后内部执行时，调用t.getLocation()，因此又要获取taxi实例的锁。从而多线程下，同时执行 Taxi.setLocation() 和 Dispatcher.getImage() 方法有很大可能会造成死锁。

例5：两个对象之间协作导致死锁，例4的优化方案，通过公开调用来消除死锁

class Point {}
class Image {
    public void drawMarker(Point location) {
        System.out.println("Driver in location: " + location);
    }
}
class Dispatcher {
    private final Set<Taxi> taxis = new HashSet<>();
    private final Set<Taxi> availableTaxis = new HashSet<>();

    public synchronized void notifyAvailable(Taxi taxi) {
        this.availableTaxis.add(taxi);
    }

    public Image getImage() {
        Set<Taxi> copy;
        synchronized (this) {
             copy = new HashSet<>(taxis);
        }

        Image image = new Image();
        for (Taxi t : copy) {
            image.drawMarker(t.getLocation());
        }
        return image;
    }
}

class Taxi {
    private Point location, destination;
    private final Dispatcher dispatcher;

    public Taxi(Dispatcher dispatcher) {
        this.dispatcher = dispatcher;
    }

    public synchronized Point getLocation() {
        return location;
    }

    public void setLocation(Point location) {
        boolean reachDestination;
        synchronized (this) {
            this.location = location;
            reachDestination = location.equals(destination);
        }
        if (reachDestination) {
            dispatcher.notifyAvailable(this);
        }
    }
}

分析：Dispatcher的getImage方法变成非同步方法了，只是在内部加了一个同步块。这种方法叫开放调用，不需要首先获取对象的锁。在方法内部是按需获取。Taxi的setLocation也是同理。