admin 管理员组文章数量: 887006
文章检索器
- 1 创作的小心思
- 2 追根溯源
- 3 算法设计
- 3.1 银行家算法
- 3.1.1 所需维护的数据结构
- 3.1.2 算法执行步骤
- 3.1.3 流程图
- 3.2 安全性算法
- 3.2.1 所需维护的数据结构
- 3.2.2 算法执行步骤
- 3.2.3 流程图
- 4 算法示例
- 4.1 示例题目
- 4.2 例题求解
- 5 C++代码实现
- 5.1 C++源代码（全）
- 5.2 测试截图
- 5.2.1 初始化
- 5.2.2 进程1发出资源请求（1，0，1）
- 5.2.3 进程2发出资源请求（1，0，1）
- 5.2.4 检查当前状态安全性
1 创作的小心思
该作旨在完成老师布置的实验任务，也借此机会系统的将银行家算法再学一遍。也可以蹭一波大家的热度，嘻嘻🤭，欢迎来访🎉🎉🎉
2 追根溯源
银行家算法（Banker’s Algorithm） 是一个避免死锁（Deadlock） 的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。(来源：百度百科)
3 算法设计
3.1 银行家算法
3.1.1 所需维护的数据结构
1、可利用资源向量 A v a i l a b l e Available Available。这是一个含有 m m m个元素的一维数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态的改变。若
A v a i l a b l e [ j ] = K Available[j] = K Available[j]=K,则表示系统中现有 R j R_j Rj 类资源 K K K 个。
2、最大需求矩阵 M a x Max Max。这是一个 n × m n×m n×m 的矩阵，它定义了系统中 n n n 个进程中的每个进程对 m m m 类资源的最大需求。若 M a x [ i ] [ j ] = K Max[i][j] = K Max[i][j]=K ,则表示进程 i i i 需要 R j R_j Rj 类资源的最大数目为 K K K 。
3、分配矩阵 A l l o c a t i o n Allocation Allocation。这是一个 n × m n×m n×m 的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。若 A l l o c a t i o n [ i ] [ j ] = K Allocation[i][j] = K Allocation[i][j]=K ,则表示进程 i i i 当前已分得 R j R_j Rj 类资源的数目为 K K K 。
4、需求矩阵 N e e d Need Need。这是一个 n × m n×m n×m 的矩阵，用以表示每一个进程尚需的各类资源数。若 N e e d [ i ] [ j ] = K Need[i][j] = K Need[i][j]=K ,则表示进程 i i i 还需要 R j R_j Rj 类资源 K K K个方能完成其任务。
3.1.2 算法执行步骤
设 R e q u e s t [ i ] Request[i] Request[i] 是进程 P i P_i Pi 的请求向量， 如果 R e q u e s t [ i ] [ j ] = K Request[i][j]=K Request[i][j]=K, 表示进程 P i P_i Pi 需要 K K K 个 R j R_j Rj类型的资源。
当 P i P_i Pi 发出资源请求后，系统按下述步骤进行检查：
(1)、如果 R e q u e s t [ i ] [ j ] ≤ N e e d [ i ] [ j ] Request[i][j]≤Need[i][j] Request[i][j]≤Need[i][j],便转向步骤(2); 否则认为出错，因为它所需要的资源数已经超过它所宣布的最大值。
(2)、如果 R e q u e s t [ i ] [ j ] ≤ A v a i l a b l e [ j ] Request[i][j]≤Available[j] Request[i][j]≤Available[j] ,便转向步骤(3); 否则，表示尚无足够资源， P i P_i Pi 须等待。
(3)、系统试探着把资源分配给进程 P i P_i Pi ，并修改下面数据结构中的值：
A v a i l a b l e [ j ] = A v a i l a b l e [ j ] − R e q u e s t [ i ] [ j ] A l l o c a t i o n [ i ] [ j ] = A l l o c a t i o n [ i ] [ j ] + R e q u e s t [ i ] [ j ] N e e d [ i ] [ j ] = N e e d [ i ] [ j ] − R e q u e s t [ i ] [ j ] Available[j]=Available[j]-Request[i][j] \\ Allocation[i][j]=Allocation[i][j]+Request[i][j] \\ Need[i][j]=Need[i][j]-Request[i][j] Available[j]=Available[j]−Request[i][j]Allocation[i][j]=Allocation[i][j]+Request[i][j]Need[i][j]=Need[i][j]−Request[i][j]
(4)、系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程 P i P_i Pi ，以完成本次分配；否则，将本次试探分配作废，恢复原来资源分配状态，让进程 P i P_i Pi 等待。
3.1.3 流程图
3.2 安全性算法
3.2.1 所需维护的数据结构
1、工作向量 W o r k Work Work, 这是一个含有 m m m 个元素的一维数组，它表示系统可提供给进程继续运行所需的各类资源的数目，在执行安全算法开始时， W o r k = A v a i l a b l e Work=Available Work=Available。（其实和 A v a i l a b l e Available Available 所维护的内容一样）
2、进程状态向量 F i n i s h Finish Finish，这是一个含有 n n n 个元素的一维数组,它表示每一个进程是否运行完成，用布尔值来表示进程的状态， F i n i s h [ i ] = T r u e Finish[i]=True Finish[i]=True 表示进程 P i P_i Pi 已经运行完成，否则运行未完成。
3.2.2 算法执行步骤
(1) 从进程集合中找到一个能满足下述条件的进程：
① F i n i s h [ i ] = F a l s e Finish[i]=False Finish[i]=False;
② N e e d [ i ] [ j ] ≤ W o r k [ j ] Need[i][j]≤Work[j] Need[i][j]≤Work[j];（注意：此处需要所有 m m m 类资源都满足该条件）
若找到，执行步骤(2)，否则，执行步骤(3)。
(2) 当进程 P i P_i Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源：
W o r k [ j ] = W o r k [ j ] + A l l o c a t i o n [ i ] [ j ] ; F i n i s h [ j ] = T r u e ; g o t o s t e p 1 ; Work[j]=Work[j]+Allocation[i][j]; \\ Finish[j]=True; \\ go\ to\ step\ 1; Work[j]=Work[j]+Allocation[i][j];Finish[j]=True;go to step 1;
(4) 如果所有进程的Finish[i]=True都满足，则表示处于安全状态；否则，系统处于不安全状态。
3.2.3 流程图
4 算法示例
4.1 示例题目
4.2 例题求解
5 C++代码实现
5.1 C++源代码（全）
1.0版本，后续有时间了可能会再回来加强一波。请求资源方面，目前只能一次性分配一个，不能同时得到请求，需要改进，其他的基本功能算是实现了。执行过程的状态，比交好实现，加个输出就OK，比较简单，代码中就没实现。
#include<cstdio>
#include<queue>
#include<vector>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010, M = 1010;
int n, m;
int Max[N][M], Allocation[N][M], Need[N][M];
int Available[M], Finish[N];
int Work[M], Request[M];
int Sum[M];//系统中m类资源的总量
void Init()
{
cout << "请输入合法的矩阵" << endl;
cout << "初始化Max矩阵" << endl;
cout << "请输入一个" << n << "行" << m << "列的矩阵:" << endl;
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
cin >> Max[i][j];
cout << "初始化Allocation矩阵" << endl;
cout << "请输入一个" << n << "行" << m << "列的矩阵:" << endl;
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
cin >> Allocation[i][j];
cout << "初始化Available向量" << endl;
cout << "请输入一行" << m << "个元素表示当前可用资源的数量:" << endl;
for (int i = 1;i <= m;i++) cin >> Available[i];
/*初始化Need矩阵*/
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= m;j++)
{
Need[i][j] = Max[i][j] - Allocation[i][j];
}
}
/*初始化Sum矩阵*/
for (int j = 1;j <= m;j++)
{
for (int i = 1;i <= n;i++)
{
Sum[j] += Allocation[i][j];
}
Sum[j] += Available[j];
}
cout << "初始化成功>^V^<" << endl;
}
/*判断初始化矩阵的合法性*/
bool Judge()
{
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= m;j++)
{
if (Allocation[i][j] > Max[i][j]) return false;
}
}
return true;
}
/*判断当前work向量是否大于Need[i]向量*/
bool Judge(int k)
{
for (int j = 1;j <= m;j++)
{
if (Need[k][j] > Work[j]) return false;
}
return true;
}
/*安全性检查的时候虚拟处理*/
void VirtureDeal(int k)
{
for (int j = 1;j <= m;j++)
{
Work[j] += Allocation[k][j];
}
Finish[k] = true;
}
/*安全性检查*/
bool SecurityCheck(queue<int>& q)
{
memcpy(Work, Available, sizeof Available);
memset(Finish, false, sizeof Finish);
for(int k = 1;k <= n;k++) //n次迭代
{
bool flag = false;
for (int i = 1;i <= n;i++)
{
if (!Finish[i] && Judge(i))
{
flag = true;
q.push(i);
VirtureDeal(i);
break;
}
}
if (!flag) return false;
}
return true;
}
/*试探性分配资源*/
void Alloc(int k)
{
for (int j = 1;j <= m;j++)
{
Allocation[k][j] += Request[j];
Need[k][j] -= Request[j];
Available[j] -= Request[j];
}
}
/*恢复原状*/
void Recover(int k)
{
for (int j = 1;j <= m;j++)
{
Allocation[k][j] -= Request[j];
Need[k][j] += Request[j];
Available[j] += Request[j];
}
}
/*请求资源*/
void Query()
{
int ID;
cout << "请输入进程ID(1 -- " << n << "):" << endl; cin >> ID;
cout << "请输入请求向量(输入" << m << "个有效整数):" << endl;
for (int j = 1;j <= m;j++) cin >> Request[j];
for (int j = 1;j <= m;j++)
{
if (Request[j] > Need[ID][j])
{
cout << "出错，请求的资源大于需求资源" << endl;
return;
}
else if (Request[j] > Available[j])
{
cout << "进程无法得到资源，继续处于等待状态！" << endl;
return;
}
}
Alloc(ID);//试探性分配
queue<int> q;
if (SecurityCheck(q))
{
cout << "分配资源成功！" << endl;
cout << "其中的一个安全序列是：";
bool mark = false;
while (q.size())
{
if (mark) cout << "->";
cout << q.front();q.pop();
mark = true;
}
cout << endl;
}
else {
cout << "无法执行分配任务！" << endl;
Recover(ID);//无法执行分配，恢复原状
}
}
int main()
{
cout << "请输入进程个数: "; cin >> n;
cout << "请输入资源的种类数: "; cin >> m;
Init();
system("pause");
while (1)
{
system("cls");
cout << "1、请求资源" << endl;
cout << "2、检查当前状态的安全性" << endl;
cout << "0、退出主程序" << endl;
while (1)
{
int op; cin >> op;
if (op < 0 || op > 2) {
cout << "操做错误，请重新输入！！！" << endl;
system("pause");
}
else {
if (op == 0) exit(0);
else if (op == 1) {
Query();
system("pause");
}
else if (op == 2)
{
queue<int> q;
if (SecurityCheck(q))
{
cout << "当前状态安全" << endl;
cout << "其中的一个安全序列是：";
bool mark = false;
while (q.size())
{
if (mark) cout << "->";
cout << q.front();q.pop();
mark = true;
}
cout << endl;
}
else {
cout << "当前状态不安全，极有可能进入死锁状态" << endl;
}
system("pause");
}
}
break;
}
}
return 0;
}
/*
Max
3 2 2
6 1 3
3 1 4
4 2 2
Allocation
1 0 0
4 1 1
2 1 1
0 0 2
Available
2 1 2
*/
5.2 测试截图
5.2.1 初始化
5.2.2 进程1发出资源请求（1，0，1）
5.2.3 进程2发出资源请求（1，0，1）
5.2.4 检查当前状态安全性
欢迎大家在评论区提出自己的疑问，我会在评论区进行回复。
也欢迎批评我写的不足之处，能力范围之内我会进行加强，我们一起共勉👊。
版权声明：本文标题：【操作系统】银行家算法的实现 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1728415698h1240723.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论