1、银行家算法c+语言流程图代码全操作系统教程 银行家算法院 系计算机与软件学院班 级08软件工程2班学 号20081344066姓 名何丽茗一、实验目的银行家算法是避免死锁的一种重要方法。通过编写一个模拟动态资源分配的银行家算法程序,进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念,并掌握避免死锁的具体实施方法。二、实验内容根据银行家算法的基本思想,编写和调试一个实现动态资源分配的模拟程序,并能够有效地防止和避免死锁的发生。三、实验方法1.算法流程图 2.算法数据结构1)可利用资源向量Available ,它是一个最多含有100个元素的数组,其中的每一个元素代表一类可利用的资源的数目,
2、其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。如果Available(j)=k,标是系统中现有j类资源k个。2)最大需求矩阵Max,这是一个nm的矩阵,它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max(i,j)=k,表示进程i需要j类资源的最大数目为k。3)分配矩阵Allocation,这也是一个nm的矩阵,它定义了系统中的每类资源当前一分配到每一个进程的资源数。如果Allocation(i,j)=k,表示进程i当前已经分到j类资源的数目为k。Allocation i表示进程i的分配向量,有矩阵Allocation的第i行构成。4)
3、需求矩阵Need,这还是一个nm的矩阵,用以表示每个进程还需要的各类资源的数目。如果Need(i,j)=k,表示进程i还需要j类资源k个,才能完成其任务。Need i表示进程i的需求向量,由矩阵Need的第i行构成。5)上述三个矩阵间存在关系:Need(i,j)=Max(i,j)-Allocation(i,j);3.银行家算法设Requesti 是进程i的请求向量,如果Requesti,j=K,表示进程i需要K个j类型的资源。当i发出资源请求后,系统按下述步骤进行检查:1)如果Request i Need,则转向步骤2;否则,认为出错,因为它所请求的资源数已超过它当前的最大需求量。2)如果Re
4、quest i Available,则转向步骤3;否则,表示系统中尚无足够的资源满足i的申请,i必须等待。3)系统试探性地把资源分配给进程i,并修改下面数据结构中的数值:Available = Available - Request iAllocation i= Allocation i+ Request iNeed i= Need i - Request i4)系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。如果安全才正式将资源分配给进程i,以完成本次分配;否则,将试探分配作废,恢复原来的资源分配状态,让进程i等待。四、实验代码以及运行示例1.源代码:#include#incl
5、ude#include#define False 0#define True 1using namespace std;int Max100100=0;/各进程所需各类资源的最大需求int Avaliable100=0;/系统可用资源char name100=0;/资源的名称int Allocation100100=0;/系统已分配资源int Need100100=0;/还需要资源int Request100=0;/请求资源向量int temp100=0;/存放安全序列int Work100=0;/存放系统可提供资源int M=100;/进程的最大数为int N=100;/资源的最大数为voi
6、d showdata()/显示资源矩阵 int i,j; cout系统目前可用的资源Avaliable:endl; for(i=0;iN;i+) coutnamei ; coutendl; for (j=0;jN;j+) coutAvaliablej ;/输出分配资源 coutendl; cout Max Allocation Needendl; cout进程名 ; for(j=0;j3;j+) for(i=0;iN;i+) coutnamei ; cout ; coutendl; for(i=0;iM;i+) cout i ; for(j=0;jN;j+) coutMaxij ; cout
7、; for(j=0;jN;j+) coutAllocationij ; cout ; for(j=0;jN;j+) coutNeedij ; coutendl; int changdata(int i)/进行资源分配 int j; for (j=0;jM;j+) Avaliablej=Avaliablej-Requestj; Allocationij=Allocationij+Requestj; Needij=Needij-Requestj; return 1;int safe()/安全性算法 int i,k=0,m,apply,Finish100=0; int j; int flag=0;
8、Work0=Avaliable0; Work1=Avaliable1; Work2=Avaliable2; for(i=0;iM;i+) apply=0; for(j=0;jN;j+) if (Finishi=False&Needij=Workj) apply+; if(apply=N) for(m=0;mN;m+) Workm=Workm+Allocationim;/变分配数 Finishi=True; tempk=i; i=-1; k+; flag+; for(i=0;iM;i+) if(Finishi=False) cout系统不安全endl;/不成功系统不安全 return -1; c
9、out系统是安全的!endl;/如果安全,输出成功 cout分配的序列:; for(i=0;iM;i+)/输出运行进程数组 couttempi; if(iM-1) cout; coutendl; return 0;void share()/利用银行家算法对申请资源对进行判定 char ch; int i=0,j=0; ch=y; cout请输入要求分配的资源进程号(0-M-1i;/输入须申请的资源号 cout请输入进程i 申请的资源:endl; for(j=0;jN;j+) coutnamejRequestj;/输入需要申请的资源 for (j=0;jNeedij)/判断申请是否大于需求,若大
10、于则出错 cout进程i申请的资源大于它需要的资源; cout 分配不合理,不予分配!Avaliablej)/判断申请是否大于当前资源,若大于则 /出错 cout进程i申请的资源大于系统现在可利用的资源; cout 分配出错,不予分配!endl; ch=n; break; if(ch=y) changdata(i);/根据进程需求量变换资源 showdata();/根据进程需求量显示变换后的资源 safe();/根据进程需求量进行银行家算法判断 void addresources()/添加资源 int n,flag; coutn; flag=N; N=N+n; for(int i=0;in;i
11、+) coutnameflag; coutAvaliableflag+; showdata(); safe();void delresources()/删除资源 char ming; int i,flag=1; coutming; for(i=0;iN;i+) if(ming=namei) flag=0; break; if(i=N) cout该资源名称不存在,请重新输入:; while(flag); for(int j=i;jN-1;j+) namej=namej+1; Avaliablej=Avaliablej+1; N=N-1; showdata(); safe();void chang
12、eresources()/修改资源函数 cout系统目前可用的资源Avaliable:endl; for(int i=0;iN;i+) coutnamei:Avaliableiendl; cout输入系统可用资源Avaliable:Avaliable0Avaliable1Avaliable2; cout经修改后的系统可用资源为endl; for (int k=0;kN;k+) coutnamek:Avaliablekendl; showdata(); safe();void addprocess()/添加作业 int flag=M; M=M+1; cout请输入该作业的最大需求量Maxendl
13、; for(int i=0;iN;i+) coutnameiMaxflagi; Needflagi=Maxflagi-Allocationflagi; showdata(); safe();int main()/主函数 int i,j,number,choice,m,n,flag; char ming; coutt-endl; coutt| |endl; coutt| 银行家算法的实现 |endl; coutt| |endl; coutt| 08软工何丽茗 |endl; coutt| |endl; coutt| 20081344066 |endl; coutt-endl; coutn; N=n
14、; for(i=0;in;i+) cout资源i+1ming; namei=ming; coutnumber; Avaliablei=number; coutendl; coutm; M=m; cout请输入各进程的最大需求量(m*n矩阵)Max:endl; for(i=0;im;i+) for(j=0;jMaxij; do flag=0; cout请输入各进程已经申请的资源量(m*n矩阵)Allocation:endl; for(i=0;im;i+) for(j=0;jAllocationij; if(AllocationijMaxij) flag=1; Needij=Maxij-Alloc
15、ationij; if(flag) cout申请的资源大于最大需求量,请重新输入!n; while(flag); showdata();/显示各种资源 safe();/用银行家算法判定系统是否安全 while(choice) coutt-银行家算法演示-endl; cout 1:增加资源 endl; cout 2:删除资源 endl; cout 3:修改资源 endl; cout 4:分配资源 endl; cout 5:增加作业 endl; cout 0:离开 endl; coutt-endl; coutchoice; switch(choice) case 1: addresources()
16、;break; case 2: delresources();break; case 3: changeresources();break; case 4: share();break; case 5: addprocess();break; case 0: choice=0;break; default: cout请正确选择功能号(0-5)!endl;break; return 1;2.运行结果:1)初始化状态:2)为进程0分配资源:3)为进程4分配资源:五、实验总结本程序的设计实现主要是用C+语言。程序设计过程中开始遇到的最大的问题是算法的结构设计问题,课本上只给了设计要求及简单的算法,要真正实现还需要考虑很多方面。在程序设计中先后参考了很多网络资料,也参考了一些别人写的的程序,让我彻底认识到自己的不足,也同时从中学到了更多。