【操作系统/OS笔记15】死锁的系统模型，死锁的处理办法，银行家算法与死锁检验算法

本次笔记内容：
11.1 死锁问题
11.2 系统模型
11.3 死锁特征
11.4 死锁处理办法
11.5 死锁预防和死锁避免
11.6 银行家算法
11.7 死锁检测和死锁恢复

死锁问题

如上图，交通中的一种阻塞问题，可以类比死锁问题。

**死锁：**一组阻塞的进程持有一种资源等待获取另一进程所占有的资源。

例子如：

• 系统有2个磁带驱动器；
• P1和P2各有一个，都需要另一个。

死锁为什么会产生？进程并行。

死锁的系统模型

模型建立

两类实体：需求方与资源。

• 资源类型$R_1,R_2,...,R_m$R1​,R2​,...,Rm​：CPU cycles，memory space，I/O devices。
• 每个资源类型$R_1$R1​有$W_1$W1​实例。
• 每个进程使用资源如下：

request/get	<-- free resource
use/hold	<-- requested/used resource
release		<-- free resource

资源

可重复使用的资源

• 在一个时间只能一个进程使用且不能被删除；
• 进程获取资源，后来释放由其他进程重用；
• 处理器，I/O通道，主和副存储器，设备和数据结构，如文件、数据库和信号量；
• 如果每个进程拥有一个资源并请求其他资源，死锁可能发生。

使用资源

• 创建和销毁；
• 在I/O缓冲区的中断，信号，消息，信息；
• 如果接收消息阻塞可能会发生死锁；
• 可能少见的组合事件会引起死锁。

资源分配图表述资源使用

资源分配图是一组顶点V和边E的集合：

• V有两种类型：
• • $P=\{P_1,P_2,...,P_n\}$P={P1​,P2​,...,Pn​}，集合包括系统中的所有进程；
• • $R=\{R_1,R_2,...,R_m\}$R={R1​,R2​,...,Rm​}，集合包括系统中的所有资源类型。
• requesting/claiming edge - directed edge $P_i - > R_j$Pi​−>Rj​
• assignment/holding edge - directed edge $R_j - > P_i$Rj​−>Pi​

如上图，对于资源来讲，还包含实例个数的信息。

如上图，P_1需要R_1的资源，但是正被P_2占用；P_2需要R_3的资源，但是正被P_3占用。

但是，上图中，不存在死锁。P_3用完R_3就会释放，P_2得以运行，接着P_1得以运行。

上图中，存在2个环。所有进程都无法释放，意味着存在死锁。

如上图，尽管存在环，P_2、P_4可以释放R_1和R_2的资源，因此死锁不存在。

总结：

• 如果图中包含循环，则没有死锁；
• 如果图中包含循环：
• • 如果每个资源类只有一个实例，那么死锁；
• • 如果每个资源类有几个实例，可能死锁。

死锁的特征

死锁可能出现如果四个条件同时成立：

• 互斥：在一个时间只能有一个进程使用资源；
• 持有并等待：进程保持至少一个资源正在等待获取其他进程持有的额外资源；
• 无抢占：一个资源只能被进程自愿释放，进程已经完成了它的任务之后；
• 循环等待：存在等待进程集合$\{P_0,P_1,...,P_N\}${P0​,P1​,...,PN​}，P_0正在等待P_1所占用的资源，P_1正在等待P_2所占用的资源，…，P_{N-1}正在等待P_N所占用资源，P_N正在等待P_0所占用资源。

死锁的必要条件如上，但上述四个条件并非死锁的充分条件。

死锁的处理办法

死锁处理办法策略

• 确保系统永远不会进入死锁状态；
• 运行系统进入死锁状态，然后恢复；
• 忽略这个问题，假装系统中从来没有发生死锁；用于大多数操作系统，包括UNIX。

死锁预防

思想为限制申请方式，包含以下策略：

• 取消互斥：共享资源不是必须的，必须占用分共享资源；（这个方法过于强硬）
• 取消占用并等待：必须保证当一个进程请求的资源，它不持有任何其他资源；（进程在不同时间段需要资源不同，因此这个方法对并行有影响，系统利用率会很低）
• 无抢占：如果进程占有某些资源，并请求其他不能被立即分配的资源，则释放当前正占有的资源；被抢占资源添加到资源列表中；只有当它能够获得旧的资源以及它请求新的资源，进程可以得到执行；（这个方法比较极端暴力）
• 打破循环等待：对所有资源类型排序，要求每个进程按照资源的顺序进行申请。（这个办法相比前三个，较为合理）

打破循环等待，在嵌入式操作系统中应用较多。因为嵌入式操作系统中，资源、应用类型有限，可以针对特殊情况进行具体设计。

死锁避免

需要系统具有一些额外的先验信息提供。主要包含以下三种办法：

• 最简单和最有效的模式是要求每个进程声明它可能需要的每个类型资源的最大数目；
• 资源的分配状态是通过限定提供与分配的资源数量，和进程的最大需求；
• 死锁避免算法动态检查的资源分配状态，以确保永远不会有一个环形等待状态；

死锁避免的思想：

• 当一个进程请求可用资源，系统必须判断立即分配是否能使系统处于安全状态；
• 系统处于安全状态指：针对所有进程，存在安全序列；
• 序列<P_1,P_2,…,P_N>是安全的指：针对每个P_j，P_i要求的资源能够由当前可用的资源+所有的P_j持有的资源来满足，其中j<i：
• • 如果P_i资源的需求不是立即可用，那么P_i可以等到所有P_j完成；
• 当P_i完成后，P_{i+1}可以得到所需要的资源，并执行、返回所分配的资源，并终止；
• 用同样的方法，P_{i+2}、…、P_N能获得其所需的资源。

如上图，避免死锁确保系统不进入unsafe状态，则系统不会死锁。

如上图，死锁避免机制检验下一时刻的状态是否安全，然后根据情况将edge转换（图中实现虚线的转换，即尽管你有请求意图，但是可能并不允许占用）。

死锁避免：银行家算法

迪克斯拉在设计早期操作系统时，受银行家启发而提出的算法。客户申请贷款，类比进程申请资源。

Banker’s Algorithm前提条件

• 多个实例；
• 每个进程都必须能最大限度地利用资源；
• 当一个进程请求一个资源，就不得不等待；
• 当一个进程获得所有的资源就必须在一段有限的时间释放它们。

基于上述前提条件，银行家算法通过尝试寻找允许每个进程获得的最大资源并结束（把资源返还给系统）的进程请求一个理想执行时序，来决定一个状态是否是安全的。不存在这满足要求的执行时序的状态都是不安全的。

Banker’s Algorithm数据结构

• n = 进程数量；
• m = 资源类型数量；
• Max（总需求量）：n×m矩阵，如果M[i,j]=k，表示进程P_i最多请求资源类型R_j的k个实例；
• Available（剩余空限量）：长度为m的向量，如果Available[j]=k，有k个类型R_j的资源实例可用；
• Allocation（已分配量）：n×m矩阵，如果Allocation[i,j]=k，则P_i当前分配了k个R_j实例；
• Need（未来需要量）：n×m矩阵，如果Need[i,j]=k，则P_i可能需要至少k个R_j实例完成任务。

$Need[i,j]=Max[i,j]-Allocation[i,j]$Need[i,j]=Max[i,j]−Allocation[i,j]

Safety State Estimating Algorithm

1 Work和Finish分别是长度为m和n的向量，初始化：

Work = Available					// 当前资源剩余空闲量
Finish[i] = false for i (1,2,...,n)	// 线程i没结束

2 找到这样的i：（找出Need比Work小的进程i）

(a) Finish[i] = false
(b) foreach(j) Need[i, j] <= Work[j]

如果没有找到这样的i，转到4。

3 认为进程可以正常结束，并回收资源：

Work = Work + Allocation[i]	// 进程i的资源需求量小于当前的剩余空闲资源量
Finish[i] = true			// 所以配置给它再回收

转到2。

4 检验是否是处于安全状态：

If Finish[i] == true for all i:
	then the system is in a safe state.
// 所有进程的Finish为true，表明系统处于安全状态。

Banker’s Algorithm

基于上述安全判断算法，设计银行家算法。

Initial: Request = request vector for process Pi. If Request[i] = k then process Pi wants k instances of resource type Ri.

While:

1. 如果Request_i <= Need_i，转到步骤2。否则，提出错误条件，因为进程i已经超过了其最大要求；
2. 如果Request_i <= Available，转到步骤3。否者，P_i必须等待，因为资源不可用；
3. 假装给P_i分配他需要的资源：

// 生成一个需要判断状态是否安全的资源分配环境
Available = Available - Request;
Allocation_i = Allocation_i + Request;
Need_i = Need_i - Request;

• 如果返回safe，将资源分配给P_i；
• 如果返回unsafe，P_i必须等待，旧的资源分配状态被恢复。

例子

例1：得到安全执行序列

如上图，P2首先满足Need小于等于Available，将P2调用，进入P2正常结束状态。

如上图，P2正常结束后，再对P1、P3和P4进行检查，P1满足Need小于等于Available。将P1运行，再正常结束，释放资源。依此类推。

最终得到一个安全的执行序列：P2,P1,P3,P4。

例2：进入了不安全状态

如上图，当进程占用资源、申请资源、系统现有可用资源如上时，则是不安全状态。银行家算法的作用就是避免这种状态：在进入这种状态前（某个进程申请一部分资源时），银行家算法会检验一下状态（进程申请资源成功后）是否安全，从而运行或取决该进程申请这部分资源。

死锁检测

• 运行系统进入死锁状态；
• 死锁检测算法；
• 恢复机制。

死锁检测算法

第一种办法：

如上图，该办法适用于每个资源类型单一实例。思想为，将图简化成只有进程顶点后，检查是否存在环。存在环则死锁。

第二种办法：

数据结构：

• Available：长度为m的向量表示每种类型的可用资源数量；
• Allocation：一个n×m矩阵定义了当前分配给各个进程每种类型资源的数量。如果Allocation[i,j]=k，进程P_i拥有资源R_j的k个实例；
• Request：一个n×m矩阵表示各进程的当前请求。如果Request[i,j]=k，表示进程P_i请求k个资源R_j的实例。

死锁检验算法：

1. Work和Finish分别是长度为m与n的向量，初始化：

(a) Work = Available	// work为当前空闲资源量
(b) foreach(i) if Allocation[i] > 0
	then Finish[i] = false
	otherwise Finish[i] = true
	// Finsi为线程是否结束

2. 找出这样的索引：

(a) Finsih[i] == false	// 线程没有结束
(b) Requestp[i] <= Work	// 且需要资源量小于当前贡献资源量

如果没有找到，转到4。

3. 让该线程正常结束，并释放资源：

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

4. 通过Finish检验是否有死锁：

foreach(i) if Finish[i] == false	// 系统处于死锁状态
if Finish[i] == false				//P_i死锁

算法需要O(m×n^2)操作检验是否系统处于死锁状态。

银行家算法、死锁检验算法还要求先验量（每个进程的需求量）。因此，银行家算法、死锁检验算法很少实际使用，而多用在调试里。

检验算法的使用

• 何时、使用什么样的频率来检验依赖于：
• • 死锁多久可能会发生？
• • 多少进程需要被回滚？
• one for each disjoint cycle：如检验算法多次被调用，有可能是资源图有多个循环，所以我们无法分辨出多个可能死锁进程中的哪些“造成”死锁。

因此，死锁检验很少单独实际使用。

死锁恢复

通过kill进程的方式

• 终止所有死锁进程；
• 在一个时间内终止一个进程直到死锁消除；
• 终止进程的顺序应该是：
• • 进程的优先级；
• • 进程运行了多久以及需要多少时间才能完成；
• • 进程占用的资源；
• • 进程完成需要的资源；
• • 多少进程需要被终止；
• • 进程是交互还是批处理。

死锁恢复也存在极端手段的问题。死锁恢复是最后一个手段，一般情况下，应避免产生死锁。

通过资源抢占的方式

• 选择一个受害者：最小的成本；
• 回滚：返回到一些安全状态，重启进程到安全状态；
• 饥饿：同一进程可能一直被选作受害者，包括回滚数量。

总结

实际上，通用操作系统普遍采用“鸵鸟方法”，即不理睬，如果死锁真出现，再恢复。