[Java 并发编程] 16. 死锁和预防死锁

1. 线程死锁

死锁：两个或多个线程因为竞争资源而造成的一种僵局。

示例：线程A拥有锁a，线程B拥有锁b，线程A尝试获取锁b，线程B尝试获取锁a，因此产生死锁。线程A将永远无法获取锁b，同样线程B也无法获取锁a。

1
2

Thread A    locks a, wait for b
Thread B    locks b, wait for a

说明：线程A和线程B必须分别拥有锁a、锁b，同时等待彼此释放锁才会造成死锁的发生，若线程A等待获取锁B时线程B释放了锁B，那么不会造成死锁。

更复杂的死锁：

1
2
3
4

Thread A    locks a, wait for b
Thread B    locks b, wait for c
Thread C    locks c, wait for d
Thread D    locks d, wait for e

线程A等待线程B释放锁，线程B等待线程C释放锁，线程C等待线程D释放锁，线程D等待线程A释放锁，造成更加复杂的死锁。

2. 数据库死锁

一个更加复杂的死锁，是数据库的事务。一个数据库事务可能由很多个 update 语句组成。当一条记录在某个事务中被更新时，其他事务更新这条记录需要等待第一个事务提交，同一个事务中的每个 update 语句可能会锁住数据库中的一些数据记录。

当多个事务同时需要更新一些记录，就可能产生数据库死锁。

示例：

1
2
3
4

Transaction A   第一个update请求： 锁住记录1
Transaction B   第一个update请求： 锁住记录2
Transaction A   第二个update请求： 尝试修改并锁住记录2
Transaction B   第二个update请求： 尝试修改并锁住记录1

3. 预防死锁

一些防止死锁的方法：

• 锁排序
• 锁超时
• 死锁检测

3.1 锁排序

当多个线程以不同的顺序竞争一些锁资源时，可能产生死锁。

如果你能确保所有的线程按照一定的顺序获取锁资源，就不会产生死锁。示例如下：

1
2
3
4
5
6
7
8
9
10
11
12

Thread A:
    lock a
    lock b

Thread B:
    wait for a
    lock c (when a lock)

Thread C:
    wait for a:
    wait for b:
    wait for c:

示例中的线程C，它必须按照 a -> b -> c 的顺序获取对应的锁，在未获取顺序排在前面的锁之前线程C无法获取后的锁。

示例中：一旦线程A获得了锁a，线程B和线程C必须等待线程A释放锁a之后才竞争获取锁a，之后它们必须按顺序获取锁b或锁c.

锁排序是一种非常简单有效的预防死锁机制。然而，你需要已知所有的锁，然后给它们设定顺序。我们并非总能已知所有的锁。

3.2 锁超时

另外一种预防死锁的机制是：给线程在尝试获取锁的时候设置一个超时时间，如果指定时间内未获取锁则放弃。如果一个线程在给定时间范围内未获取到所有有需要的锁，它将会阻塞并释放自身拥有的所有锁资源，等待一个随机的时间之后重新进入。这个随机的等待时间内，其他的线程可以获取锁资源或释放一些锁资源，改变锁资源的状态，这样使得应用程序避免死锁的发生。

示例：假设有2个线程分别是线程1，线程2按不同的顺序获取锁A，锁B

1
2
3
4
5
6
7
8
9
10
11
12
13

线程1获取锁资源A
线程2获取锁资源B

线程1尝试获取锁资源B但是锁B被线程2获取了
线程2尝试获取锁资源A但是锁A被线程1获取了

线程1尝试获取锁资源B 超时
线程1阻塞并释放锁资源A
线程1等待一个随机的时间（比如198毫秒）之后重新进入

线程2尝试获取锁资源A 超时
线程2阻塞并释放锁资源B
线程2等待一个随机的时间（比如221毫秒）之后重新进入

注意的是：线程尝试获取锁超时不一定意味着发生了死锁。因为存在其他的因素，比如持有锁的线程在设定的时间内未执行完任务，持有锁未释放锁导致其他线程尝试获取锁超时。

另外，当足够多的线程竞争同一个锁资源时，可能导致一些线程尝试获取锁时一次又一次的发生锁超时。

设置锁超时的预防死锁的机制有一个问题是：当线程进入synchronized代码块时，你无法给线程尝试进入synchronized代码块设置一个超时时间。你必须使用一个自定义的锁类或者使用 Java 5 提供的 JUC 包内的一些工具类。

3.3 锁排序 vs. 锁超时

类型	优点	缺点
锁排序	简单，易实现	适用于所有已知的锁资源，并设定锁的顺序
锁超时	灵活，不需要已知所有的锁资源	复杂，线程获取锁资源时需设定超时时间，一般情况下使用juc工具包中的类，无法给synchronized关键字设定超时时间

3.4 死锁检测

死锁检测是一种沉重的防止死锁机制。通常在设置锁顺序、设置锁超时是不可行的情况下使用。

每个线程获取锁时需要在一个数据结构（例如map、graph）中记录线程和锁资源的信息，另外，无论何时线程请求锁也需要记录到一个数据结构中，后面通过检测这个数据结构来预防死锁的发生。

当一个线程尝试获取锁时被拒绝，这个线程可以通过定义的数据结构来检测系统是否发生了死锁。

线程A持有锁1，线程B持有锁2，线程C持有锁3，线程D持有锁4，且线程A尝试获取锁2，线程B尝试获取锁3，线程C尝试获取锁4，线程D尝试获取锁1。那么定义的数据结构示例如下：

当线程A持有锁1，且尝试获取锁2被拒时，那么可以通过定义的数据结构获取到持有锁2的线程B，再获取到线程B尝试获取的锁3，再循环上面的算法得到锁三的持有线程C，获取线程C尝试获取的锁4，再循环得到锁4的持有线程D，得到线程D之后获取到线程D尝试获取的锁1，这时候检测到锁1被自己（线程A）持有，那么就检测出了系统存在死锁。

简单地说，每当一个线程获取锁被拒绝时，这个线程根据定义的数据结构检测系统是否存在死锁，具体做法是以递归的形式遍历获取失败的锁以及获取失败的锁的所属线程，判断线程获取失败的锁是否与原始线程（获取锁失败并检测死锁的那个线程）持有的锁是否相同，如果原始线程拥有的锁中包含某个线程尝试获取的锁，那么就说明系统存在死锁，否则不存在死锁。

那么怎么处理死锁呢？

1. 当某个线程获取某个锁失败时，并检测到死锁，其中一种比较简单的做法是当前检测到死锁的线程释放所有的锁资源，以便其他线程获取到当前线程释放的锁资源，同时当前线程阻塞一个随机的时间段后重新进入，这有点类似于设置锁超时的做法。
2. 另外一个更好的做法是指定一些线程的优先级，只让少量线程造成阻塞，剩余的线程在没有死锁发生的情况下继续执行任务。

3.5 预防死锁小结

通常情况下，设置获取锁的顺序是一种常见的、比较简单的预防死锁的方案，但不适用于锁数量过多和存在未知的锁资源时使用。在通过设置锁顺序方案不可行或难实行的情况下，我们可以使用juc工具包中的一些类来设置获取锁时间的方案，不过这种方案不适用于synchronized关键字。在前两种方案都比较困难实行的情况下，可以使用死锁检测的方案来检测死锁并处理死锁。