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

1、操作系统课程设计报告题目：银行家算法院 （系）：专业：班级：学生：学号：指导教师：2010 年 12 月操作系统课程设计报告题目：银行家算法院 （系）：专业：班级：学生：学号：指导教师：2010 年 12 月银行家算法摘 要本次的课程设计容是银行家算法， 在操作系统当中， 由于竞争非剥夺性资源和进程推进的不当，对系统的安全造成威胁， 所以，银行家算法就是为了避免对系统产生死锁而存在的。银行家算法包括对请求资源的试分配和对安全性的考量，当系统的安全性不能够满足的时候，则对系统进行保护。在编写银行家算法的时候需要定义 Need（需求矩阵），Allocation （分配矩阵）， Max（最大需求矩阵

2、）以及 Available （可利用资源量）。在实现一系列的功能的时候使用的数组的结构， 便于进行矩阵的加减运算， 可以提高程序的运行效率。通过编写可以基本上实现银行家算法所要达到的基本目的， 在输入正确的情况下能够输出正确的安全序列， 在不安全的情况下可以做出提醒， 并且恢复原有输入数据。关键字： 银行家算法最大需求矩阵分配矩阵需求矩阵可利用资源量目录.i112.22.1 问题描述.2）2.2 产生条件.2）2.3 运行环境.2）2.4 程序功能.2）3.33.1程序模块.3）3.2模块调用关系.3）3.3数据结构.3）3.4算法细想.4）4.54.1模块划分.5）4.2数据判断. 5）4.

3、3函数调用.5）4.4程序流程图.6）5.85.1程序调试.8）5.2程序测试.(8)6.(9)7.(10)(11)1 绪论银行家算法是操作系统当中为避免锁死的算法， 并且是最具有代表性的避免锁死的算法，能够有效的在资源分配的过程中， 对系统的安全性进行检测。 整个算法的计算步骤为对输入的数据进行试分配， 并对安全性进行检测， 当系统为安全的时，依照安全序列执行程序， 如果不安全则进入阻塞状态。 银行家算法的来源是在银行中， 客户申请贷款的数量是有限的， 每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的

4、最大值时， 都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。在避免死锁的方法中， 所施加的简直条件比在预防死锁的方法中限制条件要弱，有可能获得令人满意的系统性能。 在该方法中， 把系统的状态分为安全状态和不安全状态，只要能使系统都处于安全状态，就可避免死锁的发生。所谓安全状态与不安全状态是指如果所有过程有可能完成执行（终止） ，则一个状态被认为是安全的。 由于系统无法知道什么时候一个过程将终止， 或者之后它需要多少资源， 系统假定所有进程将最终试图获取其声明的最大资源并在不久之后终止。2 需求分析2.1问题描述：在多道程序系统中，虽然能

5、够借助于多个进程的并发执行，来改善系统资源的利用率，提高系统的吞吐量，但是依然有风险存在，那就是锁死。所谓锁死是指，多个进程在运行中因争夺资源而造成的一种僵局，当进程的这种僵持状态时，若无外力作用，它们将无法再向前推进。一组程序中，每个进程都无限等待被该组进程中的另一进程所占有的资源， 因而永远无法得到资源， 这种现象就叫做进程死锁。2.2产生条件：1、进程间竞争非剥夺性资源2、2.3运行环境Visual C+ 6.02.4程序功能在该程序中应该具有以下功能：1、从外界输入进程数，资源数以及完成银行家算法的所需的各类资源数。2、当输入越界或者非法输入时能够提示错误。3、当进程推进处于不安全状态

6、时要能够进行提示处于不安全状态，并且能够恢复数据到初始状态。当请求资源量大于可利用资源数时要能够进行提醒，并且重新输入。4、当数据完成初始化时，要能够输出数据所对应的矩阵。3 概要设计3.1 程序模块本程序包括了四个基本模块： 主函数、试分配、安全性测试、数据的输入与输出。主函数主函数用于输出系统的主要操作界面，以及调用其他的函数， 完成银行家算法。试分配：对输入的进程的Max、 Available、Allocation以及 Request 进行分配，判断是否可以正常分配。安全性测试：当试分配完成时， 通过安全性测试来对系统的安全性进行检测， 安全时输出安全序列，不安全时进行提醒，并且恢复到初

7、始化时输入的数据。3.2 模块之间关系主函数可以调用系统的所有函数，以及输出功能界面，将试分配函数，安全性测试函数和输入输出函数定义在主函数当中， 在需要时通过相应的选项进行调用。而试分配与安全性测试是并列的两个函数， 存在执行试分配后需对安全序列进行判断。输入输出函数， 确定数值，并将相对应的数据输入到对应的模块，来进行计算。3.3数据结构程序当中需要四种数据结构。1、可利用资源矩阵（ Available ），当 Available=k 时，这表示系统中有该类资源 k 个。2 、最大需求矩阵（Max），当 Max=k时，则表示进程需要的资源为k 个。3、分配矩阵（ Allocation），当

8、 Allocation=k时，则表示进程当前已被分得 k 个资源。4 、需求矩阵（ Need），当 Need=k时，则表示进程还需要k 个资源才能够完成。3.4 算法思想操作系统按照银行家制定的规则为进程分配资源， 当进程首次申请资源时，要测试该进程对资源的最大需求量， 如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源， 否则就推迟分配。 当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。 若超过则拒绝分配资源， 若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量， 若能满足则按当前的申请量分配资源，

9、否则也要推迟分配。4 详细设计4.1程序模块划分：数据的初始化：根据提示输入最大需求矩阵（Max），可利用资源量（ Available ），分配矩阵（ Allocation ）所需的数据。输出所对应的矩阵：根据输入的数据输出对应的矩阵，并且计算出需求矩阵（Need），将完整的算法需要的数据呈现给操作者。试分配：根据操作者所输入的进程号已经请求，对系统进行时分配。安全测试当试分配完成时可进行安全性测试， 当进程间是安全的时候则可以输出相应的安全序列。如果错误，则可以回到数据的初始化状态。4.2数据判断当输入的数据不符合规定时，可以对该数据进行判断， 不符合条件重新输入，例如： if(!(0<

10、;=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(i

11、n); break;/安全性检查case 5: refenpei(in); break;/恢复数据4.4 程序流程图数据初始化流程图初始化输入数据输入资源数c输入进程数t输入每个进程所需要的各类资源数每个进程已分配的各资源数提示输入有误！输入可利用资源数True输出更改后的各资源数数据初始化结束安全性流程图银行家算法开始函数初始化进程提出Request（）Request （ ）<=Need()是Request （ ）<=Available()是Available()-=Request()Allocation()+=Request()Need()-=Request()安全性检测是可以

12、分配否错误否错误否错误！不安全Available()+=Request()Allocation()-=Request()Need()+=Request()是否再次否退出程序分配是银行家算法结束5 测试与分析5.1 程序调试 :1、在数据初始化当中要考虑到输入进程数是否为负数，是否为字符。2、在安全性算法当中要考虑到当不安全时，数据能否恢复，是否可以重新进行分配。当输入的Request 大于 Need或者大于 Available的情况，当大于是需要重新输入。5.2程序测试 :输入初始化：矩阵输出安全序列输出进程不安全时6 实验心得操作系统是计算系组成当中最为重要的系统软件， 只有操作系统的存在在

13、能够使得计算机能够有正常有序的进行工作， 操作系统对于计算机来说是各项活动的组织者和指挥者。 而银行家算法的存在则是为了保证这个系统能够正常的安全的进行工作的保证。 我们可以把操作系统看成是银行， 而银行家算法则可以看成是银行的管理者，而各类资源则可以看成时银行的资金，而进程则是客户。 作为管理者的银行家算法则需要使得在银行的资金， 即操作系统的资源进行正常有序的分配，以保证操作系统能够正常运转。 并保证在进程有足够的资源进行运转。操作系统按照银行家制定的规则进行资源分配，当进程首次申请资源是，要测试进程对最远的最大需求是多少， 如果系统现有的资源能够满足， 则最该进程分配资源，否则推迟分配。

14、当进程在执行过程，依然要求分配资源时，则先测试该进程已占用的资源数与需求数是否超过了该进程的最大需求。 若超过，应该拒绝分配资源。银行家算法作为系统资源的保障，起着举足轻重的作用，所以多银行家算法必须有深入的了解，从而认识操作系统的工作过程。7 参考文献1 计算机操作系统（第三版） 汤小丹 梁红兵 哲凤屏 汤子瀛 编著 电子科技大学2 软件工程王长元 晋惠 等编著 地图3 操作系统原理 孟庆昌 等编著 机械工业附录：源程序清单：#include <iostream.h>#define M 10 / #define N 50 /资源类数进程数void Input(); /用于输入的函

15、数void Print(); /用于打印输出表格的函数void tryfenpei(int i);/试分配函数void checksafe(int x);/安全检测函数void refenpei(int i);/恢复数据函数/ 定义初始化数组int AvailableM,MaxNM,int c,t;/资源进程int in;/用户选择的进程号/*-*/void main( )int choice;char ch='Y'cout<<" 输入资源数： "cin>>c;cout<<" 输入进程数： "cin&g

16、t;>t;doif(ch='Y'|ch='y')cout<<" 银行家算法 "<<endl;cout<<"1: 输入所需数据"<<endl;cout<<"2: 显示矩阵"<<endl;cout<<"3: 试分配"<<endl;cout<<"4: 检查安全性"<<endl;cout<<"5: 恢复数据到初始状态"

17、;<<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<<"

18、该进程不存在 , 重新输入 "<<endl;else break;tryfenpei(in);/break;case 4: checksafe(in);/break;case 5: refenpei(in);/break;default: cout<<"请(1-5)break;试分配安全性检查恢复数据中选择正确的操作序号!"<<endl;cout<<" 要继续进行吗 ?（ y- 是 n 否） "else if(ch='N'|ch='n')cout<<&q

19、uot; 正在退出 ."<<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(ci

20、n>>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 br

21、eak;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;/*-输入函

22、数结束-*/*-*/void Print()输出函数int i,j;cout<<"|*|*|*|*|*|"<<endl;cout<<"|*|"<<endl;cout<<"|进程 |"<<endl;|Max| Allocation |Need| Availablecout<<"|*|*|*|*|*|"<<endl;for(i=0;i<t;i+)cout<<"| p"<<i&

23、lt;<" | "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+)c

24、out<<Availablej<<""cout<<"| "if(i>0)cout<<"|"cout<<endl;cout<<"|*|*|*|*|*|"<<endl;/*-*/输出函数结束/*- -*/ void tryfenpei(int n) 试分配函数int i;cout<<" 您输入的是 "<<"p"<<n<<""

25、<<" 进程 "<<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 (R

26、equesti>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

27、;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+)Work