银行家算法实现资源分配

《操作系统》实验报告班级信计81101学号110046120姓名缪景怡日期2014.4.29学院广陵学院专业信息与计算科学课程名称操作系统评语实验二银行家算法实现资源分配一、实验目的:在了解和掌握银行家算法的基础上，能熟练的处理课本例题中所给状态的安全性问题。能编制银行家算法通用程序，将调试结果显示在计算机屏幕上，再检测和笔算的一致性。二、实验内容:已知进程{P0,P1,P2,P3,P4}，有三类系统资源A、B、C的数量分别为10、5、7，在T0时刻的资源分配情况如下图所示：资源情况进程MaxAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P4433002431（1）若进程P1请求资源，发出请求向量Request1（1，0，2），编写程序用银行家算法判断系统能否将资源分配给它；（2）若进程P3提出请求Request(1，1，2)，用银行家算法程序验证系统能否将资源分配给它。三、实验要求：本实验要求用高级语言编写和调试一个简单的银行家算法程序。用银行家算法实现资源分配。四、实验步骤：数据结构:1.可利用资源向量Available2.最大需求矩阵Max3.分配矩阵Allocation4.需求矩阵Need功能介绍:模拟实现Dijkstra的银行家算法以避免死锁的出现.分两部分组成:第一部分:银行家算法(扫描)1．如果Request=Need,则转向2;否则,出错2．如果Request=Available,则转向3,否则等待3．系统试探分配请求的资源给进程4．系统执行安全性算法第二部分:安全性算法1.设置两个向量(1).工作向量:Work=Available(表示系统可提供给进程继续运行所需要的各类资源数目)(2).Finish:表示系统是否有足够资源分配给进程(True:有;False:没有).初始化为False2.若Finish[i]=False&&Need=Work,则执行3;否则执行4(I为资源类别)3.进程P获得第i类资源,则顺利执行直至完成!并释放资源:Work=Work+Allocation;Finish[i]=true;转24.若所有进程的Finish[i]=true,则表示系统安全;否则,不安全!五．程序清单：编写代码如下：#includeiostream.h#includeiomanip.h#defineM5/*M个进程,N个资源*/#defineN3intAVAILABLE[N];/*可用资源数组*/intMAX[M][N];/*最大需求矩阵*/intALLOCATION[M][N];/*分配矩阵*/intNEED[M][N];/*需求矩阵*/intREQUEST[M][N];/*进程需要资源数*/boolFINISH[M];/*系统是否有足够的资源分配*/intp[M];/*记录序列*/voidInit();boolSafe();voidBanker();voidOutput();voidmain(){Init();Safe();Banker();}voidInit()/*初始化算法*/{inti,j;cout请输入每个进程最多所需的各资源数,按照MxN矩阵输入:endl;for(i=0;iM;i++)for(j=0;jN;j++)cinMAX[i][j];cout请输入每个进程已分配的各资源数,按照MxN矩阵输入:endl;for(i=0;iM;i++){for(j=0;jN;j++){cinALLOCATION[i][j];NEED[i][j]=MAX[i][j]-ALLOCATION[i][j];if(NEED[i][j]0){cout您输入的第i+1个进程所拥有的第j+1个资源数错误,请重新输入:endl;j--;continue;}}}cout请输入各个资源现有的数目:endl;for(i=0;iN;i++){cinAVAILABLE[i];}}voidBanker()/*银行家算法*/{inti,pneed;charflag;while(1){cout请输入要申请资源的进程号(注:第1个进程号为0,依次类推)endl;cinpneed;cout请输入进程所请求的各资源的数量endl;for(i=0;iN;i++){cinREQUEST[pneed][i];}for(i=0;iN;i++){if(REQUEST[pneed][i]NEED[pneed][i]){cout您输入的对i进程的请求数超过进程的需求量!请重新输入!endl;continue;}if(REQUEST[pneed][i]AVAILABLE[i]){cout您输入的对i进程的请求数超过系统有的资源数!请重新输入!endl;continue;}}for(i=0;iN;i++){AVAILABLE[i]-=REQUEST[pneed][i];ALLOCATION[pneed][i]+=REQUEST[pneed][i];NEED[pneed][i]-=REQUEST[pneed][i];}if(Safe()){cout同意分配请求!endl;}else{cout您的请求被拒绝!endl;for(i=0;iN;i++){AVAILABLE[i]+=REQUEST[pneed][i];ALLOCATION[pneed][i]-=REQUEST[pneed][i];NEED[pneed][i]+=REQUEST[pneed][i];}}for(i=0;iM;i++){FINISH[i]=false;}cout您还想再次请求分配吗?是请按y/Y,否请按其它键endl;cinflag;if(flag=='y'||flag=='Y'){continue;}break;}}voidOutput()/*输出*/{inti,j;cout资源分配表：endl进程名MaxAllocationNeedAvailableendl;for(i=0;iM;i++){coutPi:;for(j=0;jN;j++)coutsetw(2)MAX[i][j];cout;for(j=0;jN;j++)coutsetw(2)ALLOCATION[i][j];cout;for(j=0;jN;j++)coutsetw(2)NEED[i][j];cout;if(i==0)for(j=0;jN;j++)coutsetw(2)AVAILABLE[j];coutendl;}}boolSafe()/*安全性算法*/{inti,j,k,l=0;intWork[N];/*工作数组*/for(i=0;iN;i++)Work[i]=AVAILABLE[i];for(i=0;iM;i++){FINISH[i]=false;}cout安全性：endl进程名WorkNeedAllocationW+AFinishendl;for(i=0;iM;i++){if(FINISH[i]==true){continue;}else{for(j=0;jN;j++){if(NEED[i][j]Work[j]){break;}}if(j==N){FINISH[i]=true;coutPi:;for(intz=0;zN;z++)coutsetw(2)Work[z];cout;for(z=0;zN;z++)coutsetw(2)NEED[i][z];cout;for(z=0;zN;z++)coutsetw(2)ALLOCATION[i][z];cout;for(k=0;kN;k++){Work[k]+=ALLOCATION[i][k];}for(z=0;zN;z++)coutsetw(2)Work[z];couttrueendl;p[l++]=i;i=-1;}else{continue;}}if(l==M){cout系统是安全的!endl;cout安全序列:endl;for(i=0;il;i++){coutp[i];if(i!=l-1){cout-;}}coutendl;Output();returntrue;}}cout系统是不安全的!endl;Output();returnfalse;}六.实验结果分析：七．总结通过本次试验熟练地掌握了利用高级语言C语言编写和调试一个动态分配资源的简单程序，实现了避免死锁的银行家算法。通过编程实现银行家算法来预防死锁，清楚地了解了安全性算法的相关内容，加深了对课堂上所讲内容的理解。银行家算法确实能保证系统时时刻刻都处于安全状态，但它要不断检测每个进程对各类资源的占用和申请情况，需花费较多的时间。