操作系统银行家算法实验报告

PAGEPAGE9银行家算法【开发语言及实现平台或实验环境】C++MicrosoftVisualStudio6.0【实验目的】（1）进一步理解利用银行家算法避免死锁的问题；（2）在了解和掌握银行家算法的基础上，编制银行家算法通用程序，将调试结果显示在计算机屏幕上，再检测和笔算的一致性。（3）理解和掌握安全序列、安全性算法【实验要求】（1）了解和理解死锁；（2）理解利用银行家算法避免死锁的原理；（3）会使用某种编程语言。【实验原理】一、安全状态指系统能按照某种顺序如<P1,P2,…,Pn>(称为<P1,P2,…,Pn>序列为安全序列)，为每个进程分配所需的资源，直至最大需求，使得每个进程都能顺利完成。二、银行家算法假设在进程并发执行时进程i提出请求j类资源k个后，表示为Requesti[j]=k。系统按下述步骤进行安全检查：（1）如果Requesti≤Needi则继续以下检查，否则显示需求申请超出最大需求值的错误。（2）如果Requesti≤Available则继续以下检查，否则显示系统无足够资源，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等待。三、安全性算法（1）设置两个向量：①工作向量Work:它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work∶=Available;②Finish:它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish［i］∶=false;当有足够资源分配给进程时，再令Finish［i］∶=true。（2）从进程集合中找到一个能满足下述条件的进程：①Finish［i］=false;②Need［i,j］≤Work［j］；若找到，执行步骤(3)，否则，执行步骤(4)。（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Work［j］∶=Work［i］+Allocation［i,j］;Finish［i］∶=true;gotostep2;（4）如果所有进程的Finish［i］=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。【实验步骤】 参考实验步骤如下：（1）参考图1-1所示流程图编写安全性算法。NNY所有finish都为true？输出安全序列NYN存在Finish[i]=false&&Need[i][j]<=Available[j]初始化Work和FinishFinish[i]=true，Work[j]=Work[j]+Allocation[i][j]所有进程都找完了？Y开始图1-1安全性算法流程图输出系统不安全（2）编写统一的输出格式。 每次提出申请之后输出申请成功与否的结果。如果成功还需要输出变化前后的各种数据，并且输出安全序列。（3）参考图1-2所示流程图编写银行家算法。（4）编写主函数来循环调用银行家算法。结束结束否是申请失败。以上分配作废，恢复原来的分配状态：Available[j]=Available[j]+Requesti[j]Allocation[i][j]=Allocation[i][j]－Requesti[j]Need[i][j]=Need[i][j]+Requesti[j]NYNYRequesti[j]>Need[i][j]出错返回：return(error)Requesti[j]>Available[j]出错返回：(进程阻塞)return(error)Available[j]=Available[j]–Requesti[j]Allocation[i][j]=Allocation[i][j]+Requesti[j]Need[i][j]=Need[i][j]–Requesti[j]假定分配：输入初始参数（资源分配及请求情况）开始假定分配之后，系统安全吗？申请成功。输出各种数据的变化图1-2银行家算法流程图【参考代码】#include<iostream>#include<string.h>#include<stdio.h>#defineFalse0#defineTrue1usingnamespacestd;intMax[100][100]={0};//各进程所需各类资源的最大需求intAvaliable[100]={0};//系统可用资源charname[100]={0};//资源的名称intAllocation[100][100]={0};//系统已分配资源intNeed[100][100]={0};//还需要资源intRequest[100]={0};//请求资源向量inttemp[100]={0};//存放安全序列intWork[100]={0};//存放系统可提供资源intM=100;//进程的最大数为intN=100;//资源的最大数为voidshowdata()//显示资源矩阵{ inti,j; cout<<"系统目前可用的资源[Avaliable]:"<<endl; for(i=0;i<N;i++)cout<<name[i]<<""; cout<<endl; for(j=0;j<N;j++)cout<<Avaliable[j]<<"";//输出分配资源 cout<<endl; cout<<"MaxAllocationNeed"<<endl; cout<<"进程名"; for(j=0;j<3;j++){ 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; }}voidchangdata(inti)//进行资源分配{ intj; 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]; } }voiddeletejob(inti){intj,count=0; for(j=0;j<N;j++){ if(Need[i][j]==0) { count++; } } if(count==N) { cout<<"!!!!!!!!!!!!!此作业需求的资源已经分配完毕，自动释放!!!!!!!!!!!!"<<endl; for(j=0;j<N;j++) { Avaliable[j]=Avaliable[j]+Allocation[i][j]; } M--; }}intsafe()//安全性算法{ inti,k=0,m,apply,Finish[100]={0}; intj; for(i=0;i<N;i++) { Work[i]=Avaliable[i]; } for(i=0;i<M;i++){ apply=0; for(j=0;j<N;j++){ if(Finish[i]==False&&Need[i][j]<=Work[j]){ apply++; if(apply==N){ for(m=0;m<N;m++) Work[m]=Work[m]+Allocation[i][m];//变分配数 Finish[i]=True; temp[k]=i; i=-1; k++; } } } } for(i=0;i<M;i++){ if(Finish[i]==False){ cout<<"系统不安全"<<endl;//不成功系统不安全 return-1; } }cout<<"系统是安全的!"<<endl;//如果安全，输出成功cout<<"分配的序列:"; for(i=0;i<M;i++){//输出运行进程数组 cout<<temp[i]; if(i<M-1)cout<<"->"; } cout<<endl; return0;}voidshare()//利用银行家算法对申请资源对进行判定{ charch; inti=0,j=0; ch='y'; cout<<"请输入要求分配的资源进程号(0-"<<M-1<<"):";cin>>i;//输入须申请的资源号 cout<<"请输入进程"<<i<<"申请的资源:"<<endl; for(j=0;j<N;j++) { cout<<name[j]<<":"; cin>>Request[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);//根据进程需求量变换资源 deletejob(i); showdata();//根据进程需求量显示变换后的资源 safe();//根据进程需求量进行银行家算法判断}}voidaddprocess(){//添加作业intflag=M; M=M+1; cout<<"请输入该作业的最大需求量[Max]"<<endl; for(inti=0;i<N;i++){ cout<<name[i]<<":"; cin>>Max[flag][i]; Need[flag][i]=Max[flag][i]-Allocation[flag][i]; } showdata(); safe();}intmain()//主函数{inti,j,number,choice,m,n,flag;charming; cout<<"\t"<<endl; cout<<"\t||||"<<endl; cout<<"\t||银行家算法的实现||"<<endl; cout<<"\t||||"<<endl; cout<<"\t||binbinwangbin||"<<endl; cout<<"\t||||"<<endl; cout<<"\t||||"<<endl; cout<<"\t"<<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; } 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++) f