《用C++编程模拟银行家算法.docx》由会员分享，可在线阅读，更多相关《用C++编程模拟银行家算法.docx（13页珍藏版）》请在三一文库上搜索。
1、操作系统课程设计报告闽江学院计算机学院 08级网络专业题目 编程模拟银行家算法学生 大熊学号 56指导教师 徐向英2010年7月2日设计题目:编程序模拟银行家算法设计目的1、银行家算法是避免死锁的一种重要方法，本实验要求用级 语言编写和调试一个简单的银行家算法程序。加深了解有关资源申 请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。2、提高学生的程序设计能力、提高算法设计质量与程序设计素 质；设计任务一、要求1. 复习银行家算法，设计一个具有若干（不少于 3种）资源和若干 （不少于5个）进程的系统。2. 定义系统的初始状态，即进程获得的资源数，还需要的资源数以 及系统可用的资源数
2、。3. 以用户输入的方式提出资源请求，并用银行家算法避免可能发生的死锁，若系统安全，允许用户继续申请资源。4. 设计的系统要求结构清晰，与用户的交互界面友好，能动态地实 现资源的申请和分配。二、思想将一定数量的资金供多个用户周转使用，当用户对资金的最大申请量不超过现存资金时可接纳一个新客户，客户可以分期借款，但借 款总数不能超过最大的申请量。银行家对客户的借款可以推迟支付， 但是能够使客户在有限的时间内得到借款，客户得到所有的借款后能 在有限的时间内归还。用银行家算法分配资源时，测试进程对资源的最大需求量，若现存资源能满足最大需求就满足当前进程的申请， 否则推迟分配，这样能够 保证至少有一个进
3、程可以得到所需的全部资源而执行到结束，然后归还资源，若OS能保证所有进程在有限的时间内得到所需资源则称系 统处于安全状态。设计思路和过程1. 概要设计1.1程序流程图 2. I第占垣|田1.2设计原理及方法银行家算法的设计思想是：当用户申请一组资源时，系统必须 做出判断；如果把这些资源分出去，系统是否还处于安全装他。若是, 就可以分出这些资源；否则，该申请暂不能满足。实现银行家算法要有若干数据结构，它们用来表示资源分配系 统的状态。令n表示系统中进程的数目，m表示资源的分类数。还需 要以下数据结构：1. Available是一个长度为m的向量，它表示每类资源可用的数量。Available j=
4、k ，表示rj类资源可用的数量为k。2. Max是一个nx m矩阵，它表示每个进程对资源的最大需求。Max i , j=k，表示进程pi至多可以申请k个rj类资源单位。3. Allocation 是一个n x m矩阵，它表示当前分给每个进程 的资源数目。Allocation i , j=k，表示进程pi当前分到k个rj 类资源。4. Need是一个nx m矩阵，它表示每个进程还缺少多少资源。 Needi , j=k ,表示进程pi尚需k个rj类资源才能完成其任务。显 然 Needi , j= Max i , j- Allocation i , j。这些数据结构的大小和数值随时间推移而改变。系统
5、所执行的安全性算法描述如下：1. 设置2个向量：工作向量 Work：它表示系统可提供给进程 继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开 始时，Work = Available 。Finishi :它表示系统是否有足够的资源分配给进程，使 之完成运行。开始时先做Finishi=true 。2. 从进程集合中找到一个满足下述条件的进程：Finishi=flase ; Needi,j < Workj;若找到，则执行步骤 3, 否则，执行步骤4。3. 当进程pi获得资源后，可顺利执行，直至完成，并释放分 配给它的资源。4. 如果所有进程的Finishi=true 都满足。则表示
6、系统处于 安全状态；否则，系统处于不安全状态。2.详细设计2.1程序源代码#include<iostream>#include<string>#include<stdio>using namespace std;#define False 0#define True 1int Max100100=0;/各进程所需各类资源的最大需求int Avaliable100=0;/ 系统可用资源char name100=0;/ 资源的名称int Allocation100100=0;/系统已分配资源int Need100100=0;/还需要资源int Request10
7、0=0;/请求资源向量int temp100=0;/存放安全序列int Work100=0;/存放系统可提供资源int M=100;/作业的最大数为 100int N=100;/资源的最大数为 100void showdata()/显示资源矩阵int i,j;cout<<" 系统目前可用的资源 Avaliable:"<<endl;for(i=0;i<N;i+)cout«namei«" cout«endl; for (j=O;jN;j+) cout«Avaliablej«"&q
8、uot;/输出分配资源cout«endl; cout«" Max Allocation Need"«endl; cout«" 进程名 for(j=0;j3;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«Maxi
9、j«" cout«" for(j=0;j<N;j+) cout«Allocationij«" cout«" for(j=0;j<N;j+) cout«Needij«" cout«endl; ) ) int changdata(int i)/进行资源分配 intj; for (j=O;jM;j+) Avaliablej=Avaliablej-Requestj; Allocationij=Allocationij+Requestj; Needij=Needi
10、j-Requestj; ) return 1; ) int safe()/安全性算法 int i,k=0,m,apply,Finish100=0; intj; 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;/变分
11、配数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<<”->
12、”;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<
13、;<":"cin>>Requestj;/输入需要申请的资源for (j=0;j<N;j+)if(Requestj>Needij)/判断申请是否大于需求，若大于则出错cout<<" 进程"<<i<<"申请的资源大于它需要的资源"cout<<"分配不合理，不予分配！"<<endl;ch='n'break;else if(Requestj>Avaliablej)/判断申请是否大于当前资源，若大于则/出错cout
14、<<" 进程"<<i<<"申请的资源大于系统现在可利用的资源"cout<<" 分配出错，不予分配!"<<endl;ch='n'break;if(ch='y') changdata(i);/根据进程需求量变换资源showdata();/ 根据进程需求量显示变换后的资源safe();/根据进程需求量进行银行家算法判断void addresources()/添加资源int n,flag;cout<<"请输入需要添加资源种类的数量
15、:"cin>>n;flag=N;N=N+n;for(int i=0;i<n;i+)cout<<"名称:"cin>>nameflag;cout<<"数量:"cin>>Avaliableflag+;showdata();safe();void changeresources()/修改资源函数cout<<"系统目前可用的资源 Avaliable:"<<endl;for(int i=0;i<N;i+)cout<<namei&l
16、t;<":"<<Avaliablei<<endl;cout<<"输入系统可用资源Avaliable:"<<endl;cin>>Avaliable0>>Avaliable1>>Avaliable2;cout<<"经修改后的系统可用资源为"<<endl;for (int k=0;k<N;k+)cout<<namek<<":"<<Avaliablek<<e
17、ndl;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;showd
18、ata();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&l
19、t;<"*资源管理系统的设计与实现*"<<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&l
20、t;<"请输入作业的数量:"cin>>m;M=m;cout<<"请输入各进程的最大需求量("<<m<<"*"<<n<<"矩阵)Max:"<<endl;for(i=0;i<m;i+)for(j=0;j<n;j+)cin>>Maxij;do(flag=0;cout<<"请输入各进程已经申请的资源量("<<m<<"*"<<
21、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(choice)cout<<"*车
22、艮行家算法*cout<<"1:增加资源"<<endl;cout<<"2:删除资源 "<<endl;cout<<"3:修改资源 "<<endl;cout<<"4:分配资源"<<endl;cout<<"5:增加作业 "<<endl;cout<<"0:离开"<<endl;cout<<"*"<<en
23、dl;cout<<" 请选择功能号："cin>>choice;switch(choice)("<<endl;(case 1: addresources();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)!"<
24、;<endl;break;return 1;3.调试及运行结果3.1程序调试及运行结果经过调试，改正了越界错误，定义错误，死循环和一些语法错误程序最终运行成功。检测结果如下： * * X* * * W X X X ')<* XXX * X XX X Xa：4 b：4 C ：110 5MaxAllocation进程名a b ca b c03 4 50 1212 3 40 2 225 4 35 4 335 4 22 3 143 5 62 4 1系统目前可用的资源AualiableJ：系统是安全的？分配的序列：2->0- >1->3->4Need a b c 3 3 32 12 0 0 03 11 115总结和体会一周的课程设计结束了。在这一周里，我做一个模拟银行家算法。我觉得在着手设计前设计的思路是很重要的。只有思路清晰才能进行 下一阶段的设计。这样才能完成整个程序的设计，完成整个文报告的 书写。课程设计这几天学到的东西还真不少。以前不清楚的现在都暴露出来了。以前认为学了没用的东西现在也用到了。 这次的课程设计使我进一步了解了调度与死锁的问题。 以及有关资源申请的问题、避 免死锁的具体实施方法。深入了解了银行家算法的资源申请和资源分 配的过程及原则。保证系统处于安全状态。