05一不小心就死锁了，怎么办？

　　上篇文章中，我们用Account.class 作为互斥锁，来解决银行间转账问题，虽然不存在并发问题，但是所有账号的转账都是串行的，例如账户A 转账户 B、账户 C 转账户 D 这两个转账操作现实世界里是可以并行的， 但是在这个方案里却被串行化了，性能太差。
　　试想互联网支付盛行的当下，8 亿网民每人每天一笔交易，每天就是 8 亿笔交易； 每笔交易都对应着一次转账操作，8 亿笔交易就是 8 亿次转账操作， 也就是说平均到每秒就是近 1 万次转账操作，若所有的转账操作都串行，性能完全不能接受。
　　现实世界中，账户的转账是支持并发的，而且是真正的并行，所有窗口都可以转账操作，那么如何实现呢？
　　我们试想在古代，没有信息化，账户的存在形式真的就是一个账本，而且每个账户都有一个账本，这些账本都统一存放在文件架上，银行柜员在给我们做转账时，要去文件夹上把转出账本和转入账本都拿到手，然后做转账。这个 柜员在拿账本的时候可能遇到以下三种情况：
　　1、文件架上恰好有转出账本和装入账本，那就直接拿走
　　2、如果文件架上只有转出账本和转入账本之一，那这个柜员就拿着这个账本，等待其他柜员把另一个账本还回来
　　3、转出账本和转入账本都没有，那智能等待其他柜员把两个账本都拿回来
　　上面这个过程在编程世界里怎么实现呢？其实用两把锁就实现了，转出账本一把，转入账本一把，在 transfer() 方法内部，我们首先尝试锁定转出账户 this（先把转出账本拿到手），然后尝试锁定转入账户 target（再把转入账本拿到手），只有当两者都成功时，才执行转账操作。这个逻辑可以图形化为下图这个样子。
　　而至于详细的代码实现，如下所示。经过这样的优化后，账户 A 转账户 B 和账户 C 转账户 D 这两个转账操作就可以并行了。  class Account {   private int balance;   // 转账   void transfer(Account target, int amt){     // 锁定转出账户     synchronized(this) {                     // 锁定转入账户       synchronized(target) {                    if (this.balance > amt) {           this.balance -= amt;           target.balance += amt;         }       }     }   }  }
　　上面看起来实现很完美，上面的实现看起来很美，并且也算是将锁用的出神入化了，相对于用 Account.class 作为互斥锁，锁定的范围太大，而我们锁定两个账户范围就小多了，这样的锁，上一章我们介绍过，叫细粒度锁。使用细粒度锁可以提高并行度，是性能优化的一个重要手段。
　　这个时候你就开始警觉了，使用细粒度锁 这么简单，有这样的好事，是不是也要付出点什么代价呢？并发编程就是要时刻保持警惕！
　　的确，使用细粒度锁是有代价的，这个代价就是可能会导致死锁。
　　在详细介绍死锁之前，我们先看看现实世界里的一种特殊场景。如果有客户找柜员张三做个转账业务：账户 A 转账户 B 100 元，此时另一个客户找柜员李四也做个转账业务：账户 B 转账户 A 100 元，于是张三和李四同时都去文件架上拿账本，这时候有可能凑巧张三拿到了账本 A，李四拿到了账本 B。张三拿到账本 A 后就等着账本 B（账本 B 已经被李四拿走），而李四拿到账本 B 后就等着账本 A（账本 A 已经被张三拿走），他们要等多久呢？他们会永远等待下去…因为张三不会把账本 A 送回去，李四也不会把账本 B 送回去。我们姑且称为死等吧。
　　现实世界里死等，就是编程领域的死锁了，死锁的一个比较专业的定义是：一组相互竞争的资源互相等待，导致永久阻塞的现象。
　　上面转账的代码是怎么发生死锁的呢？我们假设线程 T1 执行账户 A 转账户 B 的操作，账户 A.transfer(账户 B)；同时线程 T2 执行账户 B 转账户 A 的操作，账户 B.transfer(账户 A)。当 T1 和 T2 同时执行完①处的代码时，T1 获得了账户 A 的锁（对于 T1，this 是账户 A），而 T2 获得了账户 B 的锁（对于 T2，this 是账户 B）。之后 T1 和 T2 在执行②处的代码时，T1 试图获取账户 B 的锁时，发现账户 B 已经被锁定（被 T2 锁定），所以 T1 开始等待；T2 则试图获取账户 A 的锁时，发现账户 A 已经被锁定（被 T1 锁定），所以 T2 也开始等待。于是 T1 和 T2 会无期限地等待下去，也就是我们所说的死锁了。  class Account {   private int balance;   // 转账   void transfer(Account target, int amt){     // 锁定转出账户     synchronized(this){     ①       // 锁定转入账户       synchronized(target){ ②         if (this.balance > amt) {           this.balance -= amt;           target.balance += amt;         }       }     }   }  }
　　关于这种现象，我们还可以借助资源分配图来可视化锁的占用情况（资源分配图是个有向图，它可以描述资源和线程的状态）。其中，资源用方形节点表示，线程用圆形节点表示；资源中的点指向线程的边表示线程已经获得该资源，线程指向资源的边则表示线程请求资源，但尚未得到。转账发生死锁时的资源分配图就如下图所示，一个＂各据山头死等＂的尴尬局面。
　　如何预防死锁呢？并发程序一般死锁，没有其他办法，很多时候只能重启，因此解决死锁最好的办法还是规避死锁。那么如何规避呢？要规避死锁就要分析死锁发生的条件，有个叫 Coffman 的牛人早就总结过了，只有以下这四个条件都发生时才会出现死锁：  互斥，共享资源 X 和 Y 只能被一个线程占用；  占有且等待，线程 T1 已经取得共享资源 X，在等待共享资源 Y 的时候，不释放共享资源 X；  不可抢占，其他线程不能强行抢占线程 T1 占有的资源；  循环等待，线程 T1 等待线程 T2 占有的资源，线程 T2 等待线程 T1 占有的资源，就是循环等待。  反过来分析，只要我破坏其中一个，就可以成功避免死锁的发生。
　　其中，互斥这个条件我们没法破坏，因为我们用锁为的就是互斥，其他三个呢？  对于占有且等待，我们一次性申请所有资源，这样就不存在等待了。  对于不可抢占这个条件，占用部分线程的资源如果申请不到需要的其他资源就暂时的释放掉锁。  对于 循环等待，可以靠顺序申请资源锁的方式，所谓顺序申请就是资源是有线性顺序的，申请的时候可以申请资源号小的，再申请资源号大的，线性化后自然不存在循环了。  破坏占用且等待条件
　　从理论上来讲，要破坏这个条件，可以一次性申请所有资源，现实世界里，就拿我们前面的转账操作来说，它需要的资源有两个 一个是转入账户，一个是转出账户，这两个账户同时被申请时，我们该如何操作？
　　可以增加一个账本管理员，然后只允许账本管理员从文件架上取文件，也就是说柜员不能直接操作。例如，张三同时申请账本 A 和 B，账本管理员如果发现文件架上只有账本 A，这个时候账本管理员是不会把账本 A 拿下来给张三的，只有账本 A 和 B 都在的时候才会给张三。这样就保证了＂一次性申请所有资源＂。
　　对应到编程领域，＂同时申请＂这个操作是一个临界区， 我们也需要一个角色，来管理这个临界区。我们把这个角色定位为 Allocator ，它有两个重要功能：同时申请资源apply() 和同时释放资源free()。 账户 Account 类里面持有一个 Allocator 的单例（必须是单例，只能由一个人来分配资源）。  破坏不可抢占条件
　　破坏不可抢占条件看上去很简单，核心是要能够主动释放他占有的资源，这一点synchronized 是做不到的。原因是synchronized 申请资源的时候，如果申请不到，线程直接进入阻塞状态，而线程进入阻塞状态，啥也干不了，也释放不了线程已经占有的资源。
　　你可能会质疑，＂Java 作为排行榜第一的语言，这都解决不了？＂ 你的怀疑很有道理，Java 在语言层次确实没有解决这个问题，不过在 SDK 层面还是解决了的， java.util.concurrent 这个包下面提供的 Lock 是可以轻松解决这个问题的。关于这个话题，咱们后面会详细讲。  破坏循环等待条件
　　破坏这个条件需要对资源进行排序，然后按顺序申请，这个实现非常简单，我们假设每个账号都有id属性，然后申请锁的时候，就可以将ID作为排序字段，从大到小申请锁。  总结
　　当我们再编程世界遇到问题的时候，应该不局限于当下，向现实世界要答案，利用现实世界的模型来思考问题，往往能够看清问题的本质。
　　但是现实世界有些细节我们往往忽略，比如现实世界的人事智能的，拿不到锁可以沟通，但是程序是死的，就没那么智能，很容易死锁了。
　　所以沟通 这个细节就是我们容易忽略的，这也是导致死锁的根源了。