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

《银行家算法的模拟实现》--实验报告题目:银行家算法的模拟实现专业:班级:组员:指导老师:一、实验目的死锁会引起计算机工作僵死，因此操作系统中必须防止。本实验的目的在于让学生独立的使用高级语言编写和调试一个系统动态分配资源的简单模拟程序，了解死锁产生的条件和原因，并采用银行家算法有效地防止死锁的发生，以加深对课堂上所讲授的知识的理解。二、实验内容模拟实现银行家算法实现死锁避免。要求：初始数据（如系统在T0时刻的资源分配情况、每一种资源的总数量）从文本文件读入，文件中给出最大需求矩阵Max、分配矩阵Allocation，在程序中求得需求矩阵Need和可利用资源向量Available。三、实验分析过程1、整个银行家算法的思路。先对用户提出的请求进行合法性检查，再进行预分配，利用安全性检查算法进行安全性检查。1)进程一开始向系统提出最大需求量.2)进程每次提出新的需求(分期贷款)都统计是否超出它事先提出的最大需求量.3)若正常,则判断该进程所需剩余剩余量(包括本次申请)是否超出系统所掌握的剩余资源量,若不超出,则分配,否则等待2、算法用到的主要数据结构和C语言说明。（1）、可利用资源向量INTAVAILABLE[M]M为资源的类型。（2）、最大需求矩阵INTMAX[N][M]N为进程的数量。（3）、已分配矩阵INTALLOCATION[N][M]（4）、还需求矩阵INTNEED[N][N]（5）、申请各类资源数量intRequest[x];//（6）、工作向量intWork[x];（7）、intFinish[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，返回不成功标志。否则返回成功标志。四、系统流程图五、程序源代码#includeiostream.h#includestdio.h#includestdlib.hconstunsignedshortc=3;//资源类数constunsignedshortt=5;//进程数voidprint();//用于打印输出表格的函数voidinput();//用于输入的函数voidtryfenpei(inti);//试分配函数；voidrefenpei(inti);//恢复数据函数voidchecksafe(ints);//安全检测函数inttemp[t];intwork[c];开始输入资源数m,及各类资源总数，初始化Available向量输入进程数n，i=1输入进程i的最大需求向量max。i≤nmax≤资源总数提示错误重新输入i加1任选一个进程作为当前进程输入该进程的资源请求量Request调用银行家算法，及安全性算法，完成分配，或并给出提示该进程的Need向量为0该进程已运行结束Need矩阵为0所有进程运行都结束结束NYYNNY初始化need矩阵NY//定义初始化数组intneed[t][c],request[c],available[c];intmax[t][c]={3,5,7,9,11,6,8,2,9,5,6,3,5,7,4};intallocation[t][c]={1,2,5,4,8,5,4,1,8,3,3,2,4,3,1};inttotal[c]={17,21,25};intin;//用户选择的进程号/*------------------main函数-----------------------------*/intmain(intargc,char*argv[]){inti;charch='Y';intl=0,m=0,a;for(i=0;it;i++){for(intj=0;jc;j++)need[i][j]=max[i][j]-allocation[i][j];}for(m=0;mc;m++){a=0;for(intl=0;lt;l++)a+=allocation[l][m];available[m]=total[m]-a;}do{if(ch=='Y'||ch=='y'){coutok,现在开始进入实验……endl;cout请输入需要请求的进程号(0-4):;while(cinin){if(!(0=in&&in=4)){cout这里没有该进程，请重新输入～endl;}elsebreak;}cout您输入的是p[in]进程endl;cout该进程需求量为：;for(i=0;ic;i++){need[in][i]=max[in][i]-allocation[in][i];coutneed[in][i];}coutendl;coutendl;cout请输入请求资源向量:;//输入格式为ｘfor(i=0;ic;i++){while(cinrequest[i]){if(request[i]0)coutsorry,输入的数字无效～endl;elseif(request[i]need[in][i])cout超出进程需求量～endlendl;if(request[i]available[i])cout系统没有足够多的可用资源量满足进程需要～endlendl;elsebreak;}}cout输入成功～，您输入的是：request[0]request[1]request[2];cout等待已久的银行家算法开始执行～endl;tryfenpei(in);//分配函数cout试分配完成～endl;cout现在进入安全性检测……endl;checksafe(in);//安全性检测函数cout您还想继续银行家算法的实验吗～？（y－继续n终止）;}elseif(ch=='N'||ch=='n'){cout感谢您的使用，Bye～endl退出ing……endl;break;}elsecout输出无效！请重新输入endl;}while(cinch);return0;}/*-------输出函数-------*/voidprint(){inti,j;cout更新数据中...endl;cout|-------|------------|-----------|----------|-----------|endl;cout|-------|最大需求矩阵|已分配矩阵-|-需求矩阵-|可利用资源-|endl;cout|资源|Max|Allocation|Need|available|endl;cout||ABC|ABC|ABC|ABC|endl;cout|进程|||||endl;cout|-------|------------|-----------|----------|-----------|endl;for(i=0;i5;i++){cout|pi|;for(j=0;j3;j++){coutmax[i][j];}cout|;for(j=0;j3;j++){coutallocation[i][j];}cout|;for(j=0;j3;j++){coutneed[i][j];}cout|;if(i==0){for(j=0;j3;j++){coutavailable[j];}cout|;}if(i0){cout|;}coutendl;}cout|-------|------------|-----------|----------|-----------|endl;}/*--------试分配函数-------*/voidtryfenpei(inti){for(intf=0;fc;f++){available[f]=available[f]-request[f];allocation[i][f]=allocation[i][f]+request[f];need[i][f]=need[i][f]-request[f];}}/*--------恢复数据函数-------*/voidrefenpei(inti){for(intf=0;fc;f++){available[f]=available[f]+request[f];allocation[i][f]=allocation[i][f]-request[f];need[i][f]=need[i][f]+request[f];}}intcom(int*p,int*q){inti;for(i=0;ic;i++)if(p[i]q[i])return0;return1;}/*--------安全检测函数---------*/voidchecksafe(ints){intflag,temp[t],i,j,l,k=0;boolfinish[t];for(i=0;it;i++)finish[i]=false;for(j=0;jc;j++)work[j]=available[j];cout|-------|-----------------|----------|endl;cout|resource|-Work+Allocation-|--Finish--|endl;cout||ABC|T/F|endl;cout|programme|||endl;cout|-------|-----------------|----------|endl;for(i=0;it;i++){l=0;for(j=0;jc;j++){if(need[i][j]work[j])l=1;break;}if(finish[i]==false&&l==0){cout|pi|;for(j=0;jc;j++){work[j]=work[j]+allocation[i][j];if(work[j]9)coutwork[j];elsecoutwork[j];}cout;cout|;cout;finish[i]=true;couttrue;cout|;temp[k