实验四银行家算法

操作系统实验

实验四 银行家算法

学号 1115107047 姓名 吴炜松 班级 11电子B

华侨大学电子工程系

1、银行家算法和安全性检查算法原理。

操作系统的银行家算法：当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。

1、程序流程描述。 进程i发出请求资源申请，

(1)如果Request [j]<=need[i,j],转向步骤(2),否则认为出错，因为他所需要的资源数已经超过它所宣布的最大值。

(2)如果：Request i[j]<=available[i,j]，转向步骤(3)，否则提示尚无足够资源，进程i需等待。

(3)系统试探着将资源分配给申请的进程（有预先寄存操作），并修改下面数据结构中的数值：

Available[i,j]= Available[i,j]- Request [j]； Allocation[i][j]= Allocation[i][j]+ Request [j]； need[i][j]= need[i][j]- Request [j]；

(4)试分配后，执行安全性检查，调用check()函数检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程，并修改系统状态；否则本次试探分配作废，恢复原来的资源分配状态，让该进程等待。

(5)用do{…}while 循环语句，实现输入字符y/n控制是否进行进一步的资源申请。

安全性检查算法（子程序）：

(1)设置两个向量： Work（它表示系统可提供给进程继续运行所需的各类资源数目）在执行安全性算法开始时，Work= Available。 Finish（它表示系统是否有足够的资源分配给进程）初始化，Finish[i]=false；当有足够的资源分配给进程时，再令Finish[i]=true。

(2)在进程中查找符合以下条件的进程： 条件1：Finish[i]=false； 条件2：need[i][j]<=Work[j] 若找到，则执行步骤(3)否则，执行步骤(4)

(3)当进程获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，

故应执行： Work[j]= Work[j]+ Allocation[i][j]； Finish[i]=true； goto step (2)；

(4)如果所有的Finish[i]=true都满足，则表示系统处于安全状态，否则，处于不安全状态。

流程图：

由于print函数只是把所有信息按矩阵输出，比较简单，这里就不写流程图了。

2、程序及注释。

#include <stdio.h> #include <stdlib.h> #include <conio.h> # define m 50 # define false 0 # define true 1 int no1; //进程数 int no2; //资源数 int r;

int allocation[m][m], max[m][m],need[m][m], available[m];

char name1[m], name2[m]; //定义全局变量

void main() {

void check(); void print(); void shoudon(); int i,j,p=0,q=0; char c; int s;

int request[m],allocation1[m][m],need1[m][m],available1[m],f[m]; int mx[5][4]={{0,0,1,2},{1,7,5,0},{2,3,5,6},{0,6,5,2},{0,6,5,6}}; int an[5][4]={{0,0,1,2},{1,0,0,0},{1,3,5,4},{0,6,3,2},{0,0,1,4}}; int ann[5][4]={{0,0,1,2},{1,4,2,0},{2,3,5,6},{0,6,5,2},{0,6,5,6}}; printf("**********************************************\n"); printf("*** sf银行家算法演示 ***\n"); printf("**********************************************\n"); printf("\n1.演示报告给定系统1.");

printf("\n2.演示报告给定系统2.（P1提出需要（0、4、2、0）个资源）"); printf("\n3.演示手动输入系统."); printf("\n0.退出程序.");

printf("\n请选择（0~3）:"); scanf("%d",&s); switch(s) {case 1:

{no1=5; no2=4;

for(i=0;i<no1;i++) for(j=0;j<no2;j++) {max[i][j]=mx[i][j]; allocation[i][j]=an[i][j];} } break;

case 2: {no1=5; no2=4;

for(i=0;i<no1;i++) for(j=0;j<no2;j++) {max[i][j]=mx[i][j]; allocation[i][j]=ann[i][j];} } break; case 3:

shoudon(); break; case 0: printf("\n thanks for you watching! \n"); exit(0); /*退出程序*/ default: printf("\n请输入有效指令\n"); break; /*提示输入无效提示*/ }

for(i=0;i<no1;i++) for(j=0;j<no2;j++)

need[i][j]=max[i][j]-allocation[i][j]; //根据输入的两个数组计算出need矩阵的值 printf("请输入Available矩阵\n"); for(i=0;i<no2;i++)

scanf("%d",&available[i]); //输入已知的可用资源数 print(); //输出系统

check(); //检测T0时刻系统的安全状态 if(r==1) //如果安全则执行以下代码 { do{ q=0; p=0;

printf("\n请输入请求资源的进程号(0~4)：\n"); for(j=0;j<=10;j++) {

scanf("%d",&i); if(i>=no1) {

printf("输入错误，请重新输入：\n"); continue; }

else break; }

printf("\n请输入该进程所请求的资源数request[j]:\n"); for(j=0;j<no2;j++)

scanf("%d",&request[j]); for(j=0;j<no2;j++) if(request[j]>need[i][j]) p=1; //判断请求是否超过该进程所需要的资源数 if(p)

printf("请求资源超过该进程资源需求量，请求失败！\n"); else {

for(j=0;j<no2;j++)

if(request[j]>available[j]) //判断请求是否超过可用资源数 q=1; if(q)

printf("没有做够的资源分配，请求失败！\n");

else //请求满足条件 {

for(j=0;j<no2;j++) {

available1[j]=available[j];

allocation1[i][j]=allocation[i][j];

need1[i][j]=need[i][j]; // 寄存 （原已分配的资源数、仍需要的资源数、可用的资源数）

available[j]=available[j]-request[j]; allocation[i][j]+=request[j]; need[i][j]=need[i][j]-request[j]; //系统尝试把资源分配给请求的进程 }

check(); //检测分配后的安全性 if(r==1) for(j=0;j<no2;j++) { f[j]=allocation1[i][j]+request[j]; if(f[j]==max[i][j]) allocation[i][j]=0; else allocation[i][j]=f[j]; available[j]=available1[j]+allocation1[i][j]-allocation[i][j]; // 改写 （已分配的资源数、仍需要的资源数、可用的资源数） need[i][j]=need1[i][j]-request[j]; } else //如果分配后系统不安全 {

for(j=0;j<no2;j++) {

available[j]=available1[j];

allocation[i][j]=allocation1[i][j]; need[i][j]=need1[i][j]; // 还原 （已分配的资源数、仍需要的资源数、可用的资源数）

} } print(); //显示相关信息 printf("返回分配前资源数\n"); }

}printf("\n你还要继续分配吗？Y or N ?\n"); //判断是否继续进行资源分配 c=getche(); }

while(c=='y'||c=='Y'); } }

//手动输入 void shoudon(){ int i,j;

printf("请输入进程总数:\n"); scanf("%d",&no1);

printf("请输入资源种类数:\n"); scanf("%d",&no2);

printf("请输入Max矩阵:\n"); for(i=0;i<no1;i++) for(j=0;j<no2;j++)

scanf("%d",&max[i][j]); //输入已知进程最大资源需求量 printf("请输入Allocation矩阵:\n"); for(i=0;i<no1;i++) for(j=0;j<no2;j++)

scanf("%d",&allocation[i][j]); //输入已知的进程已分配的资源数 return; }

//安全算法函数

void check() {

int k,f,v=0,i,j; int work[m],a[m]; int finish[m];

r=1; //安全标志 for(i=0;i<no1;i++)

finish[i]=false; // 初始化进程均没得到足够资源数，未完成 for(i=0;i<no2;i++)

work[i]=available[i]; //work[i]表示可提供进程继续运行的各类资源数 k=no1; do{

for(i=0;i<no1;i++) {

if(finish[i]==false) {

f=1;

for(j=0;j<no2;j++)

if(need[i][j]>work[j]) f=0;

if(f==1) //找到还没有完成且需求数小于可提供进程继续运行的资源数的进程 {

finish[i]=true; //标记完成

a[v++]=i; //记录安全序列号 for(j=0;j<no2;j++)

work[j]+=allocation[i][j]; //释放该进程已分配的资源 } } }

k--; //每完成一个进程分配，未完成的进程数就减1 }

while(k>0); f=1;

for(i=0;i<no1;i++) //判断是否所有的进程都完成 {

if(finish[i]==false) //未完成 { f=0; break; } }

if(f==0) //若有进程没完成，则为不安全状态 {

printf("系统处在不安全状态！"); r=0; } else {

printf("\n系统当前为安全状态，安全序列为：\n"); for(i=0;i<no1;i++)

printf("p%d ",a[i]); //输出安全序列 } }

//显示函数

void print() { int i,j;

printf("\n");

printf("***************************资源分配情况****************************\n"); printf("进程名/号码 | Max | Allocation | Need |\n"); for (i = 0; i < no1; i++) {

printf(" p%d/%d ",i,i); for (j = 0; j < no2; j++)

{printf("%d ",max[i][j]);} for (j = 0; j < no2; j++)

{printf(" %d",allocation[i][j]); } for (j = 0; j < no2; j++)

{printf(" %d",need[i][j]);} printf("\n"); }

printf("\n");

printf("各类资源可利用的资源数为:"); for (j = 0; j < no2; j++)

{printf(" %d",available[j]);} printf("\n"); }

3、运行结果以及结论。

现在系统中A、B、C、D 4类资源分别还剩1、5、2、0个，请按银行家算法回答：

1、现在系统是否处于安全状态？ 是，且有安全序列0、2、3 、4、1。

2、如果现在进程P1提出需要（0、4、2、0）个资源的请求，系统能否满足它的请求？

可以，安全序列仍为0、2、3 、4、1。

运行截图：

主界面：

由于安全序列为0 2 3 4 1，先让0运行，结束后资源收起：

2运行 ：

3运行：

4运行：

1运行：

P1提出需要（0、4、2、0）个资源）：结果为安全。 按一程序的实现：

按2程序实现：

结论：

设计的程序运行结果与银行家算法一致，程序的延时操作流畅，界面内容清楚，还设计了界面的美观以及人性化的提示。

经过这次试验，成功的实现了按银行家算法分配资源以及安全性检测的功能，而且更深刻的了解了银行家算法和安全检测算法的实现流程，通过实际的编程操作使原本对课本知识的认识更加深入。

本文来源：https://www.bwwdw.com/article/mp01.html