操作系统（四）
引言
对付死锁，有一系列预防，避免，检测，恢复的方法。但事实是，操作系统只采用鸵鸟算法，即不预防、不避免，对可能出现的死锁采取放任的态度。下面具体来探寻里面的奥妙~
文章导读
- 死锁概述
- 死锁的预防
- 死锁的避免（银行家算法，例题）
- 死锁检测和恢复
一、死锁概述
定义
如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件，那么该组进程是死锁的。
死锁的四个必要条件
- 互斥：在一个时间只能有一个进程使用资源。
- 请求和保持（持有并等待）：进程保持至少一个资源正在等待获取其他进程持有的额外资源。
- 不可抢占：一个资源只能在进程已经完成了它的任务之后，被自愿释放。
- 循环等待：存在n个进程，进行循环等待所占资源。
值得注意的是，死锁出现后，必须满足这四个条件；但是如果出现这四个条件，不一定出现死锁。
对于死锁处理的办法有死锁预防，死锁避免，死锁检测，死锁恢复。
二、死锁的预防
预防死锁的思想就是设计一种方法，一定不会出现死锁，即破坏死锁出现的四个必要条件。
2.1 破坏互斥
让共享资源不是必须的，必须占用非共享资源。
缺点
扼杀了共享资源，系统有了很大的局限性。
2.2 破坏请求和保持
必须保证当一个进程请求的资源，它不持有任何其他资源。
缺点
需要进程请求并分配其所有资源，它开始执行之前或允许进程请求资源仅当进程没有资源；资源利用率很低，可能引发饥饿。
改进后的方法
允许一个进程只获得运行初期所需资源，便开始运行，运行的过程中再逐步释放不用的资源，请求新的资源。能够提高设备的利用率，减少进程发生饥饿的几率。
2.3 破坏不可抢占
如果进程占有某些资源，并请求其他不能被立即分配的资源，则释放当前正占有的资源。
实现细节：
1.被抢占资源添加到资源列表中。
2.只有当它能够获得旧的资源并且请求新的资源存在，进程可以得到执行。
缺点
实现复杂，代价高。
2.4 破坏循环等待
对所有资源类型进行排序并赋上序号，要求每个进程按照资源的顺序进行申请。如果需要多种资源，必须先请求序号低的资源，再请求序号高的。如果占有序号高的又想请求序号低的，必须释放所有序号大于低序号的资源。采用这种线性的方式，能够打破循环等待的条件。
缺点
1.资源的序号必须相对稳定，限制新设备的增加。
2.作业使用各类资源的顺序与系统规定顺序不同，造成浪费。
3.增加用户程序编程时的代价，必须按照规定次序申请资源。
三、死锁的避免
既然死锁的预防策略都显得特别的极端，就看看有哪些避免策略。避免死锁抓住了进程请求资源的这一契机，进程请求资源时先判断会不会产生死锁，如果会就不给。而不是基于破坏死锁必要条件的考虑。
3.1 主要思路
1.最简单和最有效的模式是要求每个进程声明它可能需要的每个类型资源的最大数目。
2.资源的分配状态是通过限定与分配的资源数量，和进程的最大需求。
3.死锁避免算法动态检查的资源分配状态，以确保永远不会有一个环形等待状态。
3.2 银行家算法
银行家算法是用于避免死锁的算法。
前提条件
1）多个实例
2）每个进程都必须能最大限度地利用资源
3）当一个进程请求一个资源，就不得不等待
4）当一个进程获得所有的资源就必须在一段有限的时间释放他们
3.2.1 需要的数据结构
n=进程数量，m=资源类型数量。
Max（总需求量）： 矩阵。如果Max[i,j]=k，表示进程
最多请求资源类型
的k个实例。
Available（剩余空闲量）：长度为m的向量。如果Available[j]=k，有k个类型的资源实例可用。
Allocation（已分配量）： 矩阵。如果Allocation[i,j]=k，则
当前分配了k个
的实例。
Need（未来需要量）： 矩阵。如果Need[i,j]=k，则
可能需要至少k个
实例完成任务。
Need[i,j]=Max[i,j]-Allocation[i,j]
3.2.2 银行家算法
银行家算法主要用于资源的预分配判断和记录各个变量的改变。
银行家算法流程图
1. ，跳转步骤2。否则认为出错。
注：是进程
对资源
的请求数量。
2.如果，跳转至步骤3，否则认为出错。
3.系统尝试把资源分配给进程 ，并修改：
4.系统执行安全性算法，检查此次分配后系统是否处于安全状态。若安全才分配，否则将本次尝试作废，恢复原来的资源分配状态，让进程 等待。
3.2.3 安全性算法
安全性算法主要检测当前的系统状态会不会发生死锁。
前提
Work和Finish分别是长度为m和n的向量；
Work表示系统可提供给进程继续运行所需的各类资源数目；
Finish表示系统是否由足够的资源分配给进程，使之运行。
安全性算法流程图
1.初始化阶段，Work=Available，表示当前资源剩余空闲量就是可获得的资源量。
Finish[i]=false，表示进程 没结束。
2.从进程集合P中，找这样的进程 ：Finish[i]=false并且Need[i,j]<=Work[j]。如果没找到，转到步骤4。
3.假设进程 获得资源后，执行完毕并释放资源。
Work[j]=Work[j]+Allocation[i,j]。表示进程i的资源需求小于当前剩余空闲资源量，所以配置给它再回收。
FInish[i]=true。将进程标志为安全状态。
转到2继续执行，直到所有进程都满足要求~
4.如果所有进程都满足Finish[i]==true ，则表示系统处于安全状态；否则处于不安全状态。
注：银行家算法主要用于将资源进行与分配，看能不能分配。而安全性检查是检查分配后，对其他进程的影响，是否处于不安全的状态，寻找安全的序列。
3.3 例题
系统有5个进程和3种资源，假定在 时的资源分配如下图所示：
问题一：此系统是不是安全的？
对其进行安全性分析，找到Need<=Available的进程，此时应该是 ，将资源预分配。
执行完毕后，释放Allocation，此时的Available等于5，3，2。然后接着找Need<=Available的进程，以此类推，可以得到一个安全序列为
，
，
，
，
。
问题二： 进程发出
时，系统按照银行家算法，是否应该分配资源？
1）首先判断
2）再判断
3）预分配资源，Available=(2,3,0); ;
。
4）进行安全性检查，可知安全序列为 ，
，
，
，
。
所以可以分配。
四、死锁检测和恢复
死锁检测则说明允许系统进入死锁状态，基于死锁检测算法判断是否处于死锁状态，如果进入死锁状态就触发恢复机制。
4.1 死锁检测算法
设置Available，Allocation，Request变量。和安全性算法很像。
1.初始化：Work=Available。遍历进程，当Allocation[i,j]>0，Finish[i]=false；否则Finish[i]=true。
解释：Work和Finish分别是长度为m和n的向量。Allocation[i,j]>0，说明进程持有资源。此时把不占用资源的进程都计入表中。
2.找到Finish[i]==false&&Request[i,j]<=Work，没有则转到步骤4。
解释：把持有资源并且Request[i,j]<=Work的进程进行预分配。
3.Work[j]=Work[j]+Allocation[i,j]；Finish[i]=true。转到步骤2。
解释：让进程释放资源，增加工作向量，能够正常结束的进程，记录到表中。
4.如果有一个进程处于false，则处于不安全的状态。
此算法的时间复杂度为
总结：由于死锁出现的概率比较小，银行家算法及检测算法的开销都比较大，而且需要预知进程对资源的最大需求数，因此一般用于系统调试。而不会真正用于操作系统的运行中。
4.2 死锁的解除
最常用的是抢资源和终止进程。
终止
撤消陷于死锁的全部进程；
逐个撤消陷于死锁的进程，直到死锁不存在。
抢占
从陷于死锁的进程中逐个强迫放弃所占用的资源，直至死锁消失；
从另外的进程那里强行剥夺足够数量的资源分配给死锁进程，以解除死锁状态。
参考文章：操作系统第五篇【死锁】，《计算机操作系统 第四版》
如果看得不过瘾，可以戳：操作系统（五）—文件管理，设备管理