大家好,又见面了,我是你们的朋友全栈君。
银行家算法流程图:
银行家算法自然语言描述:设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等待。
实例:
假定系统中有五个进程{P0, P1, P2, P3, P4}和三类资源{A, B, C},各种资源的数量分别为10、5、7,在T0时刻的资源分配情况下图所示。输入M资源总数量、Max矩阵和Allocation矩阵显示初始状态表(1)判断T0时刻是否安全?存在一个安全序列<P1,P3,P0,P2,P4>
输入M资源总数量、Max矩阵和Allocation矩阵
显示初始状态表
1.判断T0时刻是否安全?
存在一个安全序列<P1,P3,P0,P2,P4>
2. P1请求资源:P1发出请求向量Request1(1,0,2),调用银行家算法检查是否能够分配?
输入
存在一个安全序列<P1,P3,P4,P2,P0>,显示新的状态表。
3.P4请求资源:P4发出请求向量Request4(3,3,0),系统按银行家算法进行检查:
输入
① Request4(3, 3, 0)≤Need4(4, 3, 1);
② Request4(3, 3, 0) >Available(2, 3, 0),让P4堵塞等待。状态表没有变化
4.P0请求资源:P0发出请求向量Requst0(0,2,0),系统按银行家算法进行检查:
输入
① Request0(0, 2, 0)≤Need0(7, 4, 3);
② Request0(0, 2, 0)≤Available(2, 3, 0);系统暂时先假定可为P0分配资源,并修改有关数据,如下图所示。
可用资源Available(2,1,0)不能满足任何进程的需求,进入不安全状态。此时系统不分配资源给P0。
输出:找不到安全序列,状态表没有变化
5.若P0发出请求向量Requst0(0,1,0),系统是否将资源分配给它?
输入
存在一个安全序列<P0,P1,P2,P3,P4>,显示新的状态表
程序代码:
#include <malloc.h>
#include <stdio.h>
#include <string.h>
#include <windows.h>
#define M 3
#define N 5
int Resource[M];
int Max[N][M];
int Allocation[N][M];
int Need[N][M];
int Available[M];
int Work[M];
int Finish[N];
int List[N]; //存放安全序列的下标序列
void initial()
//创建初始状态:先输入 Resource、Max和 Allocation,再计算出 Need、Available。
{
int i,j;
printf("Resource--输入M种资源的总数量:\n");
for(i=0;i<M;i++)
{
scanf("%d",&Resource[i]);
Available[i]=Resource[i];
}
printf("Max--输入N个进程分别对M种资源的最大需求量:\n");
for(j=0;j<N;j++)
for(i=0;i<M;i++)
scanf("%d",&Max[j][i]);
printf("Allocation--输入N个进程获得M种资源的数量:\n");
for(j=0;j<N;j++)
for(i=0;i<M;i++)
scanf("%d",&Allocation[j][i]);
/****************************************/
for(j=0;j<N;j++)
for(i=0;i<M;i++)
Need[j][i]=Max[j][i]-Allocation[j][i];
for(j=0;j<M;j++)
for(i=0;i<N;i++)
Available[j]=Available[j]-Allocation[i][j];
}
void printState()
//输出当前的状态表|Process |Max |Allocation |Need |Available |
{
int i;
printf("状态表:\n|Process |Max |Allocation |Need |Available | \n");
for(i=0;i<N;i++)
{
if(i==0)
printf("|P%-11d|%4d%4d%4d|%4d%4d%4d|%4d%4d%4d|%4d%4d%4d|\n",i,Max[i][0],Max[i][1],Max[i][2],Allocation[i][0],Allocation[i][1],Allocation[i][2],Need[i][0],Need[i][1],Need[i][2],Available[0],Available[1],Available[2]);
else
printf("|P%-11d|%4d%4d%4d|%4d%4d%4d|%4d%4d%4d| |\n",i,Max[i][0],Max[i][1],Max[i][2],Allocation[i][0],Allocation[i][1],Allocation[i][2],Need[i][0],Need[i][1],Need[i][2]);
}
}
int isfinish()
//返回同时满足两个条件{①Finish[i]=false; ②Need[i][j]≤Work[j]}的进程下标 i(修改Finish[i]=true),否则返回-1。
{
int i,j,count;
for(i=0;i<N;i++)
{
for(j=0,count=0;j<M;j++)
if(Finish[i]==0&&Need[i][j]<=Work[j])
{
count++;
}
if(count==3)
{
for(j=0;j<M;j++)
Work[j]+=Allocation[i][j];
Finish[i]=1;
return i;
}
}
return -1;
}
int issafe()
//判定当前状态是否为安全状态 (返回 true 或 false),把安全序列的下标放入 List[N]数组。
{
int i,a,count=0;
for(i=0;i<M;i++)
Work[i]=Available[i];
for(i=0;i<N;i++)
Finish[i]=0;
for(i=0;i<N;i++)
{
a=isfinish();
if(a!=-1)
{
List[i]=a;
count++;
}
}
if(count==5)
return 1;
else
return 0;
}
void printList( )
//输出安全序列表|Process |Work |Need |Allocation |Work+Alloc |Finish |
{
int i,j;
printf("\n安全序列表如下:\n|Process |Work |Need |Allocation |Work+Alloc |Finish |\n");
for(j=0;j<M;j++)
{
Work[j]=Available[j];
}
for(i=0;i<N;i++)
{
printf("|P%-11d|%4d%4d%4d|%4d%4d%4d|%4d%4d%4d|%4d%4d%4d|true\n",List[i],Work[0],Work[1],Work[2],Need[List[i]][0],Need[List[i]][1],Need[List[i]][2],Allocation[List[i]][0],Allocation[List[i]][1],Allocation[List[i]][2],Work[0]+Allocation[List[i]][0],Work[1]+Allocation[List[i]][1],Work[2]+Allocation[List[i]][2]);
for(j=0;j<M;j++)
Work[j]+=Allocation[List[i]][j];
}
}
void reqresource(int i, int Request[M])
//表示第 i个进程请求 M类资源 request[M]
{
int flag,count1,count2;
int j;
//Step1: 判断条件 Request[j]≤Need[i][j]
for(j=0,count1=0;j<M;j++)
if(Request[j]<=Need[i][j])
count1++;
//Step2: 判断条件 Request[j]≤Available[j]
for(j=0,count2=0;j<M;j++)
if(Request[j]<=Available[j])
count2++;
if(count2!=3)
printf("\n尚无足够的资源,第%d个进程堵塞。\n",i);
//Step3: 预先分配
if(count2==3&&count1==3)
{
for(j=0;j<M;j++)
{
Available[j]=Available[j]-Request[j];
Allocation[i][j]=Allocation[i][j]+Request[j];
Need[i][j]=Need[i][j]-Request[j];
}
if(issafe()==0)
{
printf("\n不存在安全序列,不是安全状态。\n");
for(j=0;j<M;j++)
{
Available[j]=Available[j]+Request[j];
Allocation[i][j]=Allocation[i][j]-Request[j];
Need[i][j]=Need[i][j]+Request[j];
}
}
else
{
printf("\n是安全序列分配成功!\n");
printList();
}
}
//Step4:检测是否为安全状态
//填补程序
}
void main()
{
int reqid=-1,j,req[M];
initial();
printState();
if(issafe()==0)
{
printf("Initial state is unsafe!\n");
}
else
{
printf("\nInitial state is safe!\n");
printList();
printf("Input the id of request process:");
scanf("%d",&reqid);
while(reqid>=0 && reqid<N) //输入进程 id是否合法
{
printf("Input request resources:");
for(j=0;j<M;j++)
{
scanf("%d",&req[j]);
}
reqresource(reqid, req);
printState();
printf("Input the id of request process:");
scanf("%d",&reqid);
}
}
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/130950.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...