admin管理员组文章数量:1531659
一、实验目的
用高级语言编写和调试一个银行家算法程序,并可以利用银行家算法模拟分配资源以及进行安全性检查。加深对银行家算法的理解。
二、实验指导
- 银行家算法中的数据结构
(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] - 银行家算法
设Requesti是进程Pi的请求向量,如果Requesti[j]=K,表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后,系统按下述步骤进行检查:
(1) 如果Requesti[j]≤Need[i,j],便转向步骤2;否则认为出错,因为它所需要的资源数已超过它所宣布的最大值。
(2) 如果Requesti[j]≤Available[j],便转向步骤(3);否则, 表示尚无足够资源,Pi须等待。
(3) 系统试探着把资源分配给进程Pi,并修改下面数据结构中的数值:
Available[j]∶=Available[j]-Requesti[j];
Allocation[i,j]∶=Allocation[i,j]+Requesti[j];
Need[i,j]∶=Need[i,j]-Requesti[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[i]+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时刻的资源分配情况如图2-1 所示。
请求序列
(1)P1发出请求向量Request1(1,0,2)
(2)P4发出请求向量Request4(3,3,0)
(3)P0发出请求向量Requst0(0,2,0)
#include<bits/stdc++.h>
using namespace std;
const int m=3;//三类资源
const int n=5;//进程数
//数据结构
int available[m]= {3,3,2}; //可利用资源向量
int Max[n][m]= {7,5,3,3,2,2,9,0,2,2,2,2,4,3,3}; //最大需求矩阵
int allocation[n][m]= {0,1,0,2,0,0,3,0,2,2,1,1,0,0,2}; //分配矩阵
int need[n][m];//需求矩阵
//Need[i,j]=Max[i,j]-Allocation[i,j]
int Request[n][m];//请求
int Work[m];//工作向量
bool Finish[n];//系统是否有足够的资源分配
int WaddA[n][m];//记录W+A
int p[n];//记录进程号
int work[n][m];//记录work
void menu()
{
cout<<endl;
cout<<endl;
cout<<"\t1. 初始化"<<endl;
cout<<"\t2. 查看当前资源分配表"<<endl;
cout<<"\t3. 请求资源"<<endl;
cout<<"\t4. 退出"<<endl;
cout<<"\t请选择:"<<endl;
}
void init()
{
for(int i=0; i<n; i++)
{
cout<<"输入进程P"<<i<<"的资源分配情况(3类资源,空格隔开):\n";
cout<<"Max:";
for(int j=0; j<m; j++)
{
cin>>Max[i][j];
}
cout<<"\nAllocation:\n";
for(int j=0; j<m; j++)
{
cin>>allocation[i][j];
}
}
cout<<"输入当前可用资源数量(3类资源,空格隔开)";
cout<<"Avaliable:";
for(int i=0; i<m; i++)
cin>>available[i];
}
void print()
{
//计算Need
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
need[i][j]=Max[i][j]-allocation[i][j];
}
}
//打印
cout<<"\tMax |"<<"\tAllo |"<<"\tNeed |"<<"\tAvalia"<<endl;
for(int i=0; i<n; i++)
{
cout<<"P"<<i<<" \t";
for(int j=0; j<m; j++)
{
cout<<Max[i][j]<<" ";
}
cout<<"\t";
for(int j=0; j<m; j++)
{
cout<<allocation[i][j]<<" ";
}
cout<<"\t";
for(int j=0; j<m; j++)
{
cout<<need[i][j]<<" ";
}
cout<<"\t";
if(i==0)
{
for(int i=0; i<m; i++)
cout<<available[i]<<" ";
cout<<endl;
}
else
cout<<endl;
}
}
void print_sequence()
{
cout<<"\tWork |"<<"Need |"<<"\tAllo |"<<"\tW+A |"<<" Finish"<<endl;
for(int i=0; i<n; i++)
{
cout<<"P"<<p[i]<<" \t";
for(int j=0; j<m; j++)
{
cout<<work[p[i]][j]<<" ";
}
cout<<"\t";
for(int j=0; j<m; j++)
{
cout<<need[p[i]][j]<<" ";
}
cout<<"\t";
for(int j=0; j<m; j++)
{
cout<<allocation[p[i]][j]<<" ";
}
cout<<"\t";
for(int j=0; j<m; j++)
{
cout<<WaddA[p[i]][j]<<" ";
}
cout<<"\t";
cout<<Finish[p[i]]<<endl;
}
}
bool safety()
{
//初始化
int w=0;
for(int j=0; j<m; j++)
Work[j]=available[j];
for(int i=0; i<n; i++)
Finish[i]=false;
// int i=0;
// while(i<n)
// {
// if(Finish[i]==false)
// {
// int f1=1;
// for(int j=0; j<m; j++)
// {
// if(need[i][j]>Work[j])
// {
// f1=0;
// }
// }
// if(f1==1)
// {
// for(int j=0; j<m; j++)
// {
// work[i][j]=Work[j];
// Work[j]=Work[j]+allocation[i][j];
// WaddA[i][j]=Work[j];
// }
// Finish[i]=true;
// p[w++]=i;
// i=-1;//从零开始扫描
// }
// }
// i++;
// }
int count=0;
while(1)
{
for(int i=0; i<n; i++)
{
if(Finish[i]==false)
{
int f1=1;
for(int j=0; j<m; j++)
{
if(need[i][j]>Work[j])
{
f1=0;
}
}
if(f1==1)
{
for(int j=0; j<m; j++)
{
work[i][j]=Work[j];
Work[j]=Work[j]+allocation[i][j];
WaddA[i][j]=Work[j];
}
Finish[i]=true;
p[w++]=i;
count=0;
}
}
}
count++;
if(count>=n)
break;
}
int flag=1;
for(int i=0; i<n; i++)
{
if(Finish[i]==false)
{
flag=0;
}
}
// for(int i=0; i<n; i++)
// {
// cout<<p[i]<<endl;
// }
if(flag==1)
{
return true;
}
else
{
return false;
}
}
void Banker()
{
cout<<"输入请求资源的进程号:\n";
int pid;
cin>>pid;
cout<<"输入请求资源的数量(3类资源,空格隔开):";
for(int j=0; j<m; j++)
{
cin>>Request[pid][j];
}
for(int j=0; j<m; j++)
{
if(Request[pid][j]>need[pid][j])
{
cout<<"请求资源数量大于Need数量,分配失败!"<<endl;
return ;
}
else
{
if(Request[pid][j]>available[j])
{
cout<<"请求资源数量大于Aailable数量,分配失败!"<<endl;
return;
}
}
}
for(int j=0; j<m; j++)
{
available[j]=available[j]-Request[pid][j];
allocation[pid][j]=allocation[pid][j]+Request[pid][j];
need[pid][j]=need[pid][j]-Request[pid][j];
}
bool safe = safety();
if(safe==true)
{
//打印
print_sequence();
cout<<"请求成功!!"<<endl;
}
else
{
cout<<"系统将进入不安全状态,请求失败!!"<<endl;
for(int j=0; j<m; j++)
{
available[j]=available[j]+Request[pid][j];
allocation[pid][j]=allocation[pid][j]-Request[pid][j];
need[pid][j]=need[pid][j]+Request[pid][j];
}
}
}
int main()
{
int flag=1;
while(1)
{
int sel;
menu();
cin>>sel;
switch(sel)
{
case 1:
init();
break;
case 2:
print();
break;
case 3:
Banker();
break;
case 4:
flag=0;
break;
}
if(flag==0)
break;
}
return 0;
}
运行效果:
版权声明:本文标题:操作系统:实验二银行家算法 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dongtai/1724979874a1000773.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论