《银行家算法的模拟实现》—实验报告

银行家算法的模拟实现 -实验报告题 目: 银行家算法的模拟实现 专 业: 班 级: 组 员: 指导老师: 一、实验目的死锁会引起计算机工作僵死，因此操作系统中必须防止。本实验的目的在于让学生独立的使用高级语言编写和调试一个系统动态分配资源的简单模拟程序，了解死锁产生的条件和原因，并采用银行家算法有效地防止死锁的发生，以加深对课堂上所讲授的知识的理解。二、实验内容模拟实现银行家算法实现死锁避免。要求：初始数据（如系统在T0时刻的资源分配情况、每一种资源的总数量）从文本文件读入，文件中给出最大需求矩阵Max、分配矩阵Allocation，在程序中求得需求矩阵Need和可利用资源向量Available。三、实验分析过程1、整个银行家算法的思路。 先对用户提出的请求进行合法性检查，再进行预分配，利用安全性检查算法进行安全性检查。1)进程一开始向系统提出最大需求量.2)进程每次提出新的需求(分期贷款)都统计是否超出它事先提出的最大需求量.3)若正常,则判断该进程所需剩余剩余量(包括本次申请)是否超出系统所掌握的剩余资源量,若不超出,则分配,否则等待2、算法用到的主要数据结构和C语言说明。 （1）、可利用资源向量 INT AVAILABLEM M为资源的类型。 （2）、最大需求矩阵 INT MAXNM N为进程的数量。 （3）、已分配矩阵 INT ALLOCATIONNM （4）、还需求矩阵 INT NEEDNN （5）、申请各类资源数量int Requestx; / （6）、工作向量 int Workx; （7）、int Finishy; /表示系统是否有足够的资源分配给进程，0为否，非0为是3、银行家算法 （主程序） （1）、系统初始化。输入进程数量，资源种类，各进程已分配、还需求各资源数量，各资源可用数量等 （2）、输入用户的请求三元组（I，J，K），为进程I申请K个J类资源。 （3）、检查用户的请求是否小于还需求的数量，条件是 K=NEEDI,J。如果条件不符则提示重新输入，即不允许索取大于需求量 （4）、检查用户的请求是否小于系统中的可利用资源数量，条件是K=AVALIABLEI,J。如果条件不符则申请失败，阻塞该进程，重新进行进程动态资源申请（使用goto语句） （5）、进行资源的预分配，语句如下： AVALIBLEIJ= AVALIBLEIJ-K； ALLOCATIONIJ= ALLOCATIONIJ+K； NEEDIJ=NEEDIJ-K； （6）、系统调用安全性检查算法（checksafe()函数）进行检查，如果检查通过，则不用回收，否则进行回收，进程资源申请失败进入等待。4、安全性检查算法（checksafe()子函数） （1）、设置两个临时变量。 FINISHN记录进程模拟执行的结束状态，初值为0，如果可以模拟执行结束，则可设为1，也可设为其它非零值以表示执行的先后次序。 WORKM记录模拟执行中资源的回收情况，初值为AVAILABLEM的值。 （2）、在进程中查找符合以下条件的进程。 条件1：FINISHI=0 条件2：NEEDIJ=WORKJ （3）、如果查找成功则进行资源的模拟回收，语句如下： WORKJ=WORKJ+ALLOCATIONIJ； FINISHI=1 或查找到的顺序号（4）、如果查找不成功，则检查所有进程的FINISH，如果有一个为0，则系统不为0，返回不成功标志。否则返回成功标志。四、系统流程图开 始输入资源数m, 及各类资源总数，初始化Available向量输入进程数n，i=1输入进程i的最大需求向量max。inmax资源总数提示错误重新输入i加1任选一个进程作为当前进程输入该进程的资源请求量Request 调用银行家算法，及安全性算法，完成分配，或并给出提示该进程的Need向量为0该进程已运行结束Need矩阵为0所有进程运行都结束结 束NYYNNY初始化need 矩阵NY五、程序源代码#include #include#includeconst unsigned short c=3;/资源类数const unsigned short t=5;/进程数void print();/用于打印输出表格的函数void input();/用于输入的函数void tryfenpei(int i);/试分配函数；void refenpei(int i);/恢复数据函数void checksafe(int s);/安全检测函数int tempt;int workc;/定义初始化数组int needtc,requestc,availablec;int maxtc=3, 5, 7 ,9 ,11,6 ,8 ,2 ,9, 5,6 ,3 ,5 ,7 ,4;int allocationtc=1 ,2 ,5 ,4, 8,5 ,4, 1 ,8 ,3 ,3 ,2 ,4, 3, 1;int totalc=17,21,25;int in;/用户选择的进程号/*-main函数-*/int main(int argc,char *argv)int i;char ch=Y;int l=0,m=0,a;for( i=0;it;i+)for(int j=0;jc;j+)needij=maxij-allocationij;for( m=0;mc;m+)a=0;for(int l=0;lt;l+)a+=allocationlm;availablem=totalm-a;do if(ch=Y|ch=y)coutok,现在开始进入实验endl; coutin)if(!(0=in&in=4)cout这里没有该进程，请重新输入endl;else break;cout您输入的是 pin 进程endl;cout该进程需求量为： ;for(i=0;ic;i+)needini=maxini-allocationini;coutneedini ;coutendl;coutendl;cout请输入请求资源向量:;/输入格式为for(i=0;irequesti)if(requesti0) coutsorry,输入的数字无效needini) cout超出进程需求量endlavailablei) cout系统没有足够多的可用资源量满足进程需要endlendl; else break; cout输入成功，您输入的是：request0 request1 request2; cout等待已久的银行家算法开始执行endl; tryfenpei(in);/分配函数 cout试分配完成endl; cout现在进入安全性检测endl; checksafe(in);/安全性检测函数 cout您还想继续银行家算法的实验吗？（y继续n终止）; else if(ch=N|ch=n) cout感谢您的使用，Byeendl退出ingendl; break; else cout输出无效！请重新输入ch);return 0;/*-输出函数-*/void print()int i,j;cout更新数据中.endl;cout|-|-|-|-|-|endl;cout|-|最大需求矩阵|已分配矩阵-|-需求矩阵-|可利用资源-|endl;cout| 资源 | Max | Allocation| Need | available |endl;cout| | A B C | A B C | A B C | A B C |endl;cout|进程 | | | | |endl;cout|-|-|-|-|-|endl;for(i=0;i5;i+)cout| pi | ;for(j=0;j3;j+) coutmaxij ; cout | ;for(j=0;j3;j+) cout allocationij; cout | ;for(j=0;j3;j+) cout needij; cout |; if(i=0) for(j=0;j3;j+) cout availablej; cout0)cout |; coutendl; cout|-|-|-|-|-|endl;/*-试分配函数-*/void tryfenpei(int i)for(int f=0;fc;f+)availablef=availablef-requestf;allocationif=allocationif+requestf;needif=needif-requestf;/*-恢复数据函数-*/void refenpei(int i)for(int f=0;fc;f+)availablef=availablef+requestf;allocationif=allocationif-requestf;needif=needif+requestf;int com(int *p,int *q)int i;for(i=0;iqi)return 0;return 1;/*-安全检测函数-*/void checksafe(int s)int flag,tempt,i,j,l,k=0;bool finisht;for(i=0;it;i+)finishi=false;for(j=0;jc;j+)workj=availablej;cout|-|-|-|endl;cout| resource |-Work+Allocation-|-Finish-|endl;cout| | A B C | T/F |endl;cout|programme | | |endl;cout|-|-|-|endl;for(i=0;it;i+)l=0;for(j=0;jworkj)l=1;break;if(finishi=false&l=0)cout| pi | ;for(j=0;j9)cout workj ; elsecout workj ;cout ;cout|;cout ;finishi=true;couttrue ;cout|;tempk=i;/couttemp=tempkendl;k+;i=-1; /从用户选择的进程开始对每个进程都要检测coutendl; cout|-|-|-|endlendl;for(i=0;it;i+)if(finishi=false)flag=1;if(flag=1)cout系统不安全！本次资源申请不成功感！endl;cout正在恢复原来的数据.endl;refenpei(in);cout恢复数据成功!正在打印输出.endl;print();elsecout找到一个安全系列：;for(i=0;it;i+)coutPtempi;coutendl已通过安全性测试!endlendlendl;cout开始给第pin进程分配资源.endl;cout分配完成!打印输出.endlendl;print();coutendl;五、程序运行结果及分析1、运行结果输入初值，进行安全性测试，结果安全序列，依次为P4-P0-P1-P2-P3分配资源： 资源不足，无法继续实验：2、出现问题及解决方案本程序考虑了程序功能实现、格式显示合理化、输入错误异常处理等各个方面的设计，尽可能使程序设计的更加完美。在长期的设计调试过程中遇到过许多问题，通过网上搜索、查询资料、调试试验等方法一一解决。下面大致罗列一些主要问题：（1）、关于某些判断算法优劣问题：在程序中很多地方都会用到循环判断是否符合条件的算法，在设计这些算法时有很多方法，而有的算法可以更节省时间。如下安全性算法中寻找寻找符合Finishi=0条件的进程的例子：/* 算法一： for (j=0; j=Needij) counter=counter+1;/记数 if(counter=m)*/ /算法二： for (j=0; j=Needij); /可用大于等于需求 else counter=1; break; if(counter!=1)显然算法二要优于算法一。本程序中还有很多类似的地方。这里主要考虑的是一个程序的优化设计问题。（2）、关于某些系统函数调用时的执行顺序：在调用一些系统函数如getch() 、system(pause)等时发现其执行顺序的一些问题。如类似：cout =endl;cout nnnendl;system(pause);/暂停调试时发现此时：在Microsoft Visual C+ 6.0中先执行system(pause) 再输出显示，而在调试器Bloodshed Dev-C+中则顺序执行；但当把cout nnnendl; 改为 coutendlendlendl; 其他不变时，则在两中调试器中均为顺序执行，即先显示后暂停。查找了一下相关帮助： 在OSTREAM.H中有这样的一个inline函数： inline _CRTIMP ostream& _cdecl endl(ostream& _outs) return _outs n flush; 。也就是说 endl= return _outs n flush; endl除了写n进外，还调用flush函数，刷新缓冲区，把缓冲区里的数据写入文件或屏幕。如果考虑效率就用n（3）、关于设置暂停的方法：在有些地方需要暂停一下以便于用户查看信息等，总结了下大致可用以下几中方法：方法一：#include system(pause);/暂停一下并显示“输入任意键继续”方法二：#include getchar();/须按回车键结束，不是任意键方法三：#include getch();/等待键盘输入，不返回任何值，无任何显示方法四：使用 char* tt=new char; cintt; 方式，要求键盘输入一个与程序无关的变量六、心得体会 “银行家算法的模拟实现”是本学期操作系统课