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

操作系统课程设计报告小组成员指导教师吉林建筑大学计算机科学与工程学院年月日银行家算法

摘要本次的课程设计内容是银行家算法，在操作系统当中，由于竞争非剥夺性资源和进程推进的不当，对系统的安全造成威胁，所以，银行家算法就是为了避免对系统产生死锁而存在的。银行家算法包括对请求资源的试分配和对安全性的考量，当系统的安全性不能够满足的时候，则对系统进行保护。在编写银行家算法的时候需要定义Need（需求矩阵），Allocation（分配矩阵），Max（最大需求矩阵）以及Available（可利用资源量）。在实现一系列的功能的时候使用的数组的结构，便于进行矩阵的加减运算，可以提高程序的运行效率。通过编写可以基本上实现银行家算法所要达到的基本目的，在输入正确的情况下能够输出正确的安全序列，在不安全的情况下可以做出提醒，并且恢复原有输入数据。关键字：银行家算法最大需求矩阵分配矩阵需求矩阵可利用资源量1绪论银行家算法是操作系统当中为避免锁死的算法，并且是最具有代表性的避免锁死的算法，能够有效的在资源分配的过程中，对系统的安全性进行检测。整个算法的计算步骤为对输入的数据进行试分配，并对安全性进行检测，当系统为安全的时，依照安全序列执行程序，如果不安全则进入阻塞状态。银行家算法的来源是在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程在铝免死锁的方法中，所施加的简直条件比在预防死锁的方法中限制条件要弱，有可能获得令人满意的系统性能。在该方法中，把系统的状态分为安全状态和不安全状态，只要能使系统都处于安全状态，就可避免死锁的发生。所谓安全状态与不安全状态是指如果所有过程有可能完成执行（终止），则一个状态被认为是安全的。由于系统无法知道什么时候一个过程将终止，或者之后它需要多少资源，系统假定所有进程将最终试图获取其声明的最大资源并在不久之后终止2需求分析2.1问题描述：在多道程序系统中，虽然能够借助于多个进程的并发执行，来改善系统资源的利用率，提高系统的吞吐量，但是依然有风险存在，那就是一一锁死。所谓锁死是指，多个进程在运行中因争夺资源而造成的一种僵局，当进程的这种僵持状态时，若无外力作用，它们将无法再向前推进。一组程序中，每个进程都无限等待被该组进程中的另一进程所占有的资源，因而永远无法得到资源，这种现象就叫做进程死锁。2.2产生条件1、进程间竞争非剥夺性资源2、进程保持申请3、资源的独占，一个资源同一时刻只能分配给一个进程4、进程循环等待资源2.3运行环境VisualC++6.02.4程序功能在该程序中应该具有以下功能：1、从外界输入进程数，资源数以及完成银行家算法的所需的各类资源数。2、当输入越界或者非法输入时能够提示错误。3、当进程推进处于不安全状态时要能够进行提示处于不安全状态，并且能够恢复数据到初始状态。当请求资源量大于可利用资源数时要能够进行提醒，并且重新输入。4、当数据完成初始化时，要能够输出数据所对应的矩阵。3概要设计3.1程序模块本程序包括了四个基本模块：主函数、试分配、安全性测试、数据的输入与输出。11主函主函数用于输出系统的主要操作界面，以及调用其他的函数，完成银行家算法。2试分配：对输入的进程的Max、AvailablesAllocation以及Request进行分配，判断是否可以正常分配。3安全性测试：当试分配完成时，通过安全性测试来对系统的安全性进行检测，安全时输出安全序列，不安全时进行提醒，并且恢复到初始化时输入的数据。3.2模块之间关系主函数可以调用系统的所有函数，以及输出功能界面，将试分配函数，安全性测试函数和输入输出函数定义在主函数当中，在需要时通过相应的选项进行调用。而试分配与安全性测试是并列的两个函数，存在执行试分配后需对安全序列进行判断。输入输出函数，确定数值，并将相对应的数据输入到对应的模块，来进行计算。3.3数据结构程序当中需要四种数据结构。1、可利用资源矩阵(Available)＞当Available[]=k时，这表示系统中有该类资源k个。2、最大需求矩阵(Max),当Max[][]=k时，则表示进程需要的资源为k个。3、分配矩阵(Allocation),当Allocation□□二k时，则表示进程当前己被分得k个资源。4、需求矩阵(Need),当Need[][]=k时，则表示进程还需要k个资源才能够完成。3.4算法思想操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推退分配。当进程在执行中继续申请资源时，先测试该进程己占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。4详细设计4.1程序模块划分：4.1.1数据的初始化：根据提示输入最大需求矩阵(Max),可利用资源量(Available),分配矩阵(Allocation)所需的数据。4.1.2输出所对应的矩阵：根据输入的数据输出对应的矩阵，并且计算出需求矩阵(Need),将完整的算法需要的数据呈现给操作者。3试分配：根据操作者所输入的进程号己经请求，对系统进行时分配。4安全测试当试分配完成时可进行安全性测试，当进程间是安全的时候则可以输出相应的安全序列。如果错误，则可以回到数据的初始化状态。4.2数据判断当输入的数据不符合规定时，可以对该数据进行判断，不符合条件重新输入,例如：if(!(O<=in&&in<=t-l)),在程序中，用于判断所输入的进程号是否满足要求，如果不满足要求通过该语句输出“cout«〃该进程不存在，重新输入，/«endl;,,o4.3函数调用通过switch语句对所调用的函数进行判断。switch(choice)(case1:Input();break;//输入相关数据函数case2：Print();break;//打印输出相关数据表函数case3:cout<<，z请输入有请求的进程号："break：case4:checksafe(in);break;//安全性检查case5:refenpei(in);break;//恢复数据}4.4程序流程图5测试与分析5.1程序调试：1、在数据初始化当中要考虑到输入进程数是否为负数，是否为字符。2、在安全性算法当中要考虑到当不安全时，数据能否恢复，是否可以重新进行分配。当输入的Request大于Need或者大于Available的情况，当大于是需要重新输入。5.2程序测试：2.1输入初始化:轲A咨源教:瞒入进程教：斥艮行家算法「输入腐需激据2二显示矩辟=试分配=检查安全性=恢复教据至U初始状态2.2矩阵输出

Pl—>P0—>P2——>P3进入安全性检测…安全序列：分配的序列二已诵过安全，性测试，开始给第Pl—>P0—>P2——>P3进程^Maxp。!3pl!6p2!3p3!4Allocation!：Need100!!222512!1101211!1103002：!4202342Auailable1115.2.4进程不安全时请输入有请求的进程号=2愿输入的旱PC2］进程W求量为：103请输人请求咨源的数目二101输入成功，L执行银行家算试分配完成，该进程需进入安全性检测试分配后系统不拿待倾复原来的数据已恢复初始状态...输入邮］是：101算曩进行试分配，本次资源由请不成功"，Alloca,tionAua±lable6参考文献汤小丹梁红兵哲凤屏汤子瀛，《计算机操作系统（第三版）》，西安：西安电子科技大学出版社王长元李晋惠等编著，《软件工程》，西安：西安地图出版社孟庆昌等编著，《操作系统原理》，北京：机械工业出版社左万历周长林彭涛，《计算机操作系统教程（第三版）》，北京：高等教育出版社陈志泊王春玲孟伟，《面向对象的程序设计语言C++（第二版）》，北京：人民邮电出版社7附录：源程序清单ttinclude<iostream.h>ttdefineM10〃资源类数#defineN50〃进程数voidInput();〃用于输入的函数voidPrint();〃用于打印输出表格的函数voidtryfenpei(inti)://试分配函数voidchecksafe(intx);//安全检测函数voidrefenpei(inti);//恢复数据函数//定义初始化数组intAvailable[M],Max[N][M],Allocation[N][M],NeedtN][M],Request[M];intc,t;//资源进程intin;//用户选择的进程号/**voidmain()(intchoice;charch=，Y';COUt«，Z输入资源数：〃；cin>>c;COUt«，Z输入进程数：〃；cin>>t;do(if(ch==，Y'||ch==，y，)(cout«,，银行家算法，，«endl;cout«z，l:输入所需数据"《endl;cout<<z，2:显示矩阵〃《endl;cout<<z，3:试分配〃《endl;cout<<，，4:检查安全性〃《endl;cout«/z5:恢复数据到初始状态〃《endl;cout〈<〃**********************"〈〈endl;COUt«Z，请选择操作序号：〃；cin>>choice;switch(choice){case1:Input();//输入相关数据函数break;case2:Print();//打印输出相关数据表函数break;case3:cout«，z请输入有请求的进程号:”;while(cin»in)(if(!(0<=in&&in<=t-l))(cout<<，,该进程不存在，重新输入，z<<endl:}elsebreak;}tryfenpei(in);//试分配break;case4:checksafe(in)://安全性检查break;case5：refenpei(in);//恢复数据break;default:cout<<，?清(1-5)中选择正确的操作序号!z，«endl;break;)cout«"要继续进行吗?(y-是n否)〃;}elseif(ch='N'||ch==，n*)(cout<</z正在退出...，，<<endl;break;}else{cout<<〃输入无效!重新输入...，z<<endl:)}while(cin>>ch);}/*main函数结束*//*输入函数*/voidInput()(intj,n,m;cout«,，输入可利用资源:,z«endl;for(j=0;j<c;j++)(〃cout«"请输入Available[〃<<j«"]:";while(cin»Available[j])(if(Available[j]<0)cout«，,输入数字无效，请重新输入，，«endl;elsebreak;}；}cout«，z输入最大需求:,z«endl;for(n=0;n<t;n++)〃各个进程循环输入(for(m=0;m<c:m++)//c个类资源ABC循环输入(while(cin>>Max[n][m]){if(Max[n][m]<0)cout«，z输入数字无效，请重新输入〃《endl;elsebreak;)；}}cout«，z输入占有资源:，z«endl;for(n=0;n<t;n++)〃各个进程循环输入(for(m=0;m<c:m++)//c个类资源ABC循环输入(while(cin>>Allocation[nJ[m])if(Allocation[n][m]<0)cout«，,输入数字无效，请重新输入，，«endl;elsebreak;NeedEn][m]=Max[n][m]-Allocation[n][m];})cout«，,初始化完成！..."«endl;}/*输入函数结束*/

/*输出函数*/voidPrint()inti,j;・・・・・・・*|，z<<endl:cout«，z*****|z/<<endl;cout«，z进程Max|AllocationNeedAvailable|z/<<endl;cout«，/******|，，<<endl;for(i=0;i<t;i++)■]・.]■■>■]■・1—I•]■^?x■]・•]■■X■X*■]・^?x■]・^?x・1・wx■X・1・^?x■]・cout<<,，|p，/<<i<<，/|for(j=0;j<c;j++)cout<<Max[i][j]«z/〃；}cout<<"|";for(j=0;j<c;j++)(cout<<Allocation[i][j]<<〃}cout<<"I”;for(j=0;j<c;j++)(cout<<Need[i][j]<<，z〃；}cout<<"|";if(i==0)(for(j=0;j<c;j++){cout<<Available[j]<</z}cout<<〃|〃；}if(i>0)(COUt<<，ZI"；cout<<endl;}・・・・・・・・・・・・・・・・输出函数结束*/inti;cout«，,您输入的是〃《〃p[〃<Xn<X〃]〃《〃进程，z«endl;cout«，,该进程需求量为：〃；for(i=0;i<c;i++)cout<<Need[n][i]<</z”;cout<<endl;cout«，/请输入请求资源的数目：〃；for(i=0;i<c;i++)(while(cin>>Request[i])(if(Request[i]<0){cout<<，/!!输入的数字无效.，z<<endl;)elseif(Request[i]>Need[n][i]){cout<<〃!!超出进程需求量，，«endl«endl;)elseif(Request[i]>Available[i])(cout«，z!!系统没有足够的可用资源量满足进程需要，z«endl«endl;)elsebreak;))cout<<，,输入成功，输入的是："；for(intf=0;f<c;f++)cout<<Request[f]<</z";cout<<endl;cout«，,执行银行家算法，进行试分配...，，«endl;for(f=0;f<c:f++)(Available[f]=Available[f]-Request[f]:Allocationin][f]=Allocation[n][f]+Request[f]:NeedEn][f]=NeedLn][f]-Request[f];}cout<<z，试分配完成!z/<<endl:}/*试分配函数结束*//*安全检测函数*/voidchecksafe(intx)(cout«,，进入安全性检测..."«endl;inti,m,apply,j,k=0,flag=0;intWork[M],temp[N];boolFinish[N];〃t为进程数for(i=0;i<c;++i)(Work[i]=Available[i];}for(i=0;i<t;i++)(Finishli]=false;}for(i=0;i<t;i++)(apply=0;for(j=0;j<c;j++)(if(false==Finish[i]&&Need[i][j]<=Work[j]){apply++;〃标