银行家算法实验报告(共13页).doc

精选优质文档-倾情为你奉上设计题目银行家算法的实现设计形式 独立完成 设计目的1加深了解有关资源申请、避免死锁等概念。2体会和了解死锁和避免死锁的具体实施方法。设计预备知识1死锁的相关知识。 2银行家算法。3系统安全性检查。设计内容1设计进程对各类资源最大申请表示及初值的确定。2设定系统提供资源的初始状况。 3设定每次某个进程对各类资源的申请表示。4编制程序，依据银行家算法，决定其资源申请是否得到满足。5显示资源申请和分配时的变化情况。小组成员分工无银行家算法分析、设计与实现一、 设计理论描述本设计的目的是通过编写和调试一个系统动态分配资源的简单模拟程序，观察死锁产生的条件，并采用适当的算法，有效地防止和避免死锁地发生。要求如下：（1） 模拟一个银行家算法；（2） 初始化时让系统拥有一定的资源；（3） 用键盘输入的方式申请资源；（4） 如果预分配后，系统处于安全状态，则修改系统的资源分配情况；（5） 如果预分配后，系统处于不安全状态，则提示不能满足请求，设计的主要内容是模拟实现动态资源分配。同时编写和调试一个系统动态资源的简单模拟程序，观察死锁产生的条件，并使用适当的算法，有效的防止和避免死锁的发生。银行家算法. 顾名思义是来源于银行的借贷业务，一定数量的本金要应多个客户的借贷周转，为了防止银行加资金无法周转而倒闭，对每一笔贷款，必须考察其是否能限期归还。在操作系统中研究资源分配策略时也有类似问题，系统中有限的资源要供多个进程使用，必须保证得到的资源的进程能在有限的时间内归还资源，以供其他进程使用资源。如果资源分配不得到就会发生进程循环等待资源，则进程都无法继续执行下去的死锁现象。把一个进程需要和已占有资源的情况记录在进程控制中，假定进程控制块PCB其中“状态”有就绪态、等待态和完成态。当进程在处于等待态时，表示系统不能满足该进程当前的资源申请。“资源需求总量”表示进程在整个执行过程中总共要申请的资源量。显然，每个进程的资源需求总量不能超过系统拥有的资源总数, 银行算法进行资源分配可以避免死锁.二、算法描述及数据结构模型 1.银行家算法: 设进程i提出请求Requestn，则银行家算法按如下规则进行判断。 (1)如果Requestn>Needi，n，则报错返回。 (2)如果Requestn>Available，则进程i进入等待资源状态，返回。 (3)假设进程i的申请已获批准，于是修改系统状态： Available=Available-Request Allocation=Allocation+Request Need=Need-Request(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。 2.安全性检查 (1)设置两个工作向量Work=Available；FinishM=False(2)从进程集合中找到一个满足下述条件的进程， Finish i=False Need<=Work 如找到，执行(3)；否则，执行(4) (3)设进程获得资源，可顺利执行，直至完成，从而释放资源。 Work=Work+Allocation Finish=True GO TO 2 (4)如所有的进程FinishM=true，则表示安全；否则系统不安全。 3.数据结构#define False 0#define True 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()/显示资源矩阵三、源代码#include<iostream.h>#include<string.h>#include<stdio.h>#define False 0#define True 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:"<<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; else if(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<<"请输入需要删除的资源名称："do cin>>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 changeresources()/修改资源函数cout<<"系统目前可用的资源Avaliable:"<<endl; for(int i=0;i<N;i+) cout<<namei<<":"<<Avaliablei<<endl;cout<<"输入系统可用资源Avaliable:"<<endl;cin>>Avaliable0>>Avaliable1>>Avaliable2;cout<<"经修改后的系统可用资源为"<<endl;for (int k=0;k<N;k+) cout<<namek<<":"<<Avaliablek<<endl;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;do flag=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(choice) cout<<"*银行家算法演示*"<<endl; cout<<" 1:增加资源 "<<endl; cout<<" 2:删除资源 "<<endl; cout<<" 3:修改资源 "<<endl; cout<<" 4:分配资源 "<<endl; cout<<" 5:增加作业 "<<endl; cout<<" 0:离开 "<<endl; cout<<"*"<<endl; cout<<"请选择功能号：" cin>>choice; switch(choice) 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)!"<<endl;break; return 1;四、程序运行结果及分析 T0 时刻的资源分配表(各种资源的数量分别为：10、5、7) 资源情况进程MaxA B CAllocationA B CNeedA B CAvailableA B CP07 5 30 1 07 4 33 3 2P13 2 22 0 01 2 2P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 1 运行结果 五、课程设计心得与体会银行家算法是避免死锁的一种重要方法，通过编写一个简单的银行家算法程序，加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。死锁的产生，必须同时满足四个条件，即一个资源每次只能由一个进程；第二个为等待条件，即一个进程请求资源不能满足时，它必须等待，但它仍继续保持已得到的所有其他资源；第三个为非剥夺条件，即在出现死锁的系统中一定有不可剥夺使用的资源；第四个为循环等待条件，系统中存在若干个循环等待的进程，即其中每一个进程分别等待它前一个进程所持有的资源。防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会发生死锁。六.参考文献：1计算机操作系统汤子瀛等：西安电子科技大学出版社 2高级语言c+程序设计刘璟等：高等教育出版社出师表：先帝创业未半而中道崩殂，今天下三分，益州疲弊，此诚危急存亡之秋也。然侍卫之臣不懈于内，忠志之士忘身于外者，盖追先帝之殊遇，欲报之于陛下也。诚宜开张圣听，以光先帝遗德，恢弘志士之气，不宜妄自菲薄，引喻失义，以塞忠谏之路也。宫中府中，俱为一体；陟罚臧否，不宜异同。若有作奸犯科及为忠善者，宜付有司论其刑赏，以昭陛下平明之理；不宜偏私，使内外异法也。侍中、侍郎郭攸之、费祎、董允等，此皆良实，志虑忠纯，是以先帝简拔以遗陛下：愚以为宫中之事，事无大小，悉以咨之，然后施行，必能裨补阙漏，有所广益。将军向宠，性行淑均，晓畅军事，试用于昔日，先帝称之曰“能”，是以众议举宠为督：愚以为营中之事，悉以咨之，必能使行阵和睦，优劣得所。 亲贤臣，远小人，此先汉所以兴隆也；亲小人，远贤臣，此后汉所以倾颓也。先帝在时，每与臣论此事，未尝不叹息痛恨于桓、灵也。侍中、尚书、长史、参军，此悉贞良死节之臣，愿陛下亲之、信之，则汉室之隆，可计日而待也。臣本布衣，躬耕于南阳，苟全性命于乱世，不求闻达于诸侯。先帝不以臣卑鄙，猥自枉屈，三顾臣于草庐之中，咨臣以当世之事，由是感激，遂许先帝以驱驰。后值倾覆，受任于败军之际，奉命于危难之间，尔来二十有一年矣。先帝知臣谨慎，故临崩寄臣以大事也。受命以来，夙夜忧叹，恐托付不效，以伤先帝之明；故五月渡泸，深入不毛。今南方已定，兵甲已足，当奖率三军，北定中原，庶竭驽钝，攘除奸凶，兴复汉室，还于旧都。此臣所以报先帝而忠陛下之职分也。至于斟酌损益，进尽忠言，则攸之、祎、允之任也。愿陛下托臣以讨贼兴复之效，不效，则治臣之罪，以告先帝之灵。若无兴德之言，则责攸之、祎、允等之慢，以彰其咎；陛下亦宜自谋，以咨诹善道，察纳雅言，深追先帝遗诏。臣不胜受恩感激。今当远离，临表涕零，不知所言。专心-专注-专业