如何预防死锁

上一篇我们使用Account.class作为互斥锁，解决了银行转账的问题，但是我们发现这样的转账操作就变成了串行，这样对于性能就会大打折扣，现实生活中这种是不能别接受的。

事实上，并发并发编程中，转账的这种情况，需要两把锁，这样就可以实现并发，例如,我们把账户A转入账户B的场景，此时我们可以建立两把锁，分别锁住账户A和账户B，代码如下


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转给账户B100元，而同时李四要从账户B给账户A转入100元,但是张三拿到账户A的时候，发现账户B是被李四拿到了，就会等待，同时李四拿到账户B的时候，发现账户A却被李四拿走了，也就会等待。

上面就是就会产生死锁，死锁的专业定义就是，一组互相竞争资源的线程因互相等待，导致永久阻塞的现象

如何预防死锁

首先解决问题之前，我们先要知道如何发生死锁，下面四个条件同时产生就会产生死锁，

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

只要我们破坏其中一条就可以了，因为锁的本质就是利用互斥，所以没有办法破坏,不过其他三个条件都是有办法破坏的，

对于占有等待，我们可以一次性申请所有资源，这样就不存在等待了
对于不可抢占，占有的资源进一步申请其他资源时候，如果申请不到，可以主动放弃他占有的资源，这样不可抢占这个条件就可以破坏
对于循环等待，可以按照顺序申请来预防，申请的时候可以申请序号小的，在申请序号大的，这样就不会产生循环等待了。

破坏占用且等待条件

就那上面的账户A和账户B来说，我们一次性把申请所有账号,因此我们需要一个角色管理这个操作，此时我们可以在账户Account类里面持有一个Allocator的单例(必须是单例，只能有一个人分配资源),当账户在执行转账操作的时候，首先向Allocator同时申请转出账户和转入账户两个资源,成功后在锁定这两个资源,当转账操作执行完，释放锁之后，我们需要通知Allocator同时释放转出账户和转入账户这两个资源，


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

破坏不可抢占条件

破坏不可抢占条件看起来很简单，核心就是主动放弃他占有的资源，但是这一点synchronizd是做不到的，原因是由于synchronized申请资源的时候，如果申请不到，就会阻塞等待，也释放不了线程已经占有的资源，但是java,提供另外一种解决办法,就是java.util.concurrent包下面的lock就可已解决这个问题

破坏循环等待条件

破坏这个条件，需要对资源进行排序，然后按序申请资源，我们假设账户有一个属性id,我们根据这个字段id进行排序，申请的时候，我们可以按照从小到大的顺序申请，如下面代码，1-6代码就是按照转入账户和转出账户排序，然后按照序号大小顺序锁定账户，这样就不会产生循环等待


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

预防死锁就是破坏三个条件中的一个有了这个思路后，实现就简单，但是我们仍然注意的是，防止死锁的成本也是很高的，比如破坏占用且等待条件的成本要大于破坏循环等待的成本，因为破坏占用且等待条件实在循环获取多个资源，直到获取，因此破坏循环等待就是一个成本最低的方案

测试

测试

继续阅读