操作系统课程设计银行家算法(共22页).doc

精选优质文档-倾情为你奉上 操作系统课程设计报告 小组成员 指导教师 吉林建筑大学计算机科学与工程学院 年 月 日专心-专注-专业银行家算法摘 要本次的课程设计内容是银行家算法，在操作系统当中，由于竞争非剥夺性资源和进程推进的不当，对系统的安全造成威胁，所以，银行家算法就是为了避免对系统产生死锁而存在的。银行家算法包括对请求资源的试分配和对安全性的考量，当系统的安全性不能够满足的时候，则对系统进行保护。在编写银行家算法的时候需要定义Need（需求矩阵），Allocation（分配矩阵），Max（最大需求矩阵）以及Available（可利用资源量）。在实现一系列的功能的时候使用的数组的结构，便于进行矩阵的加减运算，可以提高程序的运行效率。通过编写可以基本上实现银行家算法所要达到的基本目的，在输入正确的情况下能够输出正确的安全序列，在不安全的情况下可以做出提醒，并且恢复原有输入数据。 关键字：银行家算法 最大需求矩阵 分配矩阵 需求矩阵 可利用资源量1 绪论银行家算法是操作系统当中为避免锁死的算法，并且是最具有代表性的避免锁死的算法，能够有效的在资源分配的过程中，对系统的安全性进行检测。整个算法的计算步骤为对输入的数据进行试分配，并对安全性进行检测，当系统为安全的时，依照安全序列执行程序，如果不安全则进入阻塞状态。银行家算法的来源是在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。在避免死锁的方法中，所施加的简直条件比在预防死锁的方法中限制条件要弱，有可能获得令人满意的系统性能。在该方法中，把系统的状态分为安全状态和不安全状态，只要能使系统都处于安全状态，就可避免死锁的发生。 所谓安全状态与不安全状态是指如果所有过程有可能完成执行（终止），则一个状态被认为是安全的。由于系统无法知道什么时候一个过程将终止，或者之后它需要多少资源，系统假定所有进程将最终试图获取其声明的最大资源并在不久之后终止。2 需求分析2.1 问题描述： 在多道程序系统中，虽然能够借助于多个进程的并发执行，来改善系统资源的利用率，提高系统的吞吐量，但是依然有风险存在，那就是锁死。所谓锁死是指，多个进程在运行中因争夺资源而造成的一种僵局，当进程的这种僵持状态时，若无外力作用，它们将无法再向前推进。一组程序中，每个进程都无限等待被该组进程中的另一进程所占有的资源，因而永远无法得到资源，这种现象就叫做进程死锁。2.2 产生条件1进程间竞争非剥夺性资源2进程保持申请3资源的独占，一个资源同一时刻只能分配给一个进程4进程循环等待资源2.3 运行环境 Visual C+ 6.02.4 程序功能在该程序中应该具有以下功能：1、 从外界输入进程数，资源数以及完成银行家算法的所需的各类资源数。2、 当输入越界或者非法输入时能够提示错误。3、 当进程推进处于不安全状态时要能够进行提示处于不安全状态，并且能够恢复数据到初始状态。当请求资源量大于可利用资源数时要能够进行提醒，并且重新输入。4、 当数据完成初始化时，要能够输出数据所对应的矩阵。3 概要设计3.1程序模块本程序包括了四个基本模块： 主函数、试分配、安全性测试、数据的输入与输出。3.1.1主函数主函数用于输出系统的主要操作界面，以及调用其他的函数，完成银行家算法。3.1.2试分配： 对输入的进程的Max、Available、Allocation以及Request进行分配，判断是否可以正常分配。3.1.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），将完整的算法需要的数据呈现给操作者。4.1.3 试分配：根据操作者所输入的进程号已经请求，对系统进行时分配。4.1.4 安全测试当试分配完成时可进行安全性测试，当进程间是安全的时候则可以输出相应的安全序列。如果错误，则可以回到数据的初始化状态。4.2 数据判断 当输入的数据不符合规定时，可以对该数据进行判断，不符合条件重新输入，例如：if(!(0<=in&&in<=t-1)，在程序中，用于判断所输入的进程号是否满足要求，如果不满足要求通过该语句输出“cout<<"该进程不存在,重新输入"<<endl;”。4.3 函数调用通过switch语句对所调用的函数进行判断。switch(choice)case 1: Input();break;/输入相关数据函数case 2: Print();break;/打印输出相关数据表函数 case 3: cout<<"请输入有请求的进程号:" break；case 4: checksafe(in); break;/安全性检查case 5: refenpei(in); break;/恢复数据 4.4程序流程图4.4.1数据初始化流程图提示输入有误！输入可利用资源数每个进程已分配的各资源数输入每个进程所需要的各类资源数初始化输入数据输入进程数t输入资源数c数据初始化结束True输出更改后的各资源数4.4.2安全性流程图银行家算法开始是银行家算法结束退出程序否是否再次分配Available()+=Request() Allocation()-=Request()Need()+=Request()错误！不安全否是可以分配安全性检测Available()-=Request() Allocation()+=Request()Need()-=Request()否错误错误否是是Request（）<=Available()Request（）<=Need()进程提出Request（）函数初始化5 测试与分析5.1程序调试:1、在数据初始化当中要考虑到输入进程数是否为负数，是否为字符。2、在安全性算法当中要考虑到当不安全时，数据能否恢复，是否可以重新进行分配。当输入的Request大于Need或者大于Available的情况，当大于是需要重新输入。5.2 程序测试: 5.2.1输入初始化：5.2.2 矩阵输出5.2.3 安全序列输出5.2.4进程不安全时 6 参考文献 1 汤小丹 梁红兵 哲凤屏 汤子瀛，计算机操作系统（第三版），西安： 西安电子科技大学出版社 2 王长元 李晋惠 等编著 ，软件工程 ，西安： 西安地图出版社 3 孟庆昌 等编著 ，操作系统原理， 北京： 机械工业出版社 4 左万历 周长林 彭涛，计算机操作系统教程（第三版），北京： 高等教育出版社 5 陈志泊 王春玲 孟伟，面向对象的程序设计语言c+（第二版），北京： 人民邮电出版社7附录：源程序清单#include <iostream.h>#define M 10 /资源类数#define N 50 /进程数void Input(); /用于输入的函数void Print(); /用于打印输出表格的函数void tryfenpei(int i);/试分配函数void checksafe(int x);/安全检测函数void refenpei(int i);/恢复数据函数/定义初始化数组 int AvailableM, MaxNM, AllocationNM, NeedNM, RequestM; int c,t;/资源进程 int in;/用户选择的进程号/*-*/void main( )int choice;char ch='Y'cout<<"输入资源数："cin>>c;cout<<"输入进程数："cin>>t; doif(ch='Y'|ch='y')cout<<"银行家算法"<<endl;cout<<"1:输入所需数据 "<<endl;cout<<"2:显示矩阵 "<<endl;cout<<"3:试分配 "<<endl;cout<<"4:检查安全性 "<<endl;cout<<"5:恢复数据到初始状态 "<<endl;cout<<"*"<<endl;cout<<"请选择操作序号："cin>>choice;switch(choice)case 1: Input();/输入相关数据函数 break;case 2: Print();/打印输出相关数据表函数 break;case 3: cout<<"请输入有请求的进程号:" while(cin>>in) if(!(0<=in&&in<=t-1)cout<<"该进程不存在,重新输入"<<endl;else break; tryfenpei(in);/试分配 break;case 4: checksafe(in);/安全性检查 break;case 5: refenpei(in);/恢复数据 break;default: cout<<"请(1-5)中选择正确的操作序号!"<<endl; break;cout<<"要继续进行吗?（y-是 n否）" else if(ch='N'|ch='n')cout<<"正在退出."<<endl;break;elsecout<<"输入无效!重新输入."<<endl;while(cin>>ch);/*-main函数结束-*/*-输入函数-*/void Input()int j,n,m;cout<<"输入 可利用资源:"<<endl;for(j=0;j<c;j+)/cout<<"请输入 Available"<<j<<":"while(cin>>Availablej)if(Availablej<0)cout<<"输入数字无效，请重新输入"<<endl;else break;cout<<"输入 最大需求:"<<endl;for(n=0;n<t;n+)/各个进程循环输入for(m=0;m<c;m+)/c个类资源ABC循环输入while(cin>>Maxnm)if(Maxnm<0)cout<<"输入数字无效，请重新输入"<<endl;else break;cout<<"输入 占有资源:"<<endl;for(n=0;n<t;n+)/各个进程循环输入for(m=0;m<c;m+)/c个类资源ABC循环输入while(cin>>Allocationnm)if(Allocationnm<0)cout<<"输入数字无效，请重新输入"<<endl;else break;Neednm=Maxnm-Allocationnm; cout<<"初始化完成!."<<endl;/*-输入函数结束-*/*-输出函数-*/void Print()int i,j;cout<<"|*|*|*|*|*|"<<endl;cout<<"|*| | | | |"<<endl;cout<<"| 进程| Max | Allocation | Need | Available |"<<endl;cout<<"|*|*|*|*|*|"<<endl;for(i=0;i<t;i+)cout<<"| p"<<i<<" | "for(j=0;j<c;j+)cout<<Maxij<<" "cout<<"| "for(j=0;j<c;j+) cout<<Allocationij<<" "cout<<" | "for(j=0;j<c;j+)cout<<Needij<<" "cout<<"| "if(i=0)for(j=0;j<c;j+)cout<<Availablej<<" "cout<<"| "if(i>0)cout<<" |"cout<<endl;cout<<"|*|*|*|*|*|"<<endl;/*-输出函数结束-*/*-试分配函数-*/void tryfenpei(int n)int i;cout<<"您输入的是 "<<"p"<<n<<""<<" 进程"<<endl; cout<<"该进程需求量为： " for(i=0;i<c;i+) cout<<Needni<<" " cout<<endl; cout<<"请输入请求资源的数目:" for(i=0;i<c;i+) while(cin>>Requesti) if (Requesti<0) cout<<"!输入的数字无效."<<endl; else if (Requesti>Needni) cout<<"!超出进程需求量"<<endl<<endl; else if (Requesti>Availablei) cout<<"!系统没有足够的可用资源量满足进程需要"<<endl<<endl; else break; cout<<"输入成功，输入的是："for(int f=0;f<c;f+)cout<<Requestf<<" " cout<<endl; cout<<"执行银行家算法，进行试分配."<<endl;for( f=0;f<c;f+)Availablef = Availablef - Requestf;Allocationnf = Allocationnf + Requestf;Neednf = Neednf-Requestf; cout<<"试分配完成!"<<endl; /*-试分配函数结束-*/*-安全检测函数-*/void checksafe(int x) cout<<"进入安全性检测."<<endl;int i,m,apply,j,k=0,flag=0;int WorkM,tempN;bool FinishN; /t为进程数for(i=0;i<c;+i)Worki=Availablei;for(i=0;i<t;i+) Finishi=false;for(i=0;i<t;i+) apply=0;for(j=0;j<c;j+)if (false=Finishi && Needij<=Workj)apply+;/标记是否所需的资源都得到满足if(apply=c)for(m=0;m<c;m+)Workm=Workm+Allocationim;/变分配数 w=w+aFinishi=true;tempk+=i;/将满足的进程号存入temp数组中i=-1; /若有进程满足条件则从头开始寻找 for(i=0;i<t;i+)if(Finishi=false)cout<<"试分配后系统不安全! 本次资源申请不成功!"<<endl; cout<<"等待恢复原来的数据."<<endl;refenpei(in);return ; cout<<"安全序列："<<endl; cout<<"分配的序列:"for(i=0;i<t-1;i+)cout<<"P"<<tempi<<"->" cout<<"P"<<tempt-1<<endl; cout<<"已通过安全性测试!"<<endl; cout<<"开始给第 "<<"p"<<in<<""<<"进程分配资源."<<endl; cout<<"分配完成!等待打印输出."<<endl;Print(); return ;/*-安全性检查函数结束-*/*-恢复数据函数-*/void refenpei(int i) for(int f=0;f<c;f+)Availablef = Availablef + Requestf;Allocationif = Allocationif - Requestf;Needif = Needif + Requestf;cout<<"数据已恢复初始状态."<<endl;Print();设计体会教师评语：成绩： 指导教师：设计体会教师评语：成绩： 指导教师：