算法简介

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

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

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

代码实现

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

#include<stdio.h>#include<string.h>#define M 10#define N 50int Available[M];struct job{    char name[5];    int Max[M];int Allocation[M];int Need[M];int flag;       //每次是否达到运行要求的标志int finish;     //是否运行完成};

2. 安全性算法是银行家算法的核心，该算法判断系统的安全状态，如果所有进程都能够按照某个顺序运行完成，则输出该安全序列，否则，判断系统为不安全状态。逐个循环判断进程是否满足运行条件，若满足，则将该进程的资源量全部释放，将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;       //交换flagjobs[j].flag=jobs[i].flag;jobs[i].flag=t_flag;t_flag=jobs[j].finish;       //交换finishjobs[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;}

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

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");}

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

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;}

5. 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("分配成功");}elseprintf("分配失败");printf("\n");printf("\n");printf("\n");printf("按Enter退出\n");getchar();getchar();}

样例展示