(完整word版)《银行家算法的模拟实现》—实验报告

1、银行家算法的模拟实现-实验报告题目：银行家算法的模拟实现专业:_班级：组员:_指导老师：、实验目的死锁会引起计算机工作僵死， 因此操作系统中必须防止。 本实验的目的在于让学生独立 的使用高级语言编写和调试一个系统动态分配资源的简单模拟程序， 了解死锁产生的条件和原因，并采用银行家算法有效地防止死锁的发生，以加深对课堂上所讲授的知识的理解。二、实验内容模拟实现银行家算法实现死锁避免。要求：初始数据（如系统在 T0 时刻的资源分配情 况、每一种资源的总数量）从文本文件读入，文件中给出最大需求矩阵Max 、分配矩阵Allocation ，在程序中求得需求矩阵 Need 和可利用资源向量 Availa

2、ble 。三、实验分析过程1、整个银行家算法的思路。先对用户提出的请求进行合法性检查， 再进行预分配， 利用安全性检查算法进行安全性检 查。1）进程一开始向系统提出最大需求量 .2）进程每次提出新的需求 （分期贷款 ）都统计是否超出它事先提出的最大需求量.3）若正常 ,则判断该进程所需剩余剩余量 （包括本次申请 ） 是否超出系统所掌握的 剩余资源量 ,若不超出 ,则分配 ,否则等待 2、算法用到的主要数据结构和 C 语言说明。1）、可利用资源向量2）、最大需求矩阵3）、已分配矩阵4）、还需求矩阵 5）、申请各类资源数量 6）、工作向量INT AVAILABLEM M 为资源的类型。INT MA

3、XNM N 为进程的数量。INT ALLOCA TIONNMINT NEEDNN int Requestx; / int Workx;0 为否，非 0 为是7）、 int Finishy; / 表示系统是否有足够的资源分配给进程，3、银行家算法 （主程序） （1）、系统初始化。输入进程数量，资源种类，各进程已分配、还需求各资源数量，各资 源可用数量等（2 ）、输入用户的请求三元组（I, J, K）,为进程I申请K个J类资源。（ 3）、检查用户的请求是否小于还需求的数量，条件是 K=NEEDI,J 。如果条件不符则 提示重新输入，即不允许索取大于需求量（ 4）、检查用户的请求是否小于系统中的可利

4、用资源数量，条件是 K=AVALIABLEI,J 。 如果条件不符则申请失败，阻塞该进程，重新进行进程动态资源申请（使用goto 语句）（ 5）、进行资源的预分配，语句如下： AVALIBLEIJ= A VALIBLEIJ-K ； ALLOCATIONIJ= ALLOCATIONIJ+K ； NEEDIJ=NEEDIJ-K ；6）、系统调用安全性检查算法（ checksafe（） 函数）进行检查，如果检查通过，则不用回 收，否则进行回收，进程资源申请失败进入等待。4、安全性检查算法（checksafe（）子函数）（ 1 ）、设置两个临时变量。FINISHN 记录进程模拟执行的结束状态，初值为0

5、，如果可以模拟执行结束，则可设为 1，也可设为其它非零值以表示执行的先后次序。WORKM 记录模拟执行中资源的回收情况，初值为 AVAILABLEM 的值。（ 2）、在进程中查找符合以下条件的进程。条件 1： FINISHI=0条件 2： NEEDIJ =WORKJ（ 3）、如果查找成功则进行资源的模拟回收，语句如下：WORKJ=WORKJ+ALLOCA TIONIJ ；FINISHI=1 或查找到的顺序号（ 4 ） 、如果查找不成功，则检查所有进程的FINISH ，如果有一个为 0，则系统不为 0，返回不成功标志。否则返回成功标志。四、系统流程图五、程序源代码#in elude #in cl

6、ude#in cludeconst unsigned short c=3; 资源类数 const un sig ned 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 ,

7、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+=allocation

8、lm;availablem=totalm-a;do if(ch=Y|ch=y)coutok,现在开始进入实验endl;coutin)if(!(0=in&in=4)endl;cout这里没有该进程，请重新输入else break;cout 您输入的是 pin 进程 endl;cout 该进程需求量为： ;for(i=0;ic;i+) needini=maxini-allocationini; coutneedini ;coutendl;coutendl;cout请输入请求资源向量：;/输入格式为Xfor(i=0;irequesti)if(requesti0) coutsorry,输入的数字无效n

9、eedini) cout 超出进程需求量 endlavailablei)cout 系 统 没 有 足 够 多 的 可 用 资 源 量 满 足 进 程 需 要 endlendl;else break;cout 输入成功，您输入的是： request0request1 request2;cout 等待已久的银行家算法开始执行 endl;tryfenpei(in);/ 分配函数cout 试分配完成 endl;cout现在进入安全性检测e ndl;checksafe(i n);安全性检测函数cout您还想继续银行家算法的实验吗？(y 继续n终止);else if(ch=N|ch=n)cout感谢您的使

10、用，Bye endl退出 ingendl;break;elsecout 输出无效！请重新输入 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+)

11、cout| pi | ;for(j=0;j3;j+) coutmaxij ; cout | ;for(j=0;j3;j+) cout allocationij; cout | ;for(j=0;j3;j+) cout needij; coutfor(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+reque

12、stf; 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;f

13、or(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;co

14、ut ;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;

15、i+)coutPtempi; coutendl 已通过安全性测试 !endlendlendl; cout 开始给第 pin 进程分配资源 .endl; cout 分配完成 ! 打印输出 .endlendl;print();cout哼 帑t4为 &L请P量LLE5resoupceT/F! pro granwrie*-Work+fillocation-!Fin ih! B C134S:4口王口王4:1的 源您 资* 求俭女 请宜元入一 入成配进 臾分在一JM3 检 性 全4 3等待已久的银行家算法开始执行-i:575!1 tpue !JE910 :true!: 101?15*true1141823

16、!true! 1?21251trueIP4 p0 pl p2 p3资源不足，无法继续实验:(卯-继续n终止)*乍厶吗: 验-4 实0 的-号 法潜无审 算甯进5 家话1 : 番需 想嘖入程还- 您ok请谖口王口王3紧鮒尊欝鸚扁嘉量满足进程需要系统没有足够多的可用资源量满足进程需要系统役有足够多的可用资源量满足进程需要2、出现问题及解决方案本程序考虑了程序功能实现、格式显示合理化、输入错误异常处理等各个方面的设 计，尽可能使程序设计的更加完美。在长期的设计调试过程中遇到过许多问题，通过网 上搜索、查询资料、调试试验等方法一一解决。下面大致罗列一些主要问题：(1 )、关于某些判断算法优劣问题：在程

17、序中很多地方都会用到循环判断是否符合条件的算法，在设计这些算法时 有很多方法，而有的算法可以更节省时间。如下安全性算法中寻找寻找符合Finishi=O条件的进程的例子:/*算法一:for (j=0; j=Needij) coun ter=cou nter+1;记数if(co un ter=m)*/ /算法二：for (j=0; j=Needij); /可用大于等于需求elsecoun ter=1;break;if(coun ter!=1)显然算法二要优于算法一。本程序中还有很多类似的地方。这里主要考虑的是一个程序的优化设计问题。(2)、关于某些系统函数调用时的执行顺序：在调用一些系统函数如ge

18、tch()、system(pause)等时发现其执行顺序的一些问题。如类似：cout =e ndl;cout nnnen dl; system(pause); 暂停调试时发现此时：在Microsoft Visual C+ 6.0中先执行system(pause)再输出显 示，而在调试器 Bloodshed Dev-C+中则顺序执行；但当把 cout nnne ndl;改 为coutendlendlendl;其他不变时，则在两中调试器中均为顺序执行，即先显 示后暂停。查找了一下相关帮助：在 OSTREAM.H 中有这样的一个 inline 函数：inline _CRTIMP ostream& _

19、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; 方式，要求键盘输入一个与程序无关的变量六、心得体会“银行家算法的模拟实现”是本学期操作系统课程唯一的课程设计。在设计此程序的过