05.死锁了怎么办?

前面讲到使用Account.class作为互斥锁,来解决银行业务里面的转账问题,虽然这个方法不存在并发问题,但是所有账户的转账操作都是串行的.例如账户A转账户B,账户C转帐户D这两个操作在现实世界里时可以并行的,但是在这个方案却被串行化了,这样的话性能太差了!

在现实世界里找答案.

现实中账户转账操作时支持并发的.而且绝对是真正的并行.

在古代账户的形式就是一个账本,每个账户都有一个账本.这些账本统一放在文件架上.银行柜员在给我们做转账时,要去文件架上把转出账本和转入账本都拿到手,然后做转账.这个柜员拿账本可能遇到三种情况:

1.文件架上恰好有转出账本和转入账本,那就同时拿走.

2.如果只有两本中的其中一本,那就先拿一本,同时等其他柜员把另外一本送回来.

3,两本都没有,柜员等着两本都被送回来.

上面的例子在编程世界怎么实现?其实用两把锁就可以了.转出账本一把,转入账本另一把.在transfer()方法内部,首先尝试锁定转出账户this(先把转出账本拿到手),然后尝试锁定转入账户target(再把转入账本拿到手),只有当两者都成功时,才执行转账操作.如下图:

这样账户A转帐户B和账户C转帐户D两个转账操作就可以并行了.

没有免费的午餐!

上面看上去很完美,相对于用Account.class作为互斥锁,锁定的范围太大,而锁定两个账户范围就小多了,这样的锁叫细粒度锁.使用细粒度锁可以提高并行度，是性能优化的一个重要手段.

使用细粒度锁是有代价的，这个代价就是可能会导致死锁。

特殊场景:如果有客户找柜员张三做个转账业务：账户 A 转账户 B 100 元，此时另一个客户找柜员李四也做个转账业务：账户 B 转账户 A100 元，于是张三和李四同时都去文件架上拿账本，这时候有可能凑巧张三拿到了账本 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 会无期限地等待下去，也就是我们所说的死锁了。

如何预防死锁

并发程序一旦死锁，一般没有特别好的方法，很多时候我们只能重启应用。因此，解决死锁问题最好的办法还是规避死锁。

只有以下四个条件都发生时才会出现死锁:

1. 互斥，共享资源 X 和 Y 只能被一个线程占用；

2. 占有且等待，线程 T1 已经取得共享资源 X，在等待共享资源 Y 的时候，不释放共享资源 X；

3. 不可抢占，其他线程不能强行抢占线程 T1 占有的资源；

4. 循环等待，线程 T1 等待线程 T2 占有的资源，线程 T2 等待线程 T1 占有的资源，就是循环等待

反过来分析，也就是说只要我们破坏其中一个，就可以成功避免死锁的发生

1.互斥这个条件我们没有办法破坏，因为我们用锁为的就是互斥。

2. 对于“占用且等待”这个条件，我们可以一次性申请所有的资源，这样就不存在等待了。

3.对于“不可抢占”这个条件，占用部分资源的线程进一步申请其他资源时，如果申请不到，可以主动释放它占有的资源，这样不可抢占这个条件就破坏掉了。

4.对于“循环等待”这个条件，可以靠按序申请资源来预防。所谓按序申请，是指资源是有线性顺序的，申请的时候可以先申请资源序号小的，再申请资源序号大的，这样线性化后自然就不存在循环了。

1. 破坏占用且等待条件

要破坏这个条件，可以一次性申请所有资源。可以增加一个账本管理员，然后只允许账本管理员从文件架上拿账本，也就是说柜员不能直接在文件架上拿账本，必须通过账本管理员才能拿到想要的账本。例如，张三同时申请账本 A 和 B，账本管理员如果发现文件架上只有账本 A，这个时候账本管理员是不会把账本 A 拿下来给张三的，只有账本 A 和 B 都在的时候才会给张三。这样就保证了“一次性申请所有资源”。

对应到编程领域，“同时申请”这个操作是一个临界区，我们也需要一个角色（Java 里面的类）来管理这个临界区，我们就把这个角色定为 Allocator。它有两个重要功能，分别是：同时申请资源 apply() 和同时释放资源 free()。账户 Account 类里面持有一个 Allocator 的单例（必须是单例，只能由一个人来分配资源）。当账户 Account 在执行转账操作的时候，首先向 Allocator同时申请转出账户和转入账户这两个资源，成功后再锁定这两个资源；当转账操作执行完，释放锁之后，我们需通知 Allocator 同时释放转出账户和转入账户这两个资源。具体的代码实现如下

2. 破坏不可抢占条件

破坏不可抢占条件看上去很简单，核心是要能够主动释放它占有的资源，这一点 synchronized是做不到的。原因是 synchronized 申请资源的时候，如果申请不到，线程直接进入阻塞状态了，而线程进入阻塞状态，啥都干不了，也释放不了线程已经占有的资源。

Java 在语言层次确实没有解决这个问题，不过在 SDK 层面还是解决了的，java.util.concurrent 这个包下面提供的 Lock 是可以轻松解决这个问题的。

3. 破坏循环等待条件

破坏这个条件，需要对资源进行排序，然后按序申请资源。这个实现非常简单，我们假设每个账户都有不同的属性 id，这个 id 可以作为排序字段，申请的时候，我们可以按照从小到大的顺序来申请。比如下面代码中，①~⑥处的代码对转出账户（this）和转入账户（target）排序，然后按照序号从小到大的顺序锁定账户。这样就不存在“循环”等待了。

总结

利用现实世界的模型来构思解决方案

了用细粒度锁来锁定多个资源时，要注意死锁的问题。

上面转账那个例子，我们破坏占用且等待条件的成本就比破坏循环等待条件的成本高，破坏占用且等待条件，我们也是锁了所有的账户，而且还是用了死循环 while(!actr.apply(this, target));方法，不过好在 apply() 这个方法基本不耗时。在转账这个例子中，破坏循环等待条件就是成本最低的一个方案。所以我们在选择具体方案的时候，还需要评估一下操作成本，从中选择一个成本最低的方案