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

死锁

老师，有个问题，我在实际工作当中发现，不同线程查询账户生成的对象，地址是不同的，这意味着，我锁账户没效果 作者回复: 没有效果，必须是一个对象

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;
        }
      }
    }
  } 
}

我们先看看现实世界里的一种特殊场景。如果有客户找柜员张三做个转账业务：账户 A 转账户 B 100 元，此时另一个客户找柜员李四也做个转账业务：账户 B 转账户 A 100 元，于是张三和李四同时都去文件架上拿账本，这时候有可能凑巧张三拿到了账本 A，李四拿到了账本 B。张三拿到账本 A 后就等着账本 B（账本 B 已经被李四拿走），而李四拿到账本 B 后就等着账本 A（账本 A 已经被张三拿走），他们要等多久呢？他们会永远等待下去…因为张三不会把账本 A 送回去，李四也不会把账本 B 送回去。我们姑且称为死等吧。

如何预防死锁

并发程序一旦死锁，一般没有特别好的方法，很多时候我们只能重启应用。因此，解决死锁问题最好的办法还是规避死锁。那如何避免死锁呢？要避免死锁就需要分析死锁发生的条件，有个叫 Coffman 的牛人早就总结过了，只有以下这四个条件都发生时才会出现死锁：

• 互斥，共享资源 X 和 Y 只能被一个线程占用；
• 占有且等待，线程 T1 已经取得共享资源 X，在等待共享资源 Y 的时候，不释放共享资源 X；
• 不可抢占，其他线程不能强行抢占线程 T1 占有的资源；
• 循环等待，线程 T1 等待线程 T2 占有的资源，线程 T2 等待线程 T1 占有的资源，就是循环等待。反过来分析，也就是说只要我们破坏其中一个，就可以成功避免死锁的发生。

方案一（账本管理员）

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

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

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

/*
apply()方法有锁，只有A线程执行完转账过后，才会执行finally中的actr.free(this, target)方法，这时B线程执行apply()才会返回true
*/
  // 一次性申请所有资源
  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)
    }
  } 
}
/*
我的想法是，如果Account对象中只有转账业务的话，while(actr.apply(this, target)和对象锁synchronized(Account.class)的性能优势几乎看不出来，synchronized(Account.class)的性能甚至更差；但是如果Account对象中如果还有其它业务，比如查看余额等功能也加了synchronized(Account.class)修饰，那么把单独的转账业务剥离出来，性能的提升可能就比较明显了。
作者回复: 是的，有时候性能更差，毕竟要synchronized三次。但是有些场景会更好，例如转账操作很慢，而apply很快，这个时候允许a->b,c->d并行就有优势了。
有性能优势，锁Account.class会把所有用户的转账操作都变成串行，while的这种方式只限制有关联关系的账户，比如账户c也要转账，如果c和a或b之间发生转账就会进入while等待，但如果c要转账到d就不受a和b的影响
*/

• 我觉得while(!actr.apply(this, target));和synchronized(Account.class)也使用中，Account只有一个转账操作其实两者差不多。但是如果Account中还有修改密码，查询余额等也需要加锁的操作，那就不一样了。加锁Account看似简单易懂也能保证安全，但是效率不敢恭维你来个相关操作我就全给你锁上，而前者转账对应转账的操作，修改密码对应修改密码的操作，看余额对应余额操作彼此独立，不用出现A操作等待B操作完场的这种状况。
• 在并行执行 A->B B->C 的转账过程中，A->B的转账过程，会在while(!actr.apply(this, target)); 这个循环中，阻塞B->C的转账线程。
  然而在并行执行 A->B C->D的转账过程中，是不会相互阻塞的。所谓的锁了所有账户的说法，我不是很理解。
  反观 synchronized(Account.class)， 不仅在 A->B C->D的转账过程中不能并行。甚至会串行其他需要获得Account.class这个锁的所有操作。例如查看余额。
• 老师你好，我有个疑惑，Account实例难道永远是单例的么？现实中往往针对转账操作会new 一个线程私有的Account对象吧？那这样锁是无效的，还是说老师您说的场景就是要确保项目一启动，每一个Account都只能是单例的，可能理解有误，请老师指证！作者回复: 不是单例，但是同一个账户只有一个实例

-啥不把als和apply(),free()都设为static呢？感觉作用是一样的，代码简洁些 （这个方法我深感同身受，之前做项目，static一个变量，所有人都能看到，本来是打算一个人选择一个年度进行操作的，反而，这个人改了，其他人的年度也改了）

方案三（按照顺序进行锁）

//方案二
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;
        }
      }
    }
  } 
}
/*
* 上节最后说到，不能用可变对象做锁，这里为何又synchronized（left）？
* 作者回复: 保护的是对象里面的成员，这俩对象变也只能是里面成员变，相对于里面的成员来说，这俩对象是永远不会变的。你可以这样理解。不是绝对不能用于可变对象，只是一条最佳实践。
*/

• 虽然上面两种锁的方式都是串行化了，但是具体还是有一点区别的：synchronized(Account.class)的方式相当于A->B 转账，C->D转账 先后执行，而 actr.apply(this, target)的方式则是apply-->转账-->free这样的串行方式执行，但是在转账中是可以A->B，C->D转账线程并行执行的，正如文中提到的apply方法耗时很少 所以比如一次转账耗时200ms,apply+release方式执行要20ms,所以用synchronized的方式A->B,C->D则需要耗时400ms,而appy的方式则要200+20*2=240ms,并且同时转账的人越多 apply方式的转账并行度越高 比synchronized的方式的优势越明显。 但是有一个不明白的地方,对于已经通过apply获取锁的线程，感觉没有必要对转账的账户锁定了，因为其他的线程想对相同的账户进行转账 调用apply方式是没法返回true的(已经有线程对list加入账户了)
• 考虑现实场景，做出如下假设：转账操作会相对apply方法耗时。那在高并发下synchronized(Account.class)会使得所有转账串行化，使用apply方法能提高转账的吞吐量。但apply方法也有问题，在同一个账户转账操作并发量高的场景下，apply方法频繁失败，转账的线程会不断的阻塞唤醒阻塞唤醒，开销大。也许应该改进一下由Allocator负责在有资源的情况下唤醒调用apply的线程？
• 如果有人没有理解透彻，看着例子来写生产代码，那么并发情况下会出问题，如果并发小，一直没出问题，会以为代码没问题，真正出问题的时候都分析不出来哪里错了。并发情况下，这些代码的加锁对象并不是同一个，所以是有问题的。 不同的线程都获取到了账户A的实例对象，但这些实例对象不是同一个。

• 希望所有读者都能看透这个，多线程对账户A，B实例加锁时一定要保证是同一个实例对象，就像在数据库表中通过select * from account where account_id = ? for update 加锁一样，锁住的是同一条账户记录。

  学员方案（MQ消息中间件）

  void transfer(Account target, int amt){
    boolean isTransfer = false;
  // 锁定转出账户
    synchronized(this){
          if (this.balance > amt) {
          this.balance -= amt;
          isTransfer = true;
    } 
    if (!isTransfer) {
         return;
    }
      // 锁定转入账户
      synchronized(target){ 
          target.balance += amt;
      }
  }
  /*
  反映到现实中的场景：服务员A拿到账本1先判断余额够不够，够的话先扣款，再等待其他人操作完账本2，才增加它的额度。
  但是这样转账和到账就存在一个时差，现实生活中也是这样，转账不会立马到账，短信提醒24小时内到账，所谓的最终一致性。 
  老师帮忙看看这样实现会不会有啥其他问题？
  作者回复: 实际工作中也有这么做的，只不过是把转入操作放到mq里面，mq消费失败会重试，所以能保证最终一致性。
  */

课后思考

我们上面提到：破坏占用且等待条件，我们也是锁了所有的账户，而且还是用了死循环 while(!actr.apply(this, target));这个方法，那它比 synchronized(Account.class) 有没有性能优势呢？

• synchronized(Account.class) 锁了Account类相关的所有操作。相当于文中说的包场了，只要与Account有关联，通通需要等待当前线程操作完成。while死循环的方式只锁定了当前操作的两个相关的对象。两种影响到的范围不同。
• while循环是不是应该有个timeout，避免一直阻塞下去？
  作者回复: 你考虑的很周到！