第七章 死锁¶
概述¶
定义¶
每个进程都占用着若干个资源，同时又在等待得到另外某些进程所占用的资源，造成所有进程都无法进行下去的现象
资源¶
可抢占：CPU、内存
不可抢占：打印机
资源的使用分为三个步骤：
- 申请资源【申请不成功会被阻塞】
- 使用资源
- 释放资源
模型¶
发生四个条件：
- 资源互斥条件：每一个资源最多只能同时被一个进程所使用
- 请求和保持条件：进程可以占用资源，还可以请求资源；
- 不可抢占条件：进程已经占用的资源，不会被强制性拿走
- 环路等待条件：形成环路链，每一个进程都在等待环路链中下一个进程所占用的资源。
资源分配图：
-
进程：圆圈
-
资源：方框【改进：在圈里面加点】
- 进程占用资源：资源指向进程
- (进程请求资源)资源阻塞进程：进程指向资源
结论：
- 如果有环：
- 如果每一种资源类型只有一个实例：死锁
- 如果不止一个实例：可能死锁
- 如果无环：
- 不会死锁
应对策略：
- 不管了
- 死锁的检测和解除：允许发生，但需要在检测中及时发现，然后采取措施解除
- 动态避免：通过精心设计的资源分配方案来避免
- 死锁预防：破坏死锁发生的四个条件
死锁的检测和消除¶
检测算法¶
（单资源）
人工观察法：
- 资源分配图中存在封闭的环路
算法：
- 从每个点开始 dfs 找环
（多个资源）
资源分配图的简化：
- 找到不阻塞也不孤立的节点，消去所有的边；
- 不死锁 \(\iff\) 图可以完全简化到没有边
解除¶
- 剥夺资源：把资源从一个进程手中抢到另一个进程手中；用完之后再归还
- 会影响正常运行
- 进程回退：定期保存进程信息，这样就可以回退到没有死锁的时候
- 代价很高
- 撤销进程：kill进程
- 伤害程度很大
死锁的避免¶
在资源分配的过程中就避免死锁的发生
安全状态¶
状态表示：E 表示总资源向量，A 表示空闲资源向量（1 * m），C 表示当前分配矩阵，R表示请求矩阵（n*m）
安全状态满足：
- 自身不存在死锁问题
- 存在某种调度顺序，使得即使在最坏的情况下（所有进程同时请i求），每个进程也能顺利结束
- 也就是逐个进行
银行家算法¶
给每个人设置一个（猜测的）上限
（单一资源）
首先满足还需要最少的人，然后一步步推，看有没有可能满足所有人；
（多个资源）
看有没有能满足的，就满足；O(n^2)
无用的：
- 请求矩阵 R 得不到
- 进程的个数不知道
- 资源的个数不知道（磁带机突然坏了）
死锁的预防¶
破坏四个必要条件
- 允许多个进程同时使用一个资源
- e.g. 多加一层假脱机
- 不具有普遍性
- 破坏请求和保持条件
- 要求一次申请完：但不能知道需要多少，难以保证使用效率
- 要求先释放再申请：可能被饿死
- 破坏环路条件：
- 申请资源的时候，严格按照递增次序进行，否则操作系统不予分配
- 存在无法取得所有资源的问题