操作系统—银行家算法

操作系统—银行家算法

引子最近上操作系统课学到了银行家算法，起初看课本觉得这个讲的是什么，仔细研究了一下发现这个算法最重要的一点就是安全性检查了。

抽象的过程先说一下这个算法模拟的是什么过程：假设有一个银行，里面有人民币、美元、日元、韩币等资源，有许多客户向银行申请贷款。

每个客户都可以发出申请先贷款一部分，也可以发出申请贷款全部，比如有个客户想贷款人民币3元、美元2元、日元1元，那么他每种资源只申请贷款1元也可以，但是只有全部申请够了，客户才会还银行钱，这个业务才完成了。

银行要做的事情就是判断这个客户的申请是否是狮子大开口，贷款的资源超过了他的需求。如果不是，再判断银行是否有分配给这个客户钱的能力，而这里的能力不仅包括现在的资源是否能够满足这个客户的申请，而且还包括满足这个客户的申请后，银行还有没有完成全部业务的能力。这也就是所谓的安全性检查了。

我们用极端的思想想想，如果给一个客户分了太多资源，将有可能导致银行面临一个非常困难的境地——这个客户的贷款业务还没有完成所以银行不能把钱收回来，而现在银行的钱太少了，以至于这个客户和其他客户的业务都完成不了，所以银行现在只能给钱还收不回来（客户会以你没完成我的贷款业务为借口）。

如何进行安全性检查呢？

我们可以假设银行已经把钱借给了这个客户，然后按此情况进行模拟，在这种情况下，银行如果还能够完成全部的业务，那么，这个借钱的行为就是安全的，银行你放心借吧。如果不行，那么银行你千万别借，借了之后就不能完成全部业务了。

如何模拟：这其实是一个大鱼吃小鱼的游戏（4399、摩尔庄园玩过。。），我们可以把银行现在有的资源看作是一条大鱼，然后把其他客户的业务看作是一条小鱼，银行完成一个客户的业务就能收钱，那么银行就会有更多的资源去完成其他的业务，这也就是一条大鱼，吃了其他小鱼，变得更大，然后就能吃更大的鱼的过程。

需要注意的是，我们并不需要关注大鱼吃的每一条小鱼的顺序，只需要找到比它小的鱼并吃掉就可以了，这既节省时间又不会改变结果（可以自己思考一下为什么）。如果“大鱼”最后能吃掉全部“鱼”，那么这个系统就是安全的，否则，这个系统就是不安全的。

伪代码整个算法思路如下：

为了实现银行家算法，在系统中必须设置这样四个数据结构，分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配，以及所有进程还需要多少资源的情况。　　(1) 可利用资源向量 available。这是一个含有 m 个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果 Available[j] = K，则表示系统中现Rj类资源K个。　　(2) 最大需求矩阵Max。这是一个n x m的矩阵，它定义了系统中n个进程中的每个进程对m类资源的最大需求。如果Max[i,j] = K，则表示进程i需要Rj 类资源的最大数目为K。　　(3) 分配矩阵 allocation。这也是一个n x m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果 allocation[i,jl = K，则表示进程i当前己分得j类资源的数目为K。　　(4) 需求矩阵need.这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果need[i,j] = K，则表示进程i还需要j类资源K个才能完成其业务。上述三个矩阵间存在下述关系:　　　　　　　　　　　　　　need[i,j] = Max[i,j] - allocation[i, j]

假设在进程并发执行时进程i提出请求j类资源k个后，表示为Requesti[j]=k。系统按下述步骤进行安全检查：（1）如果Requesti≤Needi则继续以下检查，否则显示需求申请超出最大需求值的错误。

（2）如果Requesti≤Available则继续以下检查，否则显示系统无足够资源，Pi阻塞等待。

（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：Available［j］∶=Available［j］-Requesti［j］;Allocation［i,j］∶=Allocation［i,j］+Requesti［j］;Need［i,j］∶=Need［i,j］-Requesti［j］;

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

安全性算法（1）设置两个向量：工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work∶=Available;Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish［i］∶=false; 当有足够资源分配给进程时， 再令Finish［i］∶=true。（2）从进程集合中找到一个能满足下述条件的进程：Finish［i］=false;Need［i,j］≤Work［j］； 若找到， 执行步骤(3)， 否则，执行步骤(4)。（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Work［j］∶=Work［i］+Allocation［i,j］;Finish［i］∶=true;go to step 2;（4）如果所有进程的Finish［i］=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。

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