实例
下面转账的代码会发生死锁。假设线程 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 个条件。
- 互斥：共享资源 X 和 Y 只能被一个线程占用
- 占有且等待：线程 T1 已经取得共享资源 X，在等待共享资源 Y 的时候，不释放共享资源 X
- 不可抢占：其他线程不能强行抢占线程 T1 占有的资源
- 循环等待：线程 T1 等待线程 T2 占有的资源，线程 T2 等待线程 T1 占有的资源，就是循环等待
如何处理死锁
如上 4 种导致死锁的原因，我们只要破坏其中一个就可以避免死锁的发生。由于，互斥这个条件我们没有办法破坏，因为我们用锁为的就是互斥。不过其他三个条件都是有办法破坏掉的，到底如何做呢？
- 破坏“占用且等待”条件：一次性申请所有资源
- 破坏“不可抢占”条件：占用部分资源的线程进一步申请其他资源时，如果申请不到，可以主动释放它占有的资源
- 破坏“循环等待”条件：按序申请资源，是指资源是有线性顺序的，申请的时候可以先申请资源序号小的，再申请资源序号大的，这样线性化后自然就不存在循环了
解决方案
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;
}
}
}
}
}
