死锁习题——银行家算法讲解

电玩女神 2022-12-24 00:48 181阅读 0赞

非剥夺资源的竞争和进程的不恰当推进顺序会导致死锁。

有 3 种方式可以解决死锁问题：

*  预防死锁；
 *  避免死锁；
 *  死锁的检测和解除；

今天要讲的银行家算法就属于死锁避免。

## 一、银行家算法 ##

> 银行家算法是最著名的死锁避免算法。

### 1、数据结构描述 ###

**可用资源向量**：`Available`，是一个数组，表示现在系统中总共还有多少可用的资源。

例如：A B C 的 Available 是 `[1，2，3]`

表示现在系统中还有 A 类资源 1 个，B 类资源 2 个，C 类资源 3 个。

--------------------

**最大需求**： `Max`，是一个矩阵，表示某进程最多需要多少某资源，一行代表一个进程，一列代表一个资源。

例如：

A B C
     P1 1 2 3
     P2 4 5 6
     P3 7 8 9
    
    //P3 进程最多需要 C 类资源 9 个.
    //P2 进程最多需要 B 类资源 5 个.

--------------------

**分配矩阵**：`Allocation` 表示系统中现在某类资源分配给某进程的数量。

A B C
     P1 1 2 3
     P2 4 5 6
     P3 7 8 9
    
    //P3 进程现在已经分配了 C 类资源 9 个.
    //P1 进程现在已经分配了 A 类资源 1 个.

--------------------

**需求矩阵**：`Need`，表示现在进程中尚需的各类资源数。

A B C
     P1 1 2 3
     P2 4 5 6
     P3 7 8 9
    
    //P1 进程现在还需要 C 类资源 3 个.
    //P2 进程现在还需要 B 类资源 5 个.

Need 矩阵 = Max 矩阵 - Allocation 矩阵。

也很好理解，最多需要的数量减去现在已经给的数量就是还需要的数量。

矩阵的减法直接 `对应位置` 相减即可。

一般情况下，Max 矩阵和 Alocation 矩阵都是已知条件，求出 Need 矩阵是解题的第一步。

### 2、银行家算法描述 ###

设 `request` 是进程 P 的请求向量，`request[A] = K` 表示进程 P 需要 A 类资源 K 个。

当 P 发出资源请求后，系统按照以下步骤进行检查。

1.  如果 `request[A]` 的值小于 `need[P，A]`，也就是说如果现在请求的数量小于 `need` 矩阵中规定的他所需要的数量，那么就转到步骤 2 ；否则认为出错，因为他所请求的数量已经超过了他所宣布的最大值。
2.  如果 `request[A]` 的值小于 `available[A]`，也就是说请求的值小于现在系统中有的值，则转向步骤 3 ；否则表示尚足够资源，进程 P 需要等待。
3.  系统 `试探` 着把资源分配给进程 P，并修改下面数据结构中的值：
    
     *  更新可用：`Available = Available - request`；
     *  更新已分配：`Allocation[P,A] = Allocation[P,A] + request[A]`；
     *  更新所需：`Need[P,A] = Need[P,A] - request[A]`;
4.  系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态，若安全才将资源分配给进程 P；否则此次的试探分配作废，恢复原来的资源分配状态，让进程 P 等待。

接下来看一下安全性算法是什么 ？

### 3、安全性算法 ###

1.  初始时 `安全序列` 为空；
2.  从 Need 矩阵中找到符合下面条件的行：该行对应的进程不在安全序列中，而且该行小于等于 Available 向量，找到后，把对应的进程加入 `安全序列`；若找不到，则执行步骤 4；
3.  进程 P 进入 `安全序列` 后，可顺利执行，直至完成，并释放分配给它的资源，故应执行 `Available = Available + Allocation[P]`，其中 `Allocation[P]` 表示进程 P 在 `Allocation` 矩阵中对应的行，返回步骤 2 。
4.  若此时安全序列中已有所有进程，则系统处于安全状态，否则处于不安全状态。

下面以一个例子来看一下：

假定系统中有 5 个进程 `{P0,P1,P2,P3,P4}` 和 3 类资源 `{A,B,C}`，各类资源的数量分别是 `10，5，7`，在 T0 时刻的资源分配表如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 1][]  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 2][]

下面来做几道题目练习一下：

## 二、例题 ##

### 例一 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 3][]  
下面是我手写的解题过程，大家可以参考。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 4][]

### 例二 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 5][]  
下面是我手写的解题过程，大家可以参考。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 6][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 7][]

### 例三 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 8][]

下面是我手写的解题过程，大家可以参考。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 9][]  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 10][]  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 11][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/9085739ed1a74a7eadd6175a047126ea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201126081247526.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201126081524618.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20201126080304840.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20201126080808523.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20201126080519975.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20201126080741433.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/20201126080705881.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 8]: https://img-blog.csdnimg.cn/20201126080850142.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 9]: https://img-blog.csdnimg.cn/20201126080914982.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 10]: https://img-blog.csdnimg.cn/20201126080927764.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 11]: https://img-blog.csdnimg.cn/20201126080938785.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA==,size_16,color_FFFFFF,t_70#pic_center