银行家算法设计实验报告.docx
《银行家算法设计实验报告.docx》由会员分享,可在线阅读,更多相关《银行家算法设计实验报告.docx(13页珍藏版)》请在冰点文库上搜索。
银行家算法设计实验报告
银行家算法设计实验报告
一.题目分析
1.银行家算法:
我们可以把操作系统看做是银行家,操作系统管理的资源相当于银行家管理的资金,进程向操作系统请求资源相当于客户向银行家贷款。
操作系统按银行家制定的规则为进程分配资源,当进程首次申请资源时,要测试该进程尚需求的资源量,若是系统现存的资源可以满足它尚需求的资源量,则按当前的申请量来分配资源,否则就推迟分配。
当进程在执行中继续申请资源时,先测试该进程申请的资源量是否超过了它尚需的资源量。
若超过则拒绝分配,若没有超过则再测试系统尚存的资源是否满足该进程尚需的资源量,若满足即可按当前的申请量来分配,若不满足亦推迟分配。
2.基本要求:
〔1〕可以输入某系统的资源以与T0时刻进程对资源的占用与需求情况的表项,以与T0时刻系统的可利用资源数。
〔2〕对T0时刻的进行安全性检测,即检测在T0时刻该状态是否安全。
〔3〕进程申请资源,用银行家算法对其进行检测,分为以下三种情况:
A.所申请的资源大于其所需资源,提示分配不合理不予分配并返回
B.所申请的资源未大于其所需资源,但大于系统此时的可利用资源,提示分配不合理不予分配并返回。
C.所申请的资源未大于其所需资源,亦未大于系统此时的可利用资源,预分配并进行安全性检查:
a.预分配后系统是安全的,将该进程所申请的资源予以实际分配并打印后返回。
b.与分配后系统进入不安全状态,提示系统不安全并返回。
〔4〕对输入进行检查,即若输入不符合条件,应当报错并返回重新输入。
3.目的:
根据设计题目的要求,充分地分析和理解题目,叙述系统的要求,明确程序要XX现的功能以与限制条件。
明白自己需要用代码实现的功能,清楚编写每部分代码的目的,做到有的放矢,有条理不遗漏的用代码实现银行家算法。
二.概要设计
1.算法思路:
先对用户提出的请求进行合法性检查,即检查请求是否大于需要的,是否大于可利用的。
若请求合法,则进行预分配,对分配后的状态调用安全性算法进行检查。
若安全,则分配;若不安全,则拒绝申请,恢复到原来的状态,拒绝申请。
2.安全性算法步骤
〔1〕设置两个变量
①剩余资源变量盘p[]。
它表示系统可提供进程继续运行所需要的各类资源数目,执行安全算法开始时,p[N]=S[N]
②标记数组C[]。
它表示系统是否有足够的资源分配给进程,使之运行完成,开始时先做C[i]=’F’,当有足够资源分配给进程时,令C[i]=’T’。
〔2〕从进程集合中找到一个能满足下述条件的进程:
①C[i]=’F’
②Q[][]<=p[]
如找到,执行步骤〔3〕;否则,执行步骤〔4〕。
〔3〕当进程T获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:
p[]=p[]+R[][];
C[i]=’T’;
转向步骤〔2〕。
〔4〕如果所有进程的C[i]=’T’,则表示系统处于安全状态;否则,系统处于不安全状态。
3.进程请求算法步骤
〔1〕如果Request[][]<=Q[],则转向步骤
(2);否则,认为出错,因为它所需要的资源数已超过它所宣布的最大值。
〔2〕如果Request[][]<=p[][],则转向步骤〔3〕;否则,表示系统XX无足够的资源,进程必须等待。
〔3〕系统试探把要求的资源分配给进程Tt(t从1开始),并修改下面数据结构中的数值:
p[j]=p[j]-Request[t-1][j];
R[t-1][j]=R[t-1][j]+Request[t-1][j];
Q[t-1][j]=Q[t-1][j]-Request[t-1][j];
(4)系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。
4.主要用到的数据结构:
(1)最大需求矩阵Max[N][N]
(2)已分配矩阵R[N][N]
(3)仍需求矩阵Q[N][N]=Max[N][N]-R[N][N]
(4)可利用资源向量p[N]
(5)申请各类资源向量Request[N]
(6)工作向量work[],C[N]
(7)各类资源总数S[N];
5.程序模块:
voidmain()系统的主函数,用来显示资源的分配情况和提示信息,同时用Main函数来调用其它子程序。
intcheck();安全性检查函数,用来检查是否有安全序列,如果存在则返回一个‘1’给主函数,否则返回‘0’。
intjudge();进程请求函数,用来进行资源请求,分为手动的和随机申请。
同时对申请的资源进行判断,检查申请是否有效,如果有效则返回一个‘1’给主函数,否则返回‘0’。
三.流程图
1.银行家算法Main()函数流程图
2.安全性检查算法check()函数流程图
3.进程请求算法judge()函数流程图
四.运行结果与说明
输入进程总数,资源总类,每类资源总数;然后输入已分配矩阵,最大需求矩阵,系统会求出尚需矩阵并且在屏幕上输出;然后系统调用check〔〕安全检查函数进行安全检查,会在屏幕上输出系统是否安全,若安全,则会输出安全序列;接着系统调用judge〔〕请求分配函数,屏幕上提醒输入要申请资源的序列号和要申请的各类资源数,输入以后,系统会进行判断要申请的资源数是否小于剩余资源数,是否小于或等于最大需求数,若都小于,系统会进行安全检查,若安全,系统就会进行资源分配。
运行结果如下:
五、总结
通过这次的课程设计,我了解掌握了银行家算法,学会模拟实现资源分配,同时通过编写和调试一个系统分配资源的简单模拟程序,观察到了死锁产生的条件,并使用适当的算法,有效的防止和避免死锁的发生。
虽然操作系统是以前学的,再接触时遗忘了许多,但是通过老师的讲解,同学的帮助,自己也仔细地看了这次课程设计的实验指导,捡回了许多东西,对于银行家算法的设计、编写的思路变得清晰。
通过几天反复的阅读实验指导,仔细的思考出现的问题,反复推敲、测试与修改,终于能完满的完成课程设计任务。
课程设计的时间虽然不长,但带了给我知识,也带给了我战胜困难、完成任务的欢乐。
希望以后有更多的机会接触这类的课程设计。
附:
程序清单
#defineN100
#include
intT[N];
intS[N];/*各类资源总数*/
intp[N];/*剩余资源数*/
charC[N];
intR[N][N];/*已分配矩阵*/
intQ[N][N];/*尚需分配矩阵*/
intMAX[N][N];/*最大需求矩阵*/
intcheck();
intjudge();
main()
{intsum,i,j,n,m;
printf("请输入进程总数:
");
scanf("%d",&m);
printf("请输入资源总类数:
");
scanf("%d",&n);
printf("请输入每类资源总数:
");
for(j=0;j{
scanf("%d",&S[j]);
}
printf("请输入已分配资源矩阵:
\n");
for(i=0;i{for(j=0;jscanf("%d",&R[i][j]);/*已分配矩阵*/
}
printf("请输入最大需求资源矩阵:
\n");
for(i=0;i{for(j=0;jscanf("%d",&MAX[i][j]);/*最大需求矩阵*/
}
printf("尚需分配资源矩阵为:
\n");
printf("进程名");
for(j=0;jprintf("R%d\t",j+1);
printf("\n");
for(i=0;i{printf("T%d\t",i+1);
for(j=0;j{Q[i][j]=MAX[i][j]-R[i][j];
printf("%d\t",Q[i][j]);/*尚需分配矩阵*/
}
printf("\n");
}
check(m,n);
judge(m,n);
}
intcheck(intm,intn)/*安全检查函数*/
{inti,j,k,l=0;
for(j=0;j{p[j]=S[j];
for(i=0;ip[j]=p[j]-R[i][j];
}
for(i=0;iC[i]='F';
for(i=0;i{if(C[i]=='T')
continue;
else
{
for(j=0;j{if(p[j]break;
}
if(j==n)
{C[i]='T';
for(k=0;kp[k]+=R[i][k];
T[l++]=i;
i-=1;
}
elsecontinue;
if(l==m)
{printf("系统是安全的\n");
printf("安全序列是:
\n");
for(i=0;i{printf("T%d",T[i]+1);
if(i!
=l-1)
printf("-->");
}
printf("\n");
return1;
}
}
}
}
intjudge(intm,intn)/*进程请求函数*/
{inti,j,t;
intRequest[N][N];
charch;
while
(1)
{
printf("输入要申请的资源的进程号(1~%d):
",m);
scanf("%d",&t);
printf("输入进程所请求的各资源的数量:
");
for(j=0;jscanf("%d",&Request[t-1][j]);
for(j=0;j{
if(Request[t-1][j]>Q[t-1][j])
{
printf("你输入的请求数超过进程的需求量!
\n");
return0;
}
if(Request[t-1][j]>p[j])
{
printf("你输入的请求数超过系统有的资源数!
\n");
return0;
}
}
for(j=0;j{
p[j]-=Request[t-1][j];
R[t-1][j]+=Request[t-1][j];
Q[t-1][j]-=Request[t-1][j];
}
if(check)
printf("同意分配请求!
\n");
else
{
printf("你的请求被拒绝!
\n");
for(j=0;j{
p[j]+=Request[t-1][j];
R[t-1][j]-=Request[t-1][j];
Q[t-1][j]+=Request[t-1][j];
}
for(i=0;iC[i]='F';
printf("你还想再次请求分配吗?
是请按y/Y,否请按n/N,再确定\n");
while
(1)
{
ch=getch();
if(ch=='y'||ch=='Y'||ch=='n'||ch=='N')
break;
else
{
printf("请按要求输入!
\n");
continue;
}
}
if(ch=='y'||ch=='Y')
continue;
else
break;
}
}
}