参考：
http://tutorials.jenkov.com/java-concurrency/deadlock.html
http://tutorials.jenkov.com/java-concurrency/deadlock-prevention.html

概念

如果线程1获取了锁A，期望获得锁B；线程2获取了锁B，期望获得锁A。此时死锁就产生了，线程1、2将会一致相互等待。描述如下：

Thread 1  locks A, waits for B
Thread 2  locks B, waits for A

复杂的死锁

上一部分简单介绍了死锁，但实际场景中会遇到更加复杂的死锁，比如多个线程（超过2个）。这时会难以检测，比如：

Thread 1  locks A, waits for B
Thread 2  locks B, waits for C
Thread 3  locks C, waits for D
Thread 4  locks D, waits for A

数据库死锁

数据库事务是一个更加复杂的能够引起死锁的场景。在一个数据库事务中，可能包含很多的SQL更新请求。当一条记录在事务中被更新时，将会被锁定以防止其他事务进行更新，直到第一个事务完成。在数据库中，同一个事务中有多条更新请求是产生死锁的原因。
如果多个事务在同一时间执行，并且需要更新相同的记录，就会有引发死锁的风险。如：

Transaction 1, request 1, locks record 1 for update
Transaction 2, request 1, locks record 2 for update
Transaction 1, request 2, tries to lock record 2 for update.
Transaction 2, request 2, tries to lock record 1 for update.

由于锁是在不同的请求中获取的，并且并非所有给定事务所需的锁都是提前知道的，因此很难检测或防止数据库事务中的死锁。

死锁预防

按顺序枷锁

当多个线程以不同的顺序获取相同的一些锁时，死锁就会产生。
如果能够确保所有的线程都能以相同的顺序获取所有的锁，死锁就不会发生。如下：

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

Thread2和Thread3都必须先获取前面的锁，才能去尝试获取后续的锁。
按顺序加锁是一种简单的而有效的死锁预防措施。然而，只有当我们知道需要获取哪些锁之后才能这么使用。事实上，我们并不是总是如此。

锁定超时

另一个死锁预防的机制是给锁设置一个超时时间，这意味着一个线程尝试获取一个锁的时候只会尝试一段时间然后放弃。如果一个线程在给定的超时时间内，没有成功的获取到所有的锁，就要释放掉所有已经获得的锁，等待一个随机的时间再次尝试。这个随机的等待时间让其他线程有机会获得锁，这样程序就会继续运行而不会被锁定住。
下面是一个示例说明了两个线程以不同的顺序尝试获得同样的锁，以及在哪里回退和重试。

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.

在上面的例子中，线程1和线程2都尝试获得锁，然后都超时了，线程2比线程1先200ms尝试获取锁，因此就会有机会成功获得两个所。线程1在之后尝试获得锁A。当线程2完成，线程1也能得到全部的两个锁（除非线程2或者其他线程持有这两个锁中的一个）

需要知道的是，锁超时并不一定是产生了死锁，它也可以是线程持有锁很长时间以完成它的任务（因为其他一些时间超时）。

死锁检测

死锁检测是一种更重的死锁预防机制，针对无法进行锁排序和锁超时的情况。
每次线程获得锁的时候，都在一个线程和锁数据结构中记录。此外。每次线程请求锁的时候也要记录在这个数据结构中。
当一个线程请求锁，但是请求被拒绝的时候，线程就可以遍历这个锁图来检查死锁。例如如果线程 A 请求锁 1 ，但锁 1 被线程 B 持有，则线程 A 可以检查线程 B 是否请求了线程 A 持有的任何锁（如果有）。如果线程 B 已请求，则发生了死锁（线程 A 已获取锁 2，请求锁 1，线程 B 已获取锁 1，请求锁 2）。

当然死锁的场景实际上会比两个线程相互等待对方的锁复杂很多。线程A等待线程B，线程B等待线程C，线程C等待线程D，线程D等待线程A。线程A为了能够检测到死锁，必须遍历检查所有线程B的请求。从线程B请求的锁，线程A会到线程C，然后到线程D，从线程D请求的锁中发现线程A已经持有的锁时，就能得知死锁发生了。
下图是4个线程请求和获得锁的图。这样的数据结构可以检测到死锁。

检测到死锁之后要做什么呢？

一个可能的做法是释放所有的锁，回退，等待一个随机的时间然后重试。这类似于更简单的锁超时机制，除了线程仅在实际发生死锁时才进行回退，而不是因为这些锁请求超时。如果多个线程竞争同一个锁，他们可能反复陷入死锁，尽管他们回退并等待。