您好,欢迎访问三七文档
一、课程设计目的和意义本设计的目的是通过编写和调试一个系统动态分配资源的简单模拟程序,观察死锁产生的条件,并采用适当的算法,有效地防止和避免死锁地发生。集体要求如下:(1)模拟一个银行家算法;(2)初始化时让系统拥有一定的资源;(3)用键盘输入的方式申请资源;(4)如果预分配后,系统处于安全状态,则修改系统的资源分配情况;(5)如果预分配后,系统处于不安全状态,则提示不能满足请求,此次课程设计的主要内容时模拟实现动态资源分配。同时要求编写和调试一个系统动态资源的简单模拟程序,观察死锁产生的条件,并使用适当的算法,有效的防止和避免死锁的发生。银行家算法是避免死锁的一种重要方法,通过编写一个简单的银行家算法程序,加深了解有关资源申请、避免死锁等概念,并体会和了解死锁和避免死锁的具体实施方法。死锁的产生,必须同时满足四个条件,即一个资源每次只能由一个进程张勇;第二个为等待条件,即一个进程请求资源不能满足时,它必须等待,单它仍继续宝石已得到的所有其他资源;第三个为非剥夺条件,即在出现死锁的系统中一定有不可剥夺使用的资源;第四个为循环等待条件,系统中存在若干个循环等待的进程,即其中每一个进程分别等待它前一个进程所持有的资源。防止死锁的机构只能确保上述四个条件之一不出现,则系统就不会发生死锁。通过这个算法可以用来解决生活中的实际问题,如银行贷款等。二、方案设计及开发过程(一)银行家算法,顾名思义是来源于银行的借贷业务,一定数量的本金要应多个客户的借贷周转,为了防止银行加资金无法周转而倒闭,对每一笔贷款,必须考察其是否能限期归还。在操作系统中研究资源分配策略时也有类似问题,系统中有限的资源要供多个进程使用,必须保证得到的资源的进程能在有限的时间内归还资源,以供其他进程使用资源。如果资源分配不得到就会发生进程循环等待资源,则进程都无法继续执行下去的死锁现象。把一个进程需要和已占有资源的情况记录在进程控制中,假定进程控制块PCB其中“状态”有就绪态、等待态和完成态。当进程在处于等待态时,表示系统不能满足该进程当前的资源申请。“资源需求总量”表示进程在整个执行过程中总共要申请的资源量。显然,,每个进程的资源需求总量不能超过系统拥有的资源总数,银行算法进行资源分配可以避免死锁.(二).算法描述1.银行家算法:设进程i提出请求Request[n],则银行家算法按如下规则进行判断。(1)如果Request[n]Need[i,n],则报错返回。(2)如果Request[n]Available,则进程i进入等待资源状态,返回。(3)假设进程i的申请已获批准,于是修改系统状态:Available=Available-RequestAllocation=Allocation+RequestNeed=Need-Request(4)系统执行安全性检查,如安全,则分配成立;否则试探险性分配作废,系统恢复原状,进程等待。2.安全性检查(1)设置两个工作向量Work=Available;Finish[M]=False(2)从进程集合中找到一个满足下述条件的进程,Finish[i]=FalseNeed=Work如找到,执行(3);否则,执行(4)(3)设进程获得资源,可顺利执行,直至完成,从而释放资源。Work=Work+AllocationFinish=TrueGOTO2(4)如所有的进程Finish[M]=true,则表示安全;否则系统不安全。3.数据结构假设有M个进程N类资源,则有如下数据结构:#defineW10#defineR20intM;//总进程数intN;//资源种类intALL_RESOURCE[W];//各种资源的数目总和intMAX[W][R];//M个进程对N类资源最大资源需求量intAVAILABLE[R];//系统可用资源数intALLOCATION[W][R];//M个进程已经得到N类资源的资源量intNEED[W][R];//M个进程还需要N类资源的资源量intRequest[R];//请求资源个数4.主要函数说明voidshowdata();//主要用来输出资源分配情况voidchangdata(int);//主要用来输出资源分配后后的情况voidrstordata(int);//用来恢复资源分配情况,如:银行家算法时,由于分配不安全则要恢复资源分配情况intchkerr(int);//银行家分配算法的安全检查voidbank();//银行家算法5源程序#includestring.h#includeiostreamusingnamespacestd;#defineFALSE0#defineTRUE1#defineW10#defineR20intM;//总进程数intN;//资源种类intALL_RESOURCE[W];//各种资源的数目总和intMAX[W][R];//M个进程对N类资源最大资源需求量intAVAILABLE[R];//系统可用资源数intALLOCATION[W][R];//M个进程已经得到N类资源的资源量intNEED[W][R];//M个进程还需要N类资源的资源量intRequest[R];//请求资源个数voidshowdata()//函数showdata,输出资源分配情况{inti,j;cout各种资源的总数量(all):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;cout资源0资源1资源2endl;for(i=0;iM;i++)for(i=0;iM;i++){cout进程pi:;for(j=0;jN;j++)coutNEED[i][j];;coutendl;}coutendl;cout各进程已经得到的资源量(allocation):endlendl;cout资源0资源1资源2endl;for(i=0;iM;i++){cout进程pi:;for(j=0;jN;j++)coutALLOCATION[i][j];coutendl;}coutendl;}voidchangdata(intk)//函数changdata,改变可用资源和已经拿到资源和还需要的资源的值{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];}}voidrstordata(intk)//函数rstordata,恢复可用资源和已经拿到资源和还需要的资源的值{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];}}intchkerr(ints)//函数chkerr,检查是否安全{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){coutendl;cout系统不安全!!!本次资源申请不成功!!!endl;coutendl;return1;}}coutendl;cout经安全性检查,系统安全,本次分配成功。endl;coutendl;return0;}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])//若请求的资源数大于进程还需要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);//调用changdata(i)函数,改变资源数if(chkerr(i))//若系统安全{rstordata(i);//调用rstordata(i)函数,恢复资源数showdata();//输出资源分配情况}else//若系统不安全showdata();//输出资源分配情况}else//若flag=N||flag=nshowdata();coutendl;cout是否继续银行家算法演示,按'Y'或'y'键继续,按'N'或'n'键退出演示:;cinflag;}}voidmain()//主函数{inti=0,j=0,p;cout请输入总进程数:endl;cinM;cout请输入总资源种类:endl;cinN;cout请输入总资源数(all_resource):endl;for(i=0;iN;i++)cinALL_RESOURCE[i];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]);}}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]);}}//初始化资源数量for(j=0;jN;j++){p=ALL_RESOURCE[j];for(i=0;iM;i++){p=p-ALLOCA
本文标题:银行家算法详解
链接地址:https://www.777doc.com/doc-2262496 .html