操作系统概念 --- 读书笔记第7章：死锁

迈不过友情╰ 2022-05-31 09:50 276阅读 0赞

7.1 死锁特征

7.1.1 死锁的定义机器特征

对于多个进程竞争一定的资源，某个进程申请资源，如果资源不可用就会陷入等待状态，如果所有的进程都处于等待状态，而无法做出其他的改变，那么就陷入了死锁状态，这个就是死锁。

如果一个系统中下面4个条件同时满足，那么就会引起死锁：

1.  **互斥**：存在资源一次只能让一个进程使用
2.  **占有并等待**：一个进程至少占用一个资源，并等待另一个资源
3.  **非抢占**：资源是非抢占的，也即一个进程拥有的资源不可以被别的进程抢占
4.  **循环等待**：有一组等待进程相互等待着下一个进程的资源

7.1.2 资源分配图

死锁可以通过构造资源分配图来发现，这个是一个有向图，假如不存在环那么肯定不存在死锁情况；如果存在环，那么可能存在死锁。

7.2 死锁处理方法

从原理上讲一共有三种方法处理死锁：

1.  通过协议预防或者避免死锁，确保系统不会进入死锁状态
2.  允许系统进入死锁状态，然后检测并修复
3.  忽视死锁问题，认为死锁不可能在系统中发生

大部分系统都采用第三种方法，就是忽视死锁，需要开发人员自己处理死锁问题。

7.3 死锁预防

所谓的死锁预防就是确认死锁的4个必要条件至少有一个不成立。

7.3.1 互斥  
有些资源本身就是非共享的，所以一般不能通过打破互斥来预防死锁。

7.3.2 占有并等待  
就让一个进程申请并占有所有的资源，否者就不占用资源，这个可能出现饿死的现象。

7.3.3 非抢占  
对于无法申请到所有资源的进程的资源可以被抢占。

7.3.4 循环等待  
对所有的资源做完全排序，并且要求每个进程按照递增顺序来申请资源

7.4 死锁避免

上面的是通过现在资源来是死锁的条件至少有一个不成立来实现的死锁的预防，这个存在设备利用率低的缺点，其实可以通过以后申请资源的附加信息**来动态的判断死锁**  
;  
7.4.1 资源分配图算法

就是构建资源分配图，然后判断是否存在环路，假如不存在环那么肯定不存在死锁情况；如果存在环，那么可能存在死锁。

7.4.2 银行家算法

当有多个实例资源的时候资源分配图算法就不适用了，这个时候可以使用银行家算法解决，这个效率要比资源分配图方案低。本方案之所以成为银行家算法是因为它可以适用于银行系统，当它不可以满足所有客户的需求的时候，银行是绝对不会分配现金。

银行家算法中的数据结构  
(1).可利用资源向量Available  
(2).最大需求矩阵Max  
(3).分配矩阵Allocation  
(4).需求矩阵Need

**.安全性算法**  
(1).设置两个向量,工作向量Work,在执行安全性算法开始时 Work=Available;Finish:表示有足够的资源分配给进程，使之运行完成,Finish\[i\]=false;当有足够资源分配给进程时，再另Finish\[i\]=false  
(2).从进程集合中找到一个满足该条件的进程:

Finish[i]=false
           Need[i][j] <= Work[j]

(3).当进程获得资源后，可顺利执行，并修改Work向量和Finsh向量

Work[i] += Allocation[i][j]
          Finish[i]=true

(4).如果所有进程的Finish\[i\]=true说明系统处于安全状态，否则系统处于不安全状态.

**资源请求算法**  
Request表示某个进程的资源请求向量，  
(1).如果Request\[i\] <= Need\[i\]\[j\]转下步，否则它所需要的资源数已超过它所需要的最大值  
(2).如果Request\[i\] <= Available\[i\]\[j\]转下步，否则尚无足够资源，进程需等待  
(3).系统试分配给进程p,并修改Available,Allocation和Need

Available[j] -= Request[j]
                   Allocation[i][j] += Request[j]
                   Need[i][j] -= Request[j]

(4)系统执行安全性算法，检查此次资源分配后系统是否处于安全状态.若安全，才正式分配；否则恢复原来的分配状态，让该进程等待

7.5 死锁检测算法

对于单个实例的资源，可以使用等待图寻找环的方法，这个就是资源分配图寻找环的方法。还可以用银行家算法的安全性检测算法，最后判断Finish\[i\]即可，如果为false表示进程i存在死锁。

7.6 死锁恢复

在判断确认存在死锁之后，然后就考虑解开死锁，一共有两种方法：

*  **终止所有进程**：这个很明显可以解决死锁，但是代价极大，因为这些进程的部分计算结果必须要放弃。
 *  **一次终止一个进程知道不存在死锁**：这个方法开销也大，因为每终止一个进程就要做一遍死锁检测算法。

同时要说明的是终止一个进程并不容易，可能造成文件不一致的情况，所以这个很麻烦。