操作系统课程设计模拟银行家算法避免死锁

模拟通过银行家算法避免死锁银行家算法产生的背景及目的1：在多道程序系统中，虽然借助于多个进程的并发执行来改善系统的运用率，提高系统的吞吐量，但也许发生一种危险—死锁。死锁就是多个进程在运营过程中因争夺资源而导致的一种僵局，当进程处在这种僵局状态时，如无外力作用，他们将无法再向前进行，如再把信号量作为同步工具时，多个Wait和Signal操作顺序不妥，会产生进程死锁。然而产生死锁的必要条件有互斥条件，请求和保持条件，不剥夺条件和环路等待条件。在防止死锁的几种方法中，都施加了较强的限制条件，在避免死锁的方法中，所施加的条件较弱，有也许获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统都处在安全状态，便可避免死锁。2：实验目的：让学生独立的使用编程语言编写和调试一个系统分派资源的简朴模拟程序，了解死锁产生的因素及条件。采用银行家算法及时避免死锁的产生，进一步理解课堂上老师讲的相关知识点。银行家算法是从当前状态出发，逐个按安全序列检查各客户中谁能完毕其工作，然后假定其完毕工作且归还所有贷款，再进而检查下一个能完毕工作的客户。假如所有客户都能完毕工作，则找到一个安全序列，银行家才是安全的。二：银行家算法中的数据结构1：可运用资源向量Available。这是一个具有m个元素的数组，其中的每个元素代表一类可运用的资源数目，其初始值是系统中所配置的该类所有可用资源的数目，其数值随该类资源的分派和回收而动态的改变。假如Available[j]=k，z则表达系统中现有Rj类资源K个。2：最大需求矩阵Max。这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。假如Max[i,j]=k，表达第i个进程需要第Rj类资源的最大数目k个.3:分派矩阵Allocation,也是n*m的矩阵，若Allocation[i,j]=k,表达第i个进程已分派Rj类资源的数目为k个。4：需求矩阵Need。也是一个n*m的矩阵，Need[i,j]=k,表达第i个进程还需Rj类资源k个。三、银行家算法及安全性算法1：银行家算法设Request[i]是进程Pi的请求向量，若Request[i][j]=k;表达进程需要j类资源k个。当Pi发出资源请求时，系统按下属环节进行检查；假如Request[i][j]<=Need[i][j];便转向环节（2），否则认为犯错，由于它所需要的资源数已超过他所宣布的最大值。假如Request[i][j]<=Available[i][j],便转向环节（3），否则认为尚无足够资源，进程需等待。系统试探着把资源分派给进程，并修改下面数据结构的数据Available[i][j]=Available[i][j]-Request[i][j];Allocation[i][j]=Allocation[i][j]+Request[i][j];Need[i][j]=Need[i][j]-Request[i][j];系统执行安全性算法，检查本次资源分派后系统是否处在安全状态。若安全，才正式将资源分派给进程Pi，已完毕本次分派。否则，将本次的试探分派作废，回复本来的资源分派状态，将进程Pi等待。2：安全性算法设立两个向量；1：工作向量Work，表达系统可提供应进程运营所需的各类资源数目，它具有m个元素，初始时Work=Available2：Finish,表达系统是否有足够的资源分派给进程，使之运营完毕。开始时先做Finish[i]=true从进程中找到一个能满需下属条件的进程1；Finish[i]=false；2：Need[i][j]<=Work[j];若找到执行环节（3），否则执行环节（4）当进程Pi顺利获得资源后，直至完毕，并释放分派给它的资源，执行：Work[j]=Work[j]+Allocation[i][j];Finish[i]=true;Gotostep(2);假如所有的进程Finish[i]都满足，则表达系统处在安全状态，否则，处在不安全状态。四、模块设计与分析及整体功能概述模块设计与分析：整个银行家算法分为初始化函数Init（），安全性算法函数safe（），银行家算法函数bank（）三部分。初始化函数生成开始时刻系统中的进程和资源情况，安全性算法判断当某进程申请资源时，系统能否处在安全状态。在本实验中，若系统处在安全状态，便生成一个安全进程序列（安全序列也许有多个）。银行家算法函数bank（）负责整体的检查与异常判断。整体功能概述：死锁会引起系统陷入僵局，操作系统必须防止此现象的发生。本实验通过一个动态分派资源的模拟程序，更清楚的理解死锁产生的因素和条件。Dijkstra的银行家算法是最有代表性的避免死锁的方法。运营程序时用户设定系统中进程和可运用资源的种类数目。输入各进程的可运用资源Available，最大需求MAX，已分派资源Allocation，需求资源Need，之后各系统发出资源请求Request，运用实验中的安全性算法判断能否产生一个安全性队列，若能，则给该进程分派成功，否则，不予分派。五、流程图设计六、源代码及调试分析#include<iostream.h>#defineMAXm50//定义最大进程数#defineMAXn100//定义最大资源数intMAX[MAXm][MAXn];//最大需求矩阵intAllocation[MAXm][MAXn];//已分派矩阵intAvailable[MAXn];//可用资源数组intNeed[MAXm][MAXn];//需求矩阵intRequest[MAXm][MAXn];//请求矩阵intFinish[MAXm];//存储完毕资源分派的进程intSequence[MAXm];//模拟的资源分派序列intWork[MAXn];//系统是否有足够的资源分派给进程intm,n;//m个进程,n个资源#defineFalse0#defineTrue1voidinput();//数据输入函数intsafealg();//安全性算法函数voidbanker();//银行家算法函数voidmain(){input();safealg();banker();}//*************初始化算法***************voidinput(){ inti,j;//************自定义进程数目与资源种类******************* cout<<"***********************************\n"; cout<<"*运用银行家算法避免死锁*\n"; cout<<"**\n"; cout<<"************************************\n"; cout<<"请输入进程的数目:"; cin>>m; cout<<"请输入资源的种类:"; cin>>n; //*****输入每个进程对每种资源的最大需求、已经获得的数量、每种类型资源的数目 cout<<"各进程资源最大需求(Max),按照"<<m<<"x"<<n<<"矩阵输入:\n"; for(i=0;i<m;i++) { cout<<"P"<<i<<":"; for(j=0;j<n;j++){ cin>>MAX[i][j]; if(j==n) cout<<"资源种类数匹配出现错误！";//当资源配置的种类数大于预先输入的数值时，犯错 } } cout<<"各进程当前获得资源(Allocation),按照"<<m<<"x"<<n<<"矩阵输入"<<endl; for(i=0;i<m;i++) { cout<<"P"<<i<<":"; for(j=0;j<n;j++) { cin>>Allocation[i][j]; if(j==n) cout<<"资源种类数匹配出现错误！";//当资源配置的种类数大于预先输入的数值时，犯错 Need[i][j]=MAX[i][j]-Allocation[i][j];//需求数等于最大需求减去已经分派数 } } cout<<"系统可用资源(Available):"<<endl; for(j=0;j<n;j++) { cin>>Available[j];//输入各种资源的可运用数 } cout<<"当前时刻的进程分派情况如图：\n"; cout<<"进程号-"<<"MAX----"<<"Allocation---"<<"Need--"<<"Available---\n";//显示各进程的资源情况for(i=0;i<m;i++) { cout<<"P"<<i<<":"; for(j=0;j<n;j++) cout<<""<<MAX[i][j];for(j=0;j<n;j++) cout<<""<<Allocation[i][j]; cout<<""; for(j=0;j<n;j++) cout<<""<<Need[i][j]; for(j=0;j<n;j++) cout<<""<<Available[j]; cout<<endl;//回车换行 }}//*****************银行家算法，为进程分派资源***********//voidbanker(){ inti,j; intchoice;while(1){cout<<endl;cout<<"输入要进行的操作(1:分派资源2:离开):";//用户选择cin>>choice;if(choice==1)//分派资源{ cout<<"从P0到P"<<m-1<<"之间选择要分派资源的进程号:\n"; cin>>i; if(i>=m) { cout<<"无此进程号!请重新输入:\n"; cin>>i;//重新输入进程号 } cout<<"请输入进程申请的资源(Request):"<<endl; for(j=0;j<n;j++) cin>>Request[i][j]; //**********银行家算法进行检查*************// for(j=0;j<n;j++) { if(Request[i][j]>Need[i][j]) { cout<<"申请的资源大于它需要的资源数,请重新输入!\n";//资源申请不合理 continue; } if(Request[i][j]>Available[j]) { //资源申请数目大于可运用数，无法分派，得等待 cout<<"当前系统可用资源不够，请等待!"<<endl; continue; } } for(j=0;j<n;j++)//资源申请得到允许时，变换各个资源数 { Available[j]=Available[j]-Request[i][j];//可用资源减少 Allocation[i][j]=Allocation[i][j]+Request[i][j];//所得资源增长 Need[i][j]=Need[i][j]-Request[i][j];//仍需资源减少 } if(safealg()<0)//安全性算法的返回值 { cout<<"分派不成功，请等待！"; for(j=0;j<n;j++)//把资源恢复成分派之前的状态 { Available[j]=Available[j]+Request[i][j]; Allocation[i][j]=Allocation[i][j]-Request[i][j]; Need[i][j]=Need[i][j]+Request[i][j]; } for(i=0;i<m;i++) { Finish[i]=False;//没有足够的资源分派给该进程 } }//if(safealg()<0) else { cout<<"批准分派请求!"<<endl; for(j=0;j<n;j++) Work[j]=Available[j];cout<<"进程号-"<<"--Work----"<<"Need---"<<"Allocation---"<<"Work+Allocation--" <<"Finish--"<<endl;for(i=0;i<m;i++)//按模拟分派序列进行分派 { cout<<"进程P"<<Sequence[i]<<":"; for(j=0;j<n;j++) cout<<Work[j]<<""; cout<<""; for(j=0;j<n;j++) cout<<Need[Sequence[i]][j]<<""; cout<<""; for(j=0;j<n;j++) cout<<Allocation[Sequence[i]][j]<<""; cout<<""; for(j=0;j<n;j++) cout<<Allocation[Sequence[i]][j]+Work[j]<<""; cout<<"";cout<<Finish[Sequence[i]]<<"";//完毕该进程 for(j=0;j<n;j++) Work[j]=Allocation[Sequence[i]][j]+Work[j];//回收该进程所分派的资源 cout<<endl; } }//if(safealg()>=0) }//if(choice=1) elseif(choice==2)//离开———— break; elsecout<<"请输入1或2!";//只认可1或2 }//while(1)}//*********安全性算法************//intsafealg(){ inti,j,k,l=0; //intWork[MAXn];//工作组 //记录序列 for(i=0;i<n;i++) Work[i]=Available[i];//工作分派初始化为系统可用资源 for(i=0;i<m;i++)//扫描所有进程，预设所有进程不能运营 { Finish[i]=False; } for(i=0;i<m;i++) {// if(Finish[i]==True) { continue; } else//对于未运营的进程，进行如下解决 {/// for(j=0;j<n;j++)//找到一个满足Finish[i]=false且Need[i][j]<=Work[j]的进程 { if(Need[i][j]>Work[j])//由于部分资源得不到满足，进程i无法运营 { break; } } if(j==n)//进程各类资源所有得到满足 { Finish[i]=True; for(k=0;k<n;k++)//进程i正常运营后，释放其占有的资源 { Work[k]+=Allocation[i][k];//工作分派加上可用资源 } Sequence[l++]=i;//模拟资源分派序列生成 i=-1;//重新扫描所有进程从i=0开始 } else {//某一资源得不到满足 continue;//试探下一个进程 } }// if(l==m)//都试探完毕 { cout<<"系统安