银行家算法实验报告(同名22949)

　计算机操作系统实验报告 何美西 1 一、 实验名称：

　银行家算法 二、 实验目的：

　银行家算法是避免死锁的一种重要方法，通过编写 一个简单的银行家算法程序，加深了解有关资源申请、避免死 锁等概念，并体会和了解死锁和避免死锁的具体实施方法。

　三、 问题分析与设计：

　1 、算法思路 ：

　先对用户提出的请求进行合法性检查，即检查 请求是否大于需要的，是否大于可利用的。若请求合法，则进 行预分配，对分配后的状态调用安全性算法进行检查。若安 全，则分配；若不安全，则拒绝申请，恢复到原来的状态，拒 绝申请。

　2 、银行家算法步骤：( 1 )如果 Request k or 二 Need 则转向步 骤 (2) ；否则，认为出错，因为它所需要的资源数已超过它所 宣布的最大值。

　(2) 如果 Reques t or 二 Available, 则转向步骤( 3 );否则，表 示系统中尚无足够的资源，进程必须等待。

　(3)

　系统试探把要求的资源分配给进程 Pi, 并修改下面数据结 构中的数值：

　Available=Available-Request[i];

　Allocation=Allocation+Request; Need=Need-Request; （4）

　系统执行安全性算法，检查此次资源分配后，系统是否处于 安全状态。

　3 、安全性算法步骤：

　（ 1 ）设置两个向量 ①工作向量 Work 。它表示系统可提供进程继续运行所需要的各类资 源数目，执行安全算法开始时， Work=Allocation; ②布尔向量 Finish 。它表示系统是否有足够的资源分配给进程，使 之运行完成，开始时先做 Finish[i]=false ，当有足够资源分配给进程 时，令 Finish[i]=true 。

　（ 2 ）

　从进程集合中找到一个能满足下述条件的进程：

　① Finish[i]=false ② Need<or=Work 如找到，执行步骤（ 3 ）；否则，执行步骤（ 4 ）。

　（ 3 ）

　当进程 P 获得资源后，可顺利执行，直至完成，并释放出分配 给它的资源，故应执行：

　Work=Work+Allocation; Finish[i]=true;

　 o o Request[i] Avai1able[i]? 转向步骤( 2 ) 4 、流程图: 系统主要过程流程图 (4 )如果所有进程的 Finish[i]=true, 则表示系统处于安全状态；否 则，系统处于不安全状态 倾分配 242111 1T 印输出* t 时刻资源分配惰况 宾陥分 AHI ■打进行和始化 \ _____________________ i 进人泰址 li

　银行家算法流程图

　 安全性算法流程图 四、实验代码: #i nclude<iostream.h> #i ncludevstri ng.h> #in clude<stdio.h> #defi ne False 0

　#define True 1

　int Allocation[100][100]={0};// 系统已分配资源 int Need[100][100]={0};// int Request[100]={0};// int temp[100]={0};// int Work[100]={0};// int p[100]={0}; int q[100][100]={0}; int z[100][100]={0}; int M=100;// 作业的最大数为 100 int N=100;// 资源的最大数为 100 int gg=1; void showdata()// 显示资源矩阵 {

　int i,j; cout<<endl<<" 此时刻的资源分配情况为：

　"<<endl; cout<<" Max Allocation Need Avaliable"<<endl;cout<<" 进程名 for(j=0;j<4;j++){ for(i=0;i<N;i++) cout<<name[i]<<" "; int Max[100][100]={0};// 大需求 int Avaliable[100]={0};// char name[100]={0};// 各进程所需各类资源的最 系统可用资源 资源的名称 还需要资源 请求资源向量 存放安全序列 存放系统可提供资源

　}

　 cout<<" "; } cout<<endl; for(i=0;i<M;i++){ cout<<" "<<i<<" "; for(j=0;j<N;j++) cout<<Max[i][j]<<" "; cout<<" "; for(j=0;j<N;j++) cout<<Allocation[i][j]<<" " cout<<" "; for(j=0;j<N;j++) cout<<Need[i][j]<<" "; if(i==0){ cout<<" "; for (j=0;j<N;j++) cout<<Avaliable[j]<<" ";// }

　cout<<endl; }输出分配资源

　 int changdata(int i)// 进行资源分配 {

　int j; for (j=0;j<M;j++) {//p[j]=Avaliable[j]; Avaliable[j]=Avaliable[j]-Request[j]; //q[i][j]=Allocation[i][j]; Allocation[i][j]=Allocation[i][j]+Request[j]; //z[i][j]=Need[i][j]; Need[i][j]=Need[i][j]-Request[j]; }

　return 1; }

　int safe()// 安全性算法 {

　int i,d,k=0,m,h,s,apply,Finish[100]={0}; int j; int flag=0; for(i=0;i<N;i++) Work[i]=Avaliable[i]; cout<<endl<<" 安全性检查 "<<endl; cout<<" Work Need Allocation Work+Allocation Finish"<<endl; cout<<" 进程名 "; for(h=0;h<4;h++){ for(s=0;s<N;s++) cout<<name[s]<<" "; cout<<" "; }

　 cout<<endl; for(i=0;i<M;i++){ apply=0; for(j=0;j<N;j++){ if (Finish[i]==False&&Need[i][j]<=Work[j]) {

　apply++; if(apply==N) { cout<<" "<<i<<" "; for(d=0;d<N;d++) cout<<Work[d]<<" "; cout<<" "; for(d=0;d<N;d++) cout<<Need[i][d]<<" "; cout<<" "; for(d=0;d<N;d++) cout<<Allocation[i][d]<<" "; cout<<" "; for(m=0;m<N;m++) { Work[m]=Work[m]+Allocation[i][m]; cout<<Work[m]<<" " }// 变分配数 Finish[i]=True; temp[k]=i; cout<<" "; cout<<"true"<<" "; cout<<endl;

　 i=-1; k++; flag++; } } } }

　for(i=0;i<M;i++){ if(Finish[i]==False){ for(j=0;j<N;j++){ Avaliable[j]=Avaliable[j]+Request[j];; Allocation[i][j]=Allocation[i][j]-Request[j];; Need[i][j]=Need[i][j]+Request[j]; } cout<<endl<<" 系统进入不安全状态！此时系统不 分配资源！

　"<<endl;// 不成功系统不安全 return 0; } }

　cout<<endl<<" 此时系统是安全的 !"<<endl;// 如果 安全，输出成功 cout<<" 安全序列为 :";

　 for(i=0;i<M;i++){// 输出运行进程数组 cout<<temp[i]; if(i<M-1) cout<<"->"; }

　cout<<endl; return 0; }

　void share()// 利用银行家算法对申请资源对进行判定 {

　char ch; int i=0,j=0; ch="y";

　{ // 出错

　cout<<endl<<" 请输入要求分配的资源进程号 (0- "<<M-1<<"):"; cin>>i;// 输入须申请的资源号 cout<<endl<<" 请输入进程 "<<i<<" 申请的资 源 :"<<e ndl; for(j=0;j<N;j++) {

　cout<<name[j]<<":"; cin>>Request[j];// 输入需要申请的资源 }

　for (j=0;j<N;j++){ if(Request[j]>Need[i][j])// 判断申请是否大于需 求，若大于则出错 { cout<<endl<<" 进程 "<<i<<" 申请的资源大于它 需要的资源 "; cout<<" 分配不合理，不予分配！

　"<<endl; ch="n"; break; }

　else { if(Request[j]>Avaliable[j])// 判断申请是否 大于当前资源，若大于则

　 cout<<endl<<" 进程 "<<i<<" 申请的资源大于系 统现在可利用的资源 "; cout<<" 分配出错，不予分配 !"<<endl; ch="n"; break; } } } if(ch=="y") { changdata(i);// 根据进程需求量变换资源 showdata();// 根据进程需求量显示变换后的资源 safe();// 根据进程需求量进行银行家算法判断 } }

　int main()// 主函数 {

　int t=1,i,j,number,choice,m,n,flag; char ming;

　<<endl; cout<<endl<<" 请首先输入系统可供资源种类的数量 cin>>n;

　cout<<" ***************** 银行家算法的设计与 实现

　 N=n; for(i=0;i<n;i++) coutvv" 资源 "<<i+1<<" 的名称 :"; cin>>ming; name[i]=ming; cout<<" 资源的数量 :"; cin>>number; Avaliable[i]=number; cout<<endl; cout<<" 请输入作业的数量 :"; cin>>m; M=m; 请输入各进程的最大需求量 矩阵 ）[Max]:"«e ndl; for(i=0;i<m;i++) for(j=0;j<n;j++) cin>>Max[i][j]; do{ flag=0;

　矩阵 )[Allocati on ]:"<<e ndl; for(i=0;i<m;i++) for(j=0;j<n;j++){cout<<endl<<" ("<<m<<"*"<<n<<" cout<<endl<<" 请输入各进程已经申请的资源量 ("<<m<<"*"<<n<<"

　 cin>>Allocation[i][j]; if(Allocation[i][j]>Max[i][j]) flag=1; Need[i][j]=Max[i][j]-Allocation[i][j]; } if(flag) cout<<endl<<" 申请的资源大于最大需求量，请重 新输入 !\n"<<endl; }

　while(flag); showdata();// 显示各种资源 safe();// 用银行家算法判定系统是否安全 while(1){ if(t==1){ cout<<endl<<" 利用银行家算法预分配资源 "<<endl; share(); t=0;} else break; cout<<endl<<" 是否继续银行家算法？ ( 按 1 键继续 , 按其它任意键退出 ):"; cin>>t; cout<<endl;

　 return 1; } 五、程序执行结果：

　 请输入各进程的最大需求量鸽旳矩阵”帕小 3 2

　此时刻的资源分配情祝为：

　tl-ax A Hoc 且 t icm Need Available 进程名 R B € ABC ft B C AUG 6 7 S 3 0 1 @ 7 4 3 S 3 2 1 3 2 2 2 » a 12 2

　2 9 fl 2 3 0 2 £09

　3 2 2 2 2 11 Oil

　4 4 3 3 0 0 2 4 3 1

　Fit

　ft B C

　rrR : 3 - -■

　3 : 2

　2 2 0 请输入作业的数量汚

　安全性检查

　 此时垂统是安全的？ 安全序列为 ：

　1->3->0->2->4 利用银行家算法预分配资源 请输入要求分配的资源进程号 <0-4> ：

　1 请输入进程 1 申请的资源：

　A ：

　1 B ：

　0 C ：

　2 此时刻的资源分配懵况为：

　Aualiahle

　Max A 1location Need 进程名 ABC ABC ABC ABC

　0 ? 5 3 0 10 7 4 3 2 3 0

　1 3 2 2 3 R 2 D 2 D

　 2 9 0 2 3 0 2 6 0 0

　 3 2 2 2 2 11 0 11

　 4 4 3 3 0 0 2 4 3 1

　 安全性检杳

　Wo >*k Need ft1location Wo>*k*A 1 locatr ion Pin ish 进程名 ABC ABC ABC ABC

　1 2 3 0 0 2 0 3 0 2 5 3 2 true 3 5 3 2 0 11 2 11 7 4 3 t>*ue 0 7 4 3 7 4 3 0 10 7 5 3 true 2 ? 5 3 6 0 8 3 0 2 10 5 5 true 4 1R 5 5 4 3 1 A A 2 1H 5 7 tvue 此时系统是安全的？

　 女全序列:1->3->0- >2->4

　是否继续银行家算法？〈按 1 键继续，按其它任意健退岀

　 利用银行家算法预分配资源 请输入要求分配的资源进程号 : 4 请输入进程 4 申请的资源：

　A ：

　3 B ：

　3 C ：

　0 进程 4 申请的资源大于系统现在可利用的资源分酉己岀错，不予分配? 是否继续银行家算法？〈按 1 键继续，按其它旺意键退出〉汽进程名 1 3 0 2 4 Work ABC 3 3 2 5 3 2 7 4 3 7 5 3 10 5 5 Need ABC 12 2 0 11 7 4 3 6 0 0 4 3 1 Hllocation ABC 2 11 0 0

　IJouk" llocat 1.0 n ABC 5 3 2 7 4 3 7 5 3 10 5 5 10 5 7 Finish true true true true true

　用银行家算法预分 S 己资源

　 请输儿要求分■配的资源进程 请输入进程 0 申请的资源: A ：

　0 B ：

　2 C ：

　0

　安全性检查

　 六、实验总结 多个进程同时运行时，系统根据各类系统资源的最大需求和各 类系统的剩余资源为进程安排安全序列，使得系统能快速且安 全地运行进程，不至发生死锁。银行家算法是避免死锁的主要 方法，其思路在很多方面都非常值得我们来学习借鉴 。

　09 信管（ 2 ）班 何美西 1 匕时刻的资源分配情况为 Max 程名 ABCAllocat ion ABC 2 2

　0 0

　 0/

　Need ABC 7 2 3 0 2 0 6 0 0 Q 1 1 4 3 1 Avaliable ABC 2 1 B AJork+Allocat ion ABC Fin is 11 Work ABC Need. ABC Allocation ABC 系统进入不安全状态！此时系统不分配资