Java并发编程学习——如何解决死锁

现实世界

前面我们使用Account.class来作为转账的锁，即当发生一个转账操作的时候，所有的用户操作都会被阻塞，这效率简直太低下。

现实世界里，账户转账操作是支持并发的，而且绝对是真正的并行，银行所有的窗口都可以做转账操作。只要我们能仿照现实世界做转账操作，串行的问题就解决了。

我们试想在古代，没有信息化，账户的存在形式真的就是一个账本，而且每个账户都有一个账本，这些账本都统一存放在文件架上。银行柜员在给我们做转账时，要去文件架上把转出账本和转入账本都拿到手，然后做转账。这个柜员在拿账本的时候可能遇到以下三种情况：

文件架上恰好有转出账本和转入账本，那就同时拿走；
如果文件架上只有转出账本和转入账本之一，那这个柜员就先把文件架上有的账本拿到手，同时等着其他柜员把另外一个账本送回来；
转出账本和转入账本都没有，那这个柜员就等着两个账本都被送回来。

而编程世界解决这个问题就是使用两把锁去控制两个转账账户。

两个锁

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账户，B账户要转账给A账户，然后A转账给B的时候申请到了A的锁，同时B转账给A的时候申请到了B的锁，这个时候线程1申请B的锁不成功(因为B的锁被线程2给拿走了)，线程2申请A的锁不成功(因为A的锁被线程1给拿走了)，这个时候两个线程就会因为获得不到锁而发生阻塞(Java中只要synchronized不成功，线程便会进入阻塞状态)，两个线程互相等待锁，却都不释放锁，那么这个时候就产生了死锁。

两个锁

如何预防死锁

首先，当死锁产生的时候一般只有杀死进程或者结束应用来解决，所以解决死锁的代价是很大的。对于死锁，最好的办法就是规避死锁。

coffman于1971年提出了死锁产生的四个必要条件

互斥条件：一个资源一次只能有一个线程(或进程)占用
部分分配条件(占有且等待)：即一个线程(或进程)不能一次性获得所有需要的资源
不可抢占条件：一个资源只能由它占有的线程(或进程)来释放，不能通被其他线程(或进程)抢占使用。
循环等待条件：每个线程(或进程)占有若干资源，并且又在等待下一个线程(或进程)所拥有的资源。

反过来讲，我们只需要破坏一个条件就可以避免死锁的产生。对于第一个互斥条件来说，我们无法破坏，因为我们就是需要使用锁的互斥条件来达到并发的目的。剩下三个我们都能破话。

部分分配条件(占有且等待)：我们只需要同时将资源一次性分配给线程
不可抢占条件：占用部分资源的线程进一步申请其他资源时，如果申请不到，可以主动释放它占有的资源，这样不可抢占这个条件就破坏掉了。
循环等待条件：按序申请资源，即使资源是有线性顺序的。

破坏部分分配条件(占有且等待)

一次性申请所有资源，对于转账来说，因为涉及到两个资源，所以我们需要一次性申请两个资源AccountA和AccountB，在现实生活中我们可以通过一个账本管理员来负责一个业务员只能同时获取到转账双发的账本，要么都获取不到。

两个锁

编程中我们也可以定义一个管理员，并且对资源的回收和发放都要是原子操作。

class Allocator {
  private List<Object> 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)
    }
  }
}

破坏不可抢占条件

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

你可能会质疑，“Java 作为排行榜第一的语言，这都解决不了？”你的怀疑很有道理，Java 在语言层次确实没有解决这个问题，不过在 SDK 层面还是解决了的，java.util.concurrent 这个包下面提供的 Lock 是可以轻松解决这个问题的。

破坏循环等待条件

破坏这个条件需要对资源进行排序，这样申请资源申请锁的时候就不会出现循环等待了。

这个实现非常简单，我们假设每个账户都有不同的属性 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;
        }
      }
    }
  }
}

总结

当我们使用细粒度锁来解决问题的时候，需要注意死锁问题。

预防死锁有三个解决方案，在上述中我们使用了两种方式避免死锁，但是显然破坏循环等待条件的做法明显优于破坏部分分配条件，所以在选用避免死锁的方法的时候还要仔细斟酌