死锁

　　之前在学校学习过程中，很少写多进程的代码，虽然操作系统中学过死锁相关的内容，但考试过后也基本就忘记了，后来自己也遇到过有些多进程死锁的情况，再加上看了有些资料，对死锁才算是有了有些深入的理解。

### 死锁的产生　　
　　想起今年年初在面试的时候，有个面试官让我写一段可能会发生死锁的代码，我就写了如下的代码。
```java
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class Test {
private static Lock lock1 = new ReentrantLock();
private static Lock lock2 = new ReentrantLock();
public static void fun1() {
try {
lock1.lock();
lock2.lock();
//do something
} catch (Exception e) {
e.printStackTrace();
} finally {
lock1.unlock();
lock2.unlock();
}
}
public static void fun2() {
try {
lock2.lock();
lock1.lock();
//do something
} catch (Exception e) {
e.printStackTrace();
} finally {
lock2.unlock();
lock1.unlock();
}
}
}
```
　　以上代码在多线程分别调用fun1()和fun2()的时候有一定几率发生死锁（如果想大概率死锁，可以在获取两次锁之间sleep一段时间）。 假设当thread1执行fun1()并获取到lock1时thread2执行fun2()并已经获取到了lock2，这个时候thread1无法获取到lock2，thread2无法获取到lock1，且双方都不会释放之前获取到的锁，两个进程互相等，谁也不谁，这就产生了死锁。
　　所以看起来死锁产生貌似需要多进程争抢某些资源，还需要进入某些互相等待的状态，但是更准确讲，死锁的产生必须依赖四个条件，而且缺一不可。
#### 互斥条件
　　多进程使用的资源必须是互斥的，也就是说一个进程在使用过过程中，另一个进程就不能再用了。　　　
#### 占有和等待
　　死锁其实都发生在进程执行都会请求多个资源的情况下，所以要产生死锁就必须得让进程可以在占有某个资源的情况下再去请求其他的资源。　　
#### 不可抢占
　　已经被某些进程使用中的资源，不能被其他的进程抢占，必须等待使用该资源的进程释放。
#### 环路等待
　　就如同上面代码所示，当死锁发生时一定是thread1等thread2，thread2等thread1的情况。真实环境中，不仅限两个进程，只要多个进程相互等待图中出现了环，切满足前三个条件，一定会出现死锁。

　　工作中不会写出我上面那么明显的死锁代码，但其实在大型系统中，各种复杂且相互交错的逻辑，难免稍不留神就发生死锁，我们如何预防，如何检测，如何解决死锁呢？

### 死锁的预防
　　在开始说死锁的预防前，我先来引入一个很有意思的问题方便大家理解死锁的产生和预防。 ___哲学家就餐问题__，有5个哲学家围坐在一张圆桌边上，哲学家平时呢就是吃饭、睡觉、思考，然后桌上有食物，但是奇葩的是只有5根筷子，分别放在5个哲学家之间，每次哲学家想吃饭必须拿起自己左边和右边的两根筷子，用完再放回去。
　　 
　　先来分析下，这里可以满足死锁产生的四个必要条件，筷子只能同时被一个哲学家使用(互斥条件)；哲学家需要拿起一根筷子再去拿另一根筷子，如果被别人用了就等着(占有和等待)；别的哲学家已经在用的筷子不能抢过来用(不可抢占)；如果５个哲学家同时要吃饭，然后都同时拿起左手边的筷子，再想去拿右手边的筷子(环路等待)；一个死锁就此诞生了。　
　　如何避免死锁产生呢？刚说了，那4个条件是死锁产生的必要条件，缺一不可，我们只需要破坏其中之一就能避免死锁。
#### 破坏互斥条件
　　我觉得这个是最难实施的，__互斥__很多时候不是人为来决定的，是资源本身所固有的一个属性，就像哲学家就餐问题中的筷子一样，一根筷子被别人拿走了，它就不在那了，就不能用了，筷子本身是有个互斥资源。
#### 破坏占有和等待条件
　　如果一个哲学家占有一根筷子并等待另一根筷子的时候，我们规定超过多长时间没拿到另一根筷子就放下已经拿到的筷子。这样就不会出现一个人拿了一根筷子，又一种再等另一根。这种策略实时起来比较简单，比如java中已经封装了带超时的锁 tryLock(long time, TimeUnit unit)。
#### 破坏不可抢占条件
　　这是一个比较霸气的做法，想想看一个哲学家饿了想吃东西，发现筷子没了，就直接从旁边哲学家手里抢过来。如何进程想用资源的时候就抢过来，永远不会发生死锁。
#### 破坏环路等待条件
　　在上文的代码中，fun1()和fun2()中获取锁的次序不一样，所以会出现环，如果获取锁的次序一样就不会出现死锁。通用的解法是，给他每个资源都做一个唯一的编号，如果某个进程要获取多个资源，必须先从小变化号的开始获取，这样一定不会发生环路等待的情况。 但在哲学家就餐问题中，使用这种方法还是会死锁，哲学家同时要吃饭，都拿小编号的筷子相当于同时拿左(右)手边的筷子，还是会死锁。所以针对哲学家就餐的问题，可以规定哲学家只能先拿奇数编号的筷子，再去拿偶数编号的筷子(反之也可以)，这样一定不会出现环路等待的情况。

### 死锁避免
　　[银行家算法](https://baike.baidu.com/item/%E9%93%B6%E8%A1%8C%E5%AE%B6%E7%AE%97%E6%B3%95/1679781?fr=aladdin)

### 死锁的检测 　
　　尽管我们有了那多的方法来预防死锁，但在复杂的系统中，难免会发生死锁，产生死锁肯定意味着有些资源无法被正常使用，系统必然处于一种有问题的状态，我们如何检测死锁并处理死锁。
　　当死锁产生时，必然进程和资源之间占有和请求的关系图中存在环，如下图。　
　　　
　　S1-->A--S2表示A进程已经拥有了S1资源并且它还想再占有S2资源。很明显上图中有个环，表示它一定存在死锁。为了检测死锁，我们先得建立一个资源占有请求图之后，只需要看其中是否存在环即可。
　　有向图中检测环的方法很多，比如[拓扑排序](https://baike.baidu.com/item/%E6%8B%93%E6%89%91%E6%8E%92%E5%BA%8F/5223807?fr=aladdin)，dfs bfs检测重复路径，这里我就不再赘述了。
　
### 死锁处理
#### 鸵鸟算法
　　死锁有个非常简单且著名的算法，就是鸵鸟算法。这算法还有名字，想必是什么高大上的算法！！只能说you think more，鸵鸟算法处理死锁，起始就是不处理。 据说鸵鸟遇到危险时，会把头埋入草堆里，以为自己眼睛看不见就是安全。。emmm 这个心态很适合我们这些90后老人养生啊！！！
#### 利用抢占恢复
　　只要把某些进程占有的一些资源转移给其他进程就好了，但一般情况下都需要人为去干预。
#### 杀进程
　　人为干掉环中的某个节点，彻底破坏环路等待，整个系统就能从死锁中恢复过来。　

### 参考资料
[1] Andrew S. Tanenbaum / Herbert Bos . 《现代操作系统》原书第四版：机械工业出版社出版社，2017：247-266.

~谢谢打赏~

赏