銀行家演算法流程圖：
銀行家演算法自然語言描述：設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);
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/273666.html
標籤：其他
上一篇：thinkphp6+騰訊云