OS复习笔记ch6-2

死锁的解决

死锁的预防（打疫苗）
死锁的避免（戴口罩）
死锁的检测（做核酸）

死锁的预防

前面我们提到了死锁的四个必要条件

防止前三个必要条件，就是间接预防
防止最后一个必要条件–循环等待，就是直接预防

接下来我们讨论一下这四个条件如何预防

互斥访问：系统属性不可修改，必须支持
保持和请求：要求一次性请求所需的全部资源
- 进程得到资源前要阻塞很长时间
- 降低了系统利用率和并发程度
- 有可能无法预先知道所需资源
不可剥夺：修改为可剥夺
1. OS可以实现，适用于资源的使用状态可以保存并恢复
2. 处理器和内存的资源可剥夺（上下文、页面置换算法）
循环等待：
1. 需要定义一个资源类型的线性序，资源在申请的时候必须按照这个序
2. 效率不高，减缓了进程的推进，以及不必要地拒绝资源访问

死锁的避免

系统需要动态作出决定：如果当前资源分配请求满足，是否会导致死锁。

需要未来的进程资源请求
动态判定当下情况有没有可能发生死锁

两种方式：

拒绝进程启动：如果进程资源请求可能导致死锁则不启动进程
拒绝资源访问：如果本次分配可能导致死锁，则拒绝进程的增量资源请求

拒绝进程启动

系统中有n个进程，m种资源

R是资源总数矩阵
V是可用的资源矩阵
claim是最大需求矩阵
allocation是已经分配的资源矩阵

保守策略

e.g.

假设银行有账面200万，有三个客户来贷款，总量分别是100、80、60万。按照保守策略，银行对第一个用户和第二个用户贷款申请可以批准一次付清，但是第三个用户就不能批准了，相当于拒绝了第三个用户的贷款申请（类比进程启动）。

拒绝资源分配

著名的银行家算法

假设按照上述案例，银行分批贷款，第一次分配完后账面只剩下10万，此时第二轮分期只能给user2，否则user1和3满足不了，后期也收不回本金。所以，银行只能一直拒绝两者的催款直到user2还款。（类比系统资源，OS会根据当前状况动态决定资源分配，是否需要拒绝进程的资源申请）。

这里就要找到安全序列，该序列可以依次满足不同用户的最大需求。

来看OS如何进行资源分配

R = V + A（资源总数 = 可用资源+已经分配的资源）

这里遍历矩阵C - A每行和V对比，找到某个在有限时间内可以执行完将资源归还给系统的进程。经过多次分配，直到所有进程运行完毕，然后得到安全分配序列。
如上图，能符合011的就只有P2进程可以满足，也就是说OS接下来只能一次满足P2进程的资源申请要求，此时安全队列中加入P2。P2执行结束之后释放自己的所有资源，此时可用资源就变成了673。

同理，我们按照之前的分配策略，可以发现对于这四个进程的唯一安全分配序列是P2→P1→P3→P4.

举一个不安全示例
当进程1在第一次剩余资源分配的时候请求资源R3，如果OS分配出去，会导致进程2也不能满足最大需求，这个时候就找不到安全分配序列，很容易发生死锁，所以之前就要拒绝进程1的资源分配请求。

教科书上给了伪代码，感兴趣的小伙伴可以看一下

避免死锁有一些优势，但是缺点也很明显。
优势

不需要如死锁检测一样抢占、回滚进程
同死锁预防相比，资源分配限制少
缺点
需要提前声明最大资源请求
设计进程独立且无同步需求
分配资源数目固定
当拥有资源时进程不退出

一般通用的OS很难满足上述需求，所以只能是理论上分析。但是对于一些嵌入式系统，由于代码和硬件固化，或许可以按照银行家算法去设计避免死锁。

死锁的检测

检测频率

检测的频率如何控制呢？
如果每次资源请求的时候都检查是否有死锁，系统开销就会很大

两个思路

进程阻塞时间过长则检测
资源利用率下降则检测

这里可以使用拓扑排序找资源分配回路（需提前简化，以防伪回路）
这个涉及图论中的邻接矩阵的表示，利用的也是前面的V、A，还有一个请求矩阵Q
所有进程都要先打上“未死锁”标签，然后检查进程序列的标签中是否有“死锁”

具体执行过程见PPT，这里不做重点

让我们来分析一些各个进程的情况：
首先，p4肯定没问题，因为它的的分配矩阵行全为0，第一步就被标记了。p3在p4的基础上没问题，因为执行第三步的时候发现p3满足条件1，于是第四步p3被标记。
而p1、p2死锁，因为返回到步骤三发现此时已经找不到符合条件的进程了，检测终止，此时两个进程未标记符合死锁条件。