操作系统 模拟银行家算法

《操作系统》课程设计报告课程名称：____操作系统_______________姓名：___________________学号：_________________同组人员姓名：______________________________________________2012年___2__月__1__日设计题目：用C/C++设计一个模拟银行家算法的程序同组同学姓名：___________________________________________________子任务描述：1.安全性算法2.利用银行家算法对申请资源对进行判定，分配资源3.添加资源、修改删除资源、分配资源。任务分析及算法设计编程实现一个资源管理系统，该系统必须包括资源的添加、删除和修改等功能，并且允许其它进程来申请这里的资源，任何一个进程来申请资源时，必须先登记该进程对资源的申请要求，然后由系统检查当前资源的状况，并用银行家算法和安全性算法来检查是否允许分配资源给进程。每个进程申请资源的情况必须进行记录并输出，并记录的数据。流程图：主函数main（）开始输入资源种类的数量N输入资源名称和数量s和number输入最大需求矩阵主函数main（）结束输入已申请矩阵申请分配的资源大于最大需求量ture安全性safe（）开始work[a]=available[a]finish[i]=false安全，输出序列系统不安全安全性safe（）结束Work[m]=Work[m]+Allocation[i][m]Finish[i]=TruetureFinish[i]==False&&Need[i][j]=Work[j]所有的进程Finish[i]==trueturefalsefalse分配share（）开始提出请求Request分配share（）结束执行Change（）tureRequest[j]Need[i][j]falseErrorRequest[j]Avaliable[j]falseErrortureAvaliable[j]=Avaliable[j]-Request[j]Allocation[i][j]=Allocation[i][j]+Request[j]Need[i][j]=Need[i][j]-Request[j]safefalse分配出错Avaliable[j]=Avaliable[j]+Request[j]Allocation[i][j]=Allocation[i][j]-Request[j]Need[i][j]=Need[i][j]+Request[j]执行分配算法及主要数据结构描述一、数据结构1．可利用资源向量Availablem个元素的数组，用于可利用的资源数目，初始值是全部可用资源数目。数值随分配资源而改变。如果Available[j]=K，则表示有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个，方能完成其任务。上述三个矩阵间存在下述关系：Need[i，j]=Max[i，j]-Allocation[i，j]二、银行家算法设Requesti是进程Pi的请求向量。如果Requesti[j]＝k，表示进程只需要k个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：1.如果Requesti[j]=Need[i，j]，则转向步骤2，否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。2.如果Requesti[j]=Available[j]，则转向步骤3，否则，表示系统中尚无足够的资源，Pi必须等待。3.系统试探把要求的资源分配给进程Pi，并修改下面数据结构中的数值：Available[j]:=Available[j]-Requesti[j]，Allocation[i，j]:=Allocation[i，j]+Requesti[j]，Need[i，j]:=Need[i，j]-Requesti[j]，4.系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配，否则，将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。三、安全性算法系统所执行的安全性算法可描述如下：1.设置两个向量工作向量Work。它表示系统可提供给进程继续运行所需要的各类资源数目，它含有m个元素，执行安全算法开始时，Work=Available。Finish。它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finish[i]=false，当有足够资源分配给进程时，Finish[i]=true。2.从进程集合中找到一个能满足下述条件的进程：（1）Finish[i]=false。（2）Need[i，j]=Work[j]，如找到，执行步骤（3），否则，执行步骤（4）。（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Work[j]:=Work[i]+Allocation[i，j]，Finish[i]:=true，（4）如果所有进程的Finish[i]:=true，则表示系统处于安全状态，否则，系统处于不安全状态。重要程序片段#includeiostream.h#includestring//#includestdio//usingnamespacestd;intMax[100][100]={0};//各进程所需各类资源的最大需求，定义二维矩阵，由作业名和资源组成。intAvaliable[100]={0};//系统可用资源，显示系统可用资源矩阵时，Avaliable和作业名组成。intAllocation[100][100]={0};//系统已分配资源，显示已分配资源矩阵，Allocation和作业名组成。charname[100]={0};//资源的名称（作业）intNeed[100][100]={0};//还需要资源的二维矩阵，由进程和资源组成.intRequest[100]={0};//请求资源向量inttemp[100]={0};//存放安全序列intWork[100]={0};//存放系统可提供资源intM=100;//进程的最大数为100intN=100;//资源的最大数为100#defineFalse0#defineTrue1voidshow()//显示资源矩阵{inti,j;cout系统目前可用的资源:endl;for(i=0;iN;i++)coutname[i];//输出每个作业的名字coutendl;for(j=0;jN;j++)coutAvaliable[j];//输出分配资源对应着每个作业coutendl;//////////////////////////////////////////////////coutMax[矩阵]Allocation[矩阵]Need[矩阵]endl;cout进程名;for(j=0;j3;j++){for(i=0;iN;i++)coutname[i];//输出不同的三个矩阵对应的所有资源名称cout;}coutendl;for(i=0;iM;i++){couti;//if(Avaliable[j]=Max[i][j])//{for(j=0;jN;j++)coutMax[i][j];cout;for(j=0;jN;j++)coutAllocation[i][j];//输出不同进程对应的对不同资源数量的请求，用矩阵表示cout;for(j=0;jN;j++)coutNeed[i][j];coutendl;}}//////////////////////////////////////////////////////////////////////////////////////////intsafe()//安全性算法{inti,k=0,m,resource,Finish[100]={0};intj;intflag=0;//标志置0for(inta=0;aN;a++){Work[a]=Avaliable[a];}/////////////for(i=0;iM;i++){//循环输出每个进程resource=0;//起始资源设为0for(j=0;jN;j++){//每个资源种类if(Finish[i]==False&&Need[i][j]=Work[j]){//如果某进程某资源还未完成并且，还需要的资源小于存于系统的资源，那么进行分配resource++;if(resource==N){for(m=0;mN;m++)Work[m]=Work[m]+Allocation[i][m];//改变每个进程分配所有资源的数量Finish[i]=True;temp[k]=i;//存储记录安全序列的顺序i=-1;k++;//对标记每个资源flag++;//标志置1}}}}for(i=0;iM;i++){if(Finish[i]==False){cout系统不安全endl;//不成功系统不安全return-1;}}cout系统是安全的!endl;//如果安全，输出成功cout分配的序列:;for(i=0;iM;i++){//输出运行进程数组,按安全序列顺序输出couttemp[i];if(iM-1)cout--;}coutendl;return0;}//////////////////////////////////////////////////intchange(inti)//进行资源分配,初始化i{intj;for(j=0;jM;j++){Avaliable[j]=Avaliable[j]-Request[j];//现在可用的资源=原来可用的-申请要用的Allocation[i][j]=Allocation[i][j]+Request[j];//现在分配的资源=原来分配的资源+申请要用的Need[i][j]=Need[i][j]-Request[j];//现在还需要的资源=原来需要的资源-已经申请要用的}return1;}voidshare()//利用银行家算法对申请资源对进行判定，分配资源{charchoose;//inti=0,j=0;choose=1;cout请输入要求分配的资源进程号(0-M-1):;cini;//输入需申请的资源号cout请输入进程i申请的资源:endl;for(j=0;jN;j++){coutname[j]:;cinRequest[j];//输入需要申请的资源}for(j=0;jN;j++){if(Request[j]Need[i][j])//判断申请是否大于需求，若大于则出错{cout进程i申请的资源大于它需要的资源;cout分配不合理，不予分配！endl;choose=0;break;}else{if(Request[j]Avaliable[j])//判断申请是否大于当前资源，若大于则出错{cout进程i申请的资源大于系统现在可利用的资源;cout分配出错，不予分配!endl;choose=0;break;}}}if(choose==1){change(i);//根据进程需求量变换资源show();//根据进程需求量显示变换后的资源safe();//根据