引言

在上一篇文章中，咱们用 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 的牛人早就总结过了，只有以下这四个条件都产生时才会呈现死锁：

1. 互斥，共享资源 X 和 Y 只能被一个线程占用；
2. 占有且期待，线程 T1 曾经获得共享资源 X，在期待共享资源 Y 的时候，不开释共享资源 X；
3. 不可抢占，其余线程不能强行抢占线程 T1 占有的资源；
4. 循环期待，线程 T1 期待线程 T2 占有的资源，线程 T2 期待线程 T1 占有的资源，就是循环期待。

反过来剖析，也就是说 只有咱们毁坏其中一个，就能够胜利防止死锁的产生。

其中，互斥这个条件咱们没有方法毁坏，因为咱们用锁为的就是互斥。不过其余三个条件都是有方法毁坏掉的，到底如何做呢？

• 对于“占用且期待”这个条件，咱们能够一次性申请所有的资源，这样就不存在期待了。
• 对于“不可抢占”这个条件，占用局部资源的线程进一步申请其余资源时，如果申请不到，能够被动开释它占有的资源，这样不可抢占这个条件就毁坏掉了。
• 对于“循环期待”这个条件，能够靠按序申请资源来预防。所谓按序申请，是指资源是有线性程序的，申请的时候能够先申请资源序号小的，再申请资源序号大的，这样线性化后天然就不存在循环了。

咱们曾经从实践上解决了如何预防死锁，那具体如何体现在代码上呢？上面咱们就来尝试用代码实际一下这些实践。

1. 毁坏占用且期待条件
从实践上讲，要毁坏这个条件，能够一次性申请所有资源。在事实世界里，就拿后面咱们提到的转账操作来讲，它须要的资源有两个，一个是转出账户，另一个是转入账户，当这两个账户同时被申请时，咱们该怎么解决这个问题呢？

能够减少一个账本管理员，而后只容许账本管理员从文件架上拿账本，也就是说柜员不能间接在文件架上拿账本，必须通过账本管理员能力拿到想要的账本。例如，张三同时申请账本 A 和 B，账本管理员如果发现文件架上只有账本 A，这个时候账本管理员是不会把账本 A 拿下来给张三的，只有账本 A 和 B 都在的时候才会给张三。这样就保障了“一次性申请所有资源”。

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

class Allocator {
        private List als =
                new ArrayList<>();

        // 一次性申请所有资源
        synchronized boolean apply(Object from, Object to) {if (als.contains(from) ||
                    als.contains(to)) {return false;} else {als.add(from);
                als.add(to);
            }
            return true;
        }

        // 偿还资源
        synchronized void free(Object from, Object to) {als.remove(from);
            als.remove(to);
        }
    }

    class Account {
        // actr 应该为单例
        private Allocator actr;
        private int balance;

        // 转账
        void transfer(Account target, int amt) {
            // 一次性申请转出账户和转入账户，直到胜利
            while (!actr.apply(this, target)) ;
            try {
                // 锁定转出账户
                synchronized (this) {
                    // 锁定转入账户
                    synchronized (target) {if (this.balance > amt) {
                            this.balance -= amt;
                            target.balance += amt;
                        }
                    }
                }
            } finally {actr.free(this, target)
            }
        }
    }

2. 毁坏不可抢占条件
毁坏不可抢占条件看上去很简略，外围是要可能被动开释它占有的资源，这一点 synchronized 是做不到的。起因是 synchronized 申请资源的时候，如果申请不到，线程间接进入阻塞状态了，而线程进入阻塞状态，啥都干不了，也开释不了线程曾经占有的资源。

你可能会质疑，“Java 作为排行榜第一的语言，这都解决不了？”你的狐疑很有情理，Java 在语言档次的确没有解决这个问题，不过在 SDK 层面还是解决了的，java.util.concurrent 这个包上面提供的 Lock 是能够轻松解决这个问题的。对于这个话题，咱们前面会具体讲。

3. 毁坏循环期待条件
毁坏这个条件，须要对资源进行排序，而后按序申请资源。这个实现非常简单，咱们假如每个账户都有不同的属性 id，这个 id 能够作为排序字段，申请的时候，咱们能够依照从小到大的程序来申请。比方上面代码中，①~⑥处的代码对转出账户（this）和转入账户（target）排序，而后依照序号从小到大的程序锁定账户。这样就不存在“循环”期待了。

 class Account {
        private int id;
        private int balance;

        // 转账
        void transfer(Account target, int amt) {
            Account left = this        ①
            Account right = target;    ②
            if (this.id > target.id) { ③
                left = target;           ④
                right = this;            ⑤
            }                          ⑥
            // 锁定序号小的账户
            synchronized (left) {
                // 锁定序号大的账户
                synchronized (right) {if (this.balance > amt) {
                        this.balance -= amt;
                        target.balance += amt;
                    }
                }
            }
        }
    }

小结

当咱们在编程世界里遇到问题时，应不局限于当下，能够换个思路，向事实世界要答案，利用事实世界的模型来构思解决方案，这样往往可能让咱们的计划更容易了解，也更可能看清楚问题的实质。

然而事实世界的模型有些细节往往会被咱们漠视。因为在事实世界里，人太智能了，以至有些细节切实是显得太不重要了。在转账的模型中，咱们为什么会漠视死锁问题呢？起因次要是在事实世界，咱们会交换，并且会很智能地交换。而编程世界里，两个线程是不会智能地交换的。所以在利用事实模型建模的时候，咱们还要认真比照事实世界和编程世界里的各角色之间的差别。

咱们明天这一篇文章次要讲了 用细粒度锁来锁定多个资源时，要留神死锁的问题。这个就须要你能把它强化为一个思维定势，遇到这种场景，马上想到可能存在死锁问题。当你晓得危险之后，才有机谈判如何预防和防止，因而，辨认出危险很重要。

预防死锁次要是毁坏三个条件中的一个，有了这个思路后，实现就简略了。但仍需注意的是，有时候预防死锁老本也是很高的。例如下面转账那个例子，咱们毁坏占用且期待条件的老本就比毁坏循环期待条件的老本高，毁坏占用且期待条件，咱们也是锁了所有的账户，而且还是用了死循环 while(!actr.apply(this, target)); 办法，不过好在 apply()这个办法根本不耗时。在转账这个例子中，毁坏循环期待条件就是老本最低的一个计划。

所以咱们在抉择具体计划的时候，还须要评估一下操作老本，从中抉择一个老本最低的计划。