在计算机系统中，死锁很容易发现，但死锁也不难处理。这篇文章总结了死锁的基本概念、必要条件以及四种处理死锁的方法。
死锁概念
在两个或多个并发进程中，如果一个进程集合中的每个进程都在等待只能由该进程集合中的其他进程才能引发的事件，那么该进程集合就产生了死锁。
死锁产生的根本原因是多个进程竞争资源时，进程的推进顺序出现不当。
出现死锁的四个必要条件：
- 互斥。在任何时刻一个资源只能被一个进程使用。
- 拥有和请求。已经得到某个资源的进程可以再请求新的资源；
- 不可抢占。已经分配给进程的资源不能被抢占，而只能被显式释放；
- 循环等待。系统中有两个或多个的进程组成一条循环，该循环中的每个进程都等待着另一个进程占有的资源。
对于死锁，有四种处理的策略：1. 忽略；2. 预防死锁；3. 避免死锁；4. 检测死锁并恢复。
死锁预防
死锁预防是指通过破坏死锁产生的四个必要条件中的一个或多个，以避免发生死锁。
- 破坏互斥：不让资源被一个进程独占，可通过假脱机技术允许多个进程同时访问资源；
- 破坏拥有和请求：有两种方案：
- 已拥有资源的进程不能再去请求其他资源。一种实现方法是要求进程在开始执行前请求需要的所有资源。
- 要求进程请求资源时，先暂时释放其当前拥有的所有资源，再尝试一次获取所需的全部资源。
- 破坏不可抢占：有些资源可以通过虚拟化方式实现可抢占；
- 破坏循环等待：有两种方案：
- 一种方法是保证每个进程在任何时刻只能占用一个资源，如果要请求另一个资源，必须先释放第一个资源；
- 另一种方法是将所有资源进行统一编号，进程可以在任何时刻请求资源，但要求进程必须按照顺序请求资源。
死锁避免
死锁避免是利用一些事先已知的信息，在分配资源时判断是否会出现死锁，如果不会出现死锁才会分配资源。
而判断是否会出现死锁就是看是否能找到一个安全序列，系统能按照这个安全序列，也就是进程的推进顺序为每个进程分配其所需资源，直到满足每个进程所需的资源，使每个进程都能顺序执行。
银行家算法
为实现银行家算法，进程在进入系统时，要求进程声明需要资源的最大数目，但不能超过系统能提供的最大资源数目。当一个进程请求资源时，需要确定是否有足够资源分配给该进程，如果有，再检查在分配资源后，系统是否安全。
假定线程数量为 n，资源类型数量为 m，银行家算法的数据结构如下：
Max(总需求量)：n*m矩阵，表示进程Ti最多请求Max[i, j]个类型为Rj的资源；Available(剩余空闲量)：长度为m的向量，表示当前有Available[i]个类型Rj的可用资源；Allocation(已分配量)：n*m矩阵，表示进程Ti当前分配了Allocation[i, j]个类型为Rj的资源；Need(未来需要量)：n*m矩阵，表示进程Ti未来需要Need[i, j]个类型为Rj资源；
可以得出它们满足等式：Need[i, j] = Max[i, j] - Allocation[i, j]。
银行家算法的核心部分，安全状态的判断如下：
- 创建长度为
m的向量Work，表示当前资源剩余量，并进行初始化：Work = Avaiable; - 在未运行的进程中寻找未来需要量
Need[i]比当前可用量Work小的进程Ti，如果找到则继续执行3，否则转4； - 执行
Work = Work + Allocation[j];，将资源分配给进程Ti运行完毕后，回收其资源。转2： - 如果资源可以分配给所有进程，则系统处于安全状态；
如此完整的银行家算法如下：首先进行初始化，Request_i 表示进程 Ti 的资源请求向量，Request_i[j] 表示进程 Ti 请求资源 Rj 的实例。然后循环判断：
- 如果
Request_i <= Need[i]，转到2。否则拒绝资源请求，因为进程已经超过最大要求； - 如果
Request_i <= Available，转到3。否则进程Ti必须等待，因为现在可用资源不足； - 通过安全状态判断来确定是否分配资源给
Ti，如果安全则分配，否则拒绝Ti的资源请求。
死锁检测和恢复
可以允许系统进入死锁状态，但会维护一个系统的资源分配图，定期调用死锁检测算法来检测途中是否存在死锁，检测到死锁发生后，采取死锁恢复算法进行恢复。
死锁检测方法如下：
- 在资源分配图中，找到不会阻塞又不独立的进程结点，使该进程获得其所需资源并运行，运行完毕后，再释放其所占有的全部资源。也就是消去该进程结点的请求边和分配边。
- 使用上面的算法进行一系列简化，若能消去所有边，则表示不会出现死锁，否则会出现死锁。
在检测死锁时，可以采用两种方法：
- 抢占资源。从一个或多个进程中抢占资源分配给死锁进程。
- 终止进程。可以终止所有的死锁进程；也可以按照某种顺序，逐个终止进程，释放其占有资源，直到死锁解除。
