【操作系统实验 / C++】模拟银行家算法（附代码）

【操作系统实验 / C++】模拟银行家算法（附代码）

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;elseflag = 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;elsereturn 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();elsereturn; 
}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;}elsecout<<endl<<"在规定次数内未发现安全序列。"<<endl<<endl;break;default:cout<<endl<<"输入错误！程序将关闭，请重新启动。"<<endl<<endl;break;}system("pause");return 0;
}