操作系统银行家算法

第1页共13页实验报告课程名称：操作系统实验名称：银行家算法实现学号：学生姓名：班级：指导教师：评分：实验日期：2013年5月31日第2页共13页1、实验目的：银行家算法是避免死锁的一种重要方法，本实验要求用高级语言编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。2、实验要求根据银行家算法的基本思想，编写和调试一个实现动态资源分配的模拟程序，并能够有效地防止和避免死锁的发生。3、实验环境Windows2007操作系统VC++6.0软件第3页共13页4、实验内容1）实现原理总资源=每个进程的已分配资源+剩余可用资源。进程需要的资源=完成此进程最大需求资源-已分配资源。当用户申请一组资源时，系统必须做出判断，如果把这些资源分出去，系统是否处于安全状态。如果剩余可用资源=进程需要的资源,就可以分出这些资源，此进程就可以运行完，否则，该申请不予满足。2）程序结构一个主函数，调用多个其他函数。程序流程图如下：进入系统进行初始化打印输出此时刻资源分配情况提出申请资源请求Request[R]Need[R]Request[R]Available[R]预分配输入y继续分配，输入n则退出。系统是否安全实际分配并打印输出退出系统YNNYNYyn图1银行家算法主要流程图3）数据结构（1）可利用资源向量AVAILABLE[R]。第4页共13页（2）最大需求矩阵MAX[W][R]。（3）分配矩阵ALLOCATION[W][R]。（4）需求矩阵NEED[W][R]。（5）进程请求向量Request[R]。假设有W个进程R类资源，则有如下数据结构：MAX[W*R]W个进程对R类资源的最大需求量AVAILABLE[R]系统可用资源数ALLOCATION[W*R]W个进程已经得到R类资源的资源量NEED[W*R]W个进程还需要R类资源的资源量。4）实现步骤(1)设进程I提出请求Request[R]，则银行家算法按如下规则进行判断。(1)如果Request[R]=NEED[I，R]，则转(2)；否则，出错。(2)如果Request[R]=AVAILABLE[R]，则转(3)；否则，出错。(3)系统试探分配资源，修改相关数据：AVAILABLE=AVAILABLE-REQUEST;ALLOCATION=ALLOCATION+REQUEST;NEED=NEED-REQUEST.(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。(5)安全性检查①设置两个工作向量WORK=AVAILABLE；FINISH[M]=FALSE。②从进程集合中找到一个满足下述条件的进程，FINISH[i]=FALSENEED=WORK如找到，执行③；否则，执行④。③设进程获得资源，可顺利执行，直至完成，从而释放资源。WORK=WORK+ALLOCATIONFINISH=TRUEGOTO2。④如所有的进程Finish[W]=true，则表示安全；否则系统不安全。第5页共13页5、实验测试及分析：得到的结果：图2数据输入第6页共13页图3数据计算分析：假定进程数量是5个，资源为3类，各类资源数量分别为10、5、7。分别输入每个进程的最大需求max和已分配资源allocation。第7页共13页输入数据如图2所示。进程可分配资源为3、3、2。P1的最大需求是3、2、2，已分配2、0、0，还需要1、2、2。给进程P1分配所需资源1、2、2。此时进程可分配资源available剩余为2、1、0。进程P1成功完成，然后释放全部资源3、2、2。此时进程可分配资源为：5、3、2。其他进程的最大需求和需要分配资源量不变，P1进程结束，P1内所有资源释放。6、实验心得体会银行家算法，多个进程同时运行，系统根据各个进程的资源需求数和各个进程已分配的数得到各个进程还需要的资源数。当一个进程可以进行资源分配时，还要检测剩余资源是否可以满足全部的进程，及安全检测。当安全检测通过时，资源可以分配。通过这次编程我加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。但很多地方还有很多问题没有学会，还要继续努力将其深入掌握。第8页共13页附录：源代码//#includestdafx.h#includestring.h#includeiostream#defineFALSE0#defineTRUE1#defineW10//最大进程数W=10#defineR20//最大资源总数R=20usingnamespacestd;intM;intN;intALL_RESOURCE[W];intAVAILABLE[R];//可利用资源向量intMAX[W][R];//最大需求矩阵intALLOCATION[W][R];//分配矩阵intNEED[W][R];//需求矩阵intRequest[R];//进程请求向量voidinputdata();//数据输入voidshowdata();//数据显示voidchangdata(intk);//进程请求资源数据改变voidrestoredata(intk);//数据恢复intchksec(ints);//系统安全性的检测intchkmax(ints);//检测最大需求voidbank();//检测分配的资源是否合理voidmain(){inti,j;inputdata();for(i=0;iM;i++){j=chksec(i);if(j==0)break;}if(i=M)cout错误提示：经安全性检查发现，系统的初始状态不安全！！！\nendl;else{cout提示：经安全性检查发现，系统的初始状态安全！endl;bank();}}voidinputdata(){inti=0,j=0,p;cout请输入总进程数:endl;第9页共13页do{cinM;if(MW)coutendl总进程数超过了程序允许的最大进程数，请重新输入:endl;}while(MW);coutendl;cout请输入资源的种类数:endl;do{cinN;if(NR)coutendl资源的种类数超过了程序允许的最大资源种类数，请重新输入:endl;}while(NR);coutendl;cout请依次输入各类资源的总数量，即设置向量all_resource:endl;for(i=0;iN;i++)cinALL_RESOURCE[i];coutendl;cout请依次输入各进程所需要的最大资源数量，即设置矩阵max:endl;for(i=0;iM;i++){for(j=0;jN;j++){do{cinMAX[i][j];if(MAX[i][j]ALL_RESOURCE[j])coutendl该最大资源数量超过了声明的该资源总数,请重新输入:endl;}while(MAX[i][j]ALL_RESOURCE[j]);}}coutendl;cout请依次输入各进程已经占据的各类资源数量，即设置矩阵allocation:endl;for(i=0;iM;i++){for(j=0;jN;j++){do{cinALLOCATION[i][j];if(ALLOCATION[i][j]MAX[i][j])coutendl已占有的资源数量超过了声明的最大资源数量,请重新输入:endl;}while(ALLOCATION[i][j]MAX[i][j]);}}coutendl;for(i=0;iM;i++)for(j=0;jN;j++)NEED[i][j]=MAX[i][j]-ALLOCATION[i][j];for(j=0;jN;j++)第10页共13页{p=ALL_RESOURCE[j];for(i=0;iM;i++){p=p-ALLOCATION[i][j];AVAILABLE[j]=p;if(AVAILABLE[j]0)AVAILABLE[j]=0;}}}voidshowdata(){inti,j;cout各种资源的总数量，即向量all_resource为:endl;cout;for(j=0;jN;j++)cout资源j:ALL_RESOURCE[j];coutendlendl;cout当前系统中各类资源的可用数量，即向量available为:endl;cout;for(j=0;jN;j++)cout资源j:AVAILABLE[j];coutendlendl;cout各进程还需要的资源数量，即矩阵need为:endlendl;for(i=0;iM;i++){cout进程Pi:;for(j=0;jN;j++)coutNEED[i][j];coutendl;}coutendl;cout各进程已经得到的资源量，即矩阵allocation为:endlendl;for(i=0;iM;i++){cout进程Pi:;for(j=0;jN;j++)coutALLOCATION[i][j];coutendl;}coutendl;}voidchangdata(intk){intj;for(j=0;jN;j++)第11页共13页{AVAILABLE[j]=AVAILABLE[j]-Request[j];ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j];NEED[k][j]=NEED[k][j]-Request[j];}}voidrestoredata(intk){intj;for(j=0;jN;j++){AVAILABLE[j]=AVAILABLE[j]+Request[j];ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j];NEED[k][j]=NEED[k][j]+Request[j];}}intchksec(ints){intWORK,FINISH[W];inti,j,k=0;for(i=0;iM;i++)FINISH[i]=FALSE;for(j=0;jN;j++){WORK=AVAILABLE[j];i=s;do{if(FINISH[i]==FALSE&&NEED[i][j]=WORK){WORK=WORK+ALLOCATION[i][j];FINISH[i]=TRUE;i=0;}else{i++;}}while(iM);for(i=0;iM;i++)if(FINISH[i]==FALSE){return1;}}return0;}intchkmax(ints){intj,flag=0;第12页共13页for(j=0;jN;j++){if(MAX[s][j]==ALLOCATION[s][j]){flag=1;AVAILABLE[j]=AVAILABLE[j]+MAX[s][j];MAX[s][j]=0;}}returnflag;}voidbank(){inti=0,j=0;charflag='Y';while(flag=='Y'||flag=='y'){i=-1;while(i0||i=M){cout请输入需申请资源的进程号（从P0到PM-1，否则重新输入!）:;coutp;cini;if(i0||i=M)cout输入的进程号不存在，重新输入!endl;}cout请输入进程Pi申请的资源数:endl;for(j=0;jN;j++){cout资源j:;cinRequest[j];if(Request[j]NEED[i][j]){cout进程Pi申请的资源数大于进程