1、题目要求
请参照课本上的银行家算法的实例，设计、实现银行家算法。
输入：某个进程请求的资源数量；
输出：已分配或者拒绝本次请求。
要求循环显示提示信息“请输入请求资源的数量和进程号：”。
2、数据结构设计
根据题目要求，以及银行家算法的特性，使用了多个全局数组用于存储进程和资源的情况。共5个进程，3个资源，如下图所示。
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; //表示当前正在处理的进程序号
同时，除了资源相关的数组外，还设置了几个信号量数组或值，用于存储每一个进程的完成情况、安全队列、完成的进程个数等。
3、程序主要思路和原理
主要思路：
- 对于该题目，我完成了两种算法，一种是题目要求的循环请求资源，输入进程的序号以及请求资源数，达到所需资源数后完成进程，以及释放资源。另一种是产生一组随机数，并尝试能否通过这组随机数产生一个安全队列，若能够产生则输出该队列。
- 提到的两种方法中，在请求资源的部分两者共用相同的函数，即判断输入的进程所需的资源数能否被当前可用的资源数满足，若能满足则分配该资源，完成进程后释放资源。同时，对银行家算法特性设置了一个安全检测函数，检测当前的资源分配是否会导致冲突，即其他的内存均没有足够的资源，若资源分配导致不安全则阻止此次分配。
- 不同的地方在于，产生安全队列的算法中，我采用了一个随机数算法用来生成一个0-4的随机数，随后尝试当前可用资源能否满足该序号的进程运行，若能满足则先将资源分配给该进程，进程结束后再释放资源，同时修改进程相关的信号量，避免再次分配资源给该进程。若在规定次数（50次）内5个进程均完成，则输出记录的安全队列，否则停止循环并说明未找到安全序列。
原理：全局数组、变量，安全性检测，随机数算法
4、程序运行结果
首先运行程序，进行初始化。依次输入最大需求数目Max，已分配数目Allocation，以及当前资源的可用数目Available。随后打印出当前进程和资源的列表，可见需要的资源数目Need已经算出。
-
①随机数算法产生安全队列： 随后出现操作列表，选择操作2，则开始通过一组随机数产生安全队列，并且依次输出结果，如下图所示。
可见成功的产生了一组安全序列。 -
②循环请求资源： 再次运行程序，初始化后选择操作1，首先对进程0请求一个A资源，输出结果如下图所示。
此时若再对进程1请求一个C资源，会造成系统死锁，资源不足以分配，此时安全性算法检测到了该错误，拒绝了此次资源分配。
此时再对进程0请求一个B资源，安全性算法没有产生问题。完成分配。
最后再对进程0请求一个C资源，进程0达到了最大需求，进程进行并完成，随后释放资源。可以看到进程0的已分配矩阵和需要资源都进行了清零，同时原先分配的资源全部进入剩余可用资源。
由上述结果可知，程序运行正常，且能够完成预先设定的两种运算，即循环请求资源和随机数算法产生安全队列，该实验完成。
5、详细代码
#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;
}
版权声明：本文为OKWeCool原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。