银行家算法
一、实验目的
1、理解银行家算法。
2、掌握进程安全性检查的方法及资源分配方法。
二、实验要求与内容、过程与结果
1、将图5-1补充完整，画出银行家算法的流程图。
图5-1 银行家算法的流程图
2、将图5-2补充完整，画出安全性检查算法的流程图。
图5-2 安全性检查算法的流程图
3、编写补充完整模拟银行家算法程序sy-5.cpp，并以下面给出的例子来验证编写程序的正确性。要求记录程序运行过程和结果。
例子：某系统有A、B、C、D 4类资源共5个进程（P0，P1，P2，P3、P4）共享，各进程对资源的需求的分配情况如表5-1所示。
现在系统中A、B、C、D 4类资源分别还剩下1、5、2、0个，请按银行家算法回答下列问题：
① 现在系统是否处于安全状态？
答：系统当前处于安全状态，安全序列为：0->2->3->4->1。
② 如果现在进程P1提出资源请求（0、4、2、0），系统能否满足它的请求？
答：能满足。
模拟银行家算法程序sy-5.cpp：
#include <iostream>
using namespace std;
int Available[100]; //可利用资源数组
int Max[50][100]; //最大需求矩阵
int Allocation[50][100]; //分配矩阵
int Need[50][100]; //需求矩阵
int Request[50][100];
int Finish[50];
int p[50];
int m,n; //m个进程，n个资源
int IsSafe( ) //系统安全性检查
{
int i,j,L=0;
int Isfind=1;
int Work[100];
for(i=0; i<n; i++)
Work[i] = Available[i] ; //建立Available副本Work，即对Work初始化
for(i=0; i<m; i++)
Finish[i] = 0 ; // 对Finish进行初始化
while(L<m&&Isfind)
{
Isfind=0;
for(i=0; i<m; i++)
{
if (Finish[i]==1) continue;
else
{
for(j=0; j<n; j++)
if(Need[i][j]>Work[j]) break;
if(j==n)
{
Finish[i]= 1 ; //表示进程i能结束
for(int k=0; k<n; k++)
Work[k] += Allocation[i][k] ; //进程i能结束，释放资源
p[L++]=i;
Isfind=1;
if(L==m)
break;
}
}
}
}
if ( L == m ) //判定是否存在安全系列。提示：判定L与m值的关系
{
cout<<"系统是安全的!"<<"安全系列是："<<endl;
for(i=0; i<m; i++)
{
cout<<p[i];
if(i<m-1) cout<<"-->";
}
cout<<endl;
return 1;
}
else
{
cout<<"系统处于不安全状态！";
return 0;
}
}
int main()
{
int i,j,mi,flag=1;
cout<<"输入进程数目：\n";
cin>>m;
cout<<"输入资源的种类数：\n";
cin>>n;
cout<<"输入每个进程最多所需要的各资源数，按照"<<m<<"×"<<n<<"矩阵输入！\n";
for(i=0; i<m; i++)
for (j=0; j<n; j++)
cin>>Max[i][j];
cout<<"输入每个进程已分配的各资源数，也按照"<<m<<"×"<<n<<"矩阵输入！\n";
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<<"个资源数错误，请重新输入!\n";
j--;
continue;
}
}
}
cout<<"请输入各个资源现有的数目：\n";
for(i=0; i<n; i++)
cin>>Available[i];
if(IsSafe()!=1)
return 0;
while(1)
{
flag=1;
cout<<"输入要申请资源的进程号(第一个进程号为0，以此类推):\n";
cin>>mi;
cout<<"输入该进程所请求各资源的数量：\n";
for(i=0; i<n; i++)
cin>>Request[mi][i];
for(i=0; i<n&&flag; i++)
{
if ( Need[mi][i]<Request[mi][i] )
{
cout <<"进程P"<<mi<<"的资源请求数超过进程的需求量，拒绝分配！\n";
flag=0;
break;
}
if ( Available[i]<Request[mi][i] )
{
cout <<"进程P"<<mi<<"的请求数超过了系统所可用的资源数，拒绝分配！\n";
flag=0;
break;
}
}
if(flag)
{
for(i=0; i<n; i++) //试探分配资源给进程mi
{
Available[i]-= Request[mi][i] ;
Allocation[mi][i]+=Request[mi][i];
Need[mi][i]-= Request[mi][i] ;
}
if ( IsSafe() == 1 ) cout<<"同意分配请求！\n" ; // 提示：调用安全性检测函数
else
{
cout<<"资源分配请求被拒绝！\n";
for(i=0; i<n; i++) //恢复进程mi以前的资源分配状态
{
Available[i]+=Request[mi][i];
Allocation[mi][i]-= Request[mi][i] ;
Need[mi][i]+=Request[mi][i];
}
}
}
for(i=0; i<m; i++)
Finish[i]=0;
char YesNo;
while(1)
{
cout<<"继续请求资源分配请按 y或Y ，结束程序请按 n或N ：";
cin>>YesNo;
cout<<endl;
if (YesNo=='y'||YesNo=='Y') break;
else if (YesNo=='n'||YesNo=='N') return 0;
}
}
}
本程序是一个简单的银行家算法实现，可以模拟对多进程的资源分配管理。
程序功能：
1.输入进程数目和资源种类数目； 2.输入每个进程最多需要的各资源的数量和已经分配的各资源的数量，计算出每个进程还需要的各个资源数量； 3.输入各个资源当前可用的数量； 4.进行系统安全性检查，判断系统是否处于安全状态； 5.根据用户输入，模拟对进程的资源请求分配； 6.如果分配后系统仍然处于安全状态，同意分配请求，否则拒绝分配请求； 7.根据用户输入，判断是否退出程序。
程序结构：
程序主体部分由主函数实现，包含了系统安全性检查函数IsSafe()和分配资源请求的处理部分。
主要变量：
1.Available[]：可用资源数组，记录每个资源当前可用的数量。 2.Max[][]：进程最多需要各资源的的数量。 3.Allocation[][]：各进程已分配的各资源数量。 4.Need[][]：各进程还需要的各资源数量。 5.Request[][]：进程的资源请求。 6.Finish[]：标记进程是否执行完毕。 7.p[]：存储安全序列。
程序运行流程：
1.用户输入进程数目和资源种类数目； 2.用户输入每个进程最多需要的各资源的数量和已经分配的各资源的数量，计算出每个进程还需要的各个资源数量； 3.用户输入各个资源当前可用的数量； 4.调用IsSafe()函数，判断系统是否处于安全状态； 5.用户输入资源分配请求，根据银行家算法进行资源分配请求处理； 6.如果处理后系统处于安全状态，输出同意分配请求信息，否则输出拒绝分配请求信息； 7.询问用户是否继续，并根据用户输入继续或结束程序。
程序分析：
银行家算法能保证系统安全性，即能够防止死锁和饥饿的情况发生。因此，在本程序中，系统安全性检查是必不可少的。IsSafe()函数的具体实现过程为：
1.将Available数组复制到Work数组中； 2.将所有进程的Finish数组置为0； 3.在未处理完所有进程的情况下，遍历所有进程，寻找可以结束的进程（即进程的Need数组小于等于Work数组）； 4.如果找到可以结束的进程，将该进程标记为已结束（Finish数组置为1），将该进程所占用的资源释放（即Work数组增加Allocation数组中该进程所占用的资源数量），将该进程的进程号存储到安全序列p[]数组中，此时需要重新遍历所有进程； 5.如果无法找到可以结束的进程，则说明系统不安全。
程序中分配资源请求的处理部分的具体实现过程为：
1.用户输入进程号和资源请求数量； 2.判断资源请求是否超过进程的需求量，如果超过则拒绝分配请求并进行下一次请求； 3.判断资源请求是否超过系统可用资源数量，如果超过则拒绝分配请求并进行下一次请求； 4.对进程进行试探性分配，如果分配后系统处于安全状态，则同意分配请求，否则拒绝分配请求，将资源分配状态恢复到进程请求前的状态； 5.询问用户是否继续进行资源请求分配，并根据用户输入决定是否继续。