死锁的概念
死锁的定义
在并发环境下，各进程因竞争资源而造成的一种相互等待对方手里的资源，导致这些进程均阻塞。若没有外力干涉，这些进程都无法继续前进。
死锁： 互相等待对方手里的资源，导致各进程都阻塞，无法前进的现象
相关概念：
- 饥饿： 由于长期得不到资源，某进程一直得不到处理机的现象
- 死循环： 某进程执行过程中一直跳不出某个循环的现象
死锁产生的必要条件
死锁的产生，以下四个条件缺一不可：
- 互斥条件： 只有对互斥资源的争抢才可能导致死锁；
- 不剥夺条件： 进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放；
- 请求和保持条件： 进程已经占用了至少一个资源，同时又提出了新的资源请求，而所请求的资源被其他进程所占用，此时请求被阻塞，但是该进程仍然保持已有的资源不放；
- 循环等待条件： 存在一种进程循环等待资源的现象，循环中的每一个进程已获得的资源同时被下一个进程所需求。
发生死锁时一定有循环等待，但发生循环等待时未必会死锁。
如果系统中还有其他同类型资源，则不会发生死锁；如果系统中每种资源只有一个，则将会发生死锁。
死锁的处理策略： - 死锁预防 - 避免死锁 - 死锁的检测及解除
死锁预防
破坏互斥条件
把只能互斥访问的资源变为共享资源。例如使用SPOOLing技术使得设备可以逻辑上共享。但是一般不常用。
破坏不剥夺条件
- 当某个进程请求新的资源而得不到时，立刻释放其已有资源，以待后面再次申请；
- 为进程设置不同的优先级，当某个进程需要的资源被其他进程占用时，可以由操作系统协作将想要的资源强行剥夺。
缺点： - 实现起来较为复杂；
这种方式会造成前一阶段工作的失效，因此仅适用于易保存和恢复的资源，例如CPU；
反复申请和释放资源会造成较大的系统开销；
若采用方案一，可能导致饥饿（某个进程一直被迫放弃已有的资源）。
破坏请求和保持条件
采用静态分配方法，在运行前一次性申请所需的全部资源，在未获得全部资源前进程不投入运行。一旦投入运行，这些资源一直归此进程所有。
缺点： - 对于使用时间很短的资源会造成资源浪费，资源利用率低； - 有可能导致某些进程饥饿。
破坏循环等待条件
采用顺序资源分配法，首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源（即编号相同的资源）一次申请完。
缺点：
- 不方便增加新的系统资源，有可能需要全部重新分配序号；
- 进程实际使用资源的顺序可能与序号不一致，会造成资源浪费；
- 必须依次申请资源，编程麻烦。
死锁避免
安全序列、不安全状态、死锁的联系
- 安全序列： 如果系统按照这种序列分配资源，则每个进程都能顺利完成。
- 安全状态： 只要能找出一个安全序列，系统就是安全状态。安全序列可能有多个。
- 不安全状态： 如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。
银行家算法
比较available数组和need矩阵，看available数组满足need矩阵哪几行，将allocation矩阵中的对应行加入available数组
在系统中有\(n\)个进程和\(m\)种资源的情况下，可以使用银行家算法来管理资源的分配。以下是银行家算法的步骤：
数据表示：
对于每个进程 \(P_i\)，声明其对各个资源的最大需求数，使用一个 \(n \times m\) 的矩阵表示，称为最大需求矩阵 \(Max\)。其中，\(Max[i, j]=K\) 表示进程 \(P_i\) 最多需要 \(K\) 个资源 \(R_j\)。
使用另一个 \(n \times m\) 的矩阵表示系统对所有进程的资源分配情况，称为分配矩阵 \(Allocation\)。
计算每个进程尚需的资源量，即 \(Need\) 矩阵，由 \(Max - Allocation\) 得到，表示各进程还需要多少资源。
用一个长度为 \(m\) 的一维数组 \(Available\) 表示当前系统中还有多少可用资源。
请求资源处理：
若 \(Request_i[j] < Need[i,j]\)，转到步骤3，否则表示请求的资源超出了最大需求，出错。
若 \(Request_i[j] < Available[j]\)，转到步骤4，否则表示尚无可用资源，\(P_i\) 需等待。
资源分配：
- 系统尝试将资源分配给 \(P_i\)，并修改相应数据：
- \(Available = Available - Request_i\)
- \(Allocation[i,j] = Allocation[i,j] + Request_i[j]\)
- \(Need[i,j] = Need[i,j] - Request_i[j]\)
- 系统尝试将资源分配给 \(P_i\)，并修改相应数据：
安全性检查：
进行安全性检查，判断此次分配后系统是否处于安全状态：
若能找到一个安全序列，则表示系统是安全的，允许分配资源给 \(P_i\)。
若找不到安全序列，系统处于不安全状态，拒绝分配资源给 \(P_i\)，使其等待。
举例
给定系统资源状态如下：
- Available = (3, 3, 2)
各进程的最大需求和已分配资源如下：
| 进程 | 最大需求 | 已分配 |
|---|---|---|
| P0 | (7, 5, 3) | (0, 1, 0) |
| P1 | (3, 2, 2) | (2, 0, 0) |
| P2 | (9, 0, 2) | (3, 0, 2) |
| P3 | (2, 2, 2) | (2, 1, 1) |
| P4 | (4, 3, 3) | (0, 0, 2) |
计算得到：
\[ \begin{align*} Max &= \begin{bmatrix} 7 & 5 & 3 \\ 3 & 2 & 2 \\ 9 & 0 & 2 \\ 2 & 2 & 2 \\ 4 & 3 & 3 \end{bmatrix} \\ Allocation &= \begin{bmatrix} 0 & 1 & 0 \\ 2 & 0 & 0 \\ 3 & 0 & 2 \\ 2 & 1 & 1 \\ 0 & 0 & 2 \end{bmatrix} \\ Need &= Max - Allocation = \begin{bmatrix} 7 & 4 & 3 \\ 1 & 2 & 2 \\ 6 & 0 & 0 \\ 0 & 1 & 1 \\ 4 & 3 & 1 \end{bmatrix} \end{align*} \]
接下来，逐行比较 \(Available\) 和 \(Need\)，选择 \(Need\) 中比 \(Available\) 小的一行，释放该进程的资源，并更新 \(Available\) 和 \(Need\)。
例如，释放 \(P1\) 的资源，则得到：
\[ \begin{align*} Need_1 &= \begin{bmatrix} 7 & 6 & 0 \\ 4 & 0 & 1 \\ 3 & 0 & 1 \\ 0 & 1 & 1 \\ 4 & 3 & 1 \end{bmatrix} \\ Available_1 &= Available + Need_1[1] = (5, 3, 2) + (3, 2, 2) = (8, 5, 4) \end{align*} \]
按照这个逻辑继续进行，直到所有进程都被释放或者无法找到满足条件的进程。
然后，再次比较 \(Available\) 和 \(Need\)，如果 \(Need\) 中有一行比 \(Available\) 小，则该行对应的进程不可满足，系统不安全，否则系统是安全的。
死锁的检测和解除
资源分配图：
结构：
- 进程节点：对应一个进程
- 资源节点：对应一类资源（可能有多个）
边：
- 进程节点 --> 资源节点：进程对资源的申请（每条边代表一个）
- 资源节点 --> 进程节点：已经为进程分配了资源（每条边代表一个）
环路：
- 若出现环路，意味着满足了循环等待条件，可能存在死锁。
- 若不存在环路，破坏了循环等待条件，必定不存在死锁。
死锁定理：
在资源分配图中，找到既不阻塞也不是孤点的进程 \(P_i\)，消去他所有的请求边和分配边；再找到下一个可以消去所有请求和分配的进程；若能消去图中的所有边，则称该图是可完全简化的。
这些步骤合理地解释了死锁检测和解除的过程。
死锁定理：
系统会发生死锁的条件是当且仅当系统状态的资源分配图是不可完全简化的。
死锁定理不需要全部的进程运行所需资源信息。
死锁的解除
在化简资源分配图后，还有边连接的进程就是死锁进程。对于死锁的进程，需要解除死锁。
- 资源剥夺法：挂起某些死锁进程（暂存到外存上），抢占其资源并分配给其他死锁的进程。需要注意防止被挂起进程产生饥饿；
- 撤销进程法（终止进程法）：强制撤销部分甚至全部死锁进程并释放其资源。优点是实现简单，缺点是会导致进程之前的努力全部木大；
- 进程回退法：让一个或多个进程回退到可以避免死锁的地步。需要系统记录进程的历史信息并设置还原点。