/*
=============================================================================
4.银行家算法的数据结构.
1),系统剩余资源量A[n],其中A[n]表示第I类资源剩余量.
2),各进程最大需求量,B[m][n],其中B[j][i]表示进程j对i 类资源最大需求.
3),已分配资源量C[m][n],其中C[j][i]表示系统j程已得到的第i资源的数量.
4),剩余需求量.D[m][n],其中D[j][i]对第i资源尚需的数目.
5.银行家算法流程:当某时刻,某进程时,提出新的资源申请,系统作以下操作:
1),判定E[n]是否大于D[j][n],若大于,表示出错. 2),判定E[n]是否大于系统剩余量A[n],若大于,则该进程等待.
3),若以上两步没有问题,尝试分配,即各变量作调整.
4),按照安全性推测算法,判断,分配过后,系统是否安全,若安全,则实际分配,否则,撤消分配,让进程等待.
6.";安全性检测";算法 1),先定义两个变量,用来表示推算过程的数据. F[n]=A[n],表示推算过程中,系统中剩余资源量的变化. J[n]=False表示推算过程中各进程是否假设";已完成";
2),流程: 在";剩余";的进程中(在推算)过程中,一些进程假设已完成,查找D[j][n]<;=F[n]的进程,找到后令J[j]=True (假设该进程完成),
F[n]+D[j][n](该进程所占资源释放),如此循环执行. 若最后,所有的F[n]=True(在推算过程中,所有进程均可以完成),则表示(分配过后)系统是安全的,否则系统是不安全的.
整体总结:
是这样的...先初始化这几个数组的值（这个不做讲解）, 然后“申请资源”，每个进程都要申请资源操作（这边要判断申请资源是否合法【是否超过所需资源，系统是否有那么多资源】）
如果所有申请资源的进程都合法了，那么就Cost资源（银行家要把用户申请的资源分配下去），分配完了之后开始判断安全性...
【这里重点讲解】,判断安全性的时候，因为之前已经把进程申请的资源都Cost出去了，所以现在“Avaliable数组”是系统剩余的资源的量.
那么判断安全性的时候是这样的....从第一个进程开始判断,如果它的Need(需求量，之前申请成功的时候银行Cost资源时，这个Need有做操作哦)是现在它所需要的资源数
那么如果 " 所需资源数（Need[i][j]） <= 系统资源剩余量(Avaliable[j])"(N个资源都要做这个判断，只有所有N的都满足才可以)
那么这个进程是可以运行的...这时候把Finished[i] = true...标记它为已经运行了，居然已经运行了，那么资源理所应当还给银行才是的...
那么Avaliable[0 -> N] += Need[i][0 -> N]; //把所有资源都还给它...然后这个进程i要设为-1,从头开始判断了...因为有的进程之前不能满足这些条件而不能运行
现在我还了这些资源给银行了，或许那些进程就可以运行了。。。。。
最后如果所有的 进程 Finished[i] 都等于true.....那么恭喜你,成功了！！！死锁拜拜~~~~~O(∩_∩)O
=============================================================================
*/
#include <iostream>
using namespace std;
#define N 100
int Avaliable[N]; //系统剩余资源量,表示第i类资源的剩余数量
int MaxNeed[N][N]; //各进程最大需求量,表示进程对资源的最大需求
int Allcation[N][N]; //已分配资源量,表示对进程已分配资源的数目
int Need[N][N]; //剩余需求量,表示线程对资源尚需的数目
int JNumber; //进程的个数
int SNumber; //资源的种类个数
int Request[N][N]; //存放申请资源的线程的信息
bool Finished[N]; //判断安全性那边要用
int LinShi[N]; //存放临时的系统剩余资源量,判断安全性那边用到
//struct RequestMethod
//{
// int RequestWho; //存放要申请资源的进程
// int RequestClass; //存放要申请资源的种类
// int RequestCount; //存放要申请资源的数目
//}Request[N][N];
//初始化矩阵数据
void Init()
{
cout<<"请输入拥有进程的个数: "<<endl;
cin>>JNumber;
cout<<"请输入资源的种类个数: "<<endl;
cin>>SNumber;
int i, j;
for (i=0; i<SNumber; ++i)
{
cout<<"请输入资源"<<i<<"的系统剩余量: "<<endl;
cin>>Avaliable[i];
}
for (i=0; i<JNumber; ++i)
{
cout<<"请输入进程"<<i<<"对资源"<<j<<"的最大需求量 和 已经分配的数量(按顺序输入哈！): "<<endl;
for (j=0; j<SNumber; ++j)
{
cin>>MaxNeed[i][j]>>Allcation[i][j];
Need[i][j] = MaxNeed[i][j] - Allcation[i][j];
}
}
}
//申请资源模块
void RequestSource()
{
cout<<"请输入各进程要申请的各资源的数目: "<<endl;
int i, j;
bool succed;
for (i=0; i<JNumber; ++i)
{
succed = true;
cout<<"请输入进程"<<i<<"要申请的各资源的数目(以" "隔开): ";
for (j=0; j<SNumber; ++j)
{
cin>>Request[i][j];
if (Request[i][j] > Need[i][j] || Request[i][j] > Avaliable[j])
{
//如果该进程对该资源还需要的数量比要申请的数目来得少的话，那么它就不能这么狠找银行家要那么多资源
//判断一下银行家有没有那么多资源....剥削光银行家倒没关系，就怕他已经没有东东让你剥！
succed = false;
}
}
if (succed == false)
{
cout<<"该进程申请的资源数目有误，请重新输入!"<<endl;
--i;
}
}
}
//资源分配模块
void SourceCost()
{
int i, j;
for (i=0; i<JNumber; ++i)
{
for (j=0; j<SNumber; ++j)
{
Allcation[i][j] += Request[i][j];
Avaliable[j] -= Request[i][j];
Need[i][j] -= Request[i][j];
}
}
}
//资源恢复模块
void SourceRelease()
{
int i, j;
for (i=0; i<JNumber; ++i)
{
for (j=0; j<SNumber; ++j)
{
Allcation[i][j] -= Request[i][j];
Avaliable[j] += Request[i][j];
Need[i][j] += Request[i][j];
}
}
}
//输出当前进程最大需求量，系统资源剩余量，进程已分配量，对资源的尚需求量
void Print()
{
int i, j;
cout<<"系统资源剩余量: "<<endl;
for (i=0; i<SNumber; ++i)
{
cout<<"资源"<<i<<"所剩余资源量: "<<Avaliable[i]<<endl;
}
cout<<"进程资源最大需求量: "<<endl;
for (i=0; i<JNumber; ++i)
{
cout<<"进程"<<i<<"对各资源的最大需求量: ";
for (j=0; j<SNumber; ++j)
{
cout<<MaxNeed[i][j]<<" ";
}
cout<<endl;
}
cout<<"进程已分配资源量: "<<endl;
for (i=0; i<JNumber; ++i)
{
cout<<"进程"<<i<<"各资源的已分配量: ";
for (j=0; j<SNumber; ++j)
{
cout<<Allcation[i][j]<<" ";
}
cout<<endl;
}
cout<<"进程对各资源的剩余需求量: "<<endl;
for (i=0; i<JNumber; ++i)
{
cout<<"进程"<<i<<"各资源的剩余需求量: ";
for (j=0; j<SNumber; ++j)
{
cout<<Need[i][j]<<" ";
}
cout<<endl;
}
}
//安全性判断
bool IsSafe()
{
int i, j, k, SuccedCount = 0;
for (i=0; i<JNumber; ++i)
{
Finished[i] = false;
}
for (i=0; i<SNumber; ++i)
{
LinShi[i] = Avaliable[i];
}
for (i=0; i<JNumber; ++i)
{
//如果已经Finished，下面的步骤就continue咯，太浪费时间了
if (Finished[i] == true)
{
continue;
}
for (j=0; j<SNumber; ++j)
{
if (Need[i][j] > LinShi[j])
{
break;
}
}
if (j == SNumber)
{
Finished[i] = true;
//设置成完成了
for (k=0; k<SNumber; ++k)
{
LinShi[k] += Allcation[i][k]; //资源释放给系统（临时的），毕竟这是在模拟是否安全性，不能真正修改Avaliable的值
}
++SuccedCount;
i = -1; //这里要注意：该进程满足之后，Finished[i] = true; 然后就要把进程下标弄成-1，让它之后再去找下一个可以满足的进程
}
}
if (SuccedCount == JNumber)
return true;
else
return false;
}
//银行家函数
void Bank()
{
int i;
char ch;
do
{
//先初始化
//先判断是否大于自己的尚要的需求
//判断一下是否大于系统剩余的资源
//把资源先拿过来,然后判断安全性
//判断安全性
//安全性不行的话，释放资源
Init(); //初始化模块
cout<<endl;
cout<<"==============================================================="<<endl;
Print();
cout<<"==============================================================="<<endl;
cout<<endl;
RequestSource(); //资源申请模块
SourceCost(); //资源分配模块
if (IsSafe()) //安全性检查模块
{
//如果安全性通过,那么就OK
cout<<"银行家模拟安全性通过，恭喜你成功了！"<<endl;
}
else
{
SourceRelease(); //资源恢复模块
cout<<"银行家模拟安全性没通过，Sorry你失败了！"<<endl;
}
cout<<"是否继续进行银行家模拟~(Y or N)："<<endl;
cin>>ch;
}while (ch == 'Y' || ch == 'y');
}
int main()
{
Bank();
return 0;
}