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

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

有 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 时刻的资源分配表如下：

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

二、例题

例一

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

例二

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

例三

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