银行家算法 os

文章目录

银行家算法

数据结构
银行家算法
安全性算法

安全状态

指系统按某种进程推进顺序，为每个进程 Pi 分配其所需的资源，直到满足每个进程对资源的最大需求，使每个进程都顺利执行完毕。这个进程推进顺序称为安全序列
如果找不到这样一个安全序列，则系统处于不安全状态。
避免死锁的解决方式在于，系统在进行资源分配时，避免使系统进入不安全状态。

银行家算法

一个银行家把他的固定资金借给若干客户，使这些客户在满足对资金的最大需求后能完成其交易，并把所借资金归还给银行家。假定每个客户分成若干次贷款，每个客户预先说明自己所要求的最大资金量，并每次提出部分资金量的申请。如果银行家满足了客户对资金的最大需求量，则该客户在资金运作完成后，在有限的时间内将全部资金归还给银行家。过程如下：

顾客的借款操作以此顺序进行，直到全部操作完成。

银行家对顾客的借款操作进行判断，确定其安全性

如果是安全的，则借出，否则暂时不借。

数据结构 (1) 可利用资源向量 Available
是一个包含了 m 个元素的数组，每一个元素代表一种资源的数量，Availbale[j] = k 代表系统中现有 Rj 类资源 k 个。其数值会随着该类资源的分配和回收而动态改变。
(2) 最大需求矩阵 Max
n×m 的矩阵，定义了系统 n 个进程中每个进程对m 类资源的最大需求。Max[i][j] = k表示进程 i 需要 Rj 类资源的最大数目为 k 个。注意这个不会动态改变
(3) 分配矩阵 Allocation
n×m 的矩阵，定义了系统中每一进程已被分配的某类资源数量。Allocation[i][j] = k 表示 i 进程已被分配 Rj 类资源的数量为 k 。
(4) 需求矩阵 Need
n×m 的矩阵，用来表示每一个进程需要的各类资源数。Need[i][j] = k 表示进程 i 还需要 Rj 类资源 k 个才能执行完成。
很明显，上面矩阵之间存在这种关系： Need[i][j] = Max[i][j] - Allocation[i][j]
银行家算法假设 Request 代表进程的请求向量， Request[i][j] = k 表示进程 Pi 向os申请 k 个Rj 类资源。当进程发出请求后，os按下面的步骤进行检查
(1) 如果 Request[i][j] <= Need[i][j]，转向 (2)，否则认为资源申请出错，因为它所申请的资源已经超出所宣称的最大值。
(2) 如果 Request[i][j] <= Available[j]，资源足够分配，转向**(3)**，否则让进程等待。
(3) 系统会试探着把资源分配给进程 Pi，并修改数据结构中的值。
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];
(4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才把资源正式分配给进程 Pi，不安全，本次的试探作废，恢复原来的资源分配状态，进程 Pi 等待。
安全性算法 (1) 设置两个向量

工作向量 Work, 表示系统能够提供的各类资源数目，初始化时 Work = Available
完成向量 Finish, 表示系统是否有足够的资源分配给某进程，使之运行完成。开始时 Finish[i] = false;

(2) 从进程集合中找到一个能运行完的进程，满足下列条件
Finish[i] = false;
Need[i][] < Work[]
如果能找到，执行步骤**(3)，否则执行(4)**
(3) 进程 Pi 获得资源后，能够执行完毕并释放资源：
Work = Work + Allocation[i];
Finish[i] = true;
返回**(2)**继续寻找
(4) 如果所有进程都满足 Finish = true, 则表示系统处于安全状态，不会发生死锁。
【银行家算法】否则，系统处于不安全状态