死锁防御战

Posted on | In | Views:

在某些应用场景下，能够做到预防死锁的发生。本文会描述三种情形：

  1. Lock Ordering
  2. Lock Timeout
  3. Deadlock Detection

Lock Ordering

多个线程需要相同的锁来完成代码顺畅运行，但是访问锁的顺序是不同的，那么就可能会发生死锁的情况。

也就是说，如果多个线程需要相同的锁，但是他们对锁的访问顺序是相同的，那么就不可能会出现死锁的情况。

1
2
3
4
5
6
7
8
9
10
11
12
Thread 1:
    lock A
    lock B

Thread 2:
    wait for A
    lock C (when A locked)

Thread 3:
    wait for A
    wait for B
    wait for C

如果现在有一个线程，需要多个锁（和 Thread 3 类似），它必须要找既定的顺序去获取锁，它不能在没获取前面锁的情况下（例如:A）去获取排在后面的锁（例如:B）。

“锁排序”是一种简单而有效的死锁预防机制。但是，只有在获取任何锁之前就知道所需的所有锁才能使用这种方式防御。

Lock Timeout

另一个死锁预防机制是对尝试“获取锁”设置超时时长，这意味着尝试获取锁的线程只会在放弃之前阻塞这么长的时间。

如果一个线程在给定的超时时间内仍没有成功获取所有必要的锁，那么它将阻塞并释放所有已持有的锁，等待一段随机时间，然后重试。

等待的随机时间用于让其他线程尝试获取相同的锁，从而让应用程序继续运行而不阻塞。

下面的例子就是两个线程尝试以不同的顺序获取相同的锁，然后线程阻塞和重试：

1
2
3
4
5
6
7
8
9
10
11
12
13
Thread 1 locks A
Thread 2 locks B

Thread 1 attempts to lock B but is blocked
Thread 2 attempts to lock A but is blocked

Thread 1's lock attempt on B times out
Thread 1 backs up and releases A as well
Thread 1 waits randomly (e.g. 257 millis) before retrying.

Thread 2's lock attempt on A times out
Thread 2 backs up and releases B as well
Thread 2 waits randomly (e.g. 43 millis) before retrying.

上例中，Thread 2 比 Thread 1 先 200ms 进行重新尝试并且在这种情况下很大可能会成功获取两个必要锁。Thread 1 将继续等待 lock A。当Thread 2运行结束，Thread 1 也能够获取两个锁。（除非Thread 2 或者其他线程在又开始插足锁得获取）

注：锁超时并不意味着线程已经死锁，也可能意味着持有锁的线程（导致另一个线程超时）需要很长的时间来完成它的任务。

另外，如果有很多的线程竞争相同的资源，他们仍然有可能多次的同时重试，即使超时和阻塞。这种情况在两个线程在重试之前等待0到500ms可能不会发生，但是如果是10到20个线程，那么情况就不一样了。它和两个线程等待相用时间或者近乎相同的时间再重试的情况差不多。

但是，锁的超时机制并不能在Java的同步代码块中设置超时，你将不得不创建自定义锁类或使用java.util.concurrency包中的一个Java 5并发结构，编写自定义锁并不困难，但超出本文范围，有兴趣的自行了解。

Deadlock Detection

死锁检测是一种较重的死锁防御机制，针对无法获取锁顺序和锁超时不可行的情况。

每当线程takes锁时，都会在线程和锁的数据结构中注明。另外，线程requests锁也会在数据结构中注明。

当线程请求锁的请求被拒绝时，线程可以遍历锁图来检查死锁。例如，如果线程A请求 lock 7，但是 lock 7被线程B持有，线程A会检测线程B是否请求线程A已经持有的锁（如果有）。如果线程B请求是线程A已经持有的锁，则发生死锁。

当然，大部分情况会更加复杂，往往都是多个线程造成死锁。

那么发现线程死锁该如何做呢?

一种可能的操作时释放所有锁，阻塞等待一段随机时间，然后重试。这和更简单的锁超时机制类似，只是线程仅在确定发生死锁的时候进行阻塞，而不仅根据发生锁超时来判断。但是，如果很多线程正在争夺相同的锁，即使它们阻塞并等待，它们也可能会重复地陷入僵局。

一个更好的选择是确定和分配线程的优先级，以便于阻塞一个（或几个）线程，其余的线程继续获取他们所需的锁，就像没有死锁发生一样。如果分配给线程的优先级是固定的，相同的线程将总是被富裕更高的优先级。为了避免这种情况，可以在检测死锁时随机分配优先级。

原文链接:

http://tutorials.jenkov.com/java-concurrency/deadlock-prevention.html#timeout