第 7 章 死锁
死锁：如果所申请的资源被其他等待进程占有，那么该等待进程有可能再也无法改变状态。
7.1 死锁特征
7.1.1 必要条件
如果一个系统中以下四个条件同时成立，那么就能引起死锁。
- 互斥：至少有一个资源必须处于非共享模式，即一次只有一个进程可使用。如果另一个进程申请该资源，那么申请进程应等到该资源释放为止。
- 占有并等待：一个进程应占有至少一个资源，并等待另一个资源，而该资源为其他进程所占有。
- 非抢占：资源不能被抢占，即资源只能被进程在完成任务后自愿释放。
- 循环等待：有一组等待进程{P0，P1，...，Pn}，P0等待的资源被P1占有，P1等待的资源被P2占有，...，Pn-1等待的资源被Pn占有，Pn等待的资源被P0占有。
7.1.2 资源分配图
P1 -->R1表示申请边，R1 --> P2表示分配边。
如果资源分配图没有环，那么系统就不处于死锁状态。如果有环，那么系统可能会也可能不会处于死锁状态。
7.2 死锁处理方法
一般来说，处理死锁问题有三种方法：
- 通过协议来预防或避免死锁，确保系统不会进入死锁状态。
- 可以允许系统进入死锁系统，然后检测它，并加以恢复。
- 可以忽视这个问题，认为死锁不可能在系统内发生。
第三种方法被大多数操作系统所采用，包括Linux和Windows。
死锁预防
确保至少有一个必要条件不成立。这些方法通过限制如何申请资源的方法来预防死锁。缺点是设备利用率低和系统吞吐量低。
死锁避免
要求操作系统实现得到有关进程申请资源和使用资源的额外信息。
7.3 死锁避免
最简单且最有用的模型要求，每个进程都应声明可能需要的每种类型资源的最大数量。
7.3.1 安全状态
如果系统能按照一定顺序为每个进程分配资源（不超过它的最大需求），仍然避免死锁，那么系统的状态就是安全的。更正式的说，只有存在一个安全序列，系统才处于安全状态。
安全状态不是死锁状态，相反，死锁状态是非安全状态。不是所有的非安全状态都能导致死锁。
7.3.2 资源分配图算法
如果有一个资源分配系统，它的每种资源类型只有一个实例。
引入需求边，用虚线表示。Pi ---> Rj 表示进程Pi 可能在将来的某个时刻申请资源Rj。系统资源的需求应事先说明。
采用环检查算法，复杂度O（N2）。
7.3.3 银行家算法
对于每种资源类型有多个实例的资源分配系统，资源分配图算法就不适用了。
当一个新的进程进入系统时，它应声明可能需要的每种类型资源实例的最大数量，这个数量不能超过系统资源的总和。当用户申请一组资源时，系统应确定这些资源的分配是否仍会使系统处于安全状态。如果会，就可以分配资源；否则，进程应该等待，直到某个其他进程释放足够多的资源为止。
数据结构：n为系统进程的数量，m为资源类型的种类
- Available：表示每种资源的可用实例数量，长度为m的向量
- Max：定义每个进程的最大需求，n*m的矩阵，Max[ i ][ j ] 表示进程Pi最多可申请资源类型Rj的k个实例
- Allocation：定义每个进程现在已分配的每种资源类型的实例数量，n*m的矩阵，Allocation[ i ][ j ] 表示进程Pi已经分配了资源类型Rj的k个实例
- Need：表示每个进程还需要的剩余资源，n*m的矩阵，Need[ i ][ j ] 表示进程Pi还可能申请资源类型Rj的k个实例
当一个进程申请使用资源时，银行家算法通过先试探分配给该进程资源，然后通过安全性算法判断分配后的系统是否处于安全状态，若不安全，则试探分配作废，让该进程继续等待。
安全算法
1. 初始化 Work = Allocation 和 Finish[ i ] = false。
2. while ( true ){
if ( 能找到 i 使其满足：a. Finish[ i ] == false && b.Needi <= Work ) {
Work = Work + Allocition i ;
Finish [ i ] = true;
}
else
exit();
}
3. 如果所有Finish [ i ] = true,那么系统处于安全状态。
示例说明
7.4 死锁检测
...
7.5 死锁恢复
当检测算法确定已有死锁时，可以通知管理员死锁发生，人工处理。也可以让系统自动恢复。打破死锁的两种选择：简单地中止一个或多个进程来打破循环等待；从一个或多个死锁进程那里抢占一个或多个资源。
7.5.1 进程中止
- 中止所有死锁进程
- 一次中止一个进程，直到消除死循环为止
7.5.2 资源抢占
不断地抢占一些进程的资源以便给其他进程使用，直到死锁循环被打破。但要处理三个问题：
- 选择牺牲进程
- 回滚
- 饥饿
原文：https://www.cnblogs.com/astonc/p/12154483.html