1. 算法原理
银行家算法是一种死锁避免算法，核心思想是：
(1)当进程申请资源时，系统预判分配后是否仍处于安全状态。
(2)若安全则分配资源，否则让进程等待。
(3)安全状态指存在一个安全序列，使得所有进程都能顺利完成。
2. 算法数据结构
max[M][M]为进程总共需求的各类资源量，allocation[M][M]为已经分配给进程的各类资源量，available[M]为系统各类资源的空闲量，need[M][M]为进程还需要请求的各类资源量，process为进程数量，resource为资源种类数，isSafe为系统是否安全的标志位。
3. 算法和算法流程图
(1) 算法步骤：当进程Pi发出资源请求Request_i时，执行以下步骤：
a. 如果 Request_i <= Need_i，则转步骤 b；否则认为出错（因为它请求的资源数超过其声明的最大需求）。
b. 如果 Request_i <= Available，则转步骤 c；否则，Pi 必须等待（因为当前资源不足）。
c. 系统试探性地把资源分配给 Pi，并修改下列数据：
Available = Available - Request_i;
Allocation_i = Allocation_i + Request_i;
Need_i = Need_i - Request_i;
d. 调用安全性算法，检查此次分配后系统是否处于安全状态。若安全，则正式分配；否则，系统撤销此次分配，让Pi等待。
(2) 安全性检查算法：
a. 从P1到Pn为一轮，每轮尝试给进程分配其还需要的资源数，若available不足，则拒绝，否则分配给其资源，并拿回运行之后获得的max资源。
b. 每一轮若有进程被分配了资源，则该轮结束之后无需检查是否仍安全。分配之后记录进程号，剩余运行进程数减一，若为0则已经找出安全序列。
C. 若某轮没有进程被分配资源，则该轮结束进行检查，若被拒绝的进程数量等于当前运行的进程数量，即所有进程均被拒绝，此时认为系统不安全。
4. 源程序
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define M 100 //进程及资源最大数量
#define TEST //注释此行以进入终端读入模式#ifndef TEST
#define PRD 1
int process, resource, isSafe;
int max[M][M], allocation[M][M], need[M][M], available[M];
#endif#ifdef TEST
#define PRD 0
int max[M][M] = { {7,5,3}, {3,2,2}, {9,0,2}, {2,2,2}, {4,3,3}, };
int allocation[M][M] = { {0,1,0}, {2,0,0}, {3,0,2}, {2,1,1}, {0,0,2} };
int available[M] = {10, 5, 7};
int need[M][M];
int process = 5;
int resource = 3;
int isSafe;
#endifint globalRun[M]; //进程运行状态
int remainProNum; //当前运行进程数量
int askPro; //读入的分配进程号
int askReq[M]; //读入的分配资源数组void in(); //读入初始数据
void needInit(); //初始化Need矩阵
void availableInit(); //初始化Available数组
void runTimeInit(); //运行时的临时变量初始化void show(); //展示当前资源分配状态
void check(); //检查是否处于安全状态
void ask(); //读入尝试分配的数据
void randomAsk(); //随机产生分配数据
void tryAllocate(); //尝试分配
void reset(); //分配操作回退int main() {puts("--------------------------------------------------------");puts("*********************银 行 家 算 法*********************");puts("--------------------------------------------------------");if(PRD) in(); //PRD模式即非TEST模式才会读入数据needInit();availableInit();runTimeInit();show();check();if(isSafe) {int times = 0;while(1) {times++;printf("--------------------------------------------------------正在进行第%d次操作\n", times);int key = 0;while(1) {printf("1自动生成 2手动读入: ");scanf("%d", &key);if(key == 1) {randomAsk();break;} else if(key ==2 ) {ask();break;} else puts("ERROR: 读入类型: 非法输入!");}tryAllocate();puts("尝试分配之后的有关资源数据");show();puts("检查分配后系统是否安全中...");check();if(!isSafe) {puts("即将回退数据...");reset();puts("回退后数据情况");show();}}}
}void in() {puts("请输入进程数和资源数:");scanf("%d%d", &process, &resource);puts("请输入Max矩阵:");for(int i=0; i<process; i++)for(int j=0; j<resource; j++)scanf("%d", &max[i][j]);puts("请输入Allocation矩阵:");for(int i=0; i<process; i++)for(int j=0; j<resource; j++)scanf("%d", &allocation[i][j]);puts("请输入各类资源的总数:");for(int i=0; i<resource; i++)scanf("%d", &available[i]);
}void needInit() {for(int i=0; i<process; i++)for(int j=0; j<resource; j++)need[i][j]=max[i][j]-allocation[i][j];
}void availableInit() {for(int i=0; i<process; i++)for(int j=0; j<resource; j++)available[j]-=allocation[i][j];
}void runTimeInit() {for(int i=0; i<process; i++)globalRun[i] = 1;remainProNum = process;
}void show() {printf("--------------------此刻资源分配情况--------------------\n");printf("| 进程名 | Max | Allocation | Need | Available |\n");for(int i=0; i<process; i++) {printf("| P%2d |", i);for(int j=0; j<resource; j++)printf(" %2d", max[i][j]);printf(" ");for(int j=0; j<resource; j++)printf(" %2d", allocation[i][j]);printf(" ");for(int j=0; j<resource; j++)printf(" %2d", need[i][j]);printf(" ");if(i==0) {for(int j=0; j<resource; j++)printf(" %2d", available[j]);}puts("");}puts("--------------------------------------------------------");
}void check() {int pointer = 0, isAcc = 0, rejNum = 0, isNeed = 0;int run[M], work[M], safe[M];for(int i=0; i<process; i++)run[i]=globalRun[i];for(int i=0; i<resource; i++)work[i]=available[i];while(1) {rejNum = 0; //该轮被拒绝的进程数量isNeed = 1; //是否需要检查已可能不安全for(int i=0; i<process; i++) {if(run[i]) {isAcc = 1; //默认接受for(int j=0; j<resource; j++) {if(need[i][j] > work[j]) {isAcc = 0; //任意一种不满足则拒绝break;}}if(isAcc) {isNeed = 0; //有进程被接受，此轮无需检查run[i] = 0; //进程结束运行safe[pointer] = i;pointer++;if(pointer == remainProNum) {printf("安全序列为: ");for(int k=0; k<pointer; k++)printf("%d ", safe[k]);puts("");isSafe = 1;return;}for(int j=0; j<resource; j++)work[j] += allocation[i][j];} else rejNum++; //被拒绝进程数量自增}}if(isNeed) {for(int i=0; i<process; i++)rejNum -= run[i];if(!rejNum) { //所有运行的进程都被拒绝puts("系统处于不安全状态!");isSafe = 0;return;}}}
}void ask() {while(1) {printf("请输入请求资源的进程(0~%d): ", process-1);scanf("%d", &askPro);if(askPro < 0 || askPro >= process) {puts("ERROR: 进程号: 非法输入!");continue;} else break;}int errType = 0;while(1) {errType = 0;printf("请输入该进程请求的各资源数(共%d种资源): ", resource);for(int i=0; i<resource; i++)scanf("%d", &askReq[i]);for(int i=0; i<resource; i++) {if(askReq[i] > need[askPro][i]) {errType = 1;break;}if(askReq[i] > available[i]) {errType = 2;break;}}if(errType == 1) {puts("ERROR: 请求资源: 超过该进程需求的资源!");continue;}if(errType == 2) {puts("ERROR: 请求资源: 超过当前空闲的资源!");continue;}if(errType == 0) {break;}}
}void randomAsk() {srand(time(NULL));int reqMax[M];while(1) {askPro = rand()%process;if(!globalRun[askPro])continue;elsebreak;}for(int i=0; i<resource; i++) {reqMax[i] = need[askPro][i] > available[i] ? available[i] : need[askPro][i];if(!reqMax[i])askReq[i] = 0;elseaskReq[i] = rand()%reqMax[i] + 1;}printf("进程P%d请求资源: ", askPro);for(int i=0; i<resource; i++)printf("%d ", askReq[i]);puts("");
}void tryAllocate() {int sumNeed = 0; //分配之后进程还需资源数量for(int i=0; i<resource; i++) {allocation[askPro][i] += askReq[i];need[askPro][i] -= askReq[i];available[i] -= askReq[i];sumNeed += need[askPro][i];}if(!sumNeed) { //所需资源为0即进程结束globalRun[askPro] = 0;remainProNum--;for(int i=0; i<resource; i++)available[i] += max[askPro][i];}
}void reset() {for(int i=0; i<resource; i++) {allocation[askPro][i] -= askReq[i];need[askPro][i] += askReq[i];available[i] += askReq[i];}if(!globalRun[askPro]) { //重置前进程为结束状态globalRun[askPro] = 1; //恢复运行remainProNum++;for(int i=0; i<resource; i++)available[i] -= max[askPro][i];}
}