银行家算法.docx
《银行家算法.docx》由会员分享，可在线阅读，更多相关《银行家算法.docx（18页珍藏版）》请在冰点文库上搜索。
银行家算法
淮海工学院计算机工程学院
实验报告书
课程名：
《操作系统原理》
题目：
银行家算法
班级：
学号：
姓名：
实验报告要求
1．目的与要求
银行家算法是操作系统中避免死锁的典型算法，本实验可以加深对银行家算法的步骤和相关数据结构用法的更好理解。
2．实验内容
用C语言编写一个简单的银行家算法模拟程序，用银行家算法实现资源分配。
程序能模拟多个进程共享多种资源的情形。
进程可动态地申请资源，系统按各进程的申请动态地分配资源。
要求程序具有显示和打印各进程的某一时刻的资源分配表和安全序列；显示和打印各进程依次要求申请的资源数量以及为某进程分配资源后的有关资源数据的情况。
3．实验步骤
1．认真理解好课本中银行家算法的实例。
2．根据课本中银行家算法的描述，画出程序流程图。
3．按照程序流程图，用C语言编程并实现。
流程图：
代码：
#include
#include
#include
#defineMaxResource10//最大系统资源类
#defineNULL0
structpcb//定义进程控制块PCB
{
intpid;//进程标号
intMax[MaxResource];//表示某个进程对某类资源的最大需求
intAllocation[MaxResource];//表示某个进程已分配到某类资源的个数
intNeed[MaxResource];//表示某个进程尚需要某类资源的个数
intmark[MaxResource];//在使用FreeRecourse是以确定是否释放资源
pcb*next;
};
voidInitialize（pcb*&head,intm,intn,intAvailable[MaxResource]）//初始化进程资源值
{
inti,j=0;
voidAddPcb（pcb*&head,pcbnode）;
pcbnode;
printf（"\t**请输入%d进程的%d个最大资源数**\t\n",n,m）;
do{
node.pid=j;
printf（"请输入第%d个进程最大需求资源数:
\n",node.pid）;
for（i=0;iscanf（"%d",&node.Max[i]）;
printf（"系统给进程%d随机分配资源数为:
\n",node.pid）;
for（i=0;i{
node.Allocation[i]=rand（）%node.Max[i];
printf（"%10d",node.Allocation[i]）;
Available[i]=Available[i]-node.Allocation[i];
}
printf（"\n"）;
printf（"进程%d还所需的资源数为:
\n",node.pid）;
for（i=0;i{
node.Need[i]=node.Max[i]-node.Allocation[i];
printf（"%10d",node.Need[i]）;
}
for（i=0;inode.mark[i]=0;
printf（"\n"）;
AddPcb（head,node）;
j++;
}while（j}
voidAddPcb（pcb*&head,pcbnode）//增加进程链表块
{
pcb*p=（pcb*）malloc（sizeof（pcb））;
pcb*last=NULL;
memcpy（p,&node,sizeof（pcb））;
p->next=NULL;
if（head==NULL）head=p;
else
{
last=head;
while（last->next!
=NULL）
last=last->next;
last->next=p;
}
}
voidShowPcb（pcb*head,int*avail,intm）//显示进程初始化的资源值
{
pcb*p=NULL;
intj;
p=head;
if（p==NULL）
{
printf（"当前没有进程，请重新输入进程!
\n"）;
exit（0）;
}
else
{
printf（"进程号最大资源值已分配资源还需资源可利用的资源状态\n\n"）;
while（p!
=NULL）
{
printf（"p[%d]",p->pid）;
for（j=0;j{
printf（"\t%4d%4d%4d%4d",p->Max[j],p->Allocation[j],p->Need[j],avail[j]）;
if（p->mark[j]）printf（"已执行\n"）;
elseprintf（"等待\n"）;
}
p=p->next;
}
}
}
pcb*Seek（pcb*head,intpid）//查找进程在链表中的位置
{
pcb*p=NULL;
p=head;
if（p==NULL）
{
printf（"没有进程，进程链表空！
\n"）;
returnp;
}
else
{
while（p!
=NULL）
{
if（p->pid==pid）break;
else
p=p->next;
}
if（NULL==p）
{
printf（"没有这个进程！
\n"）;
returnp;
}
else
returnp;
}
}
voidFreeResource（pcb*&head,intAvailable[MaxResource],intm）//若进程所需资源已全部分配，则释放该进程占据的全部系统资源
{
pcb*p=NULL;
inti;
p=head;
if（!
p）printf（"没有进程，请先初始化进程！
"）;
else
{
for（i=0;i{
if（（p->Need[i]==NULL）&&（p->mark[i]==NULL））
{
printf（"进程%d的第%d个已经执行完，释放所占系统资源！
\n",p->pid,i）;
Available[i]+=p->Allocation[i];
p->mark[i]=1;
}
}
}
}
pcb*Application（pcb*head,int*request,int*avail,intm）//再次给进程分配资源
{
intpid,i;
pcb*p=NULL;
printf（"请输入进程pid号:
\n"）;
printf（"p"）;
scanf（"%d",&pid）;
p=Seek（head,pid）;
if（p==NULL）
{
printf（"没有这个进程！
\n"）;
returnp;
}
printf（"请输入给该进程再次分配的资源数:
\n"）;
for（i=0;iscanf（"%d",&request[i]）;
for（i=0;iif（request[i]>p->Need[i]）
{
printf（"分配进程的资源数超过最大资源数！
\n"）;
returnNULL;
}
for（i=0;iif（request[i]>avail[i]）
{
printf（"分配进程的资源数超过可利用的资源数！
\n"）;
returnNULL;
}
for（i=0;i{
avail[i]=avail[i]-request[i];
p->Allocation[i]=p->Allocation[i]+request[i];
p->Need[i]=p->Need[i]-request[i];
}
FreeResource（p,avail,m）;
returnp;
}
pcb*Reasonable（pcb*head,int*finish,int*work,intm,intn）//找到当前安全可执行的进程返回
{
inti=0,j=0,count=0;
pcb*p=NULL;
while
（1）
{
if（finish[i]!
=-1）
{
p=Seek（head,finish[i]）;
if（p!
=NULL）
{
for（j=0;j{
if（p->Need[j]>work[j]）break;
elsecontinue;
}
if（j==m）returnp;//p进程安全
elsei++;
}
}
elsei++;
if（i==n）returnNULL;
}
}
voidAlter（pcb*p,int*work,int*finish,intrecord[][MaxResource],intm）//修改相关进程的资源值
{
inti;
for（i=0;i{
record[p->pid][i]=work[i];
work[i]=work[i]+p->Allocation[i];
}
finish[p->pid]=-1;
}
intSafetyCheck（pcb*head,int*avail,int*safety,intRecord[][MaxResource],intm,intn）//进程安全性算法
{
int*work=NULL;
int*finish=NULL;
pcb*p=NULL;
pcb*pro=NULL;
inti,count=0;
work=（int*）malloc（m*sizeof（int））;
finish=（int*）malloc（n*sizeof（int））;
p=head;
for（i=0;iwork[i]=avail[i];
i=0;
while（p!
=NULL）
{
finish[i]=p->pid;
p=p->next;
i++;
}
i=0;
while（count{
pro=Reasonable（head,finish,work,m,n）;
if（pro!
=NULL）
{
Alter（pro,work,finish,Record,m）;
count++;
safety[i]=pro->pid;
i++;
}
else
{
printf（"当前的系统处于不安全状态！
\n"）;
break;
}
}
if（count==n）
{
printf（"当前系统处于安全状态,存在一个安全序列:
\n"）;
for（i=0;iprintf（"p[%d]->",safety[i]）;
printf（"\n"）;
}
free（finish）;
free（work）;
finish=NULL;
work=NULL;
if（count==n）return1;
elsereturn0;
}
voidReturnSource（pcb*p,int*request,int*avail,intm）//若试分配失败，则恢复试分配前的资源状态
{
inti;
for（i=0;i{
p->Allocation[i]-=request[i];
p->Need[i]+=request[i];
avail[i]+=request[i];
}
}
voidmain（）
{
intn,m;
charch;
inti,flag=0;
intAvailable[MaxResource]={0};
intRequest[MaxResource]={0};
intRecord[MaxResource][MaxResource]={0};
intSafety[MaxResource]={0};//记录安全序列
pcb*head,*process;
head=NULL;process=NULL;
printf（"\t\t**欢迎使用银行家算法**\t\t\n"）;
printf（"请输入进程数：
\n"）;
scanf（"%d",&n）;
printf（"请输入资源数：
\n"）;
scanf（"%d",&m）;
if（m>MaxResource）
{
printf（"请输入资源数超过系统最大资源数，请重新输入！
\n"）;
scanf（"%d",&m）;
}
printf（"请输入系统总共可利用的资源数值：
\n"）;
for（i=0;iscanf（"%d",&Available[i]）;
Initialize（head,m,n,Available）;
printf（"系统为进程分配资源如下表:
\n"）;
ShowPcb（head,Available,m）;
do
{
flag=SafetyCheck（head,Available,Safety,Record,m,n）;
if（flag）
{
printf（"系统是安全的，可以再申请资源\n"）;
do
{
process=Application（head,Request,Available,m）;
if（process!
=NULL）
{
printf（"系统资源分配如下表:
\n"）;
ShowPcb（head,Available,m）;
break;
}
else
{
printf（"请求申请资源不能满足！
\n"）;
printf（"是否重新申请：
Y重新申请N退出\n"）;
getchar（）;
scanf（"%c",&ch）;
if（ch=='N'||ch=='n'）exit（0）;
}
}while（ch=='Y'||ch=='y'）;
printf（"是否还要继续操作，请选择：
Y是N否\n"）;
getchar（）;
scanf（"%c",&ch）;
}
if（!
flag）
{
printf（"系统处于不安全状态,本次申请分配作废，恢复原来的资源分配状态！
\n"）;
ReturnSource（process,Request,Available,m）;
printf（"系统原有分配资源如下表：
\n"）;
ShowPcb（head,Available,m）;
printf（"是否还要继续操作，请选择：
Y是N否\n"）;
getchar（）;
scanf（"%c",&ch）;
}
}while（ch=='Y'||ch=='y'）;
printf（"**欢迎下次使用银行家算法**\n"）;
}
截图：
图1
图2
图3
图4
图5
4．结果分析与实验体会
5.思考题
1．要找出某一状态下所有可能的安全序列，程序该如何实现？
2．银行家算法的局限性有哪些？
升级会员 