17、Java并发编程：防范死锁（锁排序，锁超时，死锁检测）

在某些情况下，可以防止死锁。我将在本文中描述三种技术：

锁排序

当多个线程需要相同的锁但以不同的顺序获取它们时，就会发生死锁。

如果确保任何线程始终以相同的顺序获取所有锁，则不会出现死锁。看看这个例子：

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

如果一个线程，例如线程3，需要多个锁，它必须按照确定的顺序获取它们。它不能获取序列后面的锁，除非它获得了前面的锁。

例如，线程2或线程3在锁定A之前都不能锁定C。由于线程1持有锁A，因此线程2和3必须首先等待锁A解锁。然后他们必须成功锁定A，才能尝试锁定B或C。

锁排序是一种简单而有效的死锁预防机制。但是，只有知道获取某个锁之前所需的所有锁，才能使用它。但并非总是能够知道。

锁超时

另一种防止死锁的机制是对锁请求设置超时，这意味着试图获取锁的线程只会尝试一定时间，然后放弃。如果线程在给定的时间内未能成功获取所有必需的锁，则它将备份、释放所有已获取的锁，等待随机一段时间，然后重试。等待的随机时间量可以让其他试图获取相同锁的线程有机会获取所有锁，从而让应用程序继续运行，而不会被阻塞。

下面的示例是两个线程尝试以不同顺序获取相同的两个锁，线程将备份并重试：

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.

在上面的示例中，线程2将在线程1之前大约200毫秒重试获取锁，因此很可能成功获取这两个锁。然后，线程1将等待尝试获取锁A。当线程2完成时，线程1将能够同时获取这两个锁（除非线程2或另一个线程在这期间又获取了锁）。

需要记住的一个问题是，仅仅因为锁超时并不一定意味着线程已经死锁。这也可能是由于持有锁的线程（导致另一个线程超时）需要很长时间才能完成其任务。

此外，如果有大量的线程争夺相同的资源，仍然有可能不断发生线程同时占用该资源的情况，即使超时和备份也无法避免。对于两个线程，等待0到500毫秒然后重试，可能不会有问题；但对于10或20个线程，情况就不同了。此时两个线程等待同样的时间（或时间足够接近以导致问题）然后重试的可能性要高得多。

锁超时机制的一个问题是，无法为Java中的同步块设置超时设置。您必须创建一个自定义锁类或使用java.util.concurrency包中的某个Java 5并发构造。 编写自定义锁并不困难，但这不在本文讨论范围之内。 Java并发教程中的后续文本将涵盖自定义锁。

死锁检测

死锁检测是一种重度的防止死锁的机制，用于无法进行锁排序和锁超时不可行的情况。

线程每获得一个锁，就会在线程和锁的数据结构（映射，图形等）中进行记录。另外，每当线程请求锁定时，此数据结构中也会对此进行记录。

当线程请求锁定但请求被拒绝时，线程可以遍历锁图以检查死锁。例如，如果线程A请求锁7，但锁7由线程B持有，则线程A可以检查线程B是否请求了线程A持有的锁（如果有）。如果线程B请求了，则表示发生死锁（线程A获取了锁1，请求锁7，线程B获取了锁7，请求锁1）。

当然，死锁的情形可能远比两个互相持有锁的线程更复杂。线程A可能等待线程B，线程B等待线程C，线程C等待线程D，线程D等待线程A。为了使线程A检测到死锁，它必须可传递地检查线程B所请求的所有锁。从线程B请求的锁中，线程A将到达线程C，然后到达线程D，从线程D中找到线程A本身持有的一个锁。然后就知道发生了死锁。

以下是4个线程（A，B，C和D）获取和请求的锁的图表。这样的数据结构可用于检测死锁。

那么，如果检测到死锁，线程将如何处理？

一种可能的操作是释放所有锁，备份，等待随机的一段时间，然后重试。 这类似于简单一点的锁超时机制，只不过线程仅在实际发生死锁时才进行备份，而非仅仅是因为锁定请求超时。 但是，如果许多线程在争用相同的锁，那么即使它们备份并等待，它们也可能反复陷入死锁。

更好的选择是确定或分配线程的优先级，以便仅备份一个（或几个）线程。 其余线程继续获取所需的锁，就好像没有发生死锁一样。 如果分配给线程的优先级是固定的，则相同的线程将始终被赋予更高的优先级。 为避免这种情况，可以在检测到死锁时随机分配优先级。