大家好,又见面了,我是你们的朋友全栈君。
自从写完第一篇博客,发现写博客也挺好玩的,比平时写word应付作业有趣的多,而且文章在网上还能帮助别人,自己平时也经常看CSDN,这不,老师要求我们实现一下操作系统的银行家算法,所以我就来了!
那么,什么是银行家算法呢?如果你很了解请跳过这一段,就是解决死锁问题的一个算法,是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础,判断并保证系统的安全运行,那么有人又会问什么是死锁?通俗来讲,就是两个进程各占了一个资源,都在等待对方让出资源从而可以进行下一步,下面我找了一张图可以帮助更清楚的认识,T1、T2是两个进程,R1、R2为两个资源。
所以银行家算法产生了,它是借助于银行家借贷时的策略而产生的一种算法,基本思想为两个模块,一个是主模块即银行家算法模块,第二个是安全性检查模块,银行家算法模块要做的是当又进程申请资源时,先检查当前系统是否能够满足进程的需求,如果能满足就试分配,程序进入安全性检查模块,如果不能满足就拒绝申请,从而保证资源不会被“空手套白狼”。
银行家算法中数据结构主要是几个数组
1、可利用资源向量Available。这是一个含有m个元素的数组,其中的每一个元素代表一类可利用的资源数目,其初始值是系统中所配置的该类全部可用资源的数目,其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K,则表示系统中现有Rj类资源K个。
2、最大需求矩阵Max。这是一个n×m的矩阵,它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K,则表示进程i需要Rj类资源的最大数目为K。
3、分配矩阵Allocation。这也是一个n×m的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K,则表示进程i当前已分得Rj类资源的数目为K。
4、需求矩阵Need。这也是一个n×m的矩阵,用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K,则表示进程i还需要Rj类资源K个,方能完成其任务。
由数学知识易得
Need[i, j]=Max[i, j]-Allocation[i, j]
银行家模块:
设Request i是进程Pi的请求向量,如果Request i[j]=K,表示进程P i需要K个R j类型的资源。当P i发出资源请求后,系统按下述步骤进行检查:
(1) 如果Request i[j]<=Need[i,j],便转向步骤(2);否则认为出错,因为它所需要的资源数已超过它所宣布的最大值。
(2) 如果Request i[j]≤Available[j],便转向步骤(3);否则,表示尚无足够资源,Pi须等待。
(3) 系统试探着把资源分配给进程P i,并修改下面数据结构中的数值:
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) 系统执行安全性算法,检查此次资源分配后系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,以完成本次分配;否则,将本次的试探分配作废,恢复原来的资源分配状态,让进程Pi等待。
安全性检查模块:
(1) 设置两个向量:
① 工作向量Work,它表示系统可提供给进程继续运行所需的各类资源数目,它含有m个元素,在执行安全算法开始时,Work:=Available。
② Finish,它表示系统是否有足够的资源分配给进程,使之运行完成。开始时先做Finish[i]:=false;当有足够资源分配给进程时,再令Finish[i]:=true。
(2) 从进程集合中找到一个能满足下述条件的进程:
① Finish[i]=false;
② Need[i,j]≤Work[j];若找到,执行步骤(3),否则,执行步骤(4)。
(3) 当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:
Work[j]:= Work[j]+Allocation[i,j];
Finish[i]:=true;
go to step (2);
(4) 如果所有进程的Finish[i]=true都满足,则表示系统处于安全状态;否则,系统处于不安全状态。
下面来举个栗子:
假定系统有五个进程{P0,P1,P2,P3,P4}和三类资源{A,B,C},各种资源的数量分别为10、5、7,在T0时刻的资源分配情况如图示。 (先忽略P1第二行的括号)
(1) T0时刻的安全性:利用安全性算法对T0时刻的资源分配情况进行分析如下图可知,在T0时刻存在着一个安全序列{P1,P3,P4,P2,P0},故系统是安全的。
(2) P1请求资源:P1发出请求向量Request1(1,0,2),系统按银行家算法进行检查:
① Request1(1,0,2)≤Need1(1,2,2)
② Request1(1,0,2)≤Available1(3,3,2)
③ 系统先假定可为P1分配资源,并修改Available,Allocation1和Need1向量,形成的资源变化情况如下图圆括号所示
④ 再利用安全性算法检查此时系统是否安全。
(4) P0请求资源:P0发出请求向量Requst0(0,2,0),系统按银行家算法进行检查:
① Request0(0,2,0)≤Need0(7,4,3);
② Request0(0,2,0)≤Available(2,3,0);
③ 系统暂时先假定可为P0分配资源,并修改有关数据
(5) 进行安全性检查:可用资源Available(2,1,0)已不能满足任何进程的需要,故系统进入不安全状态,此时系统不分配资源。
下面则是我的代码实现部分:
#include <iostream>
#include <vector>
using namespace std;
#define MAX 20
int n_process;//表示进程的个数
int n_resource;//表示资源的个数
int Resource[MAX];//表示资源的总数
int Max[MAX][MAX];//表示进程对每类资源的最大需求量
int Allocation[MAX][MAX];//表示系统给进程已分配每类资源的数目
int Need[MAX][MAX];//表示进程还需各类资源数目
int Available[MAX];//表示系统当前剩下的资源
int Work[MAX];//表示安全性检查的中间变量
bool Finish[MAX];//表示资源是否被安全性检查过
vector<int> Safeorder;//表示安全序列
void Menu()
{
cout << "------------------Banker----------------------" << endl;
cout << "* 1.初始化数据 *" << endl;
cout << "* 2.申请资源 *" << endl;
cout << "* 3.显示资源分配情况 *" << endl;
cout << "* 4.退出 *" << endl;
cout << "----------------------------------------------" << endl;
cout << "请选择:";
}
void checkInit()
{
if (n_resource)
for (int i = 0; i < n_process; i++)
{
for (int j = 0; j < n_resource; j++)
{
if (Max[i][j] < 0)
cout << "Max[" << i << "][" << j << "]输入值小于0!" << endl;
if (Allocation[i][j] < 0)
cout << "Allocation[" << i << "][" << j << "]输入值小于0!" << endl;
if (Allocation[i][j]>Max[i][j])
cout << "Allocation[" << i << "][" << j << "]的值大于Max[" << i << "][" << j << "]输入值" << endl;
}
}
for (int i = 0; i < n_resource; i++)
{
if (Available[i]<0)
cout << "Available[" << i << "]的值小于0!" << endl;
}
cout << "输入检查完毕!" << endl;
}
int Init()
{
if (n_resource != 0 && n_process != 0)
{
cout << "你已经初始化过了!" << endl;
return 1;
}
cout << "请分别输入资源个数和进程个数,中间用空格隔开:" << endl;
cin >> n_resource >> n_process;
cout << "请输入各个资源的总拥有量:" << endl;
for (int i = 0; i < n_resource; i++)
cin >> Resource[i];
for (int i = 0; i < n_process; i++)
{
cout << "P" << i << "对各个资源的最大需求量:" << endl;
for (int j = 0; j < n_resource; j++)
cin >> Max[i][j];
cout << "P" << i << "各个资源已分配量:" << endl;
for (int j = 0; j < n_resource; j++)
cin >> Allocation[i][j];
for (int j = 0; j < n_resource; j++)
Need[i][j] = Max[i][j] - Allocation[i][j];
}
for (int i = 0; i < n_resource; i++)
{
int sum[MAX] = { 0 };
for (int j = 0; j < n_process; j++)
{
if (i == 0)
sum[i] += Allocation[j][i];
if (i == 1)
sum[i] += Allocation[j][i];
if (i == 2)
sum[i] += Allocation[j][i];
}
Available[i] = Resource[i] - sum[i];
}
checkInit();
return 1;
}
bool Safecheck()
{
Safeorder.clear();
for (int i = 0; i < n_resource; i++)
Work[i] = Available[i];
for (int i = 0; i < n_process; i++)
Finish[i] = false;
//开始安全性检查
int count = 0;
for (int k = 0; k < n_process; k++)
{
for (int i = 0; i < n_process; i++)
{
if (Finish[i] == false)
{
count = 0;
for (int j = 0; j < n_resource; j++)
{
if (Need[i][j] <= Work[j])
count++;
}
if (count == n_resource)
{
for (int j = 0; j < n_resource; j++)
{
Work[j] = Work[j] + Allocation[i][j];
}
Finish[i] = true;
Safeorder.push_back(i);
}
}
}
}
count = 0;
for (int i = 0; i < n_process; i++)
{
if (Finish[i] == true)
count++;
}
if (count == n_process)
return true;
else
return false;
}
int Order()
{
int n = -1; //请求资源的进程号
int *Request = new int[n_resource];//表示请求的各个资源数量
cout << "请输入你要请求的进程号:";
cin >> n;
cout << "请输入你要请求各个资源的数量,中间用空格隔开:" << endl;
for (int i = 0; i< n_resource; i++)
cin >> Request[i];
//开始判断
for (int i = 0; i < n_resource; i++)
{
if (Need[n][i] < Request[i])
{
cout << "好啊你敢骗我,需求量比你的最大需求量还大!玩泥巴去吧!" << endl;
return 1;
}
}
for (int i = 0; i < n_resource; i++)
{
if (Available[i] < Request[i])
{
cout << "系统已经满足不了你了,你走吧!" << endl;
return 1;
}
}
//试分配资源给请求进程,并做安全性检查
for (int i = 0; i < n_resource; i++)
{
Available[i] -= Request[i];
Allocation[n][i] += Request[i];
Need[n][i] -= Request[i];
}
bool Is_safe=Safecheck();
if (Is_safe == true)
{
cout << "系统已经分配资源给P" << n << "进程了!" << endl;
cout << "其中一个安全序列为:" << endl;
for (int i = 0; i < Safeorder.size(); i++)
cout << "P" << Safeorder.at(i) << "->";
cout << "End" << endl ;
}
else
{
cout << "我妈妈说让我不分配资源给你,系统会处于不安全状态!" << endl;
//恢复试分配之前的现场
for (int i = 0; i < n_resource; i++)
{
Available[i] += Request[i];
Allocation[n][i] -= Request[i];
Need[n][i] += Request[i];
}
}
return 1;
}
void Display()
{
cout << endl;
cout << "进程 \t Max \t Allocation\tNeed\tAvailable" << endl;
for (int i = 0; i < n_process; i++)
{
cout << " P" << i << " \t";
for (int j = 0; j < n_resource; j++)
{
cout << Max[i][j] << " ";
}
cout << "\t ";
for (int j = 0; j < n_resource; j++)
{
cout << Allocation[i][j] << " ";
}
cout << "\t";
for (int j = 0; j < n_resource; j++)
{
cout << Need[i][j] << " ";
}
cout << "\t ";
for (int j = 0; i==0&&j < n_resource; j++)
{
cout << Available[j] << " ";
}
cout << endl;
}
cout << endl;
}
int main()
{
int choose = 0;
while (1)
{
Menu();
cin >> choose;
switch (choose)
{
case 1:
Init();
break;
case 2:
Order();
break;
case 3:
Display();
break;
case 4:
cout << "系统已退出!";
return 1;
default:
cout << "就1-4这你都能输错???" << endl;
break;
}
}
}
附上一些程序运行截图
程序菜单界面:
初始化数据:
P1申请资源:
P4申请资源:
P0申请资源:
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/163207.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...