《银行家算法的模拟实现》
--实验报告
题目: 银行家算法的模拟实现
专业:
班级:
组员:
指导老师:
一、实验目的
死锁会引起计算机工作僵死，因此操作系统中必须防止。本实验的目的在于让学生独立的使用高级语言编写和调试一个系统动态分配资源的简单模拟程序，了解死锁产生的条件和原因，并采用银行家算法有效地防止死锁的发生，以加深对课堂上所讲授的知识的理解。
二、实验内容
模拟实现银行家算法实现死锁避免。要求：初始数据（如系统在T0时刻的资源分配情况、每一种资源的总数量）从文本文件读入，文件中给出最大需求矩阵Max、分配矩阵Allocation，在程序中求得需求矩阵Need和可利用资源向量Available。
三、实验分析过程
1、整个银行家算法的思路。
先对用户提出的请求进行合法性检查，再进行预分配，利用安全性检查算法进行安全性检查。
1)进程一开始向系统提出最大需求量.
2)进程每次提出新的需求(分期贷款)都统计是否超出它事先提出的最大需求量.
3)若正常,则判断该进程所需剩余剩余量(包括本次申请)是否超出系统所掌握的
剩余资源量,若不超出,则分配,否则等待
2、算法用到的主要数据结构和C语言说明。
（1）、可利用资源向量INT AVAILABLE[M] M为资源的类型。
（2）、最大需求矩阵INT MAX[N][M] N为进程的数量。
（3）、已分配矩阵INT ALLOCATION[N][M]
（4）、还需求矩阵INT NEED[N][N]
（5）、申请各类资源数量int Request[x]; //
（6）、工作向量int Work[x];
（7）、int Finish[y]; //表示系统是否有足够的资源分配给进程，0为否，非0为是
3、银行家算法（主程序）
（1）、系统初始化。输入进程数量，资源种类，各进程已分配、还需求各资源数量，各资源可用数量等
（2）、输入用户的请求三元组（I，J，K），为进程I申请K个J类资源。
（3）、检查用户的请求是否小于还需求的数量，条件是K<=NEED[I,J]。如果条件不符则提示重新输入，即不允许索取大于需求量
（4）、检查用户的请求是否小于系统中的可利用资源数量，条件是K<=AVALIABLE[I,J]。
如果条件不符则申请失败，阻塞该进程，重新进行进程动态资源申请（使用goto 语句）
（5）、进行资源的预分配，语句如下：
AVALIBLE[I][J]= AVALIBLE[I][J]-K；
ALLOCATION[I][J]= ALLOCATION[I][J]+K；
NEED[I][J]=NEED[I][J]-K；
（6）、系统调用安全性检查算法（checksafe()函数）进行检查，如果检查通过，则不用回收，否则进行回收，进程资源申请失败进入等待。
4、安全性检查算法（checksafe()子函数）
（1）、设置两个临时变量。
FINISH[N]记录进程模拟执行的结束状态，初值为0，如果可以模拟执行结束，则可设为1，也可设为其它非零值以表示执行的先后次序。
WORK[M]记录模拟执行中资源的回收情况，初值为AVAILABLE[M]的值。（2）、在进程中查找符合以下条件的进程。
条件1：FINISH[I]=0
条件2：NEED[I][J]〈=WORK[J]
（3）、如果查找成功则进行资源的模拟回收，语句如下：
WORK[J]=WORK[J]+ALLOCATION[I][J]；
FINISH[I]=1 或查找到的顺序号
（4）、如果查找不成功，则检查所有进程的FINISH[]，如果有一个为0，则系统不为0，返回不成功标志。否则返回成功标志。
四、系统流程图
五、程序源代码
#include
#include
#include
const 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 temp[t];
int work[c];
//定义初始化数组
int need[t][c],request[c],available[c];
int max[t][c]={3, 5, 7 ,9 ,11,6 ,8 ,2 ,9, 5,6 ,3 ,5 ,7 ,4};
int allocation[t][c]={1 ,2 ,5 ,4, 8,5 ,4, 1 ,8 ,3 ,3 ,2 ,4, 3, 1}; int total[c]={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;i { for(int j=0;j need[i][j]=max[i][j]-allocation[i][j]; } for( m=0;m { a=0; for(int l=0;l a+=allocation[l][m]; available[m]=total[m]-a; } do { if(ch=='Y'||ch=='y') { cout<<"ok,现在开始进入实验……"< cout<<"请输入需要请求的进程号(0-4):"; while(cin>>in) { if(!(0<=in&&in<=4)) { cout<<"这里没有该进程，请重新输入～"< } else break; } cout<<"您输入的是"<<"p["< for(i=0;i { need[in][i]=max[in][i]-allocation[in][i]; cout< cout< cout< cout<<"请输入请求资源向量:";//输入格式为ｘ for(i=0;i { while(cin>>request[i]) { if(request[i]<0) cout<<"sorry,输入的数字无效～"< else if(request[i]>need[in][i]) cout<<"超出进程需求量～"< if(request[i]>available[i]) cout<<"系统没有足够多的可用资源量满足进程需要～"< else break; } } cout<<"输入成功～，您输入的是："< < cout<<"等待已久的银行家算法开始执行～"< tryfenpei(in);//分配函数 cout<<"试分配完成～"< cout<<"现在进入安全性检测……"< checksafe(in);//安全性检测函数 cout<<"您还想继续银行家算法的实验吗～？（y－继续n终止）"; } else if(ch=='N'||ch=='n') { cout<<"感谢您的使用，Bye～"< break; } else cout<<"输出无效！请重新输入"< } while (cin>>ch); return 0; } /*-------输出函数-------*/ void print() { int i,j; cout<<"更新数据中..."< cout<<"|-------|------------|-----------|----------|-----------|"< cout<<"|-------|最大需求矩阵|已分配矩阵-|-需求矩阵-|可利用资源-|"< cout<<"| 资源| Max | Allocation| Need | available |"< cout<<"| | A B C | A B C | A B C | A B C |"< cout<<"|进程| | | | |"< cout<<"|-------|------------|-----------|----------|-----------|"< for(i=0;i<5;i++) { cout<<"| p"< for(j=0;j<3;j++) { cout< cout<<" | "; for(j=0;j<3;j++) { cout<<" "< cout<<" | "; for(j=0;j<3;j++) { cout<<" "< cout<<" |"; if(i==0) { for(j=0;j<3;j++) { cout<<" "< cout<<" |"; } if(i>0) {cout<<" |"; } cout< cout<<"|-------|------------|-----------|----------|-----------|"< /*--------试分配函数-------*/ void tryfenpei(int i) { for(int f=0;f { available[f]=available[f]-request[f]; allocation[i][f]=allocation[i][f]+request[f]; need[i][f]=need[i][f]-request[f]; } } /*--------恢复数据函数-------*/ void refenpei(int i) { for(int f=0;f { available[f]=available[f]+request[f]; allocation[i][f]=allocation[i][f]-request[f]; need[i][f]=need[i][f]+request[f]; } } int com(int *p,int *q) { int i; for(i=0;i if(p[i]>q[i]) return 0; return 1; } /*--------安全检测函数---------*/ void checksafe(int s) { int flag,temp[t],i,j,l,k=0; bool finish[t]; for(i=0;i finish[i]=false; for(j=0;j work[j]=available[j]; cout<<"|-------|-----------------|----------|"< cout<<"| resource |-Work+Allocation-|--Finish--|"< cout<<"| | A B C | T/F |"< cout<<"|programme | | |"< cout<<"|-------|-----------------|----------|"< for(i=0;i { l=0; for(j=0;j { if(need[i][j]>work[j]) l=1; break; } if(finish[i]==false&&l==0) { cout<<"| p"< for(j=0;j { work[j]=work[j]+allocation[i][j]; if(work[j]>9) cout<<" "< else cout<<" "< } cout<<" "; cout<<"|"; cout<<" "; finish[i]=true; cout<<"true "; cout<<"|"; temp[k]=i;//cout<<'temp="< k++; i=-1; //从用户选择的进程开始对每个进程都要检测 cout< } } cout<<"|-------|-----------------|----------|"< { if(finish[i]==false) flag=1; if(flag==1) { cout<<"系统不安全！本次资源申请不成功感！"< cout<<"正在恢复原来的数据..."< refenpei(in); cout<<"恢复数据成功!正在打印输出..."< print(); } else { cout<<"找到一个安全系列："; for(i=0;i cout<<"P"< cout< cout<<"开始给第"<<"p]"< cout<<"分配完成!打印输出..."< print(); cout< } } } 五、程序运行结果及分析 1、运行结果 输入初值，进行安全性测试，结果安全序列，依次为P4-P0-P1-P2-P3分配资源： 资源不足，无法继续实验： 2、出现问题及解决方案 本程序考虑了程序功能实现、格式显示合理化、输入错误异常处理等各个方面的设计，尽可能使程序设计的更加完美。在长期的设计调试过程中遇到过许多问题，通过网上搜索、查询资料、调试试验等方法一一解决。下面大致罗列一些主要问题：（1）、关于某些判断算法优劣问题： 在程序中很多地方都会用到循环判断是否符合条件的算法，在设计这些算法时有很多方法，而有的算法可以更节省时间。如下安全性算法中寻找寻找符合Finish[i]==0条件的进程的例子： /* 算法一： for (j=0; j if (Work[j]>=Need[i][j]) counter=counter+1;//记数 if(counter==m){… */ //算法二： for (j=0; j if (Work[j]>=Need[i][j]); //可用大于等于需求 else{ counter=1; break; } if(counter!=1){… 显然算法二要优于算法一。本程序中还有很多类似的地方。这里主要考虑的是一个程序的优化设计问题。 （2）、关于某些系统函数调用时的执行顺序： 在调用一些系统函数如getch() 、system("pause")等时发现其执行顺序的一些问题。如类似： cout<<" =================================="< cout<<" \n\n\n"< system("pause");//暂停 调试时发现此时：在Microsoft Visual C++ 6.0中先执行system("pause") 再输出显示，而在调试器Bloodshed Dev-C++中则顺序执行；但当把cout<<" \n\n\n"< 查找了一下相关帮助： 在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; cin>>tt; 方式，要求键盘输入一个与程序无关的变量 六、心得体会 “银行家算法的模拟实现”是本学期操作系统课程唯一的课程设计。在设计此程序的过程中，我们遇到过许多问题，也学到了很多东西。本程序的设计实现主要是用C++语言实现，通过对程序算法的设计优化、输出显示的格式设计、输入过程中的异常处理等一些设计过程中的问题的考虑解决，在C++学习上也有了很大的进步。程序设计过程中开始遇到的最大的问题是算法的结构设计问题，课本上只给了设计要求及简单的算法，要真正实现还
相关主题
文本预览