银行家算法-课程设计

1、课程设计报告 操作系统原理 银行家算法 专业软件工程学生姓名陈鹏班级3班学号0810321306指导教师万方完成日期2011.06.24银行家算法一、银行家算法原理银行家算法是一种最有代表性的避免死锁的算法。要解释银行家算法，必须先解释操作系统安全状态和不安全状态。安全状态：如果存在一个由系统中所有进程构成的安全序列P1，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。不安全状态:不存在一个安全序列。不安全状态不一定导致死锁。那么什么是安全序列呢？安全序列：一个进程序列P1，Pn是安全的，如果对于每一个进程Pi(1in），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j

2、i ) 我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。在避免死锁的方法中，所施加的限制条件

3、较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。二、算法的数据结构（1）可利用资源向量Available是个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果Availablej=K，则表示系统中现有Rj类资源K个。（2）最大需求矩阵Max这是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi,j=K，则表示进程i需要Rj类资源的最大数目为K。（3）分

4、配矩阵Allocation这也是一个nm的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi,j=K，则表示进程i当前已分得Rj类资源的 数目为K。（4）需求矩阵Need这也是一个nm的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi,j=K，则表示进程i还需要Rj类资源K个，方能完成其任务。其中Needi,j=Maxi,j-Allocationi,j三、程序流程图开始输入资源数m及各类资源总数，初始化输入进程数ni=n输入进程i的最大需求向量Max=资源总数提示错误i加1初始化needNeed矩阵为0所有进程运行结束任选一个进程作为当前进程Need

5、向量为0该进程已运行输入该进程的资源请求量调用银行家算法，及安全性算法，完成分配并给出提示YNNYYYNN 四、程序代码#includeusing namespace std;#include#include#define False 0#define True 1 int Max100100=0;/各进程所需各类资源的最大需求int Avaliable100=0;/系统可用资源char name100=0;/资源的名称int Allocation100100=0;/系统已分配资源int Need100100=0;/还需要资源 int Request100=0;/请求资源向量 int temp

6、100=0;/存放安全序列 int Work100=0;/存放系统可提供资源 int M=100;/作业的最大数为100 int N=100;/资源的最大数为100 void 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+)cout

7、namei ;cout ;coutendl;for(i=0;iM;i+)cout i ;for(j=0;jN;j+)coutMaxij ;cout ;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;i

8、nt 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+;if(apply=N) for(m=0;mN;m+)Workm=Workm+Allocationim;/变分配数Finishi=True;tempk=i;i=-1; k+;flag+;for(i=0;iM;i+)

9、if(Finishi=False)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;/输入需

10、要申请的资源 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;coutn; fla

11、g=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; showdata()

12、; safe(); void addprocess()/添加作业int flag=M;M=M+1; cout请输入该作业的最打需求量Maxendl; for(int i=0;iN;i+)coutnameiMaxflagi;Needflagi=Maxflagi-Allocationflagi; showdata(); safe(); int main()/主函数int i,j,number,choice,m,n,flag;char ming;cout*资源管理系统的设计与实现*endl;coutn; N=n; for(i=0;in;i+)cout资源i+1ming;namei=ming;cout

13、number; Avaliablei=number; coutendl; coutm; M=m;cout请输入各进程的最大需求量(m*n矩阵)Max:endl;for(i=0;im;i+)for(j=0;jMaxij;doflag=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);show

14、data();/显示各种资源safe();/用银行家算法判定系统是否安全while(true)cout*银行家算法演示*endl;cout 1:增加资源 endl;cout 2:删除资源 endl;cout 3:分配资源 endl;cout 4:增加作业 endl;cout*endl;coutchoice;switch(choice)case 1: addresources();break;case 2: delresources();break;case 3: share();break;case 4: addprocess();break;default: cout请正确选择功能号(0-5

15、)!endl;break; return 1;五、运行结果六、设计体会经过几天的自己动手练习，对操作系统的掌握又进了一步，收获了很多课堂上和书上未出现过的或老师未讲到的一些知识。在完成实验的过程中，进行了反复的修改和调试，这次实验，让我基本上明白了银行家算法的基本原理，加深了对课堂上知识的理解，也懂得了如何让银行家算法实现，但编程功底的原因使程序很是繁琐。这次的设计数据是通过一道实际的题目来体现银行家算法避免死锁的问题，先用银行家算法给其中一个进程分配资源，看它所请求的资源是否大于它的需求量，才和系统所能给的资源相比较.让进程形成一个安全队列,看系统是否安全.再利用安全性算法检查此时系统是否安

16、全。要做一个课程设计，如果知识面只是停留在书本上，是不可能把课程设计完全地做好。用VC+6.0编程，感觉自己有点力不从心，很多C语言的知识都忘了，只好翻出以前的C语言课本和数据结构来复习。每次的课程设计中都能将以前的知识顺便再复习一遍，课程设计是给了我们一个机会去动手和主动复习，同时也是提醒我们应该注重平时的积累。从课程设计以后还是要多多的动手，在实践中体会理论知识，这样才不会在要做实验和设计时，觉得无从下手。银行家算法是操作系统中避免死锁的典型算法。我设计的这个程序中包含了三大块，利用数据结构初始化，银行家算法，安全性算法。在初始化这一块，程序需要用到可利用资源向量Availablej、最大需求矩阵Maxi.j、分配矩阵Allocationi,j、需求矩阵Needi,j。它们之间有着一定的联系，Needi,j=MaxI,j-Allocationi,j，请求资源时需要用到银行家算法，检查资源的分配需要用到安全性算法。在将三大块结合起来就能很好的避免死锁的发生了。通过这次的实验，我更进一步的了解了银行家算法，并对数据结构的用法理解的更透彻了，在实验的过程中我深刻的体会到了合作的意义，我遇到了一些困难，通过对书上所学的知识反复的思考与理解和与同学之间的相互讨论，最终将银行家算法真正的理