操作系统 - 看完这篇还读不懂《银行家算法》那我也没办法了

操作系统 - 看完这篇还读不懂《银行家算法》那我也没办法了

故事背景

为什么想到总结一篇从 0-1 学习银行家算法，读这篇至少要有死锁的概念，网上很多文章根本没讲解当中的一些小概念，连概念和算法过程都不了解，直接上题目怎么看得懂？

原理讲解

非剥夺资源的竞争和进程的不恰当推进顺序会导致死锁，而银行家算法就是为了解决死锁问题——避免死锁。

银行家算法：当一个进程申请使用资源的时候，银行家算法通过先 试探 分配给该进程资源，然后通过安全性算法判断分配后的系统是否处于安全状态，若不安全则试探分配作废，让该进程继续等待。

那么此时会有一个问题，如何判断系统是否处于安全状态？算法流程将用下面一张图来表示。

首先是银行家算法中的进程

包含进程Pi的需求资源数量（也是最大需求资源数量，MAX）已分配给该进程的资源A（Allocation）还需要的资源数量N（Need=M-A）

Available为空闲资源数量，即资源池（注意：资源池的剩余资源数量+已分配给所有进程的资源数量=系统中的资源总量）

假设资源P1申请资源，银行家算法先试探的分配给它（当然先要看看当前资源池中的资源数量够不够），若申请的资源数量小于等于Available，然后接着判断分配给P1后剩余的资源，能不能使进程队列的某个进程执行完毕，若没有进程可执行完毕，则系统处于不安全状态（即此时没有一个进程能够完成并释放资源，随时间推移，系统终将处于死锁状态）。

若有进程可执行完毕，则假设回收已分配给它的资源（剩余资源数量增加），把这个进程标记为可完成，并继续判断队列中的其它进程，若所有进程都可执行完毕，则系统处于安全状态，并根据可完成进程的分配顺序生成安全序列（如{P0，P3，P2，P1}表示将申请后的剩余资源Work先分配给P0–>回收（Work+已分配给P0的A0=Work）–>分配给P3–>回收（Work+A3=Work）–>分配给P2–>······满足所有进程），如此就可避免系统存在潜在死锁的风险。

数据结构与算法

数据结构

可用资源向量：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 矩阵；（请一定要理解这条很好理解的原则）

Need 矩阵 = Max 矩阵 - Allocation 矩阵；（请一定要理解这条很好理解的原则）

Need 矩阵 = Max 矩阵 - Allocation 矩阵；（请一定要理解这条很好理解的原则）

也很好理解，最多需要的数量减去现在已经给的数量就是还需要的数量。矩阵的减法直接 ​​对应位置​​ 相减即可。

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

算法（银行家——整个过程）

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

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

如果​​request[A]​​ 的值小于 ​​need[P，A]​​，也就是说如果现在请求的数量小于 ​​need​​ 矩阵中规定的他所需要的数量，那么就转到步骤 2 ；否则认为出错，因为他所请求的数量已经超过了他所宣布的最大值。如果​​request[A]​​ 的值小于 ​​available[A]​​，也就是说请求的值小于现在系统中有的值，则转向步骤 3 ；否则表示尚足够资源，进程 P 需要等待。系统​​试探​​ 着把资源分配给进程 P，并修改下面数据结构中的值：

更新可用：​​Available = Available - request​​；更新已分配：​​Allocation[P,A] = Allocation[P,A] + request[A]​​；更新所需：​​Need[P,A] = Need[P,A] - request[A]​​;

系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态，若安全才将资源分配给进程 P；否则此次的试探分配作废，恢复原来的资源分配状态，让进程 P 等待。

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

算法（银行家——安全性）

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

下面以一个例子来看一下

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

Tips：起始 Available[A,B,C] = [10,5,7] - Sum(Allocation[A,B,C]) = [3,3,2]（[2,3,0]）这个提示我不得不在这里说明下，之前很多人一开始看对这里会有疑问，这个 [3,3,2] 是怎么得到的？这个起始资源 [10,5,7] 又有什么用？

强化练习

题1

题2

题3

Tips：这题不瞒你说，网上很多一开始就放这题，我敢说，没上面概念的铺垫，你让谁在这里加加减减找规律，非常痛苦~现在的你看到这还会觉得“银行家算法”难吗？！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。