银行家算法课程设计报告Company Document number：WTUT-WT88Y-W8BBGB-BWYTT-19998中南大学软件技术课程设计报告课程名称：模拟银行家算法原理班级：学号：姓名：指导老师：2009年5月2日一设计目的模拟实现银行家算法，用银行家算法实现资源分配。
二问题描述在死锁的避免中，银行家算法把系统状态分为安全状态和不安全状态，只要能使系统始终处于安全状态，便可以避免发生死锁。
所谓安全状态，是指系统能按某种顺序为每个进程分配所需资源，直到最大需求，使每一个进程都可以顺利完成，即可找到一个安全资源分配序列。
模拟实现这个工作过程。
三设计思路我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。
操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。
当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。
若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。
四详细设计1、初始化由用户输入数据，分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵MAX、分配矩阵ALLOCATION、需求矩阵NEED赋值。
2、银行家算法在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。
在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。
银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。
设进程cusneed提出请求REQUEST [i]，则银行家算法按如下规则进行判断。
(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，则转(2)；否则，出错。
(2)如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i]，则转(3)；否则，出错。
(3)系统试探分配资源，修改相关数据：AVAILABLE[i]-=REQUEST[cusneed][i];ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];NEED[cusneed][i]-=REQUEST[cusneed][i];(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。
(5)对于某一进程i，若对所有的j，有NEED[i][j]=0，则表此进程资源分配完毕，应将占用资源释放。
3、安全性检查算法(1)设置两个工作向量Work=AVAILABLE;FINISH(2)从进程集合中找到一个满足下述条件的进程，FINISH==false;NEED<=Work;如找到，执行(3)；否则，执行(4)(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。
Work+=ALLOCATION;Finish=true;GOTO 2(4)如所有的进程Finish= true，则表示安全；否则系统不安全。
4、流程图四源程序：#include <iostream>#include <>#include <>.6秒后跳入主界面" <<endl;Sleep(6000);system("cls");cout<<" "<<endl;cout <<" 运行界面"<<endl;cout<<">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>"<<endl;cout<<"请输入进程的数目:"<<endl;cin>>m;cout<<"请输入资源的种类:"<<endl;cin>>n;cout<<"请输入每个进程最多所需的各资源数,按照"<<m<<"x"<<n<<"矩阵输入"<<endl;for(i=0;i<m;i++)for(j=0;j<n;j++)cin>>MAX[i][j];cout<<"请输入每个进程已分配的各资源数,也按照"<<m<<"x"<<n<<"矩阵输入"<<endl;for(i=0;i<m;i++){for(j=0;j<n;j++){cin>>ALLOCATION[i][j];NEED[i][j]=MAX[i][j]-ALLOCATION[i][j];if(NEED[i][j]<0){cout<<"您输入的第"<<i+1<<"个进程所拥有的第"<<j+1<<"个资源数错误,请重新输入:"<<endl;j--;continue;}}}for(j=0;j<n;j++) //已分配各资源总数{for(i=0;i<m;i++)NEEDc[j]=ALLOCATION[i][j]+NEEDc[j];}// for(i=0;i<n;i++) //此四行用于检验// {// cout<<""<<NEEDc[i]<<" ";// }cout<<"请输入各个资源现有的数目:"<<endl;for(i=0;i<n;i++){cin>>AVAILABLE[i];}for(i=0;i<n;i++) //总资源数{SUMMIT[i]=AVAILABLE[i]+ NEEDc[i];}// for(i=0;i<n;i++) //检验用// cout<<""<<SUMMIT[i]<<" ";// cout<<" "<<endl;cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;cout<<"初始化后状态显示:"<<endl;cout<<"每个进程最多所需的各资源数"<<endl;for(i=0;i<m;i++){for(j=0;j<n;j++)cout<<""<<MAX[i][j]<<" ";if(j=n-1)cout<<" "<<endl;}cout<<"每个进程已分配的各资源数"<<endl;for(i=0;i<m;i++){for(j=0;j<n;j++)cout<<""<<ALLOCATION[i][j]<<" ";if(j=n-1)cout<<" "<<endl;}cout<<"各个资源现有的数目:"<<endl;for(i=0;i<n;i++)cout<<""<<AVAILABLE[i]<<" ";cout<<" "<<endl;cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~"<<endl;}void Bank() /*银行家算法*/{int i,j,cusneed;char again;int sum=0; /*监测某一进程资源是否分配完毕*/int add=0;while(1){cout<<"请输入要申请资源的进程号(注:第1个进程号为0,依次类推)"<<endl; cin>>cusneed;cout<<"请输入进程所请求的各资源的数量"<<endl;for(i=0;i<n;i++){cin>>REQUEST[cusneed][i];// }// for(i=0;i<n;i++)// {if(REQUEST[cusneed][i]>NEED[cusneed][i]){cout<<"您输入的本个请求数超过进程的需求量!请重新输入!"<<endl;i--;continue;}if(REQUEST[cusneed][i]>AVAILABLE[i]){cout<<"您输入的本个请求数超过系统有的资源数!请重新输入!"<<endl;i--;continue;}}for(i=0;i<n;i++) //资源分配{AVAILABLE[i]-=REQUEST[cusneed][i];ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];NEED[cusneed][i]-=REQUEST[cusneed][i];}if(Safe()){cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~"<<endl;cout<<"同意分配请求!"<<endl;cout<<"此次分配后状态显示:"<<endl;cout<<"当前每个进程最多尚需的各资源数"<<endl;for(i=0;i<m;i++){for(j=0;j<n;j++)cout<<""<<NEED[i][j]<<" ";if(j=n-1)cout<<" "<<endl;}cout<<"当前每个进程已分配过的各资源数"<<endl;for(i=0;i<m;i++){for(j=0;j<n;j++)cout<<""<<ALLOCATION[i][j]<<" ";if(j=n-1)cout<<" "<<endl;}for(i=0;i<m;i++)for(j=0;j<n;j++)add=NEED[i][j]+add; //是否已分配完毕if(add!=0){for(i=0;i<n;i++)sum=NEED[cusneed][i]+sum;cout<<"sum值:"<<sum<<""<<endl;//cout<<""<<sum<<" ";cout<<" "<<endl;if (sum==0){ for(i=0;i<n;i++)AVAILABLE[i]= ALLOCATION[cusneed][i]+AVAILABLE[i];}sum=0;cout<<"各个资源现有的数目:"<<endl;for(i=0;i<n;i++)cout<<""<<AVAILABLE[i]<<" ";cout<<" "<<endl;add=0;}// cout<<""<<add<<" "endl;else{cout<<"各个资源现有的数目:"<<endl;for(i=0;i<n;i++)cout<<""<<SUMMIT[i]<<" ";cout<<" "<<endl;}cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~"<<endl;}else{cout<<"您的请求被拒绝!"<<endl; //撤消资源分配for(i=0;i<n;i++){AVAILABLE[i]+=REQUEST[cusneed][i];ALLOCATION[cusneed][i]-=REQUEST[cusneed][i];NEED[cusneed][i]+=REQUEST[cusneed][i];}}for(i=0;i<m;i++){FINISH[i]=false;}cout<<"您还想再次请求分配吗是请按y/Y,否请按其它键"<<endl; cin>>again;if(again=='y'||again=='Y'){continue;}break; //跳出while}}bool Safe() /*安全性算法*/{int i,j,k,l=0;int Work[MAXRESOURCE]; /*工作数组*/for(i=0;i<n;i++)Work[i]=AVAILABLE[i];for(i=0;i<m;i++){FINISH[i]=false;}for(i=0;i<m;i++){if(FINISH[i]==true){continue;}else{for(j=0;j<n;j++){if(NEED[i][j]>Work[j]){break;}}if(j==n){FINISH[i]=true; //FINISH在此被赋值,表进程i可顺利进行 for(k=0;k<n;k++) //并假设已执行完成{Work[k]+=ALLOCATION[i][k];}p[l++]=i;i=-1; //再从i=0开始判断}else{continue;}}if(l==m) //所有进程都可完成{cout<<"系统是安全的"<<endl;cout<<"安全序列:"<<endl;for(i=0;i<l;i++){cout<<p[i];if(i!=l-1) //最后一项不输-->{cout<<"-->";}}cout<<""<<endl;return true;}}cout<<"系统是不安全的"<<endl;return false;}五运行调试及结果说明初始化时若已分配资源多于最多所需资源则会报错，需重新输入（如上图所示）初始化后状态显示资源分配时请求量超过需求量或现有资源数同样会报错（如上图）特殊情况：若申请资源数既不大于资源需求量，又不大于现有资源数，但仍有可能导致死锁，如上图所示。