博客

银行家算法是最著名的避免死锁的办法，它的思想是：把操作系统视作银行家，操作系统管理的资源视作银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家进行贷款。操作系统按照银行家制定的规则为进程分配资源。进程运行之前先声明对各种资源的最大需求量，当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过该进程声明的最大需求量。若超过则拒绝分配资源，若未超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。你可能对此段文字可能不是特别明白，下面来举个例子。

现在我初始的资源为（10，5，7），相当于第一类资源10个，第二类资源5个，第三类资源7个。为5个进程进行分配，五个进程最大需求和已分配的表如下表。从最大需求和已分配可以算出最多还需要多少，两个相减即可。

通过上面的已分配的，我们可以得到一共已分配多少，把它加起来就行得到已分配（7，2，5），这样用初始资源减去已分配的，得到剩余资源（3，3，2），接下来从P0往下找，看（3，3，2）能满足哪个需求，发现P1不可以，P2可以，那么我们先把资源分配给P2，P2加入安全序列，P2执行完后释放资源，释放完资源后，现有资源为（2，0，0）+（3，3，2）=（5，3，2）。继续找哪个满足（5，3，2），发现P3是满足（5，3，2）的，那么将P3加入安全序列，P3释放资源后，剩余可用资源就为（2，1，1）+（5，3，2）=（7，4，3）。接下来可以发现剩下几个都满足，那么就可以依次或者根据你的想法把他们都加入安全序列，安全序列并不唯一。（安全序列这一知识在死锁一文中有提及）

（1）数据结构描述

可利用资源量Available

：含有m个元素的数组，其中每个元素代表一类可用的资源数目。Available[j]=K表示系统中现有Rj类资源K个。

最大需求矩阵Max

：n×m矩阵，定义系统中n个进程中的每个进程对m类资源的最大需求。Max[i,j]=K表示进程i需要Rj类资源的最大数目为K。

分配矩阵Allocation

：n×m矩阵，定义系统中每类资源当前已分配给每个进程的资源数。Allocation[i,j]=K表示进程i当前已分得Rj类资源的数目为K。不要混淆Allocation和Available。

需求矩阵Need

：n×m矩阵，表示每个进程接下来最多还需要多少资源。Need[i,j]=K表示进程i还需要Rj类资源的数目为K。

上述三个矩阵存在下述关系： Need = Max – Allocation  可以结合前面那个例子来理解。

一般情况下，在银行家算法中，Max矩阵和Allocation矩阵是已知条件，而求出Need矩阵是第一步。

（2）银行家算法描述

设Reuqest(i)是进程Pi的请求向量，Request(i)[j]=K表示进程Pi需要j类资源K个。当Pi发出资源请求后，系统按下述步骤进行检查：

①Request(i)≤Need[i,j]，则转向步骤②；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。

②若Request(i)[j]≤Available[j]，则转向步骤③；否则，表示尚无足够资源，Pi需等待。

③系统试探着把资源分配给进程Pi，并修改下面数据结构中的值：

Available = Available – Request(i);

Allocation[i,j] = Allocation[i,j] + Request(i)[j];

Need[i,j]=Need[i,j]-Request(i)[j];

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

（3）安全性算法

设置工作向量Work，有m个元素，表示系统中的剩余可用资源数目。在执行安全性算法开始时，Work=Available。

①初始时安全序列为空。

②从Need矩阵中找出符合下面条件的行：该行对应的进程不在安全序列中，而且该行小于等于Work向量，找到后，把对应的进程加入安全序列；若找不到，则执行步骤④。

③进程Pi进入安全序列后，可顺利执行，直至完成，并释放分配给它的资源，因此应执行Work=Work+Allocation[i]，其中Allocation[i]表示进程Pi代表的在Allocation矩阵中对应的行，然后返回步骤②。

④若此时安全序列中已有所有进程，则系统处于安全状态，否则系统处于不安全状态。

以上都是文字描述，可能会感觉到很抽象，安全性算法的例子已经在上面有讲了，可用往上翻，那个就是安全性算法的例子，我把表拿下来，大家就能再了解下了。

Work一开始是等于Avaliable的，也就是（3，3，2），这时按步骤来，将Work和Need里的去比较，一开始的例子是拿Avaliable去比，其实是一样的因为Work的初始就是Avaliable。跟之前一样找到了P1是小于Work，然后加入安全序列，释放掉资源后Work就等于Work加上Allocation的资源分配，然后再执行2，直到所有进程在安全序列，或者处于不安全状态，也要按照实际的题目情况来看，本例子是在安全状态的。这就是安全性算法，接下来让我们看下银行家算法。

安全性算法是银行家算法的核心

，在银行家算法中，一般会有某个进程的一个资源请求向量，只要执行之前银行家算法的前三步，马上就会得到更新的Allocation矩阵和Need矩阵，再按照上面的安全性算法判断，就能知道系统能否满足进程提出的资源请求了。

假设当前系统中资源的分配和剩余情况如上面的例子，我把它表格拿下来。

（1）P1请求资源：P1发出请求向量Request[1](1,0,2)，系统按照银行家算法检查。

PS：这里方括号中的1代表进程1的下标

。

Request[1](1,0,2)≤Need[1](1,2,2)

Request[1](1,0,2)≤Available[1](3,2,2)

系统先假设可为P1分配资源，并修改

Available = Available – Request[1] = (2,3,0)

Allocation[1] = Allocation[1] + Request[1] = (3,0,2)

Need[1] = Need[1] – Request[1] = (0,2,0)

由此形成的资源变化情况如下图圆括号内容。

另Work = Available = （2，3，0），再利用之前的安全性算法来检查此时系统是否安全。由于之前已经对此进行过叙述，这里就不再叙述，可得到一个安全序列{P1，P3，P4，P2，P0}。因此，系统是安全的，可以将P1所申请的资源分配给它。接下来的操作其实都一样，就是步骤来进行操作，直到Available不能满足任何进程的需要，那么就会让那个进程j进行等待，并且把Available，Allocation[j]和Need[j]恢复为之前的值。

用中文来描述银行家算法如下：

1.检查此次申请是否超过了之前声明的最大需求数。

2.检查此时系统剩余的可用资源是否还能满足这次请求。

3.试探着分配，更改各数据结构。

4.用安全性算法检查此次分配是否会导致系统进入不安全状态。

本文是我在学银行家算法时记录的，其实重点还是在理解那些矩阵是啥，比如我要请求资源，那我请求的资源肯定不能超过它本来需要的资源，请求资源成功后，相当于给它又分配了一些资源，那么我就可以为分配矩阵加上请求资源的数量，因为分配过了，所以我现在需要的就可以少一点了，也可以理解为分配矩阵大了，那最大减去分配就是新的需求矩阵了。一些内容参考自操作系统的书本并且加上自己的理解，如果有问题的可以在评论区一起探讨。