银行家算法课程设计.doc

课程设计报告 操作系统原理 银行家算法 专业软件工程学生姓名陈鹏班级3班学号0810321306指导教师万方完成日期2011.06.24银行家算法一、银行家算法原理银行家算法是一种最有代表性的避免死锁的算法。要解释银行家算法，必须先解释操作系统安全状态和不安全状态。安全状态：如果存在一个由系统中所有进程构成的安全序列P1，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。不安全状态:不存在一个安全序列。不安全状态不一定导致死锁。那么什么是安全序列呢？安全序列：一个进程序列P1，Pn是安全的，如果对于每一个进程Pi(1in），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i ) 我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。二、算法的数据结构（1）可利用资源向量Available是个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果Availablej=K，则表示系统中现有Rj类资源K个。（2）最大需求矩阵Max这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi,j=K，则表示进程i需要Rj类资源的最大数目为K。（3）分配矩阵Allocation这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi,j=K，则表示进程i当前已分得Rj类资源的 数目为K。（4）需求矩阵Need这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi,j=K，则表示进程i还需要Rj类资源K个，方能完成其任务。其中Needi,j=Maxi,j-Allocationi,j三、程序流程图开始输入资源数m及各类资源总数，初始化输入进程数ni<=n输入进程i的最大需求向量Max<=资源总数提示错误i加1初始化needNeed矩阵为0所有进程运行结束任选一个进程作为当前进程Need向量为0该进程已运行输入该进程的资源请求量调用银行家算法，及安全性算法，完成分配并给出提示YNNYYYNN 四、程序代码#include<iostream>using namespace std;#include<string.h>#include<stdio.h>#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 temp100=0;/存放安全序列 int Work100=0;/存放系统可提供资源 int M=100;/作业的最大数为100 int N=100;/资源的最大数为100 void showdata()/显示资源矩阵 int i,j; cout<<"系统目前可用的资源Avaliable:"<<endl; for(i=0;i<N;i+)cout<<namei<<" " cout<<endl; for (j=0;j<N;j+)cout<<Avaliablej<<" "/输出分配资源cout<<endl; cout<<" Max Allocation Need"<<endl; cout<<"进程名 " for(j=0;j<3;j+)for(i=0;i<N;i+)cout<<namei<<" "cout<<" "cout<<endl;for(i=0;i<M;i+)cout<<" "<<i<<" "for(j=0;j<N;j+)cout<<Maxij<<" "cout<<" "for(j=0;j<N;j+)cout<<Allocationij<<" "cout<<" "for(j=0;j<N;j+)cout<<Needij<<" "cout<<endl; int changdata(int i)/进行资源分配int j;for (j=0;j<M;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; Work0=Avaliable0; Work1=Avaliable1; Work2=Avaliable2; for(i=0;i<M;i+)apply=0; for(j=0;j<N;j+)if (Finishi=False&&Needij<=Workj)apply+;if(apply=N) for(m=0;m<N;m+)Workm=Workm+Allocationim;/变分配数Finishi=True;tempk=i;i=-1; k+;flag+;for(i=0;i<M;i+)if(Finishi=False)cout<<"系统不安全"<<endl;/不成功系统不安全return -1;cout<<"系统是安全的!"<<endl;/如果安全，输出成功cout<<"分配的序列:"for(i=0;i<M;i+)/输出运行进程数组cout<<tempi;if(i<M-1)cout<<"->"cout<<endl;return 0;void share()/利用银行家算法对申请资源对进行判定char ch;int i=0,j=0;ch='y'cout<<"请输入要求分配的资源进程号(0-"<<M-1<<"):"cin>>i;/输入须申请的资源号cout<<"请输入进程 "<<i<<" 申请的资源:"<<endl;for(j=0;j<N;j+)cout<<namej<<":"cin>>Requestj;/输入需要申请的资源 for (j=0;j<N;j+)if(Requestj>Needij)/判断申请是否大于需求，若大于则出错cout<<"进程 "<<i<<"申请的资源大于它需要的资源"cout<<" 分配不合理，不予分配！"<<endl; ch='n' break; elseif(Requestj>Avaliablej)/判断申请是否大于当前资源，若大于则/出错cout<<"进程"<<i<<"申请的资源大于系统现在可利用的资源"cout<<" 分配出错，不予分配!"<<endl;ch='n'break; if(ch='y')changdata(i);/根据进程需求量变换资源showdata();/根据进程需求量显示变换后的资源 safe();/根据进程需求量进行银行家算法判断 void addresources()/添加资源int n,flag;cout<<"请输入需要添加资源种类的数量:"cin>>n; flag=N; N=N+n;for(int i=0;i<n;i+)cout<<"名称:"cin>>nameflag; cout<<"数量:" cin>>Avaliableflag+; showdata();safe(); void delresources()/删除资源 char ming;int i,flag=1; cout<<"请输入需要删除的资源名称："docin>>ming;for(i=0;i<N;i+)if(ming=namei)flag=0;break; if(i=N)cout<<"该资源名称不存在，请重新输入：" while(flag); for(int j=i;j<N-1;j+) namej=namej+1;Avaliablej=Avaliablej+1; N=N-1; showdata(); safe(); void addprocess()/添加作业int flag=M;M=M+1; cout<<"请输入该作业的最打需求量Max"<<endl; for(int i=0;i<N;i+)cout<<namei<<":"cin>>Maxflagi;Needflagi=Maxflagi-Allocationflagi; showdata(); safe(); int main()/主函数int i,j,number,choice,m,n,flag;char ming;cout<<"*资源管理系统的设计与实现*"<<endl;cout<<"请首先输入系统可供资源种类的数量:" cin>>n; N=n; for(i=0;i<n;i+)cout<<"资源"<<i+1<<"的名称:"cin>>ming;namei=ming;cout<<"资源的数量:" cin>>number; Avaliablei=number; cout<<endl; cout<<"请输入作业的数量:"cin>>m; M=m;cout<<"请输入各进程的最大需求量("<<m<<"*"<<n<<"矩阵)Max:"<<endl;for(i=0;i<m;i+)for(j=0;j<n;j+)cin>>Maxij;doflag=0;cout<<"请输入各进程已经申请的资源量("<<m<<"*"<<n<<"矩阵)Allocation:"<<endl;for(i=0;i<m;i+)for(j=0;j<n;j+)cin>>Allocationij;if(Allocationij>Maxij)flag=1; Needij=Maxij-Allocationij; if(flag)cout<<"申请的资源大于最大需求量，请重新输入!n"while(flag);showdata();/显示各种资源safe();/用银行家算法判定系统是否安全while(true)cout<<"*银行家算法演示*"<<endl;cout<<" 1:增加资源 "<<endl;cout<<" 2:删除资源 "<<endl;cout<<" 3:分配资源 "<<endl;cout<<" 4:增加作业 "<<endl;cout<<"*"<<endl;cout<<"请选择功能号："cin>>choice;switch(choice)case 1: addresources();break;case 2: delresources();break;case 3: share();break;case 4: addprocess();break;default: cout<<"请正确选择功能号(0-5)!"<<endl;break; return 1;五、运行结果六、设计体会经过几天的自己动手练习，对操作系统的掌握又进了一步，收获了很多课堂上和书上未出现过的或老师未讲到的一些知识。在完成实验的过程中，进行了反复的修改和调试，这次实验，让我基本上明白了银行家算法的基本原理，加深了对课堂上知识的理解，也懂得了如何让银行家算法实现，但编程功底的原因使程序很是繁琐。这次的设计数据是通过一道实际的题目来体现银行家算法避免死锁的问题，先用银行家算法给其中一个进程分配资源，看它所请求的资源是否大于它的需求量，才和系统所能给的资源相比较.让进程形成一个安全队列,看系统是否安全.再利用安全性算法检查此时系统是否安全。要做一个课程设计，如果知识面只是停留在书本上，是不可能把课程设计完全地做好。用VC+6.0编程，感觉自己有点力不从心，很多C语言的知识都忘了，只好翻出以前的C语言课本和数据结构来复习。每次的课程设计中都能将以前的知识顺便再复习一遍，课程设计是给了我们一个机会去动手和主动复习，同时也是提醒我们应该注重平时的积累。从课程设计以后还是要多多的动手，在实践中体会理论知识，这样才不会在要做实验和设计时，觉得无从下手。银行家算法是操作系统中避免死锁的典型算法。我设计的这个程序中包含了三大块，利用数据结构初始化，银行家算法，安全性算法。在初始化这一块，程序需要用到可利用资源向量Availablej、最大需求矩阵Maxi.j、分配矩阵Allocationi,j、需求矩阵Needi,j。它们之间有着一定的联系，Needi,j=MaxI,j-Allocationi,j，请求资源时需要用到银行家算法，检查资源的分配需要用到安全性算法。在将三大块结合起来就能很好的避免死锁的发生了。通过这次的实验，我更进一步的了解了银行家算法，并对数据结构的用法理解的更透彻了，在实验的过程中我深刻的体会到了合作的意义，我遇到了一些困难，通过对书上所学的知识反复的思考与理解和与同学之间的相互讨论，最终将银行家算法真正的理解，并且将它用C+实现。在以后的学习当中我会更加努力的将这一门课程学好。这次课程设计时间上虽说仓促点，但是我依然学到了很多的实用性知识。除了更深的了解这个算法，而且对C语言进行了复习，而且其过程中有很多的知识点都不记得了。七、参考文献1 庞丽萍.操作系统原理M. 武汉：华中科技大学出版社，20082 杨树青,王欢.Linux环境下C编程指南M. 北京：清华大学出版社，20073 陈维兴,林小茶. C+面对对象程序设计教程M. 北京：清华大学出版社，20044杨路明. C语言程序设计教程M. 北京：北京邮电大学出版社，2005