【注意】代码在文末，以下为详细实验报告
【实验目的】
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性；若分配不会导致系统进入不安全状态，则分配，否则等待。通过编写一个模拟动态资源分配的银行家算法程序，帮助学生进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念，并掌握避免死锁的具体实施方法
【实验内容】
Linux下实现银行家算法，通过构造可利用资源向量、最大需求矩阵、分配矩阵以及需求矩阵来进行判断，当进程请求资源时，系统必须确定是否有足够的资源分配给该进程，是否处于不安全状态。整个银行家算法分为假定分配资源、安全性检查两步，如果通过安全性检查，则为进程分配相应资源。
【实验环境】（含主要设计设备、器材、软件等）
【实验步骤、过程】（含原理图、流程图、关键代码，或实验过程中的记录、数据等）
一、数据结构
（1）可利用资源向量Available
可利用资源向量是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果Available［j］=K，则表示系统中现有Rj类资源K个。
（2）最大需求矩阵Max
最大需求矩阵是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max［i,j］=K，则表示进程i需要Rj类资源的最大数目为K。
（3）分配矩阵Allocation
分配矩阵是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation［i,j］=K，则表示进程i当前已分得Rj类资源的数目为K。
（4）需求矩阵Need。
需求矩阵是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need［i,j］=K，则表示进程i还需要Rj类资源K个，方能完成其任务。
Need［i,j］=Max［i,j］-Allocation［i,j］
图1 数据结构
二、算法描述
1.银行家算法
设Requesti是进程Pi的请求向量，如果Requesti［j］=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：
(1)如果Requesti［j］≤Need［i,j］，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布最大值。
(2)如果Requesti［j］≤Available［j］，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。
(3)系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：
Available［j］=Available［j］-Requesti［j］;
Allocation［i,j］=Allocation［i,j］+Requesti［j］;
Need［i,j］=Need［i,j］-Requesti［j］;
系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。
2.安全性算法
(1）设置两个向量：
工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available;
工作向量Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish［i］=false; 当有足够资源分配给进程时， 再令Finish［i］=true。
(2）从进程集合中找到一个能满足下述条件的进程：
Finish［i］=false;
Need［i,j］≤Work［j］；若找到，执行 (3)，否则，执行 (4)
(3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
Work［j］=Work［i］+Allocation［i,j］;
Finish［i］=true;
go to step 2;
(4）如果所有进程的Finish［i］=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态;
图2 安全性算法代码实现
三、程序流程图
1.总体流程图
图3 总体流程图
图4 分配资源实现代码
3.安全性算法
图5 安全性算法流程图
四、伪代码
1.安全性算法伪代码
int safe() //当前分配是否满足安全性
{
int j=0;
int tag=0;
for(int i=0;i<输入的进程数;i++)
将所有进程的Finish置为false；
for(int i=0;i<输入的资源数;i++)
{
work = available
}
for(int k=0;k<输入的进程数;k++)
{
for(int i=0;i<输入的进程数;i++)
{
if (Finish处于完成状态)
{
不再执行下面语句，进入下次循环；
}
for (j=0;j<资源数;j++)
{
if (need>work)
{
break；
}
}
if(判断条件j等于资源数)
{
for(j=0;j<自由数;j++)
Work = work + allocation；
Finish = true；
}
}
}
if (满足安全性判断函数)
{return 1}
else reurn 0;
}
2.分配资源伪代码
void request() //某进程向系统请求资源
{
int index;
int i=0;
for (int m=0;m<资源数;m++)
{
将安全序列清空；
}
临时可利用资源
临时资源分配矩阵
临时需求矩阵
//用临时的资源进程储存，方便判断安全性法则是否满足
//先将各种资源数、进程数、需求矩阵拷贝到各个临时矩阵中去
cout<<请输入请求资源的进程号
cin>>index;
cout<<"请输入请求进程请求各个资源的数目号："<<endl;;
for (int ii=0;ii<资源数;ii++)
{
输入到Request[index][ii];
}
//判断此请求是否满足要求
for( i=0;i<资源数;i++)
{
if (safe())
{
结束下面语句，直接进入下一次循环
}
else if(requset>need)
{
cout<<"进程请求错误！"<<endl;
break;
}
else
{
cout<<"请求不被允许，请等待！"<<endl;
break;
}
}
if (满足条件) //满足条件，假设可为index分配资源
{
for(int j=0;j<资源数;j++)
{
更新各个临时矩阵；
}
if 临时矩阵满足安全性法则)
{
//如果资源分配满足安全性要求，更改实际的各个资源和进程信息
Update all array；
cout<<"满足安全性算法，资源分配成功！"<<endl;
}
else
{
cout<<"不满足安全性算法，不分配资源！"<<endl;
}
}
}
六、编译指令
//银行家算法
$ g++ -o bank.out bank.c
$ ./bank.out
图6 所有编译指令
七、运行结果
银行家算法的运行结果参照课本上的例题，在此处通过代码来对课本上的例题进行验证，课本上的原例题如下所示
假定系统中有五个进程{P0, P1, P2, P3, P4}和三类资源{A,B,C},各种资源的数量分别为10、5、7,在T0时刻的资源分配情况下表所示。
（1）T0时刻安全性检测
（2）P1请求资源: P1发出请求向量Request1(1, 0, 2)，系统按银行家算法进行检查，再利用安全性算法对分配后系统安全性进行检测判断是否真的分配。
（3）P4 请求资源: P4 发出请求向量Request4(3，3，0)。
（4）P0请求资源: P0发出请求向量Request0(0, 2, 0)。
（5）将（4）改为Request0(0, 1, 0)。
运行结果如下
图7 运行结果
经运行结果验证，此时刻通过了安全性算法得到检查，属于安全状态，不会发生死锁，接下来假设P1请求资源向量Request1为（1,0,2）
运行结果如下
图8 运行结果
由所进行的安全性检查得知，可以找到一个安全序列{P1，P3，P0，P2，P4}。因此，系统是安全的，可以立即将P1所申请的资源分配给它
下面P4请求资源（3,3,0）
满足Request（3,3,0）<=Need（4,3,1）
但是Request（3,3,0）>Avaliable（2,3,0），因此P4等待
下面P0请求资源（0,2,0）
运行结果如下
图9 运行结果
由图可知，可用资源Available（2,1,0）已不能满足任何进程的需要，故系统没有通过安全性检查，进入不安全状态，此时系统不分配资源。
【实验结果或总结】（对实验结果进行相应分析，或总结实验的心得体会，并提出实验的改进意见）
在银行家算法中主要实现了：显示当前资源情况、当前状态安全检查、请求资源分配等功能。同时也让我更加深入地理解了死锁发生所必须的四个条件：互斥、请求和保持、不抢占、循环等待，也让我明白了，安全状态一定是没有死锁发生，而不安全状态不一定导致死锁。
最后感谢倪福川老师和其他同学给予我的帮助，我也会继续努力，更加认真地完成每一次作业，学好操作系统。
代码
#include <iostream>
#include<cstring>
using namespace std;
#define False 0
#define True 1
//主要数据结构
int N=50;//进程的最大数
int M=100;//资源的最大数
char NAME[100]={0};//资源的名称
int Max[50][100]={0};//最大需求矩阵
int Avaliable[100]={0};//可用资源矩阵
int Allocation[50][100]={0};//系统已分配矩阵
int Need[50][100]={0};//还需要资源矩阵
int Request[100]={0};//请求资源向量
int Security[100]={0};//存放安全序列
int Work[100]={0};//存放系统可提供资源
/********
初始化数据：输入进程数量、资源种类、
各种资源可利用数量、
各进程的资源已分配数量、
各进程对资源最大需求量等。
********/
void chushihua()
{
/* n为进程个数，即矩阵行数，m为资源个数，即矩阵列数。*/
int i,j,n,m;
int number,flag;
char name;//输入资源名称
cout<<"系统可用资源个数为:";
cin>>m;
M=m;
for(i=0;i<m;i++)
{
cout<<"资源"<<i<<"的名称:";
cin>>name;
NAME[i]=name;
cout<<"资源"<<name<<"的初始个数为:";
cin>>number;
Avaliable[i]=number;
}
cout<<endl;
cout<<"请输入进程的数量:";
cin>>n;
N=n;
cout<<"请输入各进程的最大需求矩阵的值("<<n<<"*"<<m<<"矩阵)[Max]:"<<endl;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
cin>>Max[i][j];
int temp[100]={0};
do
{
flag=0;
cout<<"请输入各进程已经分配的资源量("<<n<<"*"<<m<<"矩阵)[Allocation]:"<<endl;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
cin>>Allocation[i][j];
if(Allocation[i][j]>Max[i][j]) flag=1;
Need[i][j]=Max[i][j]-Allocation[i][j];
temp[j]+=Allocation[i][j];
}
if(flag==1)
cout<<"申请的资源大于最大需求量，请重新输入!";
cout<<endl;
}while(flag);
for(j=0;j<m;j++)
Avaliable[j]=Avaliable[j]-temp[j];
}
/********
显示资源分配矩阵
********/
void showdata()
{
int i,j;
cout<<"*************************************************************"<<endl;
cout<<"系统目前可用的资源[Avaliable]:"<<endl;
for(i=0;i<M;i++)
cout<<NAME[i]<<" ";
cout<<endl;
for (j=0;j<M;j++)
cout<<Avaliable[j]<<" ";//输出分配资源
cout<<endl;
cout<<"系统当前的资源分配情况如下："<<endl;
cout<<" Max Allocation Need"<<endl;
cout<<"进程名 ";
for(j=0;j<3;j++)
{
for(i=0;i<M;i++)
cout<<NAME[i]<<" ";
cout<<" ";
}
cout<<endl;
for(i=0;i<N;i++)
{
cout<<" P"<<i<<" ";
for(j=0;j<M;j++)
cout<<Max[i][j]<<" ";
cout<<" ";
for(j=0;j<M;j++)
cout<<Allocation[i][j]<<" ";
cout<<" ";
for(j=0;j<M;j++)
cout<<Need[i][j]<<" ";
cout<<endl;
}
}
/********
安全性算法
********/
int safe()
{
int i,j,k=0,n,apply;
int Finish[100]={0};
for (j=0;j<N;j++)
Work[j]=Avaliable[j];
for(i=0;i<N;i++)
{
apply=0;
for(j=0;j<M;j++)
{
if (Finish[i]==False&&Need[i][j]<=Work[j])
{
apply++;
if(apply==M)
{
for(n=0;n<M;n++)
Work[n]=Work[n]+Allocation[i][n];//变分配数
Finish[i]=True;
Security[k]=i;
i=-1;
k++;
}
}
}
}
for(i=0;i<N;i++)
{
if(Finish[i]==False)
{
cout<<"系统不安全，已瘫痪"<<endl;//不成功系统不安全
return -1;
}
}
cout<<"系统是安全的!"<<endl;//如果安全，输出成功
cout<<"存在一个安全序列:";
for(i=0;i<N;i++)
{//输出运行进程数组
cout<<"P"<<Security[i];
if(i<N-1) cout<<"->";
}
cout<<endl;
return 0;
}
/********
尝试分配资源
********/
int test(int i)//进行资源分配
{
int j;
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];
}
return 1;
}
/********
利用银行家算法对申请资源对进行试分配
********/
void bank()
{
char ch;
int i,j;
ch='y';
cout<<"请输入请求分配资源的进程号(0-"<<N-1<<"):";
cin>>i;//输入须申请资源的进程号
cout<<"请输入进程P"<<i<<"要申请的资源个数:"<<endl;
for(j=0;j<M;j++)
{
cout<<NAME[j]<<":";
cin>>Request[j];//输入需要申请的资源
}
for (j=0;j<M;j++)
{
if(Request[j]>Need[i][j])//判断申请是否大于需求，若大于则出错
{
cout<<"进程P"<<i<<"申请的资源大于它需要的资源";
cout<<" 分配不合理，不予分配！"<<endl;
ch='m';
break;
}
else
{
if(Request[j]>Avaliable[j])//判断申请是否大于当前可分配资源，若大于则出错
{
cout<<"进程"<<i<<"申请的资源大于系统现在可利用的资源";
cout<<endl;
cout<<" 系统尚无足够资源，不予分配!"<<endl;
ch='m';
break;
}
}
}
if(ch=='y')
{
test(i);//根据进程需求量变换资源
showdata();//根据进程需求量显示变换后的资源
safe();//根据进程需求量进行银行家算法判断
}
}
int main()//主函数
{
char choice;
cout<<"\t---------------------------------------------------"<<endl;
cout<<"\t|| ||"<<endl;
cout<<"\t|| 银行家算法的实现 ||"<<endl;
cout<<"\t|| ||"<<endl;
cout<<"\t|| ||"<<endl;
cout<<"\t|| 在此输入个人姓名：卢家伟 ||"<<endl;
cout<<"\t|| ||"<<endl;
cout<<"\t---------------------------------------------------"<<endl;
chushihua();//初始化数据
showdata();//显示各种资源
safe();//用银行家算法判定系统是否安全
while(choice)
{
cout<<"*************************************************************"<<endl;
cout<<endl;
cout<<endl;
cout<<"\t-------------------银行家算法演示------------------"<<endl;
cout<<" R(r):请求分配 "<<endl;
cout<<" E(e):退出 "<<endl;
cout<<"\t---------------------------------------------------"<<endl;
cout<<"请选择：";
cin>>choice;
switch(choice)
{
case 'r':
case 'R':
bank();break;
case 'e':
case 'E':
choice=0;break;
default: cout<<"请正确选择!"<<endl;break;
}
}
}
