死锁-银行家算法实验报告

实验目的银行家算法是避免死锁的一种重要方法。通过编写一个模拟动态资源分配的银行家算法程序，进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念，并掌握避免死锁的具体实施方法二、实验要求根据银行家算法的基本思想，编写和调试一个实现动态资源分配的模拟程序，并能够有效地防止和避免死锁的发生。（1）设计思想说明设计银行家算法是为了避免死锁三、实验方法内容1.算法设计思路银行家算法又称“资源分配拒绝”法，其基本思想是，系统中的所有进程放入进程集合，在安全状态下系统受到进程的请求后试探性的把资源分配给他，现在系统将剩下的资源和进程集合中其他进程还需要的资源数做比较，找出剩余资源能满足最大需求量的进程，从而保证进程运行完成后还回全部资源。这时系统将该进程从进程集合中将其清除。此时系统中的资源就更多了。反复执行上面的步骤，最后检查进程的集合为空时就表明本次申请可行，系统处于安全状态，可以实施本次分配，否则，只要进程集合非空，系统便处于不安全状态，本次不能分配给他。请进程等待2.算法流程图3.算法中用到的数据结构数据结构的说明1.可利用资源向量AVAILABLE。这是一个含有M个元素的数组，其中的每一个元素代表一类可利用的资源数目，其3初始值是系统中所配置的该类全部可哦那个资源的数目，其数值随该类资源的分配和回收而动态的改变。2.最大需求矩阵MAX。这是一个M*N的矩阵，它定义了系统中N个进程中的每一个进程对M类资源的最大需求。3.分配矩阵ALLOCATION。这也是一个M*N的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。4.需求矩阵NEED。这也是一个M*N的矩阵，用以表示每一个进程尚需的各类资源数。5.NEED[R,W]=MAX[R,W]-ALLOCATION[R,W]4.主要的常量变量#defineW10//最大进程数W=10#defineR20//最大资源总数R=20intAVAILABLE[R];//可利用资源向量intMAX[W][R];//最大需求矩阵intALLOCATION[W][R];//分配矩阵intNEED[W][R];//需求矩阵intRequest[R];//进程请求向量voidchangdata(intk);//进程请求资源数据改变intchksec(ints);//系统安全性的检测5.主要模块voidinputdata()voidshowdata()voidchangdata(intk)voidrestoredata(intk)intchksec(ints)intchkmax(ints)四、实验代码#includestring.h#includeiostream.h#defineFALSE0#defineTRUE1#defineW10//最大进程数W=10#defineR20//最大资源总数R=20intM;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;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++){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++){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;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;}c{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申请的资源数大于进程Pi还需要j类资源的资源量!;cout申请不合理，出错!请重新选择!endlendl;flag='N';break;}else{if(Request[j]AVAILABLE[j]){cout进程Pi申请的资源数大于系统可用j类资源的资源量!;cout申请不合理，出错!请重新选择!endlendl;flag='N';break;}}}if(flag=='Y'||flag=='y'){changdata(i);if(chksec(i)){coutendl;cout该分配会导致系统不安全!!!本次资源申请不成功，不予分配!!!endl;coutendl;restoredata(i);}else{coutendl;cout经安全性检查，系统安全，本次分配成功，且资源分配状况如下所示：endl;coutendl;showdata();if(chkmax(i)){cout在资源分配成功之后，由于该进程所需的某些资源的最大需求量已经满足，endl;cout因此在进程结束后系统将回收这些资源！endl;cout在资源收回之后，各进程的资源需求和分配情况如下所示：endl;showdata();}}}coutendl;cout是否继续银行家算法演示,按'Y'或'y'键继续,按'N'或'n'键退出演示:;cinflag;}}五、实验结果1.执行结果2.结果分析银行家算法就是当接收到一个系统资源的分配后找到一个安全序列，使得进程间不会发生死锁，若发生死锁则让进程等待。六、实验总结通过本次银行家算法实验，加深了我对银行家算法的了解，掌握了如何利用银行家算法避免死锁。实验中遇到点问题，通过查阅资料、询问老师顺