多线程死锁的产生以及如何避免死锁
1、死锁的定义
多线程以及多进程改善了系统资源的利用率并提升了系统 的处理能力。然而，并发执行也带来了新的问题——死锁。所谓死锁是指多个线程因竞争资源而形成的一种僵局（互相等待），若无外力做用，这些进程都将没法向前推动。
下面咱们经过一些实例来讲明死锁现象。
先看生活中的一个实例，2我的一块儿吃饭可是只有一双筷子，2人轮流吃（同时拥有2只筷子才能吃）。某一个时候，一个拿了左筷子，一人拿了右筷子，2我的都同时占用一个资源，等待另外一个资源，这个时候甲在等待乙吃完并释放它占有的筷子，同理，乙也在等待甲吃完并释放它占有的筷子，这样就陷入了一个死循环，谁也没法继续吃饭。。。
在计算机系统中也存在相似的状况。例如，某计算机系统中只有一台打印机和一台输入 设备，进程P1正占用输入设备，同时又提出使用打印机的请求，但此时打印机正被进程P2 所占用，而P2在未释放打印机以前，又提出请求使用正被P1占用着的输入设备。这样两个进程相互无休止地等待下去，均没法继续执行，此时两个进程陷入死锁状态。java
2、死锁产生的缘由
1) 系统资源的竞争
一般系统中拥有的不可剥夺资源，其数量不足以知足多个进程运行的须要，使得进程在 运行过程当中，会因争夺资源而陷入僵局，如磁带机、打印机等。只有对不可剥夺资源的竞争 才可能产生死锁，对可剥夺资源的竞争是不会引发死锁的。数据结构
2) 进程推动顺序非法
进程在运行过程当中，请求和释放资源的顺序不当，也一样会致使死锁。例如，并发进程 P一、P2分别保持了资源R一、R2，而进程P1申请资源R2，进程P2申请资源R1时，二者都 会由于所需资源被占用而阻塞。
信号量使用不当也会形成死锁。进程间彼此相互等待对方发来的消息，结果也会使得这 些进程间没法继续向前推动。例如，进程A等待进程B发的消息，进程B又在等待进程A 发的消息，能够看出进程A和B不是由于竞争同一资源，而是在等待对方的资源致使死锁。多线程
3) 死锁产生的必要条件
产生死锁必须同时知足如下四个条件，只要其中任一条件不成立，死锁就不会发生。并发
- 互斥条件：进程要求对所分配的资源（如打印机）进行排他性控制，即在一段时间内某 资源仅为一个进程所占有。此时如有其余进程请求该资源，则请求进程只能等待。
- 不剥夺条件：进程所得到的资源在未使用完毕以前，不能被其余进程强行夺走，即只能 由得到该资源的进程本身来释放（只能是主动释放)。
- 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源 已被其余进程占有，此时请求进程被阻塞，但对本身已得到的资源保持不放。
- 循环等待条件：存在一种进程资源的循环等待链，链中每个进程已得到的资源同时被 链中下一个进程所请求。即存在一个处于等待状态的进程集合{Pl, P2, ..., pn}，其中Pi等 待的资源被P(i+1)占有（i=0, 1, ..., n-1)，Pn等待的资源被P0占有，如图2-15所示。
直观上看，循环等待条件彷佛和死锁的定义同样，其实否则。按死锁定义构成等待环所 要求的条件更严，它要求Pi等待的资源必须由P(i+1)来知足，而循环等待条件则无此限制。 例如，系统中有两台输出设备，P0占有一台，PK占有另外一台，且K不属于集合{0, 1, ..., n}。
Pn等待一台输出设备，它能够从P0得到，也可能从PK得到。所以，虽然Pn、P0和其余 一些进程造成了循环等待圈，但PK不在圈内，若PK释放了输出设备，则可打破循环等待, 如图2-16所示。所以循环等待只是死锁的必要条件。
dom
资源分配图含圈而系统又不必定有死锁的缘由是同类资源数大于1。但若系统中每类资 源都只有一个资源，则资源分配图含圈就变成了系统出现死锁的充分必要条件。ide
产生死锁的一个例子工具
* 而td1在睡眠的时候另外一个flag==0的对象（td2）线程启动，先锁定o2,睡眠500毫秒spa
* td1睡眠结束后须要锁定o2才能继续执行，而此时o2已被td2锁定；线程
* td2睡眠结束后须要锁定o1才能继续执行，而此时o1已被td1锁定；3d
* td一、td2相互等待，都须要获得对方锁定的资源才能继续执行，从而死锁。
*/
public int flag = 1;
//静态对象是类的全部对象共享的
private static Object o1 = new Object(), o2 = new Object();
public void run() {
System.out.println("flag=" + flag);
if (flag == 1) {
synchronized (o1) {
try {
Thread.sleep(500);
} catch (Exception e) {
e.printStackTrace();
}
synchronized (o2) {
System.out.println("1");
}
}
}
if (flag == 0) {
synchronized (o2) {
try {
Thread.sleep(500);
} catch (Exception e) {
e.printStackTrace();
}
synchronized (o1) {
System.out.println("0");
}
}
}
}
public static void main(String[] args) {
DeadLock td1 = new DeadLock();
DeadLock td2 = new DeadLock();
td1.flag = 1;
td2.flag = 0;
//td1,td2都处于可执行状态，但JVM线程调度先执行哪一个线程是不肯定的。
//td2的run()可能在td1的run()以前运行
new Thread(td1).start();
new Thread(td2).start();
}
}
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只有在获取了锁A以后才能尝试获取锁C(译者注：获取锁A是获取锁C的必要条件)。由于线程1已经拥有了锁A，因此线程2和3须要一直等到锁A被释放。而后在它们尝试对B或C加锁以前，必须成功地对A加了锁。
按照顺序加锁是一种有效的死锁预防机制。可是，这种方式须要你事先知道全部可能会用到的锁(译者注：并对这些锁作适当的排序)，但总有些时候是没法预知的。
加锁时限
另一个能够避免死锁的方法是在尝试获取锁的时候加一个超时时间，这也就意味着在尝试获取锁的过程当中若超过了这个时限该线程则放弃对该锁请求。若一个线程没有在给定的时限内成功得到全部须要的锁，则会进行回退并释放全部已经得到的锁，而后等待一段随机的时间再重试。这段随机的等待时间让其它线程有机会尝试获取相同的这些锁，而且让该应用在没有得到锁的时候能够继续运行(译者注：加锁超时后能够先继续运行干点其它事情，再回头来重复以前加锁的逻辑)。
如下是一个例子，展现了两个线程以不一样的顺序尝试获取相同的两个锁，在发生超时后回退并重试的场景：
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或者其它线程在线程1成功得到两个锁以前又得到其中的一些锁）。
须要注意的是，因为存在锁的超时，因此咱们不能认为这种场景就必定是出现了死锁。也多是由于得到了锁的线程（致使其它线程超时）须要很长的时间去完成它的任务。
此外，若是有很是多的线程同一时间去竞争同一批资源，就算有超时和回退机制，仍是可能会致使这些线程重复地尝试但却始终得不到锁。若是只有两个线程，而且重试的超时时间设定为0到500毫秒之间，这种现象可能不会发生，可是若是是10个或20个线程状况就不一样了。由于这些线程等待相等的重试时间的几率就高的多（或者很是接近以致于会出现问题）。
(译者注：超时和重试机制是为了不在同一时间出现的竞争，可是当线程不少时，其中两个或多个线程的超时时间同样或者接近的可能性就会很大，所以就算出现竞争而致使超时后，因为超时时间同样，它们又会同时开始重试，致使新一轮的竞争，带来了新的问题。)
这种机制存在一个问题，在Java中不能对synchronized同步块设置超时时间。你须要建立一个自定义锁，或使用Java5中java.util.concurrent包下的工具。写一个自定义锁类不复杂，但超出了本文的内容。后续的Java并发系列会涵盖自定义锁的内容。
死锁检测
死锁检测是一个更好的死锁预防机制，它主要是针对那些不可能实现按序加锁而且锁超时也不可行的场景。
每当一个线程得到了锁，会在线程和锁相关的数据结构中（map、graph等等）将其记下。除此以外，每当有线程请求锁，也须要记录在这个数据结构中。
当一个线程请求锁失败时，这个线程能够遍历锁的关系图看看是否有死锁发生。例如，线程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本身持有着。这是它就知道发生了死锁。
下面是一幅关于四个线程（A,B,C和D）之间锁占有和请求的关系图。像这样的数据结构就能够被用来检测死锁。
那么当检测出死锁时，这些线程该作些什么呢？
一个可行的作法是释放全部锁，回退，而且等待一段随机的时间后重试。这个和简单的加锁超时相似，不同的是只有死锁已经发生了才回退，而不会是由于加锁的请求超时了。虽然有回退和等待，可是若是有大量的线程竞争同一批锁，它们仍是会重复地死锁（编者注：缘由同超时相似，不能从根本上减轻竞争）。
一个更好的方案是给这些线程设置优先级，让一个（或几个）线程回退，剩下的线程就像没发生死锁同样继续保持着它们须要的锁。若是赋予这些线程的优先级是固定不变的，同一批线程老是会拥有更高的优先级。为避免这个问题，能够在死锁发生的时候设置随机的优先级。