死锁与死锁避免算法
1.什么是死锁？
死锁（Deadlock）是在多任务环境中的一种资源竞争问题，其中两个或多个进程（线程）互相等待对方持有的资源，导致所有进程都无法继续执行。死锁是一种非常棘手的问题，因为它会导致系统无法正常运行。
举个例子。比如买东西，如果商家要先拿钱才给东西，顾客要先拿到东西才给钱，那么会发生死锁。
另外，哲学家就餐问题是一个死锁的经典例子。
2.死锁的条件
死锁需要满足四个必要条件：
- 互斥（mutual exclusion）：资源只能同时分配给一个进程，不能共享。
- 禁止抢占（no preemption）：资源已被占有的情况下不能被强制剥夺。
- 持有并等待（hold and wait）：一个进程可以在等待时持有系统资源。
- 环路等待（circular waiting）：一系列进程互相持有其他进程所需要的资源，形成资源请求等待的环形图。
死锁只有在四个条件同时满足时发生，预防死锁必须至少破坏其中一项。
3.如何避免死锁？
只要破坏死锁的四个必要条件的任意一个，便可避免死锁。
- 破坏互斥条件：允许多个进程共享某些资源，从而避免互斥条件。
- 破坏非抢占条件：进程占有的资源，可被其他高优先级进程强制夺取。
- 破坏持有并等待条件：无法获取资源时，释放已经占有的资源。
- 破坏环路等待条件：定义一个资源分配顺序，要求进程只能按照这个顺序请求资源。
最常见的有两个算法：
- 资源有序分配法
- 银行家算法
2.1 资源有序分配法
资源有序分配法通过破坏「环路等待条件」避免死锁。
线程 A 和 线程 B 获取资源的顺序要一样，当线程 A 是先尝试获取资源 A，然后尝试获取资源 B 的时候，线程 B 同样也是先尝试获取资源 A，然后尝试获取资源 B。也就是说，线程 A 和线程 B 总是以相同的顺序申请自己想要的资源。
2.2 银行家算法
简介
银行家算法是由 Edsger W. Dijkstra 于 1965 年 THE 操作系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统安全运行。
在银行中，银行拥有的资金是有限的。当客户向银行贷款时，银行家会评估客户申请贷款的数量是否超过可用资金，如果不超过则放贷，如果超过则客户需要等待。在这样的描述中，银行家好比操作系统，资金就是资源，客户相当于要申请资源的进程。
银行家算法的核心思想是「通过预先判断资源分配是否安全，来决定是否分配资源」。
如何判断资源分配是否安全？
当一个进程申请资源的时候，银行家算法先「试探」分配给该进程资源，然后判断分配后的系统是否处于安全状态。如果处于安全状态，则资源请求是安全的，分配资源；如果脱离安全状态，则资源请求不安全，该进程继续等待。
那什么是安全状态？
如果存在一个由系统中「所有进程」构成的安全序列 P1, …, Pn，则系统处于安全状态。
那什么是安全序列？
介绍安全序列之前需要知道银行家算法涉及的四种变量：
- 某个进程申请资源最大量 Max
- 已分配给某个进程的资源量 Allocation
- 资源未分配量 Available
- 某个进程还需要的资源量 Need
其中 Need[i,j]=Max[i,j]-Allocation[i,j]。i 和 j 表示第 i 个进程和第 j 种资源。
假设进程 P1 申请某个资源，银行家算法先试探地分配给它（当然先要看看当前资源池中的资源数量够不够），若申请的资源数量小于等于Available。然后接着判断分配给 P1 后剩余的资源，能不能使进程队列的某个进程执行完毕。若没有进程可执行完毕，则系统处于不安全状态（即此时没有一个进程能够完成并释放资源，随时间推移，系统终将处于死锁状态）。
若进程 P2 可执行完毕，则假设回收已分配给 P2 的资源（剩余资源数量增加），把这个进程标记为可完成，并继续判断队列中的其它进程。若所有进程都可执行完毕，则系统处于安全状态。可完成的进程顺序构成一个安全序列。
安全序列是指一个进程序列 {P1，…，Pn} 是安全的，即对于每一个进程 Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程 Pj (j < i ) 占有资源量之和。
判断资源分配是否安全流程如下：
小结
银行家算法是一种有效的避免死锁的资源分配策略，通过模拟资源分配的情况，前置检查系统是否处于安全状态来避免死锁。
如果分配完资源，剩余资源能够满足某个进程执行完成，然后回收执行完成的进程资源，找到一个安全序列，那么系统处于安全状态。
通过银行家算法分配资源，进程不会出现环路等待的情况，因为剩余资源可以满足某个进程完成执行，所以不会发生死锁。
4.如何排查死锁？
如果你想排查你的 Java 程序是否死锁，则可以使用 jstack 工具，它是 JDK 自带的线程堆栈分析工具。
在 Linux 下，我们可以使用 pstack + gdb 工具来定位死锁问题。
pstack 命令可以显示每个线程的栈跟踪信息（函数调用过程），它的使用方式也很简单，只需要 pstack PID 就可以了。
那么，在定位死锁问题时，我们可以多次执行 pstack 命令查看线程的函数调用过程，多次对比结果，确认哪几个线程一直没有变化，且是因为在等待锁，那么大概率是由于死锁问题导致的。
当然，也可以使用 gdb 调试进程，查看代码执行流是否阻塞在获取锁的位置。
5.活锁
活锁（Livelock）与死锁相似，死锁是行程都在等待对方先释放资源；活锁则是行程彼此释放资源又同时占用对方释放的资源。当此情况持续发生时，尽管资源的状态不断改变，但每个行程都无法获取所需资源，使得事情没有任何进展。
活锁的时候进程是不会挂起，会一直占用 CPU 资源。
假设两人正好面对面碰上对方：
- 死锁：两人互不相让，都在等对方先让开。
- 活锁：两人互相礼让，却恰巧站到同一侧，再次让开，又站到同一侧，同样的情况不断重复下去导致双方都无法通过。
对于某些检测死锁并从死锁中恢复的算法来说，Livelock 是一种风险。如果有多个进程执行操作，则可以重复触发死锁检测算法。这可以通过确保只有一个进程(任意选择或按优先级选择)执行操作来避免。