操作系统课程设计银行家算法报告

第21页共21页操作系统课程设计银行家算法报告《操作系统--银行家算法》课程设计报告姓名：学号：班级：计科班专业：计算机科学与技术指导老师：时间：2022XX大学计算机科学与信息学院目录1课程设计目的……………………12课程设计的要求…………………13课程设计题目描绘………………24课程设计之银行家算法原理……25程序构造分析^p及代码实现……46课程设计总结……………………25一、课程设计的目的操作系统是计算机系统的核心系统软件，它负责控制和管理整个系统的资并组织用户协调使用这些资，使计算机高效的工作。《操作系统课程设计》是《操作系统》理论课的必要补充，是复习和检验所学课程的重要手段，本课程设计的目的是综合应用学生所学知识，通过实验环节，加深学生对操作系统根本原理和工作过程的理解，进步学生独立分析^p问题、解决问题的才能，增强学生的动手才能。二、课程设计的要求1．分析^p设计内容，给出解决方案〔要说明设计实现的原理，采用的数据构造〕。2．画出程序的根本构造框图和流程图。3．对程序的每一部分要有详细的设计分析^p说明。4．代码格式要标准。5．设计适宜的测试用例，对得到的运行结果要有分析^p。6．设计中遇到的问题，设计的心得体会。7．按期提交完好的程序代码、可执行程序和课程设计报告。三、课程设计题目描绘银行家算法是一种最有代表性的防止死锁的算法。要解释银行家算法，必须先解释操作系统平安状态和不平安状态。平安状态：假如存在一个由系统中所有进程构成的平安序列P1，…，Pn，那么系统处于平安状态。平安状态一定是没有死锁发生。不平安状态:不存在一个平安序列。不平安状态不一定导致死锁。那么什么是平安序列呢？平安序列：一个进程序列{P1，…，Pn}是平安的，假如对于每一个进程Pi(1≤i≤n〕，它以后尚需要的资量不超过系统当前剩余资量与所有进程Pj(j<i)当前占有资量之和。银行家算法：我们可以把操作系统看作是银行家，操作系统管理的资相当于银行家管理的资金，进程向操作系统恳求分配资相当于用户向银行家贷款。操作系统按照银行家制定的规那么为进程分配资，当进程首次申请资时，要测试该进程对资的最大需求量，假如系统现存的资可以满足它的最大需求量那么按当前的申请量分配资，否那么就推延分配。当进程在执行中继续申请资时，先测试该进程已占用的资数与本次申请的资数之和是否超过了该进程对资的最大需求量。假设超过那么回绝分配资，假设没有超过那么再测试系统现存的资能否满足该进程尚需的最大资量，假设能满足那么按当前的申请量分配资，否那么也要推延分配。四、课程设计之银行家算法原理1．银行家算法的思路先对用户提出的恳求进展合法性检查，即检查恳求的是不大于需要的，是否不大于可利用的。假设恳求合法，那么进展试分配。最后对试分配后的状态调用平安性检查算法进展平安性检查。假设平安，那么分配，否那么，不分配，恢复原来状态，回绝申请。2．银行家算法中用到的主要数据构造可利用资向量intAvailable[j]j为资的种类。最大需求矩阵intMax[i][j]i为进程的数量。分配矩阵intAllocation[i][j]需求矩阵intneed[i][j]=Max[i][j]-Allocation[i][j]申请各类资数量intRequesti[j]i进程申请j资的数量工作向量intWork[x]intFinish[y]3．银行家算法bank进程i发出恳求申请k个j资，Requesti[j]=k(1)检查申请量是否不大于需求量：Requesti[j]<=need[i,j],假设条件不符重新输入，不允许申请大于需求量。(2)检查申请量是否小于系统中的可利用资数量：Requesti[j]<=available[i,j]，假设条件不符就申请失败，阻塞该进程，用goto语句跳转到重新申请资。(3)假设以上两个条件都满足，那么系统试探着将资分配给申请的进程，并修改下面数据构造中的数值：Available[i,j]=Available[i,j]-Requesti[j]；Allocation[i][j]=Allocation[i][j]+Requesti[j]；need[i][j]=need[i][j]-Requesti[j]；(4)试分配后，执行平安性检查，调用safe函数检查此次资分配后系统是否处于平安状态。假设平安，才正式将资分配给进程；否那么本次试探分配作废，恢复原来的资分配状态，让该进程等待。(5)用do{…}while循环语句实现输入字符y/n判断是否继续进展资申请。4．平安性检查算法〔safe函数〕(1)设置两个向量：工作向量Work，它表示系统可提供应进程继续运行所需的各类资数目，在执行平安性算法开场时，Work=Available。Finish，它表示系统是否有足够的资分配给进程，使之运行完成。开场时先做Finish[i]=0；当有足够的资分配给进程时，再令Finish[i]=1。(2)在进程中查找符合以下条件的进程：条件1：Finish[i]=0；条件2：need[i][j]<=Work[j]假设找到，那么执行步骤(3)否那么，执行步骤(4)(3)当进程获得资后，可顺利执行，直至完成，并释放出分配给它的资，故应执行：Work[j]=Work[j]+Allocation[i][j]；Finish[i]=1；gotostep2；(4)假如所有的Finish[i]=1都满足，那么表示系统处于平安状态，否那么，处于不平安状态。五、程序构造分析^p及代码实现1．程序构造程序共有以下五个部分：(1).初始化chushihua：用于程序开场进展初始化输入数据：进程数量、资种类、各种资可利用数量、各进程的各种资已分配数量、各进程对各类资最大需求数等。(2).当前平安性检查safe：用于判断当前状态平安性，根据不同地方的调用提示处理不同。(3).银行家算法bank：进展银行家算法模拟实现的模块，调用其他各个模块进展银行家算法模拟过程。(4).显示当前状态show：显示当前资分配详细情况，包括：各种资的总数量(all)、系统目前各种资可用的数量、各进程已经得到的资数量、各进程还需要的资量。(5).主程序main逐个调用初始化、显示状态、平安性检查、银行家算法函数，使程序有序的进展。2．数据构造程序使用的全局变量：constintx=10，y=10；//定义常量intAvailable[x];//各种资可利用的数量intAllocation[y][y];//各进程当前已分配的资数量intMax[y][y];//各进程对各类资的最大需求数intNeed[y][y];//还需求矩阵intRequest[x];//申请各类资的数量intWork[x];//工作向量，表系统可提供应进程运行所需各类资数量intFinish[y];//表系统是否有足够的资分配给进程，0为否，1为是intp[y];//存储平安序列inti,j;//全局变量，主要用于循环语句中intn,m;//n为进程的数量,m为资种类数intl=0,counter=0;3．函数声明voidchushihua;//系统初始化函数voidsafe;//平安性算法函数voidbank;//银行家算法函数voidshow;//输出当前资分配情况4．主函数mainintmain{cout<<……//显示程序开场提示信息chushihua;//初始化函数调用cout<<endl<<endl;showdata;//输出初始化后的状态//===判断当前状态的平安性===safe;//平安性算法函数调用if(l<n){cout<<“＼n当前状态不平安，无法申请,程序退出!!!!!“<<endl;cout<<endl;system(“pause“);sign;//调用签名函数return0;//break;}else{inti;//部分变量l=0;cout<<“＼n平安的状态!!!“<<endl;cout<<“平安序列为:“;cout<<endl<<“进程“<<“(“<<p[0]<<“)“;//输出平安序列，考虑显示格式，先输出第一个for(i=1;i<n;i++){cout<<“==》》“<<“进程“<<“(“<<p[i]<<“)“;}for(i=0;i<n;i++)Finish[i]=0;//所有进程置为未分配状态cout<<endl<<endl;}bank;//银行家算法函数调用return0;}5.操作系统银行家算法流程图：初始化函数chushihua开场AVAILABLE[[i]-=REQUEST[i];ALLOCATION[i]+=REQUEST[i];NEED[i]-=REQUEST[i];输入进程的数量输入资种类数输入个资当前可用资数输入各进程当前已分配的资数输入各进程对各类资的最大需求输出提示：输入有误，请重新输入初始化函数chushihua完毕，银行家函数Bank提出恳求REQUEST[i]Error;REQUEST[i]<=NEED[i]REQUEST[i]<=AVAILABLE[[i]Error;Safe;输出提示：你的恳求被拒！AVAILABLE[i]-=REQUEST[i]；ALLOCATION[i]-=REQUEST[i];NEED[i]+=REQUEST[i]；输出提示：同意分配恳求是否进展再次分配退出程序，银行家算法Bank完毕;平安性算法Safe开场Work=AVAILABLE;FINISH=false；NEED[i]<=Work--FINISH[i]=false;Work+=ALLOCATION[i];FINISH[i]=ture;所有进程的FINISH=ture；输出提示：系统是不平安的平安，输出平安序列Returnture；平安算法safe完毕2.程序代码：#include<iostream.h》#include<stdio.h》#include<stdlib.h》#include<string.h》//定义全局变量constintx=10,y=10;//常量，便于修改intAvailable[x];//各资可利用的数量intAllocation[y][y];//各进程当前已分配的资数量intMax[y][y];//各进程对各类资的最大需求数intNeed[y][y];//尚需多少资intRequest[x];//申请多少资intWork[x];//工作向量，表示系统可提供应进程继续运行所需的各类资数量intFinish[y];//表示系统是否有足够的资分配给进程，1为是intp[y];//存储平安序列inti,j;//i表示进程，j表示资intn,m;//n为进程i的数量,m为资j种类数intl=0;//l用来记录有几个进程是Finish[i]=1的，当l=n是说明系统状态是平安的intcounter=0;//函数声明voidchushihua;//初始化函数voidsafe;//平安性算法voidshow;//函数show,输出当前状态voidbank;//银行家算法voidjieshu;//完毕函数voidchushihua{cout<<“输入进程的数量:“;//从此开场输入有关数据cin》》n;cout<<“输入资种类数:“;cin》》m;cout<<endl<<“输入各种资当前可用的数量(“<<m<<“种):“<<endl;for(j=0;j<m;j++){cout<<“输入资“<<j<<“可利用的数量Available[“<<j<<“]:“;cin》》Available[j];//输入数字的过程...Work[j]=Available[j];//初始化Work[j]，它的初始值就是当前可用的资数}cout<<endl<<“输入各进程当前已分配的资数量Allocation[“<<n<<“][“<<m<<“]:“<<endl;for(i=0;i<n;i++){for(j=0;j<m;j++){cout<<“输入进程“<<i<<“当前已分配的资“<<j<<“数量:“;cin》》Allocation[i][j];}cout<<endl;Finish[i]=0;//初始化Finish[i]}cout<<endl<<“输入各进程对各类资的最大需求Max[“<<n<<“][“<<m<<“]:“<<endl;for(i=0;i<n;i++){for(j=0;j<m;j++){cout<<“输入进程“<<i<<“对资“<<j<<“的最大需求数:“;cin》》Max[i][j];if(Max[i][j]》=Allocation[i][j])//假设最大需求大于已分配，那么计算需求量Need[i][j]=Max[i][j]-Allocation[i][j];elseNeed[i][j]=0;//Max小于已分配的时候，此类资已足够不需再申请}cout<<endl;}cout<<endl<<“初始化完成“<<endl;}//平安性算法函数voidsafe{l=0;for(i=0;i<n;i++){//i++if(Finish[i]==0){//逐个查找Finish[i]==0的进程条件一counter=0;//记数器for(j=0;j<m;j++){if(Work[j]》=Need[i][j])counter=counter+1;//可用大于需求，记数}if(counter==m)//i进程的每类资都符合Work[j]》=Need[i][j]条件二{p[l]=i;//存储平安序列Finish[i]=1;//i进程标志为可分配for(j=0;j<m;j++)Work[j]=Work[j]+Allocation[i][j];//释放资l=l+1;//记数,如今有L个进程是平安的，当L=N时说明满足平安序列i=-1;//从第一个进程开场继续寻找满足条件一二的进程}}}}//显示当前状态函数voidshow//函数show,输出当前资分配情况{inti,j;//部分变量intAll[y];//各种资的总数量intL1;//部分变量L1cout<<“当前的状态为：“<<endl;cout<<“各种资的总数量:“<<endl;for(j=0;j<m;j++){cout<<“资“<<j<<“:“;All[j]=Available[j];//总数量=可用的+已分配的for(i=0;i<n;i++)All[j]+=Allocation[i][j];cout<<All[j]<<““;}cout<<endl<<“当前各种资可用的量为(available):“<<endl;for(j=0;j<m;j++)cout<<“资“<<j<<“:“<<Available[j]<<““;cout<<endl<<“各进程已经得到的资量(allocation):“<<endl;for(i=0;i<=m;i++){for(j=i;j<m;j++)cout<<“资“<<j;cout<<endl;for(L1=0;L1<n;L1++){cout<<“进程“<<L1<<“:“;for(j=i;j<m;j++)cout<<Allocation[L1][j]<<““;cout<<endl;}}cout<<endl<<“各进程还需要的资量(need):“<<endl;for(i=0;i<=m;i++){for(j=i;j<m;j++)cout<<“资“<<j;cout<<endl;for(L1=0;L1<n;L1++){cout<<“进程“<<L1<<“:“;for(j=i;j<m;j++)cout<<Need[L1][j]<<““;cout<<endl;}}}//银行家算法函数voidbank{cout<<endl<<“进程申请分配资：“<<endl;intk=0;//用于输入进程编号boolr=false;//初值为假，输入Y继续申请那么置为真do{//输入恳求cout<<“输入申请资的进程(0-“<<n-1<<“):“;cin》》k;cout<<endl;while(k》n-1)//输入错误处理{cout<<endl<<“输入错误，重新输入：“<<endl;cout<<endl<<“输入申请资的进程(0--“<<n-1<<“):“;cin》》k;cout<<endl;}cout<<endl<<“输入该进程申请各类资的数量:“<<endl;for(j=0;j<m;j++){do{//do……while循环判断申请输入的情况cout<<“进程“<<k<<“申请资[“<<j<<“]的数量:“;cin》》Request[j];cout<<endl;if(Request[j]》Need[k][j]){//申请大于需求量时出错，提示重新输入〔贷款数目不允许超过需求数目〕cout<<“申请大于需要量!“<<endl;cout<<“申请的资“<<j<<“的数量为“<<Request[j]<<“,大于进程“<<k<<“对该资需求量“<<Need[k][j]<<“。“<<endl;cout<<“重新输入!“<<endl;}else//先判断是否申请大于需求量，再判断是否申请大于可利用量if(Request[j]》Available[j]){//申请大于可利用量，应该阻塞等待？……？？？cout<<“＼n没有那么多资，目前可利用资“<<j<<“数量为“<<Available[j]<<“,本次申请不成功，进程等待!“<<endl;Finish[k]=0;//该进程等待gotoppp;//goto语句跳转，完毕本次申请}}while(Request[j]》Need[k][j]);//Request[j]》Available[j]||}//改变Avilable、Allocation、Need的值for(j=0;j<m;j++){Available[j]=Available[j]-Request[j];Allocation[k][j]=Allocation[k][j]+Request[j];Need[k][j]=Need[k][j]-Request[j];Work[j]=Available[j];}//判断当前状态的平安性safe;//调用平安性算法函数if(l<n){l=0;cout<<“＼n试分配后，状态不平安,所以不予分配!恢复原状态“<<endl;//恢复数据for(j=0;j<m;j++){Available[j]=Available[j]+Request[j];Allocation[k][j]=Allocation[k][j]-Request[j];Need[k][j]=Need[k][j]+Request[j];Work[j]=Available[j];}for(i=0;i<n;i++)Finish[i]=0;//进程置为未分配状态}else{l=0;cout<<“＼n申请资成功!!!“<<endl;for(j=0;j<m;j++){if(Need[k][j]==0);else{//有一种资还没全部申请到，那么该进程不可执行，不能释放拥有的资l=1;//置l为1，作为判断标志break;}}if(l!=1){//进程可以执行，那么释放该进程的所有资for(j=0;j<m;j++){Available[j]=Available[j]+Allocation[k][j];Allocation[k][j]=0;}cout<<“该进程已得到所有需求资，执行后将释放其所有拥有资！“<<endl;}l=0;//归零cout<<“＼n平安的状态!“<<endl;cout<<“平安序列为:“;cout<<endl<<“进程“<<“(“<<p[0]<<“)“;//输出平安序列，考虑显示格式，先输出第一个Finish[0]=0;for(i=1;i<n;i++){cout<<“==》》“<<“进程“<<“(“<<p[i]<<“)“;Finish[i]=0;//所有进程置为未分配状态}cout<<endl<<endl;}show;//显示当前状态ppp://申请大于可利用量，应该阻塞等待,完毕本次资申请，GOTO语句跳转至此cout<<endl<<“是否继续申请资(y/n)?“;char*b=newchar;//输入y/n，判断是否继续申请<<endlcin》》b;cout<<endl;cout<<““<<endl<<endl;cout<<endl;if(*b==＇y＇||*b==＇Y＇)r=true;else{r=false;//输入非Y那么令R=falsejieshu;//调用完毕函数}}while(r==true);}//完毕函数voidjieshu{cout<<endl<<endl;cout<<“＼t＼t演示计算完毕“<<endl;cout<<endl<<endl;}//主函数intmain{cout<<endl<<endl<<“＼t＼t＼t＼t模拟银行家算法“<<endl<<endl;chushihua;//初始化函数调用cout<<endl;show;