一、 实验名称:银行家算法
二、 实验目的:银行家算法是避免死锁的一种重要方法,通过编写一个简单的银行家算法程序,加深了解有关资源申请、避免死锁等概念,并体会和了解死锁和避免死锁的具体实施方法。
三、 问题分析与设计:
1、算法思路:先对用户提出的请求进行合法性检查,即检查请求是否大于需要的,是否大于可利用的。若请求合法,则进行预分配,对分配后的状态调用安全性算法进行检查。若安全,则分配;若不安全,则拒绝申请,恢复到原来的状态,拒绝申请。
2、银行家算法步骤:(1)如果Requesti<or =Need,则转向步骤(2);否则,认为出错,因为它所需要的资源数已超过它所宣布的最大值。
(2)如果Request<or=Available,则转向步骤(3);否则,表示系统中尚无足够的资源,进程必须等待。
(3)系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值:
Available=Available-Request[i];
Allocation=Allocation+Request;
Need=Need-Request;
(4)系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。
3、安全性算法步骤:
(1)设置两个向量
①工作向量Work。它表示系统可提供进程继续运行所需要的各类资源数目,执行安全算法开始时,Work=Allocation;
②布尔向量Finish。它表示系统是否有足够的资源分配给进程,使之运行完成,开始时先做Finish[i]=false,当有足够资源分配给进程时,令Finish[i]=true。
(2)从进程集合中找到一个能满足下述条件的进程:
①Finish[i]=false
②Need<or=Work
如找到,执行步骤(3);否则,执行步骤(4)。
(3)当进程P获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:
Work=Work+Allocation;
Finish[i]=true;
转向步骤(2)。
(4)如果所有进程的Finish[i]=true,则表示系统处于安全状态;否则,系统处于不安全状态。
四.程序源代码:
#include <stdio.h>
#define W 5//最大进程数W=5
#define R 3//最大资源总数=3
int Available[3];//可利用资源向量
int Max[5][3];//最大需求矩阵
int Allocation[5][3]; //分配矩阵
int Need[5][3];//需求矩阵
int Request[3];//进程请求向量
void dispose()
{
printf("请输入可利用资源向量Available(格式:a,b,c)\n");
scanf("%d,%d,%d",&Available[0],&Available[1],&Available[2]);
printf("请输入最大需求数Max(格式:a,b,c)\n");
for(int j=0;j<5;j++)
{
printf("进程%d:\n",j);
scanf("%d,%d,%d",&Max[j][0],&Max[j][1],&Max[j][2]);
}
printf("请输入分配数Allocation(格式:a,b,c)\n");
for(j=0;j<5;j++)
{
printf("进程%d\n",j);
scanf("%d,%d,%d",&Allocation[j][0],&Allocation[j][1],&Allocation[j][2]);
}//输入Max[5][3],Available[5][3],Allocation[5][3]
for(j=0;j<5;j++)
for(int i=0;i<3;i++)
Need[j][i]=Max[j][i]-Allocation[j][i];//求出Need[5][3]
}
main()
{
printf(" 银行家算法 \n");
dispose();
printf("安全性检查\n");
int Work[3];//系统可提供进程继续运行所需的各类资源数
char Finish[5];//表示系统是否有足够的资源分配
for(int i=0;i<5;i++)
Finish[i]='f';
for(int k=0;k<3;k++)
Work[k]=Available[k];
int q[5];
for(int x=0;x<50;x++)
{
printf("请输入一个序列:\n");
scanf("%d,%d,%d,%d,%d",&q[0],&q[1],&q[2],&q[3],&q[4]);
for(i=0;i<5;i++)
{
if((Need[q[i]][0]<=Work[0])&&(Need[q[i]][1]<=Work[1])&&(Need[q[i]][2]<=Work[2]))//比较Need[i][j]与Work[j]
{
for(k=0;k<3;k++)
Work[k]=Work[k]+Allocation[q[i]][k];
Finish[i]='t';
}
}
if((Finish[0]=='t')&&(Finish[1]=='t')&&(Finish[2]=='t')&&(Finish[3]=='t')&&(Finish[4]=='t'))//通过Finish[i]判断系统是否安全
break;
else
printf("此序列不是安全序列,请重新输入一个序列!\n");
if(x==49)
return 0;
}
printf("这个系统安全!\n");
int a;
printf("请输入Request进程:\n");
scanf("%d",&a);
printf("该进程Request(a,b,c)\n");
scanf("%d,%d,%d",&Request[0],&Request[1],&Request[2]);//输入请求量Request[3]
if((Request[0]<=Need[a][0])&&(Request[1]<=Need[a][1])&&(Request[2]<=Need[a][2]))//判断Request[i]<=Need[a][i]
{
if((Request[0]<=Need[a][0])&&(Request[0]<=Need[a][1])&&(Request[0]<=Need[a][2]))//判断Request[i]<=Available[a][i]
{
for(int k=0;k<3;k++)
{
Available[k]=Available[k]-Request[k];
Allocation[a][k]=Allocation[a][k]+Request[k];
Need[a][k]=Need[a][k]-Request[k];
//如果上述判断成功,则修改相应的Available[k],Allocation[a][k],Need[a][k]
}
printf("资源分配成功!\n");
}
else
{
printf("资源分配失败!\n");
return 0;
}
}
else
{
printf("资源分配失败!\n");
return 0;
}
}
程序截图:
五.实验总结
多个进程同时运行时,系统根据各类系统资源的最大需求和各类系统的剩余资源为进程安排安全序列,使得系统能快速且安全地运行进程,不至发生死锁。银行家算法是避免死锁的主要方法,其思路在很多方面都非常值得我们来学习借鉴。
银行家算法
//Breaker.h文件代码
#include<iostream.h>
#include<string.h>
#include<stdio.h>
#define False 0
#define True 1
int Max[100][100]={0};//各进程所需各类资源的最大需求
int Avaliable[100]={0};//系统可用资源
char name[100]={0};//资源的名称
int Allocation[100][100]={0};//系统已分配资源
int Need[100][100]={0};//还需要资源
int Request[100]={0};//请求资源向量
int temp[100]={0};//存放安全序列
int Work[100]={0};//存放系统可提供资源
int M=100;//作业的最大数为100
int N=100;//资源的最大数为100
int S=1;//定义变量用于数据恢复
void showdata()//显示资源矩阵
{
int i,j;
cout<<"系统目前可用的资源[Avaliable]:"<<endl;
for(i=0;i<N;i++)
cout<< name[i]<<" ";//输出第i类资源的名称
cout<<endl;
for (j=0;j<N;j++)
cout<<Avaliable[j]<<" ";//输出分配资源
cout<<endl;
cout<<" M a x Allocation Need"<<endl;
cout<<"进程名 ";
for(j=0;j<3;j++)//for循环 输出显示的资源类别名称
{
for(i=0;i<N;i++)
cout<<name[i]<<" ";
cout<<" ";
}
cout<<endl;
for(i=0;i<M;i++)
{
cout<<" "<<i<<" ";
for(j=0;j<N;j++)
cout<<Max[i][j]<<" ";
cout<<" ";
for(j=0;j<N;j++)
cout<<Allocation[i][j]<<" ";
cout<<" ";
for(j=0;j<N;j++)
cout<<Need[i][j]<<" ";
cout<<endl;
}
}
int safe()//安全性算法
{
int i,j,k=0,m,apply,Finish[100]={0};
for(j=0;j<N;j++)
Work[j]=Avaliable[j];
for(i=0;i<M;i++)//作业
{
apply=0;
for(j=0;j<N;j++)//种类
{
if (Finish[i]==False&&Need[i][j]<=Work[j])//Finish[i]==False是个很关键的条件,也使下面的i=-1变得高效很多
{
apply++;
if(apply==N) //N个种类对应的Work都必须成立,即apply会自加到N
{
for(m=0;m<N;m++)
Work[m]=Work[m]+Allocation[i][m];//变分配数,更新Work
Finish[i]=True;
temp[k]=i; //存储安全序列
k++;
i=-1;//此i用得相当的好!!!每次安全序列增加时for(i=0;i<M;i++)都会从头开始循环
} //避免在Work更新后有些可以进入安全序列的进程出现丢失
}
}
}
for(i=0;i<M;i++)
{
if(Finish[i]==False)
{
cout<<"系统不安全"<<endl;//不成功系统不安全
S=-1;
return S;
}
}
cout<<"系统是安全的!"<<endl;//如果安全,输出成功
cout<<"分配的序列:";
for(i=0;i<M;i++)//输出运行进程数组
{
cout<<temp[i];
if(i<M-1) cout<<"->";
}
cout<<endl;
return 0;
}
int changdata(int i)//进行资源分配
{
int j;
for (j=0;j<N;j++)
{
Avaliable[j]=Avaliable[j]-Request[j];
Allocation[i][j]=Allocation[i][j]+Request[j];
Need[i][j]=Need[i][j]-Request[j];
}
return 1;
}
int discover(int i)//进行资源恢复
{
int j;
for (j=0;j<N;j++)
{
Avaliable[j]=Avaliable[j]+Request[j];
Allocation[i][j]=Allocation[i][j]-Request[j];
Need[i][j]=Need[i][j]+Request[j];
}
return 1;
}
void share() //对申请资源对进行判定
{
char ch;
int i=0,j=0;
ch='y';
cout<<"请输入要求分配的资源进程号(0-"<<M-1<<"):"; //M-1???
cin>>i;//输入须申请的资源号
cout<<"请输入进程 "<<i<<" 申请的资源:"<<endl;
for(j=0;j<N;j++)
{
cout<<name[j]<<":";
cin>>Request[j];//输入需要申请第j类的资源数量
}
for (j=0;j<N;j++)
{
if(Request[j]>Need[i][j])//判断申请是否大于需求,若大于则出错
{
cout<<"进程 "<<i<<"申请的资源大于它需要的资源";
cout<<" 分配不合理,不予分配!"<<endl;
ch='n';
break;
}
else
{
if(Request[j]>Avaliable[j])//判断申请是否大于当前可分配资源,若大于则
{ //出错
cout<<"进程"<<i<<"申请的资源大于系统现在可利用的资源";
cout<<" 分配出错,不予分配!"<<endl;
ch='n';
break;
}
}
}
if(ch=='y')
{
changdata(i);//根据进程需求量变换资源,即第i个作业Pi
safe();//根据进程需求量进行银行家算法判断
if(S==-1)
{
cout<<"资源分配后系统不安全,资源已恢复!"<<endl;
discover(i);
}
showdata();//根据进程需求量显示变换后的资源
}
}
void addresources() //添加资源
{
int n,i,flag;
cout<<"请输入需要添加资源的个数:";
cin>>n;
flag=N;
N=N+n;
for(;flag<N;flag++)
{
cout<<"请输入资源的名称:";
cin>>name[flag];
cout<<"请输入资源的可分配数量:";
cin>>Avaliable[flag];
for(i=0;i<M;i++)
{
cout<<"请输入第 "<<i<<" 进程的对该资源的最大需求量[Max]:"<<endl;
cin>>Max[i][flag];
Need[i][flag]=Max[i][flag]-Allocation[i][flag];
}
}
showdata();
safe();
}
void delresources(){//删除资源
char ming;
int i,m,flag=1;
cout<<"请输入需要删除的资源名称:";
do{
cin>>ming;
for(i=0;i<N;i++)
if(ming==name[i]){
flag=0;
break;
}
if(i==N)
cout<<"该资源名称不存在,请重新输入:";
}
while(flag);
{
for(int j=i;j<N-1;j++)
{
name[j]=name[j+1];
Avaliable[j]=Avaliable[j+1];
}
for(m=0;m<M;m++)
{
for(j=i;j<N-1;j++)
{
Allocation[m][j]=Allocation[m][j+1];
Max[m][j]=Max[m][j+1];
Need[m][j]=Need[m][j+1];
}
}
}
N=N-1; //删除一个资源,所以资源总数减一
showdata();
safe();
}
void changeresources() //修改资源函数
{
int i,k;
cout<<"系统目前可用的资源[Avaliable]:"<<endl;
for(i=0;i<N;i++)
cout<<name[i]<<":"<<Avaliable[i]<<endl;
for(i=0;i<N;i++)
{
cout<<"输入"<<name[i]<<"可用资源[Avaliable]:"<<endl;
cin>>Avaliable[i];
cout<<endl;
}
cout<<"经修改后的系统可用资源为"<<endl;
for (k=0;k<N;k++)
cout<<name[k]<<":"<<Avaliable[k]<<endl;
safe();
}
void addprocess() //添加作业
{
int flag=M;
M=M+1;
cout<<"请输入该进程对每类资源的最大需求量[Max]"<<endl;
for(int i=0;i<N;i++)
{
cout<<name[i]<<":";
cin>>Max[flag][i];
Need[flag][i]=Max[flag][i]-Allocation[flag][i];
}
showdata();
safe();
}
//Breaker.cpp文件代码
#include "Banker.h"
int main()//主函数
{
int i,j,number,choice,m,n,flag;
char ming; //存储资源的名称
cout<<"*****************资源管理系统的设计与实现*****************"<<endl;
cout<<"请首先输入系统可供资源种类的数量:";
cin>>n;
N=n; //存储资源的种类数
for(i=0;i<n;i++)
{
cout<<"资源"<<i+1<<"的名称:";
cin>>ming; //输入资源的名称
name[i]=ming;
cout<<"资源的数量:";
cin>>number; //存储资源的数量
Avaliable[i]=number; //记录第i类资源的可用数
}
cout<<endl;
cout<<"请输入作业的数量:";
cin>>m;
M=m; //记录作业数量
cout<<"请输入各进程的最大需求量("<<m<<"*"<<n<<"矩阵)[Max]:"<<endl;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
cin>>Max[i][j];
do{
flag=0;
cout<<"请输入各进程已经申请的资源量("<<m<<"*"<<n<<"矩阵)[Allocation]:"<<endl;
for(i=0;i<m;i++)
for(j=0;j<n;j++){
cin>>Allocation[i][j];
if(Allocation[i][j]>Max[i][j])
flag=1;
Need[i][j]=Max[i][j]-Allocation[i][j];
}
if(flag)
cout<<"申请的资源大于最大需求量,请重新输入!\n";
}
while(flag); //flag用于标记已经申请的资源是否大于最大需求量
showdata();//显示各种资源
safe();//用银行家算法判定系统是否安全
while(choice)
{
cout<<"**************银行家算法演示***************"<<endl;
cout<<" 1:增加资源 "<<endl;
cout<<" 2:删除资源 "<<endl;
cout<<" 3:修改资源 "<<endl;
cout<<" 4:分配资源 "<<endl;
cout<<" 5:增加作业 "<<endl;
cout<<" 6:显示资源 "<<endl;
cout<<" 0:离开 "<<endl;
cout<<"*******************************************"<<endl;
cout<<"请选择功能号:";
cin>>choice;
switch(choice)
{
case 1: addresources();break; //增加资源
case 2: delresources();break; //删除资源
case 3: changeresources();break; //修改资源
case 4: share();break; //分配资源
case 5: addprocess();break; //增加作业
case 6: showdata();break; //显示资源
case 0: choice=0;break; //离开
default: cout<<"请正确选择功能号(0-6)!"<<endl;break;
}
}
return 1;
}
计算机操作系统实验报告一实验名称银行家算法二实验目的银行家算法是避免死锁的一种重要方法通过编写一个简单的银行家算法程序加深了解有关…
C语言实现银行家算法程序设计实验报告实验报告C语言实现银行家算法程序设计实验报告C语言实现银行家算法程序设计实验报告C语言实现银行…
淮海工学院计算机工程学院实验报告书课程名操作系统原理题目银行家算法班级学号511021012姓名操作系统原理实验报告1一实验目的银…
计算机操作系统课程设计题目银行家算法分析学院计算机与软件学院专业网络工程班级20xx级1班学号20xx1346001姓名方锡指导教…
操作系统试验姓名谢路班级软件0912学号题目银行家算法报告20xx年12月13日星期一实验银行家算法一实验目的银行家算法是一种最有…
操作系统课程设计报告题目银行家算法院系专业班级学生学号指导教师操作系统课程设计报告摘要Dijkstra提出的银行家算法是最具代表性…
武汉理工大学华夏学院课程设计报告书课程名称操作系统原理题目编程序模拟银行家算法系名信息工程系专业班级计应20xx姓名王汝平学号10…
C语言实现银行家算法程序设计实验报告实验报告C语言实现银行家算法程序设计实验报告C语言实现银行家算法程序设计实验报告C语言实现银行…
淮海工学院计算机工程学院实验报告书课程名操作系统原理题目银行家算法班级学号姓名操作系统原理实验报告1一实验目的银行家算法是操作系统…