【实验名称】银行家算法
【实验目的】
1.加深了解有关资源申请、避免死锁等概念；
2.体会和了解死锁和避免死锁的具体实施方法；
3.掌握银行家算法，设计实验数据验证其分配策略。
【实验原理】
银行家算法设置以下四个数据结构:
1.可利用资源向量Available:其初始值是系统中所配置的该类全部可用资源的数目。
2.最大需求矩阵Max:它定义了系统中n个进程中的每一个进程对m类资源的最大需求。
3.分配矩阵Allocation:它定义了系统中每一类资源当前已分配给每一个进程的资源数。
4.需求矩阵Need：用一表示每一个进程尚需的各类资源数。
【实验内容】
实验内容：设计一个n个并发进程共享m个系统资源的程序实现银行家算法。
代码（详情见代码注释）：
#include<iostream>
using namespace std;
int n, m; //系统中进程总数n和资源种类总数m
int Available[100]; //资源可用总量
int Max[100][100]; //最大需求矩阵
int Allocation[100][100] = {0}; //当前给分配给每个进程的各种资源数量
int Need[100][100];//当前每个进程还需分配的各种资源数量
int Work[100]; //当前可分配的资源
bool Finish[100]; //进程是否结束
//显示功能
void show_function()
{
cout << "\n\n* 功能选择 *" << endl;
cout << "*1.显示当前资源情况 *" << endl;
cout << "*2.当前状态安全检查 *" << endl;
cout << "*3.请求资源分配 *" << endl;
cout << "*4.退出程序 *" << endl;
return;
}
//初始数据输入
void input()
{
cout << "请输入进程总数：" << endl;
cin >> n;
cout << "请输入资源种类总数：" << endl;
cin >> m;
cout << "请依次输入各种资源数量：" << endl;
for (int i = 0; i < m; i++)
{
cin >> Available[i];
}
for (int i = 0; i < n; i++)
{
cout << "*** 输入进程P" << i << "的初始信息 ***" << endl;
cout << "请输入该进程所需各资源的最大量：" << endl;
for (int j = 0; j < m; j++)
{
cin >> Max[i][j];
}
cout << "请输入该进程已分配各资源的数量：" << endl;
for (int j = 0; j < m; j++)
{
cin >> Allocation[i][j];
}
}
return;
}
//显示当前资源情况
void show()
{
//输出分配矩阵Allocation
cout << "\n*** 当前资源分配情况 ***" << endl;
cout << "进程";
for (int i = 0; i < m; i++)
{
cout << "\t资源" << i;
}
cout << endl;
for (int i = 0; i < n; i++)
{
cout << "P" << i;
for (int j = 0; j < m; j++)
{
cout << "\t" << Allocation[i][j];
}
cout << endl;
}
//输出需求矩阵Need
cout << "\n*** 当前资源需求情况 ***" << endl;
cout << "进程";
for (int i = 0; i < m; i++)
{
cout << "\t资源" << i;
}
cout << endl;
for (int i = 0; i < n; i++)
{
cout << "P" << i;
for (int j = 0; j < m; j++)
{
cout << "\t" << Need[i][j];
}
cout << endl;
}
//输出可利用资源量Available
cout << "\n*** 当前资源剩余情况 ***" << endl;
for (int i = 0; i < m; i++)
{
cout << "资源" << i << "\t";
}
cout << endl;
for (int j = 0; j < m; j++)
{
cout << Available[j] << "\t";
}
cout << endl;
//输出进程执行情况
cout << "\n*** 当前进程执行情况 ***" << endl;
for (int i = 0; i < n; i++)
{
cout << "进程" << i << "\t";
}
cout << endl;
for (int j = 0; j < n; j++)
{
if (Finish[j])
{
cout << "true" << "\t";
}
else
{
cout << "false" << "\t";
}
}
cout << endl;
}
//判断是不是所有进程均已执行完
bool judge_end(bool *finish)
{
bool flag = 1;
for (int i = 0; i < m; i++)
{
if (finish[i] != true)
{
flag = 0;
break;
}
}
return flag;
}
//状态安全检查
void safety(int *result)
{
int ji = 1;
//初始化Work
for (int i = 0; i < m; i++)
{
Work[i] = Available[i];
}
//初始化finish，finish是在本次测试中标记是不是所有进程都执行完
bool finish[100];
for (int i = 0; i < n; i++)
{
finish[i] = Finish[i];
}
int flag1 = 0;
bool flag2 = 1;
for (int i = 0; i < n; i++)
{
//当循环新开始时，标记这次循环当前还没有结束任何进程
if (i == 0)
flag1 = 0;
//跳过已经完成的进程
if (finish[i] == true)
continue;
//Work与Need比较
int flag3 = 1;
for (int j = 0; j < m; j++)
{
if (Work[j] < Need[i][j])
{
flag3 = 0;
break;
}
}
//若资源不够则跳过这一进程
if (flag3 != 1)
{
//是不是本次循环进程一个都没能结束
if (i == n - 1 && flag1 != 1)
{
//分析一个都没能结束的原因
//是不是全部进程已经都执行完了
if (judge_end(finish))
break;
else
{
//存在没结束的进程但无法结束
flag2 = 0;
break;
}
}
continue;
}
else
{
//若资源够，则执行完该进程，释放该进程占用的资源
result[ji] = i;
ji++;
for (int j = 0; j < m; j++)
{
Work[j] = Work[j] + Allocation[i][j];
}
finish[i] = true;
flag1 = 1;//标记这一轮找到了可以执行完的进程
i = -1;//从头再开始遍历进程集合
}
}
result[0] = flag2;
return;
}
//资源分配
bool allocate(int number,int *request)
{
int flag = 1;
for (int i = 0; i < m; i++)
{
if (request[i] > Need[number][i])
{
flag = 0;
break;
}
}
if (flag == 0)
{
cout << "请求大于该进程还需要的资源量，请求不合法" << endl;
return 0;
}
flag = 1;
for (int i = 0; i < m; i++)
{
if (request[i] > Available[i])
{
flag = 0;
break;
}
}
if (flag == 0)
{
cout << "请求大于当前系统剩余的资源量，请求不合法" << endl;
return 0;
}
// 尝试分配
for (int i = 0; i < m; i++)
{
Need[number][i] = Need[number][i] - request[i];
Allocation[number][i] = Allocation[number][i] + request[i];
Available[i] = Available[i] - request[i];
}
//安全性判断
int *result = (int*)malloc(sizeof(int) * 101);
memset(result, -1, sizeof(int) * 101);
safety(result);
if (result[0])
{
cout << "存在此安全序列：";
cout << "P" << result[1];
for (int i = 2;; i++)
{
if (result[i] == -1)
{
break;
}
cout << " --> P" << result[i];
}
cout << endl;
return 1;
}
else
{
cout << "根据安全性检查，本次分配不安全"<<endl;
//撤销分配
for (int i = 0; i < m; i++)
{
Need[number][i] = Need[number][i] + request[i];
Allocation[number][i] = Allocation[number][i] - request[i];
Available[i] = Available[i] + request[i];
}
return 0;
}
}
void end(int number)
{
int flag = 1;
for (int i = 0; i < m; i++)
{
if (Need[number][i] != 0)
{
flag = 0;
break;
}
}
//若果这个进程已经不需要再分配资源了
//执行完该进程，释放已分配资源
if (flag == 1)
{
cout << "*** 进程P"<<number<<"执行完成！ ***" << endl;
Finish[number] = true;
for (int i = 0; i < m; i++)
{
Available[i] = Available[i] + Allocation[number][i];
Allocation[number][i] = 0;
}
}
}
int main()
{
//freopen("in.txt", "r", stdin);
cout << "******************************" << endl;
cout << "*** 欢迎来到银行家算法 ***" << endl;
cout << "***1.显示当前资源情况 ***" << endl;
cout << "***2.当前状态安全检查 ***" << endl;
cout << "***3.请求资源分配 ***" << endl;
cout << "***4.退出程序 ***" << endl;
cout << "******************************\n" << endl;
memset(Finish, false, sizeof(Finish));
//初始数据输入
input();
//计算Need矩阵和剩余的可以利用资源Available
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
Need[i][j] = Max[i][j] - Allocation[i][j];
Available[j] = Available[j] - Allocation[i][j];
}
}
int flag;
while (true)
{
//功能选择
show_function();
cout << "请选择功能：";
cin >> flag;
if (flag == 1)
{
//显示当前资源情况
//包括当前资源分配情况和资源剩余情况
show();
}
else if (flag == 2)
{
//当前状态安全检查
int *result = (int*)malloc(sizeof(int) * 101);
memset(result, -1, sizeof(int) * 101);
safety(result);
if (result[0] == 1)
{
cout << "存在此安全序列：";
cout << "P" << result[1];
for (int i = 2;; i++)
{
if (result[i] == -1)
{
break;
}
cout << " --> P" << result[i];
}
cout << endl;
cout << "*** 此刻状态安全 ***" << endl;
}
else
{
cout << "*** 此刻状态不安全！ ***" << endl;
}
}
else if (flag == 3)
{
//请求资源分配
int *request = (int*)malloc(sizeof(int) * 100);
int number;
cout << "请输入发出请求的进程：P";
cin >> number;
cout << "请输入请求各资源的数量：" << endl;
for (int i = 0; i < m; i++)
{
cin >> request[i];
}
if (allocate(number, request))
{
cout << "*** 该分配安全，分配成功！ ***" << endl;
//成功分配的进程，能完成的就完成，释放占用的资源
end(number);
}
else
{
cout << "*** 分配失败！ ***" << endl;
}
}
else if (flag == 4)
{
//退出程序
cout << "成功退出！" << endl;
break;
}
}
return 0;
}
运行演示（详情见图片中解释）：
以课本银行家算法的例题作为输入数据。
从实验结果可以看出，实验成功。
【小结或讨论】
在银行家算法中主要实现了：显示当前资源情况、当前状态安全检查、请求资源分配等功能。为实现这些功能我设计了如下函数：初始数据输入函数void input()、显示当前资源情况函数void show()、判断是不是所有进程均已执行完bool judge_end(bool *finish)、状态安全检查函数void safety(int *result)、资源分配函数bool allocate(int number,int *request)、进程结束函数void end(int number)等。
这次实验我觉得核心难点就是安全状态的判断，这一块确实比较复杂，如果思路不够清晰就很容易混乱。这一块我在上述代码中已经加了很详细的注释，在这里我再总结一下我的总体思路：
1. 先初始化Work；
2. 初始化finish，直接复制Finish数组，因为这里只是尝试分配，我们不能直接用真实标记进程结束的Finish数组；
3.完成初始化后我们开始从头遍历进程集合，在循环新开始时，标记这次循环当前还没有结束任何进程，因为才刚刚开始嘛，肯定是没有的；
4.判断，跳过已经完成的进程；
5. Work与Need比较；
6. 若资源不够则跳过这一进程；
7.跳过时先判断，是不是已经到最后一个进程了？若是，是不是本次循环进程一个都没能结束？如果还是的话分析原因，是不是因为全部进程已经都执行完了？若是则状态安全，且找到了安全序列。若不是则表明存在没结束的进程但无法结束，即该状态不安全。
8. 若资源够，则执行完该进程，释放该进程占用的资源。把这个进程纳入安全序列、将该进程标记结束、标记这一轮找到了可以执行完的进程、从头再开始遍历进程集合。
上面的这个过程可以说是十分复杂了，我也是认真思考了好久才写出来的，之前我把进程结束的判断放在了进程循环的开头，但这种方式就导致遍历到最后一个自动跳出，而跳出了“本次循环进程一个都没能结束”的判断，导致本来是不安全状态的判断出错。
以上就是对安全状态的总结了，其他我觉得就不是很困难了。因为这里比较难、比较重要的缘故，这里的算法我看的十分详细。所以在理解之后，再写银行家算法就比较流畅了，写起来也知道前因后果了。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/34748.html
