Deadlock Prevention
##### 预防死锁
文章的地址：翻译文章的源地址
线程死锁
在某些情况下，是有可能预防死锁的。这篇文章将会描述三种预防死锁的方法：
1.锁顺序
2.锁超时
3.死锁侦测
锁顺序
多个线程在请求同样的锁，但是请求锁的顺序不同，可能会导致死锁。
如果你确定任何一个线程抢占所有锁的顺序都是相同的，那么死锁就不会发生，如下例：
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，在去锁C之前必须已经拿到锁A。因为线程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提前200ms抢占锁，很有可能全部的抢占到两个锁，线程1将会重新等待锁A，当线程2执行 完毕后，线程1将会抢占到两个锁。
需要注意的一点是：线程锁超时并不是意味着线程已经死锁。也有可能是拥有锁的线程（引起其他的线程出现时间超时）要花费 比较上的时间完成任务。
另外，如果很多的线程争抢相同的资源，那么就可能线程每次都恰好等待相同的时间，只能一次次的超时重试。这种情况在两个 线程重试前等待0到500ms的时候，不太会出现。但是在10个到20个的线程的情况下就不一样了，两个线程再重试之前等待相同 的时间的概率就会大上很多。
锁超时的一个问题是：对进入一个synchronized代码块设置超时是不太可能的。你可能需要自己创建一个自定义的lock类或者 使用java5 的concurrent包，这部分不在我们讨论的范围内，留着以后讨论。
死锁检查
死锁检查是一个比较重的防止机制，适合情况是：锁顺序和锁超时不适合的情况。
线程每次抢占一个锁的时候，它就在一个关于线程和锁的数据结构（map或者图等）中标记一下。另外，每当线程需要抢占一个 锁的时候，也需要在这个数据结构中标记一下。
当一个线程有抢占锁的请求，但是这个请求被拒的时候，那么这个线程就去锁的这个数据结构（锁图）中检查死锁的情况。如果线程 A请求锁7，但是锁7被线程B占有，然后锁A需要检查线程B请求的锁是否被线程A占有。如果线程B请求的锁线程A有占有的，那么 死锁就会发生。（线程A有锁1请求锁7，线程B有锁7请求锁1）。
当然，死锁的情况有时候比上面描述的要复杂。线程A等待线程B，线程B等待线程C，线程C等待线程D，线程D等待线程A，线程 A。为了侦测线程A的死锁，必须检测线程B全部请求到了锁，对应线程B请求到的锁，必须检测线程C，然后是线程D，然后发现 这个线程请求的锁被已被A抢占，这样就能够知道会有死锁的发生。
下面就是四个线程（A,B,C,D）已经抢占的锁和要请求锁的图形化说明：
死锁发现以后，需要怎么做呢？
一种可能的而行为是：释放所有的锁，回退，等待一个随机的时间，重新开始。这有点像锁超时的机制，除了锁超时机制 是死锁发生以后的行为，不仅仅是因为他们的锁请求超时了。 然而当大量的线程竞争同几个锁的时候，即使它们回退等待 ，但是也有可能再次的出现死锁的情况。
一个比较好的办法是确定或者分配线程优先级，这样有一些线程就会回退，其余的线程就会拿到需要的锁然后执行。 如果分配给线程的优先级是固定的，相同的线程总是能得到更高的优先级。每当检测到死锁时，要避免这样的情况，你可以 随机分配优先级。