#include<iostream>
using namespace std;
int m,n;//设置资源数、进程数为全局变量
void Banker(int *Request,int *Available,int **Allocation,int **Need);//函数声明部分
void Security(int *Available,int **Allocation,int **Need);
void PrintProcess(int *array,int *Work,int *Available,int **Allocation,int **Need);
void main()
{
cout<<"请输入资源类数：";
cin>>m;
int *Available=new int[m+1];//建立Available数组长度为资源类数加1，从1开始存储
int *Request=new int[m+1];//建立Request数组存放进程请求的资源数目
for(int i=1;i<=m;i++)
{
cout<<"请输入当前系统可用资源"<<i<<"的数目(Available)：";
cin>>Available[i];//初始化Available数组
}
cout<<"\n请输入进程数：";
cin>>n;
int **Max=new int*[n+1];//创建动态二维数组Max,Need,Allocation.
for(i=0;i<=n;i++)
Max[i]=new int[m+1];
int **Need=new int*[n+1];//数组大小为(n+1)*(m+1),以便从1开始计数
for(i=0;i<=n;i++)
Need[i]=new int[m+1];
int **Allocation=new int*[n+1];
for(i=0;i<=n;i++)
Allocation[i]=new int[m+1];
for(i=1;i<=n;i++)//初始化Allocation矩阵
{
cout<<"请输入进程"<<i<<"已经分配的"<<m<<"类资源的数目(Allocation)：";
for(int j=1;j<=m;j++)
cin>>Allocation[i][j];
}
cout<<endl;
int *A=new int[m+1];//数组A用于存放已经分配出去的每类资源的数目
for(i=1;i<=m;i++)
A[i]=0; //初始化A数组每项为0
for(int j=1;j<=m;j++)
for(i=1;i<=n;i++)
A[j]=A[j]+Allocation[i][j];
for(i=1;i<=n;i++)//初始化Max矩阵
{
cout<<"请输入进程"<<i<<"对"<<m<<"类资源的最大需求量(Max)：";
for(int j=1;j<=m;j++)
{
L1: cin>>Max[i][j];
if(Max[i][j]>A[j]+Available[j]) //若需求量大于当前资源可用量和已分配出去的量的总和，则不能满足需求
{
cout<<"需求过大，请重新输入！";
goto L1;
}
}
}
for(i=1;i<=n;i++)//初始化Need矩阵,Need=Max-Allocation
{
for(j=1;j<=m;j++)
Need[i][j]=Max[i][j]-Allocation[i][j];
}
Banker(Request,Available,Allocation,Need);//调用银行家算法
}
void Banker(int *Request,int *Available,int **Allocation,int **Need)//银行家算法
{
int x;
L3: cout<<"\n当前请求资源的进程为：";
cin>>x;
L2: cout<<x<<"号进程请求的各类资源数目为(Request)：";
for(int i=1;i<=m;i++)
{
cin>>Request[i];
if(Request[i]>Need[x][i])
{
cout<<"请求的资源数量超过最大需求值！请重新输入！";
goto L2;
}
if(Request[i]>Available[i])
{
cout<<"当前无足够资源分配给进程"<<m<<"请重新选择请求资源的进程！";
goto L3;
}
}
for(int j=1;j<=m;j++)//如果可以满足此进程的需求，则对Available,Allocation,Need做相应的修改
{
Available[j]=Available[j]-Request[j];
Allocation[x][j]=Allocation[x][j]+Request[j];
Need[x][j]=Need[x][j]-Request[j];
}
Security(Available,Allocation,Need);//调用安全性算法检查系统安全性
}
void Security(int *Available,int **Allocation,int **Need)//安全性算法
{
int *Work=new int[m+1];//设置工作向量Work,表示系统可提供给进程继续运行所需的各类资源数目
for(int i=1;i<=m;i++)
Work[i]=Available[i];//初始化Work=Available
int *Finish=new int[n+1];//设置向量Finish,表示系统是否有足够的资源分配给进程，使之运行完成，0代表FALSE，1代表TRUE
for(i=1;i<=n;i++)
Finish[i]=0;//初始化每个进程的Finish向量为0
int *array=new int[n+1];//array存储安全调度的进程号组成的序列
for(i=1;i<=n;i++)
array[i]=0;//初始化安全序列为0
int sum=0,t=1;
i=1;
while(sum!=n)//说明仍有进程未调度
{
if(Finish[i]==0) //当前进程并未被执行
{
int pass=0;
for(int j=1;j<=m;j++)
{
if(Need[i][j]<=Work[j])//确保每一类资源的需求量都小于当前能提供的资源量
pass=pass+1;
}
if(pass==m) //如果pass变量等于m，说明每一类资源都足够分配给当前进程，当前选定的进程可以运行
{
for(int j=1;j<=m;j++)
Work[j]=Work[j]+Allocation[i][j];
Finish[i]=1;
array[t]=i;//将当前的进程号存放到安全序列数组中
t++;
i++;
if(i==n+1)//如果当前已经搜索到进程队列的末尾，那么将重新从1开始继续搜索符合条件的进程
i=1;
sum=0;
for(int ii=1;ii<=n;ii++)
sum=sum+Finish[ii];
continue;//当前进程资源释放完毕，继续搜索下一个满足条件的进程
}
else //pass变量不等于m，说明资源不足够分配给当前进程，需选择其他进程
{
i++;
if(i==n+1)//如果当前已经搜索到进程队列的末尾，那么将重新从1开始继续搜索符合条件的进程
i=1;
sum=0;
for(int ii=1;ii<=n;ii++)
sum=sum+Finish[ii];
continue;
}
}
else //当前进程已经被执行过
{
i++;//搜索下一个
if(i==n+1)//如果当前已经搜索到进程队列的末尾，那么将重新从1开始循环搜索符合条件的进程
i=1;
sum=0;
for(int ii=1;ii<=n;ii++)
sum=sum+Finish[ii];
continue;
}
}
PrintProcess(array,Work,Available,Allocation,Need);
//跳出while循环，说明所有进程Finish[i]=1都满足，程序调度完毕，系统处于安全状态
cout<<"当前系统安全!\n可以满足此进程资源请求!\n";
cout<<"\n安全序列为：";
for(t=1;t<=n;t++)
cout<<array[t]<<" ";
cout<<endl;
}
void PrintProcess(int *array,int *Work,int *Available,int **Allocation,int **Need)
{
int tt=1;
for(int i=1;i<=m;i++)
Work[i]=Available[i];//初始化Work=Available
cout<<"\n试探将资源分配给当前进程,进行安全性检查...\n\n";
cout<<" ----------------------------------------------------------------\n";
cout<<" Work Need Allocation Work+Allocation Finish\n";
while(tt<=n)
{
cout<<" P"<<array[tt]<<" ";
for(int j=1;j<=m;j++)
cout<<Work[j]<<" ";
cout<<"\t";
for(j=1;j<=m;j++)
cout<<Need[array[tt]][j]<<" ";
cout<<" ";
for(j=1;j<=m;j++)
cout<<Allocation[array[tt]][j]<<" ";
cout<<" ";
for(j=1;j<=m;j++)
cout<<Work[j]+Allocation[array[tt]][j]<<" ";
cout<<"\t TRUE\n";
for(j=1;j<=m;j++)
Work[j]=Work[j]+Allocation[i][j];
tt++;
}
cout<<" ----------------------------------------------------------------\n";
}
