操作系统银行家算法设计实现报告.doc

1、银行家算法的模拟实现一、设计目的（1）了解进程产生死锁的原因，了解为什么要进行死锁的避免。（2）掌握银行家算法的数据结构，了解算法的执行过程，加深对银行家算法的理解。二、设计内容编制银行家算法通用程序，并检测所给状态的系统安全性。1.银行家算法中的数据结构：可利用资源向量Available。这是一个含有m个 元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。Availablej=K，则表示系统中现有Rj 类资源K个。最大需求矩阵Max。这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资

2、源的最大需求。如果Maxi，j=K，则表示进程i需要Rj类资源的最大数目为K。分配矩阵Allocation。这也是一个n*m的矩阵，它定义了系统中每一类资源 当前已分配给没一进程的资源数。如果Allocationi，j=K，则表示 进程i当前已分得Rj类资源的数目为K。需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi,j=K，则表示进程i还需要Rj类资源K个，方能完成其任务。上述三个矩阵存在如下关系： Needi,j= Maxi，j- Allocationi，j2.银行家算法设是进程的请求向量，如果j=K，表示进程需要K个类型的资源。当发出资源请求后

3、，系统按下述步骤进行检查：(1)如果j= Needi,j，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。(2)如果j= Needi,j工作向量Work，它表示系统可提供进程继续运行所需的给类资源数目，它含有m个元素，在执行安全算法开始时，Work:=Available。 2Finish,它表示系统是否有足够的资源分配给进程，使之运行完成。开始先做Finishi:=false；当有足够资源分配给进程时，再令Finishi:=true。(2)从进程集合中找到一个能满足下述条件的进程： 1Finishi=false; 2Needi,j=Workj；若找到，执行步骤，否则

4、，执行步骤。(3)当进程获得资源后，可顺利执行，直至完成，并释放分配给它的资源，故应执行： Workj：= Workj+ Allocationi,j； Finishi：=true； go to step2；(4) 如果所有进程的Finishi：=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。三、 设计步骤1、 设计思路分析 依次输出进程数量与各类型资源数量，检查某一时刻系统是否处于安全状态，若系统处于安全状态则就行资源分配，也就是对用户提出的请求进行合法性检查，即检查请求的是不大于需要的资源量，是否不大于可利用的资源量。若请求合法，则进行试分配。最后对试分配后的状态调用安全

5、性检查算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态，让其等待，返回。2、 总体框架设计银行家算法分配资源增加资源删除资源安全性检测退出图1 总体框架图3、 银行家算法函数流程图银行家算法Bank（）开始初始化Imit();提出请求REQUEST()；REQUEST()=NEEDiREQUESTi=AVILABLEiAVILABLEi-=REQUESTi;ALLOCATIONi+=REQUESTi；NEEDi-=REQUESTi；Safe();输出提示：系统是安全的！是否再次进行分配ErrorError输出提示：分配不合理，不予分配！AVILABLEi+=REQUESTi;AL

6、LOCATIONi-=REQUESTi；NEEDi+=REQUESTi；退出程序falsetruefalsetruefalsetruefalsetrue 图2 银行家算法流程图4、 安全性算法流程图安全性算法Safe()开始Work=AVAILABLE；FINISH=false；NEEDi=Work&FINISHi=falseWork+=ALLOCATIONi;FINISHi=true;所有进程的FINISH=true安全，输出序列，输出提示：系统安全是安全的！return true;安全性算法Safe()结束输出提示：系统不安全falsefalsetruetrue 图3 安全性算法流程图5、

7、 详细设计（1） 安全性检测当前安全性检查safe()：用于判断当前状态安全性，根据不同地方的调用提示处理不同。具体代码如下：int safe() int i,k=0,m,apply,Finish100=0; int j; int flag=0; Work0=Avaliable0; Work1=Avaliable1; Work2=Avaliable2; for(i=0;iM;i+) apply=0;/对每一个进程都进行检测 for(j=0;jN;j+)/对每一个进程的每一种资源都进行检测 if (Finishi=False&Needij=Workj) apply+;/用来判断用不用对当前进程资

8、源进行分配 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; cout系统是安全的!endl; cout分配的序列:;for(i=0;iM;i+) couttempi; if(iM-1) cout; coutendl; return 0;（2） 利用银行家算法对申请资源进行判定函数void share()/利用银行家算法对

9、申请资源对进行判定 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) cout进程 i申请的资源大于它需要的资源; cout 分配不合理，不予分配！Avaliablej)/判断申请是否大于当前资源，若大于则 /出错 cout进程i申请的资源大于系统现在可利用的资源; cout 分配出错，不予分配!endl; ch=n; break; if(ch=y) changdata(

10、i); showdata(); safe(); （3） 资源分配int changdata(int i) int j; for (j=0;jM;j+) Avaliablej=Avaliablej-Requestj; Allocationij=Allocationij+Requestj; Needij=Needij-Requestj; return 1;/返回6、 运行结果及其讨论（1） 输入资源的种类以及剩余资源数量 图4如图4所示，输入系统3中类型资源a,b,c,剩余资源数量分别为3,3,2（2） 输入进程的数量以及各进程最大需求量，已经申请分配的资源量，如图5所示： 图5（3） 根据安全性

11、算法判定输入的数据，系统是安全的，如图6所示： 图6（4）进行分配资源，1进程请求资源，请求向量Request1(1，0，2），按银行家算法进行检查，系统安全，可以进行分配，如图7所示： 图7（5）4进程请求资源，Requst(3,3,0),按银行家算法进行检查，申请的资源大于系统现在可利用的资源，分配错误，如图8所示： 图8（6）0进程请求资源，Requst(0，2，0),按银行家算法进行检查，安全性检查：可用资源已不能满足任何进程的需要，故系统不安全，如图9所示： 图9五、附录（源代码）#include#include#include#define False 0#define True

12、1int 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;/作业的最大数为100int N=100;/资源的最大数为100void showdata()/显示资源矩阵 int i,j; cout系统目前可用的资源Avaliable:e

13、ndl; for(i=0;iN;i+) coutnamei ; coutendl; for (j=0;jN;j+) coutAvaliablej ;/输出分配资源 coutendl; cout Max Allocation Needendl; cout进程名 ; for(j=0;jN;j+) for(i=0;iM;i+) coutnamei ; cout ; coutendl; /依次输入进程名称 for(i=0;iM;i+) cout i ; for(j=0;jN;j+) coutMaxij ; /依次输入max值 cout ; for(j=0;jN;j+) coutAllocationij

14、 ;/依次输入allocation值 cout ; for(j=0;jN;j+) coutNeedij ;/依次输入need值 coutendl; int changdata(int i)/进行资源分配，系统先执行安全性算法，若安全则进行此次试分配，如果请求向量request满足前两个条件后，执行其下 int j; for (j=0;jM;j+) Avaliablej=Avaliablej-Requestj;/当前的可用资源就为原可用资源减去申请资源量 Allocationij=Allocationij+Requestj;/当前已分配就得为已分配资源要加上申请的资源量 Needij=Needi

15、j-Requestj;/当前需求就为原需求减去分配的资源量 return 1;/返回int safe()/安全性算法 int i,k=0,m,apply,Finish100=0;/Finish都赋值为0，false，表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finish=false，当有足够资源分配时，令Finish=true int j; int flag=0; Work0=Avaliable0;/在执行安全算法开始时，定义work=avaliable,表示系统可提供给进程继续运行所需的给类资源数目 Work1=Avaliable1; Work2=Avaliable2; f

16、or(i=0;iM;i+) apply=0;/对每一个进程都进行检测 for(j=0;jN;j+)/对每一个进程的每一种资源都进行检测 if (Finishi=False&Needij=Workj) /如果第I个进程还没有检测过开始检测，并且所需资源量小于等于其工作量 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)

17、cout系统不安全endl;/不成功系统不安全 return 1; cout系统是安全的!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;/输入需要申

18、请的资源 for (j=0;jNeedij)/判断申请是否大于需求，若大于则出错 cout进程 i申请的资源大于它需要的资源; cout 分配不合理，不予分配！Avaliablej)/判断申请是否大于当前资源，若大于则 /出错 cout进程i申请的资源大于系统现在可利用的资源; cout 分配出错，不予分配!endl; ch=n; break; if(ch=y) changdata(i);/根据进程需求量变换资源 showdata();/根据进程需求量显示变换后的资源 safe();/根据进程需求量进行银行家算法判断 void addresources()/添加资源 int n,flag;co

19、utn;flag=N;N=N+n;for(int i=0;in;i+) 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;showd

20、ata();safe();int main()/主函数 int i,j,number,choice,m,n,flag;char ming; cout 欢迎进入银行家算法系统endl; cout * *endl; cout * *endl; cout * 设计者 *endl; cout * *endl; cout * *endl; coutendl;coutn;N=n; for(i=0;in;i+) cout资源i+1ming; namei=ming; cout剩余资源的数量:number; Avaliablei=number;coutendl;coutm;M=m;cout请输入各进程的最大需求

21、量(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-Allocationij; if(flag) cout申请的资源大于最大需求量，请重新输入!n;while(flag); showdata();/显示各种资源 safe();/用银行家算法判定系统是否安全 while(choice) cout 模拟银行家算法演示 endl; cout * 1.分配资源 *endl; cout * 2.增加资源 *endl; cout * 3.删除资源 *endl; cout * 0.退出系统 *endl; coutendl; coutchoice; switch(choice) case 1: share();break; case 2: addresources();break; case 3: delresources();break; case 0: choice=0;break; default: cout请正确选择功能号(0-4)!endl;break; return 1;18