#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
using namespace std;

int Available[3]; //可用资源数组
int Need[5][3] = {0}; //需要资源数组
int Max[5][3]; //最大需求量数组
int Allocation[5][3]; //当前分配资源数组
int Request[5][3] = {0}; //请求的资源数
int IsFinish[5] = {0}; //判断进程是否完成的数组
int Array[5] = {0}; //安全队列数组
int FinishNum = 0; //完成算法的进程个数
int n=0; //表示当前正在处理的进程序号

void Show() //展示函数
{
cout<<endl;
cout<<"----------------------------------------------------------------------------"<<endl;
cout<<'\t'<<'\t'<<"最大需求矩阵"<<'\t'<<"已分配矩阵"<<'\t'<<"需要资源"<<'\t'<<"剩余可用资源"<<endl;
cout<<'\t'<<'\t'<<" Max "<<'\t'<<"Allocation"<<'\t'<<" Need "<<'\t'<<" Available "<<endl;
cout<<"----------------------------------------------------------------------------"<<endl;
cout<<"进程名称"<<"\tA B C "<<"\tA B C"<<"\tA B C"<<"\tA B C"<<endl;

int i,j;
for(i=0; i<5; i++)
{
cout<<" P"<<i<<'\t'<<'\t';

for(j=0; j<3; j++)
cout<<Max[i][j]<<" ";
cout<<'\t';

for(j=0; j<3; j++)
cout<<Allocation[i][j]<<" ";
cout<<'\t';

for(j=0; j<3; j++)
cout<<Need[i][j]<<" ";
cout<<'\t';

if(i == 0)
{
for(j=0; j<3; j++)
cout<<Available[j]<<" ";
}
cout<<endl;
}
cout<<"----------------------------------------------------------------------------"<<endl;
}
bool Check() //对银行家算法的安全性检测
{
int i,j;
int work[3] = {0};
bool finish[3];

for(i=0; i<3; i++) //初始化
work[i] = Available[i];
for(j=0; j<3; j++)
finish[j] = false;

int check = 0;
bool flag;

for(i=0; i<3; i++)
{
if(Need[n][i] <= work[i])
check ++;
}

if(check == 3)
flag = true;
else
flag = false;

check = 0;

for(i=0; i<3; i++) //循环检测
{
for(i=0; i<3; i++)
{
if(finish[i] == false && flag == true)
{
for(j=0; j<3; j++)
work[j] = work[j] + Allocation[n][j];
finish[i] = true;
check ++;
}
}
}

if(check == 3)
return true;
else
return false;
}
int Finish(int i) //检测某一进程是否完成
{
int j;
int check = 0;

for(j=0; j<3; j++)
{
if(Need[i][j] == 0)
check ++;
}

if(check == 3)
IsFinish[i] = 1;
return IsFinish[i];
}
void Process() //处理请求的函数
{
int i,j,check1 = 0,check2 = 0;

for(i=0; i<3; i++)
{
if(Request[n][i] <= Need[n][i])
{
if(Request[n][i] <= Available[i])
check1 ++;
else
{
cout<<"没有足够的资源分配给进程"<<n<<"请求的 ";
for(j=0; j<3; j++)
{
cout<<Request[n][j]<<" ";
}
cout<<"，请等待！"<<endl<<endl;
}
}

else
{
cout<<"进程"<<n<<"请求的资源 ";
for(j=0; j<3; j++)
cout<<Request[n][j]<<" ";
cout<<"超过了进程的需求数！"<<endl;
}
}

if(check1 == 3) //若请求的资源数目均小于可用
{
cout<<endl<<"开始处理进程"<<n<<"的请求 ";
for(i=0; i<3; i++)
cout<<Request[n][i]<<" ";
cout<<endl;

for(j=0; j<3; j++)
{
Available[j] = Available[j] - Request[n][j];
Allocation[n][j] = Allocation[n][j] + Request[n][j];
Need[n][j] = Need[n][j] - Request[n][j];
}

if(Check() == true)
{
if(Finish(n) == 1) //如果进程结束则释放资源
{
cout<<endl<<"进程"<<n<<"已经结束，释放资源。"<<endl;

for(i=0; i<3; i++)
{
Available[i] = Available[i] + Allocation[n][i];
Allocation[n][i] = 0;
Need[n][i] = 0;
}

Array[FinishNum] = n;
FinishNum ++;
}
Show();
}

else
{
cout<<endl<<"进程"<<n<<"请求的资源 ";
for(j=0; j<3; j++)
cout<<Request[n][j]<<" ";
cout<<"导致系统不安全！资源申请失败！返回。"<<endl;

for(j=0; j<3; j++) //回收资源
{
Available[j] = Available[j] + Request[n][j];
Allocation[n][j] = Allocation[n][j] - Request[n][j];
Need[n][j] = Need[n][j] + Request[n][j];
}
}
}
}
void Requester() //请求队列，产生一个 0-4 的随机数，并尝试是否能生成安全队列
{
int i,j,check = 0;
time_t t;
srand((unsigned)time(&t)+rand());
n = rand()%5;

for(i=0; i<3; i++)
{
if(Need[n][i] <= Available[i])
check ++;
}

for(j=0; j<3; j++)
{
if(check == 3)
{
Request[n][j] = Need[n][j];
}
else
{
srand((unsigned)time(&t)+rand());
Request[n][j] = rand()%5;
}
}

if(IsFinish[n] == 0)
Process();
else
return;
}
int main()
{
int i,j;
cout<<"银行家算法，共有5个进程，3种资源，首先分配资源。"<<endl;
cout<<"请输入每个进程对于每个资源的最大需求数目(3*5)："<<endl;
for(i=0; i<5; i++)
{
for(j=0; j<3; j++)
cin>>Max[i][j];
}

cout<<"请输入每个进程的每个资源的已分配数目(3*5)："<<endl;
for(i=0; i<5; i++)
{
for(j=0; j<3; j++)
{
cin>>Allocation[i][j];
Need[i][j] = Max[i][j] - Allocation[i][j];

if(Need[i][j] < 0)
Need[i][j] = 0;
}
}

cout<<"请输入每个资源的现有可用数目(3)：";
for(i=0; i<3; i++)
cin>>Available[i];

cout<<endl<<"初始化..."<<endl;
Show();

int check = 0;
char choice;

cout<<endl<<"-------------操作列表-------------";
cout<<endl<<"请选择银行家算法的操作模式：";
cout<<endl<<"1.手动请求资源，循环输入进程序号；";
cout<<endl<<"2.根据所给的资源自主算出安全队列。";
cout<<endl<<"----------------------------------";
cout<<endl<<"**请输入选择的操作：";
cin>>choice;

switch(choice)
{
case '1':
do
{
cout<<endl<<"请输入进程号(0-4)：";
cin>>n;

cout<<endl<<"请输入请求的资源(3)：";
for(i=0; i<3; i++)
cin>>Request[n][i];

Process();
}while(FinishNum < 5);
break;

case '2':
do
{
Requester();
check ++;
}while(check != 50);

if(FinishNum == 5)
{
cout<<endl<<"发现一组安全序列：";
for(i=0; i<4; i++)
cout<<Array[i]<<"-->";
cout<<Array[4]<<endl<<endl;
}
else
cout<<endl<<"在规定次数内未发现安全序列。"<<endl<<endl;
break;

default:
cout<<endl<<"输入错误！程序将关闭，请重新启动。"<<endl<<endl;
break;
}

system("pause");
return 0;
}