八、死锁

一、什么是死锁(deadlock)？

死锁是因为使用了加锁机制所引发的。是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去，此时称系统处于死锁状态或系统产生了死锁。

二、死锁的必要条件

• 多个操作者（M>=2）操作多个资源（N>=2） M>=N
• 争夺资源的顺序不对
  严格意义上来说：

1.互斥
2.不剥夺
3.请求和保持
4.循环等待

三、代码示例

/**
 *类说明：演示普通账户的死锁和解决
 */
public class NormalDeadLock {
    private static Object valueFirst = new Object();//第一个锁
    private static Object valueSecond = new Object();//第二个锁

    //先拿第一个锁，再拿第二个锁
    private static void fisrtToSecond() throws InterruptedException {
        String threadName = Thread.currentThread().getName();
        synchronized (valueFirst){
            System.out.println(threadName + " 1st");
            Thread.sleep(100);
            synchronized (valueSecond){
                System.out.println(threadName + " 2nd");
            }
        }
    }

    //先拿第二个锁，再拿第一个锁
    private static void SecondToFisrt() throws InterruptedException {
        String threadName = Thread.currentThread().getName();
        //TODO
        synchronized (valueSecond){
            System.out.println(threadName + " 2nd");
            Thread.sleep(100);
            synchronized (valueFirst){
                System.out.println(threadName + " 1st");
            }
        }
    }

    private static class TestThread extends Thread{

        private String name;

        public TestThread(String name) {
            this.name = name;
        }

        public void run(){
            Thread.currentThread().setName(name);
            try {
                //先拿第一个锁再拿第二个锁
                SecondToFisrt();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }

    public static void main(String[] args) {
        Thread.currentThread().setName("TestDeadLock");
        TestThread testThread = new TestThread("SubTestThread");
        testThread.start();
        try {
            fisrtToSecond();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

运行结果：

死锁
可以看到，两个线程僵持着，程序没有死，两个线程都没有做事，阻塞了，而且没有打印任何的异常信息。你只会感觉到程序越来越慢。死锁一旦发生，问题的定位是很难的。
但是我们用的idea，可以看到如下的堆栈信息：
堆栈信息
可以看到一个线程持有了一把锁，在等待另一个锁。但是另一个线程持有的刚好是另一个线程需要的锁，等待的也是另一个线程持有的锁，他们互不释放，因此产生了死锁。
在生产环境中，我们可以用jdk提供的jstack命令去观察线程的堆栈。参考：https://www.cnblogs.com/wuchanming/p/7766994.html

四、解决方法

如果我们知道线程的锁的顺序，直接调整锁的顺序即可，但是如果是动态的场景，我们很难去发现线程锁的顺序。这种情况我们有两种解决方法：

• 增加一个第三个锁，先比较第一个和第二个锁的哈希值，如果双方没有比较出大小，就锁第三个锁，直到两把锁比较出大小为止。相当于NBA必须有输赢

/**
 *
 *类说明：不会产生死锁的安全转账
 * 谁的hash在前，就先锁谁
 */
public class SafeOperate implements ITransfer {

    private static Object tieLock = new Object();//第三把锁

    @Override
    public void transfer(UserAccount from, UserAccount to, int amount)
            throws InterruptedException {

        int fromHash = System.identityHashCode(from);
        int toHash = System.identityHashCode(to);

        if(fromHash<toHash){
            synchronized (from){
                System.out.println(Thread.currentThread().getName()+" get "+from.getName());
                Thread.sleep(100);
                synchronized (to){
                    System.out.println(Thread.currentThread().getName()+" get "+to.getName());
                    from.flyMoney(amount);
                    to.addMoney(amount);
                    System.out.println(from);
                    System.out.println(to);
                }
            }
        }else if(toHash<fromHash){
            synchronized (to){
                System.out.println(Thread.currentThread().getName()+" get"+to.getName());
                Thread.sleep(100);
                synchronized (from){
                    System.out.println(Thread.currentThread().getName()+" get"+from.getName());
                    from.flyMoney(amount);
                    to.addMoney(amount);
                    System.out.println(from);
                    System.out.println(to);
                }
            }
        }else{
            synchronized (tieLock){
                synchronized (from){
                    synchronized (to){
                        from.flyMoney(amount);
                        to.addMoney(amount);
                    }
                }
            }
        }
    }
}

• 使用tryLock()机制

/**
 *
 *类说明：不会产生死锁的安全转账第二种方法
 * 尝试拿锁
 */
public class SafeOperateToo implements ITransfer {

    @Override
    public void transfer(UserAccount from, UserAccount to, int amount)
            throws InterruptedException {
        Random r = new Random();
        while(true){
            if(from.getLock().tryLock()){
                System.out.println(Thread.currentThread().getName()
                        +" get"+from.getName());
                try{
                    if(to.getLock().tryLock()){
                        try{
                            System.out.println(Thread.currentThread().getName()
                                    +" get"+to.getName());
                            from.flyMoney(amount);
                            to.addMoney(amount);
                            System.out.println(from);
                            System.out.println(to);
                            break;
                        }finally{
                            to.getLock().unlock();
                        }
                    }
                }finally {
                    from.getLock().unlock();
                }

            }
            //为什么要休眠两毫秒？拿锁的过程会很长，反复地拿锁，这种情况会造成CPU的浪费。
            //有A,B两个线程，都需要去拿c,d两把锁
            //A持有了c锁，同事B持有了d锁；A想要获取d锁，于是去尝试，但是B想要获取c锁，于是也去尝试，尝试结束之后如果没有获取到锁的话，就将自己持有的锁释放掉，但是释放之后另一个需要相应锁的线程并不知道
            //然后接着又拿起自己的锁去尝试。。。。又去释放，造成了资源的浪费。
            //这种情况叫活锁，让拿锁的时机稍微错开一点点，打断了拿锁和释放锁之间的碰撞情况
            Thread.sleep(r.nextInt(2));
        }
    }
}

活锁（为什么需要休眠两毫秒？）

拿锁的过程会很长，反复地拿锁，这种情况会造成CPU的浪费。
有A,B两个线程，都需要去拿c,d两把锁。A持有了c锁，同事B持有了d锁；A想要获取d锁，于是去尝试，但是B想要获取c锁，于是也去尝试，尝试结束之后如果没有获取到锁的话，就将自己持有的锁释放掉，但是释放之后另一个需要相应锁的线程并不知道。然后接着又拿起自己的锁去尝试......又去释放，这样一直循环下去。造成了资源的浪费。
这种情况叫活锁，让拿锁的时机稍微错开一点点，打断了拿锁和释放锁之间的碰撞情况

五、线程饥饿

低优先级的线程总是拿不到执行时间以至于这个线程一直干等着得不到执行。