死锁预防与死锁避免

【死锁预防】

预防死锁的方法是通过破坏死锁的四个必要条件中的一个或几个，以避免发生死锁

由于互斥条件是非共享设备所必须的，不仅不能改变，还要加以保证，因此主要是破坏产生死锁的后三个条件

• 破坏请求与保持条件：系统必须做到当一个进程在请求资源时，其不能持有不可抢占资源，因此一般利用 AND 信号量机制，在进程开始前，一次性地为进程申请所需的全部资源
• 破坏不可抢占条件：允许进程先运行，但当提出的新要求不被满足时，必须释放其已保持的所有资源，待以后需要时再重新申请
• 破坏环路等待条件：将所有资源按类型进行线性排队，赋予不同序号，所有进程对资源的请求必须严格按照资源序号递增的次序提出，从而保证在形成的资源分配图中不会出现环路

可以看出，破坏请求与保持条件，算法简单，易于实现且十分安全，但资源浪费严重，且进程可能会延迟运行；破坏不可抢占条件实现复杂，可能会造成反复申请与释放的情况；破坏环路等待条件较前两者有了极大改善，资源利用率与系统吞吐量有了明显提高，但存在资源编号限制新设备的增加、应用中的使用设备顺序与规定顺序不协调等情况

【死锁避免】

预防死锁的限制条件都太强，造成一定程度上的应用不变，因此在实际应用中，常采用避免死锁的方法，避免死锁只施加较弱的限制条件，但获得了令人满意的系统性能

安全状态与安全序列

在避免死锁方法中，将系统的状态分为安全状态与不安全状态，当系统处于安全状态时，可避免发生死锁，当系统处于不安全状态时，可能进入死锁：

• 安全状态：系统能按某种进程顺序为每个进程分配所需资源，直至满足每个进程对资源的最大需求，并能顺利完成
• 不安全状态：系统无法找到一种使多个进程能够顺利分配资源执行完的安全序列

而安全序列，就是指系统按此进程序列进行分配资源，就能使每个进程都顺利完成

---

假定系统中有三个进程 $P_1,P_2,P_3$，共有 $12$ 个资源，三个进程分别要求 $10$ 个、$4$ 个、$9$ 个资源，假设在 $T_0$ 时刻，进程 $P_1,P_2,P_3$ 已获得 $5$ 个、$2$ 个、$2$ 个资源，尚有 $3$ 个资源未分配，那么有：

进程	最大需求	已分配	可用
$P_1$	$10$	$5$	$3$
$P_2$	$4$	$2$
$P_3$	$9$	$2$

经过分析可知，由于存在一个安全序列 $P_2,P_1,P_3$，那么系统处于安全状态

即将剩余的 $3$ 个资源取出 $2$ 个分配给进程 $P_2$，使其继续运行，待执行完毕后即可释放出 $4$ 个资源，此时有：

进程	最大需求	已分配	可用
$P_1$	$10$	$5$	$5$
$P_2$	$0$	$0$
$P_3$	$9$	$2$

此时可用资源达到了 $5$ 个，那么再将这 $5$ 个资源分配给进程 $P_1$，使其继续运行，待运行完毕后，即可释放出 $10$ 个资源，此时有：

进程	最大需求	已分配	可用
$P_1$	$0$	$0$	$10$
$P_2$	$0$	$0$
$P_3$	$9$	$2$

这时进程 $P_3$ 就有足够的资源，从而使得每个进程都能顺利完成

每次资源分配时，都应按照上述实例来分析资源分配图，看该次操作后是否有安全序列，若不存在安全序列，说明该操作会使系统进入不安全状态

需要注意的是，只要使系统始终处于安全状态，便可避免发生死锁，但不是所有的不安全状态都是死锁状态。

银行家算法与安全性算法

基本思路

银行家算法是最有代表性的避免死锁的算法，其有 Dijkstra 提出，该算法因能用于银行系统现金贷款的发放而得名

该算法随时对系统中的所有资源信息进行统计，包括每种资源的数量、已分配给各进程的数量等，每当进程提出某种资源请求时，会判断该请求分配后是否安全，如果安全才分配

也就是说，对每个资源请求的处理都要保证系统始终从一个安全状态到另一个安全状态

数据结构

1.进程请求资源的数量

进程请求某类型资源的数量 Request[i][j]：代表进程 $P_i$ 请求 $j$ 类型资源的数量

例如：$Request[i][j]=k$ 表示进程 $P_i$ 需要 $k$ 个 $j$ 类型的资源

2.各类可利用资源的数量

各类可利用资源的数量 Available[m]：包含 $m$ 个元素，每个元素代表一类可利用的资源数目，初始值是系统配置的该类资源的全部数目，值随着资源的分配与回收而动态改变

例如：$Available[j]=k$ 表示系统中 $j$ 类资源现有可用资源 $k$ 个

3.每个进程对每类资源的最大需求

每个进程对每类资源的最大需求 Max[n][m]：系统 $n$ 个进程中每个进程分别对 $m$ 类资源的最大需求，初始值是进程的需要资源数

例如：$Max[i][j]=k$ 表示进程 $i$ 需要 $j$ 类资源的最大数目为 $k$

4.每个进程对每类资源的已分配矩阵

每个进程对每类资源的已分配矩阵 Allocation[n][m]​：系统 $n$ 个进程中每个进程分别对 $m$ 类资源已获得的资源数量

例如：$Allocation[i][j]=k$ 表示进程 $i$ 当前已获得 $j$ 类资源的数量为 $k$

5.每个进程对每类资源的需求矩阵

每个进程对每类资源的需求矩阵 Need[n][m]​：系统 $n$ 个进程中每个进程分别对 $m$ 类资源还需要的资源数量

例如：$Need[i][j]=k$ 表示进程 $i$ 还需要 $j$ 类资源 $k$ 个

需要注意的是，上述的三个矩阵存在如下关系：

$$Max[i][j]=Allocation[i][j]+Need[i][j]$$

安全性算法

安全性算法用于检查系统是否处于安全状态，其工作流程如下：

1.设置工作向量与标记向量

工作向量 Work[m]：表示系统可提供给进程继续运行所需的各类资源数目，其初始值与 Available[m] 向量相同

例如：$Work[j]=k$ 表示系统中 $j$ 类资源可提供给进程 $k$ 个

标记向量 Finish[n]：表示系统是否有足够的资源分配给进程，初始值为 false，当有足够资源分配给进程 $P_i$ 时，有 Finish[i]=true

2.在进程集合中寻找进程

在进程集合中找到一个满足下述条件的进程 $P_i$：

$$\begin{cases} Finish[i]=false\\ Need[i][j] \leq Work[j] \end{cases}$$

若能找到，执行步骤 3，否则，执行步骤 4

3.分配资源

当进程 $P_i$ 获得资源后，可顺利执行，直至完成，并释放出分配给他的资源，因此执行：

$$\begin{cases} Work[j]=Work[j]+Allocation[i][j]\\ Finish[i]=true \end{cases}$$

然后转到步骤 2，寻找下一个满足条件的进程

4.判断安全状态

若所有进程的 $Finish[i]=true$ 均满足，则表示系统处于安全状态，否则，系统处于不安全状态

银行家算法

银行家算法是一种资源分配策略，在经过安全性算法确定系统安全状态后，若处于安全状态，则执行该算法分配资源

当进程 $P_i$ 发出资源请求后，系统按下述步骤进行检查：

1. 若 $Request_i[j] \leq Need[i][j]$，转向步骤 2，否则认为出错，即所需资源数已超过宣布的最大值
2. 若 $Request_i[j] \leq Available[j]$，转向步骤 3，否则表示尚无所需资源，进程 $P_i$ 需等待
3. 系统试探着将资源分配给进行 $P_i$，并修改下面数据结构中的值： $$\begin{cases} Available[j] = Available[j]-Request_i[j]\\ Allocation[i][j]=Allocation[i][j]+Request_i[j]\\ Need[i][j]=Need[i][j]-Request_i[j] \end{cases}$$
4. 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态，若安全，则将资源正式分配给进程 $P_i$，以完成本次分配，否则，本次的试探分配作废，恢复原来的分配状态，让进程 $P_i$ 等待

实例

安全性算法

设系统有 $5$ 个进程 $\{P_0,P_1,P_2,P_3,P_4\}$，$3$ 类资源 $\{R_1,R_2,R_3\}$，数量分别为 $10,5,7$，在 $T_0$ 时刻，可分配资源 Available 为 $(3,3,2)$，同时资源分配表如下：

进程	Max	Allocation
$P_1$	$(7,5,3)$	$(0,1,0)$
$P_2$	$(3,2,2)$	$(2,0,0)$
$P_3$	$(9,0,2)$	$(3,0,2)$
$P_4$	$(2,2,2)$	$(2,1,1)$
$P_5$	$(4,3,3)$	$(0,0,2)$

首先，求 Need​ 矩阵，有：

$$\begin{align} Need &= Max-Allocation \notag \\ &= \begin{bmatrix} 7 & 5 & 3\\ 3 & 2 & 2\\ 9 & 0 & 2\\ 2 & 2 & 2\\ 4 & 3 & 3\\ \end{bmatrix} - \begin{bmatrix} 0 & 1 & 0\\ 2 & 0 & 0\\ 3 & 0 & 2\\ 2 & 1 & 1\\ 0 & 0 & 2\\ \end{bmatrix} \notag \\ &= \begin{bmatrix} 7 & 4 & 3\\ 1 & 2 & 2\\ 6 & 0 & 0\\ 0 & 1 & 1\\ 4 & 3 & 1\\ \end{bmatrix} \notag \end{align}$$

之后，将 Work 向量和 Need 矩阵各行比较，找出比 Work 小的行，初始时，有：

$$\begin{align} P_1:(3,3,2)>(1,2,2)\rightarrow Need_1=(3,2,2),Allocation_1=(2,0,0) \notag \\ P_3:(3,3,2)>(0,1,1)\rightarrow Need_1=(2,2,2),Allocation_1=(2,1,1) \notag \\ \end{align}$$

将 $P_1,P_3$ 依次加入安全序列，然后释放资源

$$Work=(3,3,2)+(2,0,0)+(2,1,1)=(7,4,3)$$

此时，Need 矩阵更新为：

$$Need=\begin{bmatrix} 7 & 4 & 3\\ 6 & 0 & 0\\ 4 & 3 & 1\\ \end{bmatrix}$$

最后，重复上述步骤，即可得到一个安全序列：

$$\{P_1,P_3,P_4,P_2,P_0\}$$

银行家算法

设系统有 $5$ 个进程 $\{P_0,P_1,P_2,P_3,P_4\}$，$3$ 类资源 $\{R_1,R_2,R_3\}$，数量分别为 $10,5,7$，在 $T_0$ 时刻，可分配资源 Available 为 $(3,3,2)$，同时资源分配表如下：

进程	Max​	Allocation​
$P_1$	$(7,5,3)$	$(0,1,0)$
$P_2$	$(3,2,2)$	$(2,0,0)$
$P_3$	$(9,0,2)$	$(3,0,2)$
$P_4$	$(2,2,2)$	$(2,1,1)$
$P_5$	$(4,3,3)$	$(0,0,2)$

下面给出银行家算法中可能出现的三种情况的实例：

1.分配成功

初始时，$P_2$ 请求资源 $Request_2=(1,0,2)$，此时，有：

$$\begin{align} Request_2=(1,0,2)\leq Need_1=(1,2,2) \notag \\ Request_2=(1,0,2)\leq Available=(3,3,2) \notag \end{align}$$

假定可为 $P_2$ 分配资源，则：

$$\begin{cases} Available=(2,3,0) \notag \\ Allocation_2=(3,0,2) \notag \\ Need_2=(0,2,0) \notag \end{cases}$$

令向量 $Work=Available=(2,3,0)$，然后执行安全性算法检查，可得安全序列：

$$\{P_1,P_3,P_4,P_2,P_0\}$$

此时，可为 $P_2$ 分配资源

2.需要等待

初始时，$P_5$ 申请资源 $Request_5=(3,3,0)$，此时，有：

$$\begin{align} Request_5=(3,3,0)\leq Need_5=(4,3,1) \notag \\ Request_5=(3,3,0)\geq Available=(2,3,0) \notag \end{align}$$

可分配的资源不足，$P_4$ 需要等待

3.拒绝分配

初始时，$P_1$ 申请资源 $Request_1=(0,2,0)$，此时，有：

$$\begin{align} Request_1=(0,2,0)\leq Need_2=(7,4,3) \notag \\ Request_1=(0,2,0)\geq Available=(2,3,0) \notag \end{align}$$

假定为 $P_1$ 分配资源，则：

$$\begin{cases} Available=(2,1,0) \notag \\ Allocation_1=(0,3,0) \notag \\ Need_1=(7,2,3) \notag \end{cases}$$

令向量 $Work=Available=(2,1,0)$，然后执行安全性算法检查，此时无法满足任何进程的需要，进入不安全状态，因此拒绝为 $P_1$ 分配资源