计算机操作系统实验二银行家算法.doc
《计算机操作系统实验二银行家算法.doc》由会员分享，可在线阅读，更多相关《计算机操作系统实验二银行家算法.doc（6页珍藏版）》请在冰点文库上搜索。
实验报告
课程名称
操作系统实验
班级
实验日期
姓名
学号
实验成绩
实验名称
银行家算法
实
验
目
的
及
要
求
1、了解掌握银行家算法，学会模拟实现资源分配，同时有要求编写和调试一个系统分配资源的简单模拟程序，观察死锁产生的条件，并使用适当的算法，有效的防止和避免死锁的发生
实
验
内
容
1、在多道程序系统中，虽可借助与多个进程的并发执行，来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险---死琐。
产生死锁的原因可归结为两点：
1：
竞争资源。
当系统中供多个进程共享的资源如打印机、公用队列等，其数目不足以满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁。
2：
进程间推进顺序非法。
进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁。
最有代表性的避免死锁的算法，是Dijkstra的银行家算法。
这是由于该算法能用与银行系统现金贷款的发放而得名的。
算
法
描
述
及
实
验
步
骤
1.算法描述：
设Request[i]是进程Pi的请求向量，如果Requesti[j]=K,表示进程Pi需要K个Rj类型的资源，当Pi发出资源请求后，系统按下面步骤进行检查：
（1）如果Requesti[j]<=Need[i,j]，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
（2）如果Requesti[j]<=Available[j],便转向步骤3；否则，表示尚无足够资源，Pi须等待。
（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：
Available[j]:
=Available[j]-Requesti[j];
Allocation[i,j]:
=Allocation[i,j]+Requesti[j];
Need[i,j]:
=Need[i,j]-Requesti[j];
（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。
若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。
2.数据结构
银行家算法中的数据结构：
（1）可利用资源向量Available。
这是一个含有n个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。
如果Available[j]=K,则表示系统中现有Rj类资源K个。
（2）最大需求矩阵Max。
这是一个m*n的矩阵，它定义了系统中n个进程中每一个进程对m类资源的最大需求。
如果Max[i,j]=K,则表示进程i需要Rj类资源的最大数目为K。
（3）分配矩阵Allocation。
这也是一个m*n的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。
如果Allocation[i,j]=K,则表示进程i当前已分得Rj类资源的数目为K。
（4）需求矩阵Need。
这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。
如果Need[i,j]=K,则表示进程i还需要Rj类资源K个，方能完成其任务。
（5）工作数组Work.。
这是一个含有n个元素的数组，它代表可以提供分配的资源数，初始值是Available中的数值，随着资源的回收，它的值也会改变，公式是Work[i]=Work[i]+Allocation[i]。
3.算法流程图
程序初始化
随机分配资源
并显示在屏幕
检查安全序列
是否要申请资源
退出程序
输入Request
RequestRequestNeed[i][j]=Need[i][j]-Request[j]
Available[j]=Available[j]-Request[j]
报错
检查安全序列
保留原始Available、Request
恢复原始
Available、Request
判Allocation=Max
Available[j]=Max[i][j]+work[j]
Finish[i]=1
输出结果
调
试
过
程
及
实
验
结
果
实验结果为：
附
录
#include
#include
#include
#definem50
intno1;//进程数
intno2;//资源数
intr;
intallocation[m][m],need[m][m],available[m],max[m][m];
charname1[m],name2[m];//定义全局变量
voidmain（）
{
voidcheck（）;
voidprint（）;
inti,j,p=0,q=0;
charc;
intrequest[m],allocation1[m][m],need1[m][m],available1[m];
printf（"**********************************************\n"）;
printf（"*银行家算法的设计与实现*\n"）;
printf（"**********************************************\n"）;
printf（"请输入进程总数:
\n"）;
scanf（"%d",&no1）;
printf（"请输入资源种类数:
\n"）;
scanf（"%d",&no2）;
printf（"请输入Max矩阵:
\n"）;
for（i=0;i for（j=0;j scanf（"%d",&max[i][j]）;//输入已知进程最大资源需求量
printf（"请输入Allocation矩阵:
\n"）;
for（i=0;i for（j=0;j scanf（"%d",&allocation[i][j]）;//输入已知的进程已分配的资源数
for（i=0;i for（j=0;j need[i][j]=max[i][j]-allocation[i][j];//根据输入的两个数组计算出need矩阵的值
printf（"请输入Available矩阵\n"）;
for（i=0;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;
}
elsebreak;
}
printf（"\n请输入该进程所请求的资源数request[j]:
\n"）;
for（j=0;j scanf（"%d",&request[j]）;
for（j=0;j if（request[j]>need[i][j]）p=1;
//判断请求是否超过该进程所需要的资源数
if（p）
printf（"请求资源超过该进程资源需求量，请求失败！
\n"）;
else
{
for（j=0;j if（request[j]>available[j]）
q=1;
if（q）
printf（"没有做够的资源分配，请求失败！
\n"）;
else//请求满足条件
{
for（j=0;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];
//系统尝试把资源分配给请求的进程
}
print（）;
check（）;//检测分配后的安全性
if（r==0）//如果分配后系统不安全
{
for（j=0;j {
available[j]=available1[j];
allocation[i][j]=allocation1[i][j];
need[i][j]=need1[i][j];
//还原已分配的资源数，仍需要的资源数和可用的资源数
}
printf（"返回分配前资源数\n"）;
print（）;
}
}
}printf（"\n你还要继续分配吗？
YorN?
\n"）;
//判断是否继续进行资源分配
c=getche（）;
}while（c=='y'||c=='Y'）;
}
}
voidcheck（）//安全算法函数
{
intk,f,v=0,i,j;
intwork[m],a[m];
boolfinish[m];
r=1;
for（i=0;i finish[i]=false;//初始化进程均没得到足够资源数并完成
for（i=0;i work[i]=available[i];//work[i]表示可提供进程继续运行的各类资源数
k=no1;
do{
for（i=0;i {
if（finish[i]==false）
{
f=1;
for（j=0;j if（need[i][j]>work[j]）
f=0;
if（f==1）//找到还没有完成且需求数小于可提供进程继续运行的资源数的进程
{
finish[i]=true;
a[v++]=i;//记录安全序列号
for（j=0;j work[j]+=allocation[i][j];//释放该进程已分配的资源
}
}
}
k--;//每完成一个进程分配，未完成的进程数就减1
}while（k>0）;
f=1;
for（i=0;i {
if（finish[i]==false）
{
f=0;
break;
}
}
if（f==0）//若有进程没完成，则为不安全状态
{
printf（"系统处在不安全状态！
"）;
r=0;
}
else
{
printf（"\n系统当前为安全状态，安全序列为：
\n"）;
for（i=0;i printf（"p%d",a[i]）;//输出安全序列
}
}
voidprint（）//输出函数
{
inti,j;
printf（"\n"）;
printf（"*************此时刻资源分配情况*********************\n"）;
printf（"进程名/号|Max|Allocation|Need|\n"）;
for（i=0;i {
printf（"p%d/%d",i,i）;
for（j=0;j {printf（"%d",max[i][j]）;}
for（j=0;j {printf（"%d",allocation[i][j]）;}
for（j=0;j {printf（"%d",need[i][j]）;}
printf（"\n"）;
}
printf（"\n"）;
printf（"各类资源可利用的资源数为:
"）;
for（j=0;j {printf（"%d",available[j]）;}
printf（"\n"）;
}
升级会员 