银行家算法-C语言实现

大家好，又见面了，我是你们的朋友全栈君。

算法简介

银行家算法（Banker’sAlgorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。
—百度百科

当一个进程申请使用资源的时候，银行家算法通过先试探分配给该进程资源，然后通过安全性算法判断分配后的系统是否处于安全状态，若不安全则试探分配作废，让该进程继续等待。

安全性算法是判断分配后的系统是否会进入不安全状态，若不存在安全序列，则判定系统已经进入不安全状态。如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。

代码实现

定义进程结构体，flag表示是否满足运行需求，finish表示是否已经运行完成，name表示进程名称，Max表示进程需要的最大需求资源量，Allocation表示该进程已经得到分配的资源量，Need表示该进程运行完成还需分配的资源量。定义资源向量Available，表示系统当前可进行分配的资源量。

#include<stdio.h>
#include<string.h>

#define M 10
#define N 50

int Available[M];

struct job{ 
   
	char name[5];
    int Max[M];
	int Allocation[M];
	int Need[M];
	int flag;       //每次是否达到运行要求的标志
	int finish;     //是否运行完成
};

安全性算法是银行家算法的核心，该算法判断系统的安全状态，如果所有进程都能够按照某个顺序运行完成，则输出该安全序列，否则，判断系统为不安全状态。逐个循环判断进程是否满足运行条件，若满足，则将该进程的资源量全部释放，将finish值设为1，表示运行完成，并将其放在运行完成的进程队列尾（未运行的进程队列前），然后继续循环后续的进程，寻找下一个满足运行条件的进程… …。判断所有进程的finish是否都为1，即是否都完成运行，如果都已经完成，则排序后的进程队列就是其中的一个安全序列，否则说明不存在安全序列。

int safe(struct job jobs[N],int n,int m,int Available[M])
{ 

char t_name[5];
int t_Max;
int t_Allocation;
int t_Need;
int t_flag;
int i,j,k;
for(i=0;i<n;i++)
{ 

for(j=i;j<n;j++)      //遍历后面的所有作业，寻找满足的作业
{ 

for(k=0;k<m;k++)  //判断作业是否能够执行
{ 

if(jobs[j].Need[k]>Available[k])
jobs[j].flag=0;
}
if(jobs[j].flag==1)        //如果满足要求，执行之后释放所有资源
{ 

for(k=0;k<m;k++)
{ 

jobs[j].Need[k]=0;
jobs[j].Allocation[k]=0;
Available[k]+=jobs[j].Max[k];
jobs[j].finish=1;
}
//将第j个作业和第i个作业互换位置
strcpy(t_name,jobs[j].name);		//交换作业名
strcpy(jobs[j].name,jobs[i].name);
strcpy(jobs[i].name,t_name);
t_flag=jobs[j].flag;       //交换flag
jobs[j].flag=jobs[i].flag;
jobs[i].flag=t_flag;
t_flag=jobs[j].finish;       //交换finish
jobs[j].finish=jobs[i].finish;
jobs[i].finish=t_flag;
for(k=0;k<m;k++)					//交换其他值
{ 

t_Max=jobs[j].Max[k];       //交换最大需求
jobs[j].Max[k]=jobs[i].Max[k];
jobs[i].Max[k]=t_Max;
t_Need=jobs[j].Need[k];       //交换还需要的资源量
jobs[j].Need[k]=jobs[i].Need[k];
jobs[i].Need[k]=t_Need;
t_Allocation=jobs[j].Allocation[k];       //交换已分配的资源
jobs[j].Allocation[k]=jobs[i].Allocation[k];
jobs[i].Allocation[k]=t_Allocation;
}
break;
}
}
for(j=i+1;j<n;j++)      //遍历后面的所有作业，将flag重新初始化为1
{ 

jobs[j].flag=1;
}
}
for(i=0;i<n;i++)
{ 

if(jobs[i].finish==0)
{ 

printf("不存在安全序列");
return 0;
}
}
printf("存在安全序列为：");
for(i=0;i<n;i++)
{ 

printf("%s ",jobs[i].name);
}
printf("\n");
return 1;
}

输出函数的实现，输出每个进程的资源分配情况及系统剩余可分配资源情况。

void print(struct job jobs[N],int n,int m)
{ 

int i,k;
printf("进程名称\tMax\t\tAllocation\tNeed\n");
for(i=0;i<n;i++)
{ 

printf("%s\t\t",jobs[i].name);
for(k=0;k<m;k++)
{ 

printf("%d ",jobs[i].Max[k]);
}
printf(" \t");
for(k=0;k<m;k++)
{ 

printf("%d ",jobs[i].Allocation[k]);
}
printf(" \t");
for(k=0;k<m;k++)
{ 

printf("%d ",jobs[i].Need[k]);
}
printf("\n");
}
printf("\n");
printf("当前可分配资源为：");
for(k=0;k<m;k++)
{ 

printf("%d ",Available[k]);
}
printf("\n");
printf("\n");
}

合法性检测函数，该函数判断资源量是否存在负数，如果存在，则说明输入错误或银行家算法试探分配错误。

int judge(struct job jobs[N],int n,int m)
{ 

int i,k;
for(i=0;i<n;i++)
{ 

for(k=0;k<m;k++)
{ 

if(jobs[i].Max[k]<0||jobs[i].Allocation[k]<0||jobs[i].Need[k]<0)
return 0;
}
}
for(k=0;k<m;k++)
{ 

if(Available[k]<0)
return 0;
}
return 1;
}

main函数实现数据的输入，并调用输出函数输出分配前的资源情况，然后输入进程请求的资源量，并试探着将资源分配给请求资源的进程，分配后再调用输出函数输出分配后的资源情况，最后调用安全性算法检测资源分配后系统是否仍然存在安全序列。

int main()
{ 

struct job jobs[N];
int i,k,m,n;
int I,t;
int A[M];
printf("请输入资源的种数：");
scanf("%d",&m);
printf("请输入进程的个数：");
scanf("%d",&n);
printf("\n");
for(i=0;i<n;i++)
{ 

printf("请输入第%d个进程的名称：",i+1);
scanf("%s",jobs[i].name);
printf("请输入第%d个进程所需最大的资源（各种资源数用空格隔开）：",i+1);
for(k=0;k<m;k++)
{ 

scanf("%d",&jobs[i].Max[k]);
}
printf("请输入第%d个进程已经分配的资源（各种资源数用空格隔开）：",i+1);
for(k=0;k<m;k++)
{ 

scanf("%d",&jobs[i].Allocation[k]);
jobs[i].Need[k]=jobs[i].Max[k]-jobs[i].Allocation[k];
}
jobs[i].flag=1;
jobs[i].finish=0;
printf("\n");
}
printf("请输入当前系统剩余可进行分配的资源（各种资源数用空格隔开）：",i+1);
for(k=0;k<m;k++)
{ 

scanf("%d",&Available[k]);
}
printf("\n");
if(judge(jobs,n,m)==0)
{ 

printf("输入有误！\n");
return 0;
}
printf("当前资源分配情况如下：\n");
print(jobs,n,m);
printf("请输入要请求资源的进程是第几个：");
scanf("%d",&I);
I--;
printf("请输入要请求的资源（各种资源数用空格隔开）：");
for(k=0;k<m;k++)
{ 

scanf("%d",&A[k]);
}
for(k=0;k<m;k++)
{ 

jobs[I].Allocation[k]=jobs[I].Allocation[k]+A[k];
jobs[I].Need[k]=jobs[I].Need[k]-A[k];
Available[k]=Available[k]-A[k];
}
printf("\n");
if(judge(jobs,n,m)==0)
{ 

printf("输入有误！\n");
return 0;
}
printf("分配后资源情况如下：\n");
print(jobs,n,m);
printf("分配后系统");
t=safe(jobs,n,m,Available);
printf("\n");
if(t==1)
{ 

printf("分配成功");
}
else
printf("分配失败");
printf("\n");
printf("\n");
printf("\n");
printf("按Enter退出\n");
getchar();
getchar();
}