银行家算法模拟程序设计

银行家算法模拟程序设计目录一、课程设计的目的 3二、课程设计的要求 3三、课程设计题目描述 3四、算法流程图 41、银行家算法流程图 42、安全性检查算法流程图 5五、课程设计之银行家算法原理 51．银行家算法的思路 52．银行家算法 53．安全性检查算法（IsSafe()函数） 6六、源程序结构分析及代码实现 71．程序结构 72．数据结构 73．函数声明 84.源代码 86.运行界面 14七、课程设计的总结 16一、课程设计的目的操作系统是计算机系统的核心系统软件，它负责控制和管理整个系统的资源并组织用户协调使用这些资源，使计算机高效的工作。《操作系统课程设计》是《操作系统》理论课的必要补充，是复习和检验所学课程的重要手段，本课程设计的目的是综合应用学生所学知识，通过实验环节，加深学生对操作系统基本原理和工作过程的理解，提高学生独立分析问题、解决问题的能力，增强学生的动手能力。二、课程设计的要求1．分析设计内容，给出解决方案（要说明设计实现的原理，采用的数据结构）。2．画出程序的基本结构框图和流程图。3．对程序的每一部分要有详细的设计分析说明。4．源代码格式要规范。5．设计合适的测试用例，对得到的运行结果要有分析。6．设计中遇到的问题，设计的心得体会。7．按期提交完整的程序代码、可执行程序和课程设计报告。三、课程设计题目描述银行家算法是一种最有代表性的避免死锁的算法。

要解释银行家算法，必须先解释操作系统安全状态和不安全状态。

安全状态：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。

不安全状态:不存在一个安全序列。不安全状态不一定导致死锁。

安全序列：一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj(j<i)当前占有资源量之和。

银行家算法：我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。四、算法流程图错误Requesti<=Needi?1、银行家算法流程图 错误Requesti<=Needi? 否 是进程Pi阻塞Requesti<=Available?进程Pi阻塞Requesti<=Available? 否是试分配：试分配：Available-=RequestiAllocationi+=RequestiNeedi-=Requesti试将分配作废，恢复原资源分配状态执行安全性算法，检查试将分配作废，恢复原资源分配状态执行安全性算法，检查分配后的系统状态安全正式分配正式分配2、安全性检查算法流程图Work=AvailableWork=AvailableFinish[i]=0找一个满足下列条件的进程Finish[i]=0且Needi<Work所有进程的Finish[i]=1?找一个满足下列条件的进程Finish[i]=0且Needi<Work所有进程的Finish[i]=1? 是 不是 找到系统处于安全状态系统处于不系统处于安全状态系统处于不安全状态Work+=AllocationFinish[i]=1五、课程设计之银行家算法原理1．银行家算法的思路先对用户提出的请求进行合法性检查，即检查请求的是不大于需要的，是否不大于可利用的。若请求合法，则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态，拒绝申请。2．银行家算法进程mi发出请求申请k个j资源，Request[mi][j]=k(1)Request[mi][j]<=need[mi][j],检查申请量是否不大于需求量,若条件不符重新输入，不允许申请大于需求量。(2)Request[mi][j]<=available[mi][j]，检查申请量是否小于系统中的可利用资源数量,若条件不符就申请失败，阻塞该进程，重新申请资源。(3)若以上两个条件都满足，则系统试探着将资源分配给申请的进程，并修改下面数据结构中的数值：Available[i]-=Request[mi][i]; Allocation[mi][i]+=Request[mi][i]; Need[mi][i]-=Request[mi][i](4)试分配后，执行安全性检查，调用IsSafe()函数检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程；否则本次试探分配作废，恢复原来的资源分配状态，让该进程等待。(5)用while循环语句实现输入字符y/n判断是否继续进行资源申请。3．安全性检查算法（IsSafe()函数）(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；(4)如果所有的Finish[i]=1都满足，则表示系统处于安全状态，否则，处于不安全状态六、源程序结构分析及代码实现1．程序结构程序共有以下七个部分：安全性检查IsSafe()：用于判断当前状态安全性，根据不同地方的调用提示处理不同。初始化算法1Read()：用于程序开始进行初始化数据，从文件中读入数据：进程数量、资源种类、各种资源可利用数量、各进程的各种资源已分配数量、各进程对各类资源最大需求数等。初始化算法2Input()：用于程序开始进行初始化数据，从键盘上输入数据：进程数量、资源种类、各种资源可利用数量、各进程的各种资源已分配数量、各进程对各类资源最大需求数等。Init():进行银行家算法模拟实现的模块，调用其他各个模块进行银行家算法模拟过程。Menu():显示菜单。Design()：主界面设计模块。主函数main()：逐个调用初始化、显示状态、安全性检查、银行家算法函数，使程序有序的进行2．数据结构银行家算法中用到的主要数据结构：intAvailable[100]//各种资源可利用的数量intAllocation[50][100]//各进程当前已分配的资源数量intMax[50][100]//各进程对各类资源的最大需求数intNeed[50][100]//需求矩阵intRequest[50][100]//申请各类资源的数量intWork[100]//工作向量，表系统可提供给进程运行所需各类资源数量intFinish[50]//表系统是否有足够的资源分配给进程，0为否，1为是intp[50];//存储安全序列intm，n;//m为进程的数量,n为资源种类数3．函数声明intIsSafe();//安全性检测voidRead();//从文件读入数据voidInput();//从键盘输入数据voidInit();//银行家算法voidMenu();//菜单voidDesign();//主界面设计4.源代码#include<iostream.h>#include<stdio.h>#include<stdlib.h>#include<conio.h>voidmain(){ Design();printf("┃请按任意键进行初始化操作...┃\n"); printf("┗━━━━━━━━━━━━━━━━━━━━━━━━━┛\n"); printf(">>>"); getch(); system("cls"); cout<<"请输入进程的数目:"; cin>>m; cout<<"请输入资源种类:";cin>>n; Menu();}intIsSafe(){ inti,j,k; intlen=-1;///记录安全序列的进程个数，如果len==m，即表示处于安全状态 int Work[100]; for(i=0;i<n;i++) {Work[i]=Available[i]; } for(i=0;i<m;i++) Finish[i]=0;for(i=0;i<m;i++) {if(Finish[i]==1)continue; else { for(j=0;j<n;j++) { Need[i][j]=Max[i][j]-Allocation[i][j];if(Need[i][j]>Work[j])break; if(Need[i][j]<0)return0; } if(j==n){ for(k=0;k<n;k++)Work[k]+=Allocation[i][k]; Finish[i]=1; len++; p[len]=i; i=-1; } elsecontinue; } } if(len==m-1) { cout<<"系统是安全的\n"; cout<<"安全序列是:"; for(i=0;i<=len;i++) { cout<<p[i]; if(i!=len)cout<<"-->"; } cout<<endl; return1; } elsereturn0;}voidRead(){inti,j;FILE*fp;fp=fopen("Max.txt","r+"); cout<<"从Max.txt文件中读入数据，则每个进程最多需要的各类资源数为:"<<endl; for(i=0;i<m;i++) { for(j=0;j<n;j++) { fscanf(fp,"%d",&Max[i][j]); cout<<Max[i][j]<<""; } cout<<endl; } fclose(fp);fp=fopen("Allocation.txt","r+"); cout<<"从Allocation.txt文件中读入数据，则每个进程已分配的各类资源数为:"<<endl; for(i=0;i<m;i++) { for(j=0;j<n;j++) { fscanf(fp,"%d",&Allocation[i][j]); cout<<Allocation[i][j]<<""; Need[i][j]=Max[i][j]-Allocation[i][j]; } cout<<endl; } fclose(fp); fp=fopen("Available.txt","r+"); cout<<"从Available.txt文件中读入数据，则现有空闲各类资源数为:"; for(i=0;i<n;i++) { fscanf(fp,"%d",&Available[i]); cout<<Available[i]<<""; }cout<<endl; fclose(fp);}voidInput(){inti,j; cout<<"输入每个进程最多所需的各类资源数，按照"<<m<<"*"<<n<<"矩阵输入"<<endl; for(i=0;i<m;i++) {for(j=0;j<n;j++) { cin>>Max[i][j]; } }cout<<"输入每个进程已分配的各类资源数，按照"<<m<<"*"<<n<<"矩阵输入"<<endl; for(i=0;i<m;i++) {for(j=0;j<n;j++) { cin>>Allocation[i][j]; } } for(i=0;i<m;i++) {for(j=0;j<n;j++) { Need[i][j]=Max[i][j]-Allocation[i][j]; if(Need[i][j]<0) { cout<<"你输入的第"<<i+1<<"个进程的第"<<j+1<<"个资源数错误，请重新输入"<<endl; j--; continue; } } }cout<<"请输入现有未分配的各类资源数目："; for(i=0;i<n;i++) { cin>>Available[i]; }}voidInit(){ inti,mi; charok;IsSafe(); while(1)//死循环，只要括号里为非零，就一直循环这条句子。 { cout<<"请输入要申请资源的进程号(第一个进程号为0，以此类推)"; cin>>mi; cout<<"请输入该进程所请求的各类资源的数目:"; for(i=0;i<n;i++)cin>>Request[mi][i];for(i=0;i<n;i++) {while(Request[mi][i]>Need[mi][i]) { cout<<"你输入的请求数超过进程的需求数，错误！"<<endl; break; } while(Request[mi][i]>Available[i]) {cout<<"你输入的请求数超过系统的资源数，系统无法满足！"<<endl;break; } break; }for(i=0;i<n;i++) { Available[i]-=Request[mi][i]; Allocation[mi][i]+=Request[mi][i]; Need[mi][i]-=Request[mi][i]; } if(IsSafe())cout<<"系统成功分配资源！"<<endl; else { cout<<"系统未能成分配资源,收回预分配资源！"<<endl; for(i=0;i<n;i++) {Available[i]+=Request[mi][i]; Allocation[mi][i]-=Request[mi][i]; Need[mi][i]+=Request[mi][i]; } } for(i=0;i<m;i++)Finish[i]=0;cout<<"你还想再次请求分配吗？是请按y/Y,否请按n/N:"; while(1) { cin>>ok; if(ok=='y'||ok=='Y'||ok=='n'||ok=='N')break; elsecontinue; } if(ok=='y'||ok=='Y')continue; else { system("cls"); Menu(); } } }voidMenu(){intcode;printf("***********************\n"); printf("*请选择：*\n"); printf("**\n"); printf("*1.从文件中读入数据*\n");printf("*2.从键盘输入数据*\n"); printf("*3.退出*\n"); printf("***********************\n"); printf("请选择操作：\b\b");scanf("%d",&code); do { switch(code) { case1:Read(); Init(); break; case2:Input(); Init(); break; case3:system("cls"); Design(); printf("┃谢谢使用银行家算法!┃\n"); printf("┗━━━━━━━━━━━━━━━━━━━