实验四银行家算法.doc

.

操作系统实验

实验四 银行家算法

学号 1115102002
姓名 蔡凤武
班级 11电子A

华侨大学电子工程系

实验目的
1、 理解银行家算法。
2、 掌握进程安全性检查的方法与资源分配的方法。
实验内容与基本要求
编制模拟银行家算法的程序，并以下面给出的例子验证所编写的程序的正确性。
进程
已占资源
最大需求数
A
B
C
D
A
B
C
D
P0
0
0
1
2
0
0
1
2
P1
1
0
0
0
1
7
5
0
P2
1
3
5
4
2
3
5
6
P3
0
6
3
2
0
6
5
2
P4
0
0
1
4
0
6
5
6

现在系统中A、B、C、D 4类资源分别还剩1、5、2、0个，请按银行家算法回答：
1、 现在系统是否处于安全状态？
2、 如果现在进程P1提出需要（0、4、2、0）个资源的请求，系统能否满足它的请求？

1、银行家算法和安全性检查算法原理。
操作系统的银行家算法：当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。
1、 程序流程描述。
 银行家算法：
(1) 步骤：1如果Request [j]<=Need[i],转向步骤(2),否则认为出错，因为他所需要的资源数已经超过它所宣布的最大值。
(2) 步骤2；如果：Request [i]<=Available[i]，转向步骤(3)，否则提示尚无足够资源，进程i需等待。 
(3) 步骤3：系统试探分配相关资源，并修改下面数据： 
Available[i]= Available[i]- Request [j]； Allocation[i]= Allocation[i]+ Request [i]； Need[i]= Need[i]- Request [i]； 
(4) 步骤4：执行安全性检查，如安全，则分配成立；否则本次试探分配作废，恢复原来的资源分配状态，让该进程等待。
安全性检查算法：
安全性检查算法主要是根据银行家算法进行资源分配后，检查资源分配后的系统状态之中。具体算法如下：
(1) 步骤1：设置两个向量： Work= Available，Finish[i]=false； 说明：Finish（它表示系统是否有足够的资源分配给进程）Work（它表示系统可提供给进程继续运行所需的各类资源数目）
(2) 步骤2：在进程中查找符合以下条件的进程：Finish[i]=false，need<=Work 若能找到，则执行步骤(3)，否则，执行步骤(4)
(3) 步骤3：当进程获得资源后，可顺利执行，直至完成，从而释放资源： Work= Work+ Allocation； Finish=true； goto step (2)；
(4) 步骤4：如果所有进程的Finish=true都满足，则表示系统处于安全状态，否则，系统不安全状态。
流程图：
主函数：开始

显示背景设置

输入进程的数目

输入资源的种类

输入每个进程最多所需的各资源数

输入各个资源现有的数目
检测系统安全性

输入请求资源的进程号及其
请求的各资源的数量

Request<=Need?
否
显示错误

否
是
进程Pi阻塞
Request<=Available?

是
尝试分配资源：
Available[i]= Available[i]- Request [j] 
Allocation[i]= Allocation[i]+ Request [i]
Need[i]= Need[i]- Request [i]；

执行安全性算法，检查安全性

否

是否安全

正式分配）
是
试将分配作废，恢复原资源分配状态

同意分配请求

还想再次请求分配吗？是按Y，否按N

开始
初始化设置，work，finish

Work=Available
Finish[i]=false(1,2,3,…)

否

Needi>work,
Finish[i]=False

否
``
是
Needi>work,
Finish[i]=False

Work=Work+Allocationi;
Finish[i]=ture;

系统处于不安全状态

系统处于安全状态

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个，请按银行家算法回答：
3、 现在系统是否处于安全状态？
是，且有安全序列0、2、1 、3、4。
4、 如果现在进程P1提出需要（0、4、2、0）个资源的请求，系统能否满足它的请求？
可以

运行截图：
主界面：

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

2运行 ：

3运行：

4运行：

1运行：

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

按2程序实现：

结论：
设计的程序运行结果与银行家算法一致，程序的延时操作流畅，界面内容清楚，还设计了界面的美观以及人性化的提示。
经过这次试验，成功的实现了按银行家算法分配资源以及安全性检测的功能，而且更深刻的了解了银行家算法和安全检测算法的实现流程，通过实际的编程操作使原本对课本知识的认识更加深入。

单纯的课本内容，并不能满足学生的需要，通过补充，达到内容的完善
教育之通病是教用脑的人不用手，不教用手的人用脑，所以一无所能。教育革命的对策是手脑联盟，结果是手与脑的力量都可以大到不可思议。

.