10.1 死锁

每个人都想拥有其他人需要的资源，同时又等待其他人已经拥有的资源，并且每个人在获取所有需要的资源之前都不会放弃已经拥有的资源

• 过度地使用加锁，可能导致锁顺序死锁（Lock-Ordering Deadlock）
• 使用线程池和信号量来限制对资源的使用等限制行为可能会导致资源死锁（Resource Deadlock）
• 数据库系统的设计中考虑了监测死锁以及从死锁中恢复：选择一个牺牲者并放弃这个事物。可以重新执行被强行终止的事物。
• JVM 在解决死锁问题上没有DB那么强大，线程就永远不能再使用了。
• 当死锁出现时，往往是在最糟糕的时候——高负载情况下。

10.1.1锁顺序死锁

原因：2个线程试图以不同的顺序来获得相同的锁。

程序清单10-1 简单的锁顺序死锁（不要这么做）

//注意，容易发生死锁
public class LeftRightDeadlock {
    private final Object left = new Object();
    private final Object right = new Object();
    
    public void leftRight() {
        synchronized (left) {
            synchronized (right) {
                //TODO doSomething();
            }
        }
    }
    
    public void rightLeft() {
        synchronized (right) {
            synchronized (left) {
                //TODO doSomething();
            }
        }
    }
}

10.1.2动态的锁顺序死锁

程序清单10-2 动态的锁顺序死锁（不要这么做）

A线程：transferMoney(myAccount, yourAccount, 10);
B线程：transferMoney(yourAccount,myAccount, 20);

public class DynamicOrderDeadlock {
    public void transferMoney(Account fromAccount, 
                              Account toAccount, 
                              DollarAmount amount) 
            throws InsufficientResourcesException {
        synchronized (fromAccount) {
            synchronized (toAccount) {
                if(fromAccount.getBalance().compareTo(amount) < 0) {
                    throw new InsufficientResourcesException();
                } else {
                    fromAccount.debit(amount);
                    toAccount.credit(amount);
                }
            }
        }
    }
}

程序清单10-3 通过所顺序来避免死锁

//程序清单10-3 通过所顺序来避免死锁
    private static final Object tieLock = new Object();

    public void transferMoney2(Account fromAccount, Account toAccount, DollarAmount amount)
            throws InsufficientResourcesException {
        //----------方法内部类实现真正的业务逻辑----------
        class Helper {
            public void transferMoney2() throws InsufficientResourcesException {
                if (fromAccount.getBalance().compareTo(amount) < 0) {
                    throw new InsufficientResourcesException();
                } else {
                    fromAccount.debit(amount);
                    toAccount.credit(amount);
                }
            }
        }
        
        //---------以下代码只用来实现锁排序-----------
        
        int fromHash = System.identityHashCode(fromAccount);
        int toHash = System.identityHashCode(toAccount);
        //按照统一的规则定义锁顺序，而不是根据参数的先后顺序
        if(fromHash < toHash)
            synchronized (fromAccount) {
                synchronized (toAccount) {
                    new Helper().transferMoney2();
                }
            }
        else if(fromHash > toHash)
            synchronized (toAccount) {
                synchronized (fromAccount) {
                    new Helper().transferMoney2();
                }
            }
        else if(fromHash == toHash) //在极少数情况下，2个对象可能有相同的散列值
            /*
             * 加时赛(TieBreaking[打破僵局])锁，保证每次只有一个线程以未知的顺序获得下面2个锁
             * 经常有散列冲突的情况，这里可能会成为性能瓶颈
             * 不过System.identityHashCode中出现散列冲突的概率很低，
             * 因此这项技术以很小的代价，换来了最大的安全性
             */
            synchronized (tieLock) {
                synchronized (fromAccount) {
                    synchronized (toAccount) {
                        new Helper().transferMoney2();
                    }
                }
            }
    }

程序清单10-4 在典型条件下会发生死锁的循环???没看懂!!!

public class DemonstrateDeadlock {
    private static final int NUM_THREADS = 20;
    private static final int NUM_ACCOUNTS = 5;
    private static final int NUM_ITERATIONS = 100_0000;
    
    public static void main(String[] args) {
        final Random rnd = new Random();
        final Account[] accounts = new Account[NUM_ACCOUNTS];
        
        for (int i = 0; i < accounts.length; i++)
            accounts[i] = new Account();
        
        class TransferThread extends Thread {
            @Override
            public void run() {
                for (int i = 0; i < NUM_ITERATIONS; i++) {
                    int fromAcct = rnd.nextInt(NUM_ACCOUNTS);
                    int toAcct = rnd.nextInt(NUM_ACCOUNTS);
                    DollarAmount amount = new DollarAmount(new BigDecimal(rnd.nextInt()));
                    DynamicOrderDeadlock transfer = new DynamicOrderDeadlock();
                    try {
                        transfer.transferMoney2(accounts[fromAcct], accounts[toAcct], amount);
                    } catch (InsufficientResourcesException e) {
                        e.printStackTrace();
                    };
                }
                super.run();
            }
        }
        
        for (int i = 0; i < NUM_THREADS; i++)
            new TransferThread().start();
    }
}

10.1.3对象之间协作死锁

程序清单10-5 在互相协作对象之间的锁顺序死锁（不要这么做）

Taxi类的setLocation()的锁顺序和Dispatcher. getImage()的锁的顺序是相反的
若2个线程分别调用这2个方法，则有可能会出现死锁

import java.util.HashSet;
import java.util.Set;

import net.jcip.annotations.GuardedBy;
//程序清单10-5 在互相协作对象之间的锁顺序死锁（不要这么做）
public class Taxi {
    @GuardedBy("this")
    private Point location,destination;
    private final Dispatcher dispatcher;

    public Taxi(Dispatcher dispatcher) {
        this.dispatcher = dispatcher;
    }
    
    public synchronized Point getLocation() {
        return location;
    }
    //线程在收到GPS接收器的更新事件时更新车辆位置
    public synchronized void setLocation(Point location) { //现获取taxi的内置锁：this
        this.location = location;
        if(location.equals(destination)) //判断是否到达目的地
            //本方法也是synchronized的，所以就出现了嵌套锁
            dispatcher.notifyAvaliable(this);//获取dispatcher的锁
    }
    
}

class Point{}

class Dispatcher {
    @GuardedBy("this")private final Set<Taxi> taxis;
    @GuardedBy("this")private final Set<Taxi> avaliableTaxis;
    
    public Dispatcher() {
        this.taxis = new HashSet<>();
        this.avaliableTaxis = new HashSet<>();
    }
    
    public synchronized void notifyAvaliable(Taxi taxi) {
        avaliableTaxis.add(taxi);
    }
    public synchronized Image getImage() { //先获取Dispatcher内置锁:this
        Image image = new Image();
        for(Taxi taxi : taxis)
            image.drawMarker(taxi.getLocation());//再获取taxi的锁
        return image;
    }
    
}
class Image {
    public void drawMarker(Point point) {
        //TODO .... 
    }
}

10.1.4 开放调用

如果在调用某个方法时不需要持有锁，这种调用被称为开放调用（Open Call）:
指不在方法声明上➕锁，但可以在方法内使用更细粒度的代码块儿
开放调用避免死锁的方法，类似于采用封装机制来提供线程安全的方法。

程序清单10-6 通过公开调用来避免在相互协作的对象之间产生死锁

import java.util.HashSet;
import java.util.Set;

import net.jcip.annotations.GuardedBy;

public class Taxi2 {
    @GuardedBy("this")
    private Point location,destination;
    private final Dispatcher2 dispatcher;

    public Taxi2(Dispatcher2 dispatcher) {
        this.dispatcher = dispatcher;
    }
    
    public synchronized Point getLocation() {
        return location;
    }
    //线程在收到GPS接收器的更新事件时更新车辆位置
    public void setLocation(Point location) { //现获取taxi的内置锁：this
        boolean reachedDestination = false;
        synchronized (this) {
            this.location = location;
            if(location.equals(destination))//判断是否到达目的地
                reachedDestination = true;
        }
        //notifyAvaliable获取Dispatcher2的内置锁，但是但是并没有再嵌套Taxi2的内置锁内
        if(reachedDestination)
            dispatcher.notifyAvaliable(this);
    }
}

class Dispatcher2 {
    @GuardedBy("this")private final Set<Taxi2> taxis;
    @GuardedBy("this")private final Set<Taxi2> avaliableTaxis;
    //....
    public Dispatcher2() {
        this.taxis = new HashSet<>();
        this.avaliableTaxis = new HashSet<>();
    }
    
    public synchronized void notifyAvaliable(Taxi2 taxi) {
        avaliableTaxis.add(taxi);
    }
    public Image getImage() {
        Set<Taxi2> copy;
        synchronized (this) {
            copy = new HashSet<>(taxis);
        }
        Image image = new Image();
        for(Taxi2 taxi : copy)
            //getLocation获取taxi的锁,但是并没有再嵌套Dispatcher2的内置锁内
            image.drawMarker(taxi.getLocation());
        return image;
    }
}

10.1.5 资源死锁

当多个线程在相同的资源集合上等待时，也会产生死锁
eg:

1. 一个任务连接2个数据库，并且请求2个资源时不保证遵循相同的顺序。
   线程A持有D1的连接并等待D2的连接
   线程B持有D2的连接并等待D1的连接
2. 线程饥饿死锁（Thread Starvation Deadlock） 8.1.1章节

10.2 死锁的避免与诊断

1. 每次至多只能获取，不会产生死锁（通常不现实）
2. 如果必须获取，必须考虑锁的顺序，尽量减少➕锁交互数量，写文档
3. 中：两阶段策略（Tow-Part Strategy）    原则：尽可能使用开放调用
     1) 首先：什么地方（Where）获取多个锁
     2) 然后：全局分析，确保顺序一致。

10.2.1 支持定时的锁

检测死锁且可以从死锁中恢复过来：显示使用Lock.tryLock() （参见第13章）来替代内置锁机制。

区别：
  1) 内置锁：没有获得锁，一直等待下去。
  2) 显示锁：没有获得锁，指定超时时限。超时后Lock.tryLock()返回失败信息

10.2.2 通过线程转储（Thread Dump）信息来分析死锁（JVM支持）

• Window：Ctrl + Break
• Unix：Ctrl + \ 或者 kill -3 ，输出到了/proc//fd/1
• jstack：jstack >> 输出文件

10.3其它活跃性危险

10.3.1 饥饿

当线程由于无法访问它所需要的资源而不能继续执行时，就发生了饥饿（Starvation）
导致原因：

优先级处理不当
持有锁时执行无法结束的结构（无限循环、无限制等待某个资源）

10.3.2 糟糕的响应性

GUI程序使用了后台线程（运行时间长），会与前台事件竞争CPU
不良的锁管理：eg:某线程长时间占用锁

10.3.3 活锁（Livelock）

活锁通常是由过度的错误恢复代码造成的。将不可修复的错误地认为可修复。
不会阻塞线程，但也不会继续执行完成，因为线程将不断地执行相同的操作，而且总是失败。
eg:调事物 ——>回滚 ——>再调——>再回滚——>再调——>再回滚——>......

2个过于礼貌的人，在路上面对面相遇了，彼此都让出对方的路，然而又在另一条路上相遇了......。因此他们就这样反复避让下去。

解决办法:
在重试机制中引入随机性。eg:都稍后再处理，稍后的时间随机。