银行家算法
银行家算法模拟实现
直接上代码吧！！！
bank.h:
#include<iostream>
using namespace std;
#include<vector>
//预定资源数组
#define PRO 50//最大进程数
#define MAXAVSUR 10//最大资源种类数
int AVAILABLE[MAXAVSUR];//现有可使用资源数
int ALLOCATION[PRO][MAXAVSUR];//已分配资源数
int NEED[PRO][MAXAVSUR];//各个进程现需资源数
int REQUESET[MAXAVSUR];//银行家算法中请求申请资源的数目
//初始化方式以一个进程为单位，现将本进程的ALLOCATION 输完紧接着输入 NEED
void init(int pro, int sur)
{
cout << "请按照格式给出初始化数据!!" << endl;
cout << "格式：ALLOCATION [SUR1] [SUR2] .... | NEED [SUR1] [SUR2] ....\n";
for (int i = 0; i<pro; i++)
{
for (int j = 0; j<sur; j++)
{
cin >> ALLOCATION[i][j];
}
for (int j = 0; j<sur; j++)
{
cin >> NEED[i][j];
}
}
cout << "格式：AVAILABLE [SUR1] [SUR1]...\n";
for (int j = 0; j<sur; j++)
{
cin >> AVAILABLE[j];
}
cout << "初始化工作完毕！！" << endl;
cout << "------------------------------------------------------" << endl;
cout << "AVAILABLE" << endl;
for (int j = 0; j<sur; j++)
{
cout << AVAILABLE[j]<<" ";
}
cout << endl;
cout << "ALLOCATION\t\t\t NEED\t\t\t " << endl;
for (int i = 0; i<pro; i++)
{
for (int j = 0; j<sur; j++)
{
cout << ALLOCATION[i][j] << "\t";
}
for (int j = 0; j<sur; j++)
{
cout << NEED[i][j] << "\t";
}
cout << endl;
}
}
//安全性算法
bool safe(int* list, int pro, int sur, int req)
{
//work数组定义
int work[MAXAVSUR];
for (int i = 0; i<sur; i++)
{
work[i] = AVAILABLE[i];
}
//标记当前安全进程
bool finish[PRO] = { false };
int l = 0;//一次找一个，找pro次
int j = 0;//控制每个进程的资源类型
bool flag = false;
//每一趟循环必须寻找到一个或者多个，用flag表示寻到一个或者多个。
//当flag为假时，表明已经死锁，直接退出，返回flag表示不安全
//当l = pro时表示安全序列可以找到，为安全，返回flag。
while (l < pro)
{
flag = false;
for (int i = 0; i < pro; i++)
{
if (finish[i] == true)
continue;
for (j = 0; j < sur; j++)
{
if (NEED[i][j] > work[j])
break;
}
if (j == sur)
{
flag = true;
finish[i] = true;
for (int k = 0; k < sur; k++)
{
work[k] += ALLOCATION[i][k];
}
list[l++] = i;
}
else
continue;
}
if (flag == false)
return flag;
}
return flag;
}
void bank()
{
int n, m, pro1;//进程数，资源种类,请求分配的进程
//初始化工作
printf("请输入进程个数[n]: ");
cin >> n;
printf("请输入资源种类数:[m]: ");
cin >> m;
init(n, m);
//银行家算法
bool avalid = false;//检测所要求申请资源进程的合法性
while (1)
{
cout << "请输入想要为之申请资源的进程编号，编号在0~n范围之内[pro]: ";
cin >> pro1;
while (avalid == false)
{
if (pro1 > n)
{
cout << "输入的进程不存在，请重新输入:[pro] ";
cin >> pro1;
}
else
avalid = true;
}
//用户为申请进程初始化申请资源
int request[MAXAVSUR];
cout << "输入所要分配的各个资源的数目" << endl;
while (1)
{
for (int j = 0; j < m; j++)
{
cin >> request[j];
}
for (int i = 0; i < m; i++)
{
if (request[i]>AVAILABLE[i])
cout << "request[%d] > AVAILABLE[%d] 请重新输入！！" << endl;
}
break;
}
//预分配结果
for (int j = 0; j < m; j++)
{
AVAILABLE[j] -= request[j];
NEED[pro1][j] -= request[j];
ALLOCATION[pro1][j] += request[j];
}
//安全性算检测
//1.如果安全输出安全序列，并进行是否能进行资源回收工作
//2.否则直接退出
int list[PRO] = { 0 };
if (safe(list, n, m, pro1))
{
cout << "------------------------------------------------------" << endl;
cout << "AVAILABLE：" << endl;
int s;
//以下循环为判断是否需要回收资源，flag为表识
bool flag = false;
for (s = 0; s < m; s++)
{
if (NEED[pro1][s] != 0)
break;
}
if (s == m)
flag = true;
//在打印目前所剩资源之前得进行回收资源操作
for (int j = 0; j<m; j++)
{
//1.判断是否有资源可回收，判断flag标识
if (flag)
{
AVAILABLE[j] += ALLOCATION[pro1][j];
ALLOCATION[pro1][j] = 0;
}
cout << AVAILABLE[j]<< " ";
}
cout << endl;
cout << "安全序列为：" << endl;
for (int i = 0; i < n; i++)
{
cout << list[i] << " ";
}
cout << endl;
cout << "ALLOCATION\t\t\t NEED\t\t\t " << endl;
for (int i = 0; i<n; i++)
{
for (int j = 0; j<m; j++)
{
cout << ALLOCATION[i][j] << "\t";
}
for (int j = 0; j<m; j++)
{
cout << NEED[i][j] << "\t";
}
cout << endl;
}
cout << endl;
}
else
{
cout << "------------------------------------------------------" << endl;
cout << "不可给予分配，不存在安全序列！" << endl;
//不予以分配是将预分配的资源换回
cout << "AVAILABLE" << endl;
for (int j = 0; j < m; j++)
{
AVAILABLE[j] += request[j];
NEED[pro1][j] += request[j];
ALLOCATION[pro1][j] -= request[j];
}
for (int j = 0; j<m; j++)
{
cout << AVAILABLE[j] << " ";
}
cout << endl;
}
cout << "继续分配选择y/n?" << endl;
char ch;
cin >> ch;
if (ch == 'y')
continue;
else
break;
}
}
void testbank()
{
bank();
}
main.cpp:
#include"bank.h"
int main()
{
testbank();
return 0;
}
测试样例：
1.以下序列为可以正常执行不存在死锁的：
2.下面是存在死锁的情况：