皮匠和银行家

银⾏家算法的模拟和实现

最近在做操作系统的课程设计，其中实验四是“银⾏家算法的模拟和实现”。好在前⾯看过⼀点，有点印象。所以想尝试⾃⼰写⼀下，下⾯是我的

编码过程以及个⼈的⼀点分享，如果有问题欢迎指出，也希望能和我⼀起交流。我的邮箱是：***************************

⼀、什么是银⾏家算法？

银⾏家算法顾名思义就是模拟银⾏的借贷业务的⼀种算法，操作系统就相当于⼀个银⾏家，⽽进程就是客户，进程向操作系统请求资源、归还资源

就相当于客户向银⾏借贷、还贷。这个应该是很好理解的。理解这个名词之后，下⾯我们看看具体深⼊⼀点，银⾏家能否给⼀名客户贷款的要求是

什么呢？很简单：在它还款期间，整个银⾏要能进⾏正常的资⾦周转。如果可以，那好，就借款给它，如果不能就不借给他。恩，就这么⼲脆。

换做操作系统的资源分配，也是如此：操作系统能否响应⼀个进程的资源请求，要求是，在它归还分配的资源之前，系统能维持⼀个正常的资源周

转。到底什么是正常的周转？你可能在想。正常的周转就是，系统现有的资源能够满⾜多个进程的需求。也就是系统处于⼀个安全的状态。

⼆银⾏家算法的数据结构

上⾯的论述，对银⾏家算法应该有了⼀点模糊的印象了，下⾯就深⼊⼀步的探究，为了⽅便，下⾯先就介绍银⾏家算法的数据结构。操作系统的资

源可以是很多种，不同的进程对资源的需求也不同。

n:进程的数量m：资源的种类

定义：

名词数据结构

分配矩阵Allocation[n][m]

最⼤需求矩阵Max[n][m]

需求矩阵Need[n][m]

可利⽤资源Available[m]

请求资源Request[n][m]

进程i对资源j：

Allocation[i][j]表⽰进程i已分配资源j的数量

Max[i][j]：表⽰进程i对资源j的最⼤需求的数量

Need[i][j]:表⽰进程i对资源j剩下的需求（Max[i][j]-Allocation[i][j]）

Available[j]：对各个进程经过⼀番资源的分配后，资源j的数量。

Request[i][j]:进程i对资源j的请求数量。

（注：这⾥要区分请求和需求。可以这样理解，请求是动态、不确定的，进程对资源的请求有时多有时少）

三、银⾏家算法的流程

回到前⾯，先假设当前系统是处于⼀个正常周转的状态，这时⼀个进程i发出资源请求，系统能否分配给它要经历如下步骤：

1.进程i的资源请求过度了吗？要知道⼀个进程在最初始状态是声明了最⼤的资源请求的。⽤数据结构表⽰就是：Request[i][j]

如果满⾜就继续往下，不满⾜就拒绝分配。不满⾜，通俗讲就是此时进程i的资源请求是过分的，撕毁条约，得⼨进尺。

2.系统当前的资源情况能满⾜进程i的资源请求吗？经过步骤⼀，这时进程i的请求是合理的。但是这时也不能给它分配，要判断⼀下此时资源够不

够？现在也不考虑资源周转的问题，当务之急是当前资源能否满⾜进程i的请求。如果可以，就继续往下，不可以则进程需要等待，直到系统有

⾜够的资源再说。

3.系统处于安全状态吗？经过步骤⼀、⼆，进程i能否得到系统的资源分配还需要经过最后⼀道难关：系统将资源分配给该进程i后，还能处于⼀

个安全状态吗？或者说，系统还能进⾏正常的资源周转吗？这个地⽅可以说是整个算法的重中之重了。粗略来讲：系统先尝试对该进程i进⾏

资源分配，然后进⾏安全性检测，如果系统安全则分配成功，否则则撤销分配。详细的过程我下⾯再讲。

四、银⾏家算法中的安全性检测

上⾯将的数据结构、算法流程其实都是很容易理解的，但就判断当前系统是否安全可能还懵懵懂懂：到底怎么进⾏安全性检测？

我觉得这部分应该是整个算法最关键的地⽅，只要⼲掉它，就OK了！

前⾯讲了系统先对该进程尝试进⾏资源分配（注意是尝试！），就会得到新的资源情况，更新的过程我们可以看看，对进程i进⾏资源分配

Request[i][j]，资源更新情况如下：

Need[i][j]=Need[i][j]-Request[i][j]

Allocation[i][j]=Allocation[i][j]+Request[i][j]

Available[j]=Available[j]-Request[i][j]

(0<=i

然后资源更新后的系统进⾏安全性检测，具体我们先看⼀个例⼦：

ProcessAllocationNeedAvailable

P2

P110001750

P213542356

P303320652

P400140656

问：该状态是不是安全状态？

我们是先找出⼀个进程，使得系统可利⽤的资源能够它的所有资源需求

可以看到只有P0满⾜要求，就把p0加⼊安全队列中，然后将它以前占⽤的所有资源收回。这个时候，Available=Available+Allocation

即：Available:1622+0032=1654

Need中减少P0进程

Need=begin{bmatrix}1&7&5&02&3&5&60&6&5&20&6&5&6end{bmatrix}

⼜接着找⼀个进程，看是否满⾜：系统可利⽤的资源满⾜它的所有资源需求。

可以看到，P3Need=0652满⾜要求，P4Need=0656也满⾜要求，将P3加⼊安全队列中。这⾥我们可以任意选择⼀个，我们选择

P3，Available=Available+Allocation，将P3的分配资源Allocation归还。P3Allocation=0332

所以Available:1654+0332=1986

Need=begin{bmatrix}1&7&5&02&3&5&60&6&5&6end{bmatrix}

继续，可以看到P1、P4满⾜要求，选择P1，将P1加⼊安全队列中：

P1Allocation=1000

所以Available:1986+1000=2986

Need=begin{bmatrix}2&3&5&60&6&5&6end{bmatrix}

可以看到P2、P4都满⾜要求，选择P2，将P2加⼊安全队列中：

P2Allocation=1354

所以Available:2986+1354=3|12|13|10

选择P4，将P4加⼊安全队列中：

P2Allocation=0014

Available:3|12|13|10+0014=3|12|14|14

到此为⽌，所有的进程都加⼊安全队列中，说明整个系统是处于安全状态的，如果没有进程加⼊安全队列中，说明系统是不安全的，可能会发⽣死

锁，银⾏家算法是避免死锁⽽出名的⼀种算法，由此可见⼀斑。

五、尝试编程

当在（四）中描述算法的逻辑后，聪明的你应该有思路了，想尝试实现这个算法了。写完后想检测对⽐⼀下，我前⾯找到了⼀个⼩例⼦：银⾏家算

法例⼦讲解

我⾃⼰按照上⾯的思路实现了这个算法，如果有问题，欢迎评论留⾔。

源代码如下，有注释。

#include

#include

#include

#definemax50

intAllocation[max][max];

intAvailable[max];

intresources[max];

intMax[max][max];

intNeed[max][max];

intresourcesSize;//资源总数

intprocessSize;//进程总数

boolisSecurity;//系统是否安全

boolcheckSecurity();

voidinitialize()

{

printf("请输⼊资源总数n");

scanf("%d",&resourcesSize);

printf("输⼊各个资源的数量：n");

for(inti=0;i

{

printf("资源%d=",i);

scanf("%d",&resources[i]);

}

printf("输⼊进程数量n");

scanf("%d",&processSize);

printf("输⼊每个进程对资源的最⼤需求n");

for(inti=0;i

{

for(intj=0;j

{

printf("进程%d对资源%d的最⼤需求=",i,j);

scanf("%d",&Max[i][j]);

}

}

printf("对每个进程的资源已分配情况：n");

for(inti=0;i

{

for(intj=0;j

{

printf("已对进程%d分配资源%d的数量=",i,j);

scanf("%d",&Allocation[i][j]);

}

}

for(inti=0;i

{

for(intj=0;j

{

Need[i][j]=Max[i][j]-Allocation[i][j];

}

}

for(intj=0;j

{

for(inti=0;i

{

resources[j]-=Allocation[i][j];//分配完之后剩下的资源总数

}

}

Available[j]=resources[j];//可⽤资源数

}

checkSecurity();

}

boolcheckSecurity()

{

boolcurity[processSize];//curity[i]表⽰进程i是否安全

intcurityQueue[processSize];//表⽰安全队列，将进程的id号加进去

memt(curity,fal,processSize);//初始化为不安全的。

intlastNoSecurity=processSize;//初始化上次不安全进程数为processSize

inttemp[max];//避免检测时对Available数组进⾏修改

for(inti=0;i

{

temp[i]=Available[i];

}

intk=0;//添加安全进程到curityQueue中。计数的作⽤

while(true)

{

intcurrentNoSecurity=0;//每次检测都currentNoSecurity都从0开始计数，表⽰当前不安全的进程数

intcount;

for(inti=0;i

{

count=0;

if(curity[i]==true)continue;//跳过安全的进程

for(intj=0;j

{

if(Need[i][j]<=temp[j])//资源数满⾜进程i对它的需求

count++;

el

break;

}

if(count==resourcesSize)//所有可利⽤的资源全部满⾜进程i+1的需求,将此进程加⼊安全队列中

{

curity[i]=true;//进程i是安全的

//将进程i+1已分配的资源偿还

printf("进程%d是安全的哦,资源可利⽤更新为：n",i);

for(intj=0;j

{

temp[j]+=Allocation[i][j];

printf("%d",temp[j]);

}

printf("n");

curityQueue[k++]=i;

}

//当不满⾜时，暂时说明此进程是不安全的，当前不安全进程数+1

el

{

currentNoSecurity++;

printf("进程%d现在还不安全n",i);

}

}

//检测⼀遍后，下⾯判断检测的结果

if(currentNoSecurity==0)//检测完毕，所有进程都已加⼊安全队列中。系统可以进⾏资源分配了。

{

printf("当前系统是安全的，可以对进程进⾏资源分配，安全队列如下：n");

for(inti=0;i

{

printf("%d",curityQueue[i]);

}

printf("n");

returntrue;

}

//当下检测不是安全队列的进程数如果跟上次⼀样，就说明扫⼀遍后找不出符合安全性的进程了。

if(currentNoSecurity==lastNoSecurity)

{

//不安全

printf("当前系统是不安全的，不能进⾏资源的分配！");

returnfal;

}

//⾄少有⼀个加⼊了安全队列中了，所以再扫⼀遍进程队列，再检测⼀遍。

el{

lastNoSecurity=currentNoSecurity;

}

}

returnfal;

}

boolanswerQuest()

{

intRequest[resourcesSize];

printf("输⼊哪个进程的资源请求？n");

intprocess;

scanf("%d",&process);

for(intj=0;j

{

printf("输⼊进程%d对资源%d的请求=",process,j);

scanf("%d",&Request[j]);

}

//有多少我就请求多少，这貌似合理，系统也是安全的。但是这是不对的！不能多于最⼤请求

for(intj=0;j

{

if(Request[j]+Allocation[process][j]>Max[process][j]){

printf("进程%d对资源%d的请求不合理，超出所宣布的最⼤值！",process,j);

returnfal;

}

}

//没有⼤于最⼤请求，但是当前系统可能还没有这么资源分配他们

for(intj=0;j

{

if(Request[j]>Available[j])

{

printf("系统还没有⾜够的资源%d响应进程%d的请求",j,process);

}

}

//尝试分配

printf("尝试分配资源n");

for(intj=0;j

{

Allocation[process][j]+=Request[j];

Need[process][j]-=Request[j];

}

for(intj=0;j

{

Available[j]-=Request[j];

}

if(!checkSecurity()){//如果系统不处于安全状态。则本次分配作废，恢复原来的资源分配状态

printf("分配作废，恢复原来的状态n");

for(intj=0;j

{

Allocation[process][j]-=Request[j];

Need[process][j]+=Request[j];

}

for(intj=0;j

{

Available[j]+=Request[j];

}

returnfal;

}

returntrue;

}

voidlook()

{

printf("最⼤资源需求：n");

for(inti=0;i

{

for(intj=0;j

{

printf("%dt",Max[i][j]);

}

printf("n");

}

}

printf("已分配资源：n");

for(inti=0;i

{

for(intj=0;j

{

printf("%dt",Allocation[i][j]);

}

printf("n");

}

printf("Need需求：n");

for(inti=0;i

{

for(intj=0;j

{

printf("%dt",Need[i][j]);

}

printf("n");

}

printf("现有资源：n");

for(intj=0;j

{

printf("%dt",Available[j]);

}

printf("n");

}

voidmenu()

{

printf("nnt1.继续对进程进⾏资源的分配？n");

printf("t2.查看资源情况n");

printf("");

}

intmain()

{

printf("nntt银⾏家算法,欢迎使⽤ttnn");

printf("createdbyjiangzhengtaon");

printf("time:2018.6.2817:43n");

printf("place：yifubuilding431n");

printf("nt1.请输⼊系统的初始状态n");

initialize();

intchoo;

while(1)

{

menu();

scanf("%d",&choo);

switch(choo)

{

ca1:

if(answerQuest())

printf("请求成功！");

el

printf("请求失败！");

break;

ca2:look();break;

ca3:

printf("再见！");

exit(0);

}

}

return0;

}

六、总结

安全性检测这部分应该是银⾏家算法的重中之重了，将逻辑搞清楚应该是不难的。具体的思路是：如果找到⼀个进程，使得当前可利⽤资源

（Available）能够满⾜它的需求（Need），就先对其分配资源，然后收回分配给它之前的资源（Allocation），接着更新

Available（Available+=Allocation），然后将其加⼊安全性序列。继续找⼀个进程，重复上⾯操作。需要注意的是，必须要循环多次，因为前⾯

没有符合条件的进程可能因为后⾯的资源更新⼜符合条件了。最后，临界条件是如果循环⼀遍后，还是找不到符合条件的进程，那么说明系统不安

全，退出循环，反之如果所有的进程都加⼊安全性序列，就说明此系统是安全的，退出循环。

我处理的⼀个细节是：循环判断的时候，要跳过之前加⼊安全性序列的进程。