实例

下面转账的代码会发生死锁。假设线程 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;
        }
      }
    }
  } 
}

死锁是如何产生的

上面的源码发生了死锁，我们再看看导致死锁的 4 个条件。

1. 互斥：共享资源 X 和 Y 只能被一个线程占用
2. 占有且等待：线程 T1 已经取得共享资源 X，在等待共享资源 Y 的时候，不释放共享资源 X
3. 不可抢占：其他线程不能强行抢占线程 T1 占有的资源
4. 循环等待：线程 T1 等待线程 T2 占有的资源，线程 T2 等待线程 T1 占有的资源，就是循环等待

如何处理死锁

如上 4 种导致死锁的原因，我们只要破坏其中一个就可以避免死锁的发生。由于，互斥这个条件我们没有办法破坏，因为我们用锁为的就是互斥。不过其他三个条件都是有办法破坏掉的，到底如何做呢？

1. 破坏“占用且等待”条件：一次性申请所有资源
2. 破坏“不可抢占”条件：占用部分资源的线程进一步申请其他资源时，如果申请不到，可以主动释放它占有的资源
3. 破坏“循环等待”条件：按序申请资源，是指资源是有线性顺序的，申请的时候可以先申请资源序号小的，再申请资源序号大的，这样线性化后自然就不存在循环了

解决方案

1. 破坏“占用且等待”条件

增加一个账本管理员，然后只允许账本管理员从文件架上拿账本，也就是说柜员不能直接在文件架上拿账本，必须通过账本管理员才能拿到想要的账本。

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{
      if (this.balance > amt){
        this.balance -= amt;
        target.balance += amt;
      }
    } finally {
      actr.free(this, target)
    }
  } 
}

更好的方案，等待 - 通知机制：通过 synchronized 配合 wait、notify、notifyAll 实现
notify：随机地通知等待队列中的一个线程
notifyAll： 通知等待队列中的所有线程
在 synchronized 代码块外部调用 wait、notify、notifyAll；锁定this，而用 target.wait() 调用，都会抛出java.lang.IllegalMonitorStateException异常

class Allocator {
  private List<Object> als;
  // 一次性申请所有资源
  synchronized void apply(Object from, Object to){
    // 经典写法
    while(als.contains(from) || als.contains(to)){
      try{
        wait();
      }catch(Exception e){
      }   
    } 
    als.add(from);
    als.add(to);  
  }
  // 归还资源
  synchronized void free(Object from, Object to){
    als.remove(from);
    als.remove(to);
    notifyAll();
  }
}

2. 破坏“不可抢占”条件

通过 Lock 锁解决

3. 破坏“循环等待”条件

假设每个账户都有不同的属性 id，这个 id 可以作为排序字段，申请的时候，我们可以按照从小到大的顺序来申请。

class Account {
  private int id;
  private int balance;
  // 转账
  void transfer(Account target, int amt){
    
    // 排序 start *********************************
    Account left = this
    Account right = target;  
    if (this.id > target.id) {
      left = target;
      right = this;
    }
    // 排序 end *********************************

    // 锁定序号小的账户
    synchronized(left){
      // 锁定序号大的账户
      synchronized(right){ 
        if (this.balance > amt){
          this.balance -= amt;
          target.balance += amt;
        }
      }
    }
  } 
}