一、银行家算法
银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。
在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。
二、方案分析
模拟实现银行家算法对系统资源进行分配，以防止死锁的出现。本课题肯定不可能实现对实际操作系统的资源管理，而是通过对模拟资源数据的处理，检测银行家算法在防止死锁出现的作用。先对用户提出的请求进行合法性检查，即检查请求的是不大于需要的，是否不大于可利用的。若请求合法，则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态，拒绝申请。
三、开发环境
- Windows操作系统
- VS 2017
- C语言
四、设计思想及实验步骤
4.1 设计思想
先对用户提出的请求进行合法性检查，即检查请求的是不大于需要的，是否不大于可利用的。若请求合法，则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态，拒绝申请。
4.2 银行家算法中的数据结构
可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态改变。如果Available[j]=K，则表示系统中现有Rj类资源K个。
最大需求矩阵Max。这是一个 的矩阵，它定义了系统中 个进程中的每一个进程对 类资源的最大需求。如果Max[I,j]=K，则进程i需要Rj类资源的最大数目为K。
分配矩阵Allocation。这也是一个 的矩阵，它定义了系统中每一类资源当前已分配给每一个进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已经分得Rj类资源的数目为K。
需求矩阵Need。这也是一个 的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成任务。
即：
int M ; // 总进程数 int N ; // 资源种类 int ALL_RESOURCE[W]; // 各种资源的数目总和 int Max[W][R]; // 最大需求矩阵，M个进程对N类资源最大资源需求 int Available[R]; // 可利用资源向量， int Allocation[W][R];// 分配矩阵，各个进程M已经得到N类资源的资源数 int Need[W][R]; // M个进程还需要N类资源的资源量 int Request[R]; // 进程的请求资源个数
以上三个矩阵间存在下述关系：
Need[i,j] = Max[i,j] - allocation[i, j]
4.3 银行家算法bank()
设Request i是进程Pi的请求向量，如果Requesti[j]=K,表示进程Pi需要K个Rj类型的资源。发出请求后，系统按下述步骤进行检查：
- （1）检查申请量是否不大于需求量。如果
Request i[j]<=Need[i,j],便转向步骤（2）；否则认为出错，因为他所需要的资源数已经超过它所宣布的最大值。 - （2）检查申请量是否小于系统中的可利用资源数量。如果
Requesti[j]<=Available[i,j]，便转向步骤（3）；否则认为尚无足够资源，Pi必须等待。 - （3）若以上两个条件都满足，则系统试探着将资源分配给申请的进程，并修改下面数据结构中的数值：
Available[j]=Available[j]-Request[j]; Allocation[k][j]=Allocation[k][j]+Request[j]; Need[k][j]=Need[k][j]-Request[j];
- （4）试分配后，系统执行安全性算法，调用safe()函数检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程，以完成本次分配，并将安全序列打印出来；否则本次试探分配作废，恢复原来的资源分配状态，让该进程等待。
4.4 安全性算法safe()
（1）设置两个向量
- 工作向量：
- Work，它表示系统可提供给进程继续运行所需要的各类资源数目，它含有m个元素，在执行安全性算法开始时，Work: =Available
- Finish，它表示系统是否有足够资源分配给进程，使之运行完成。开始时先做Finish[i]:=false；当有足够的资源分配给进程时，再令Finish[i]:=true
（2）从进程集合中找到一个满足下述条件的进程
- Finish[i]:=false；
- Need[i,j]<=Work[j]；若找到，执行步骤（3），否则，执行步骤（4）
（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行
Work[j] = Work[j] + Allocation[i,j]; Finish[i] = true; go to step 2;
（4）如果所有的进程Finish= true都满足，则表示系统处于安全状态；否则系统处于不安全状态
五、程序的基本结构框图和流程图
5.1 程序结构功能图
5.2 流程图
六、源代码
#include<stdio.h> // 预处理 #define FALSE 0 #define TRUE 1 #define W 10 #define R 10 int safe_queue[10]; static int cnt = 0; int M; // 进程数 int N; // 资源种类数 int all_resource[W]; // 各种资源数目 int max[W][R]; // 最大需求矩阵，M个进程对N类资源最大资源需求 int available[R]; // 可利用资源数 int allocation[W][R]; // 已分配矩阵，各个进程M得到N类资源的资源数 int need[W][R]; // M个进程还需要N类资源的数目 int request[R]; // 进程请求的资源个数 void display(); // 项目信息 void show(); // 显示当前各进程的分配和需求信息 void fenpei(int k); // 分配资源 void huishou(int k); // 上一个进程结束释放所得资源后，系统重新获得的可利用资源huishou bool safe(); // 安全性算法 void bank(); // 银行家算法 int main() { int i = 0, j = 0, p; display(); printf("------------------------------------------------\n\n"); // 信息输入 printf("请输入进程数:"); scanf("%d", &M); printf("请输入资源种类:"); scanf("%d", &N); printf("请输入%d个各类资源总数:", N); for (i = 0; i < N; i++) { scanf("%d", &all_resource[i]); } printf("请输入%d个各进程所需要的各类资源的最大数量(M*N矩阵输入):\n", M*N); for (i = 0; i < M; i++) { for (j = 0; j < N; j++) { do { scanf("%d", &max[i][j]); if (max[i][j] > all_resource[j]) printf("占有资源超过了声明的该资源总数,请重新输入\n"); } while (max[i][j] > all_resource[j]); } } printf("请输入%d个各进程已经分配的各类资源的数量:\n", M*N); //各进程已经分配的各类资源的数量 for (i = 0; i < M; i++) { for (j = 0; j < N; j++) { do { scanf("%d", &allocation[i][j]); if (allocation[i][j] > max[i][j]) printf("已分配的资源超过了声明的最大资源,请重新输入\n"); } while (allocation[i][j] > max[i][j]); } } // 需要资源的数目=最大-已分配 for (i = 0; i < M; i++) for (j = 0; j < N; j++) need[i][j] = max[i][j] - allocation[i][j]; // 可利用资源数=总的-所有进程用的 for (j = 0; j < N; j++) { p = all_resource[j]; for (i = 0; i < M; i++) { p = p - allocation[i][j]; // 减去已经被占据的资源 available[j] = p; if (available[j] < 0) available[j] = 0; } } show(); // 显示当前各进程的分配和需求信息 bank(); // 调用银行家算法进行计算 return 0; } // 打印项目信息 void display() { printf("\n\n\n ------------------------------------------\n"); printf(" | | \n"); printf(" | 题目：银行家算法实现 | \n"); printf(" | | \n"); printf(" -------------------------------------------\n"); } // 显示当前各进程的分配和需求信息 void show() { int i, j; printf("\n-----------------------------------------------------------------\n"); printf("各种资源的总数量:\n"); //各种资源的总数量 for (j = 0; j < N; j++) { printf(" %d", all_resource[j]); } printf("\n-----------------------------------------------------------------\n"); printf("目前各种资源可利用的数量为:\n");//各种资源的总数量减去已分配后剩余的资源量 for (j = 0; j < N; j++) { printf(" %d", available[j]); } printf("\n-----------------------------------------------------------------\n"); printf("各进程还需要的资源数量:\n"); //各进程还需要的资源数量 for (i = 0; i < N; i++) { printf(" 资源%d", i); } printf("\n"); for (i = 0; i < M; i++) { printf("进程%d ", i); for (j = 0; j < N; j++) printf("%d ", need[i][j]); printf("\n"); } printf("\n"); printf("-----------------------------------------------------------------\n"); printf("各进程已经得到的资源量: \n");//打印各进程已经得到的资源量 for (i = 0; i < N; i++) { printf(" 资源%d", i); } printf("\n"); for (i = 0; i < M; i++) { printf("进程%d ", i); for (j = 0; j < N; j++) { printf("%d ", allocation[i][j]); } printf("\n"); } printf("\n"); } // 分配资源 void fenpei(int k) { int j; // 系统试探着把资源分配给进程Pi,并修改下面的数据结构fenpei for (j = 0; j < N; j++) { available[j] = available[j] - request[j]; allocation[k][j] = allocation[k][j] + request[j]; need[k][j] = need[k][j] - request[j]; } } // 上一个进程结束释放所得资源后，系统重新获得的可利用资源 void huishou(int k) { int j; for (j = 0; j < N; j++) { available[j] = available[j] + request[j]; allocation[k][j] = allocation[k][j] - request[j]; need[k][j] = need[k][j] + request[j]; } } /* 安全性算法，设置两个向量Work和Finish. Work：表示系统可提供给进程继续运行所需的各类资源数目； Finish：表示系统是否有足够的资源分配给进程。 */ bool safe() { int Work[R], Finish[W]; // 设置两个向量Work和Finish. int i, j, m; for (j = 0; j < N; j++) Work[j] = available[j]; // 在执行安全算法之前，初始化 for (i = 0; i < M; i++) Finish[i] = FALSE; // 系统初始化，将各进程的初始完成状态设置为FALSE for (i = 0; i < M; i++) // M进程 { for (j = 0; j < N; j++) // j类资源 { for (m = 0; m < M; m++) // 对M线程都对应查M次 { // 如果m进程还未完成 且 所需小于系统可用的，那么试分配资源 if (Finish[m] == FALSE && need[m][j] <= Work[j]) { Work[j] = Work[j] + allocation[m][j]; // 该进程完成后，系统可用的变为原来的加上该进程已分配的 Finish[m] = TRUE; // 当有足够的资源分配给进程时，设置为TRUE safe_queue[cnt] = m; // 记录安全进程序列 cnt++; } } } } // 判断系统安全性 for (i = 0; i < M; i++) { if (Finish[i] == FALSE) { printf("\n经安全性算法检查，此时系统处于不安全状态! 本次分配不成功!!!\n\n"); return 1; } else { printf("\n经安全性算法检查，此时系统安全，分配成功。\n"); printf("此时系统的安全序列是：\n"); for (i = 1; i < cnt; i++) { printf("%d ", safe_queue[i]); // 打印安全序列 } printf("\n"); return 0; } } return 1; } // 银行家算法进行计算 void bank() { int i = 0, j = 0; char flag = 'Y'; while (flag == 'Y' || flag == 'y') { i = -1; while (i < 0 || i >= M) { printf("-----------------------------------------------------------------\n"); printf("请输入申请资源的进程号:\n"); //进程Pi发出请求 scanf("%d", &i); if (i < 0 || i >= M) printf("对不起，输入的进程号不存在，请重新输入!\n"); } printf(" 请输入进程%d申请各类资源的数量:\n", i); for (j = 0; j < N; j++) { printf("资源%d: ", j); scanf("%d", &request[j]); // 若请求的资源数大于进程还需要i类资源的资源量j if (request[j] > need[i][j]) { printf("进程%d申请的资源数大于进程%d还需要%d类资源的数量!\n", i, i, j); printf("若继续执行系统将处于不安全状态!\n"); flag = 'N'; break; } else { // 若请求的资源数大于可用资源数 if (request[j] > available[j]) { printf(" 进程%d申请的资源数大于系统可用%d类资源的数量!\n", i, j); printf(" 若继续执行系统将处于不安全状态!\n"); flag = 'N'; break; } } } if (flag == 'Y' || flag == 'y') { fenpei(i); // 调用fenpei(i)函数，改变资源数 safe_queue[cnt] = i; cnt++; // 若系统安全 if (safe()) { huishou(i); // 调用huishou(i)函数，恢复资源数 show(); // 输出资源分配情况 } else // 若系统不安全，输出资源分配情况 show(); } else //执行flag=N||flag=n printf("\n"); printf(" 是否继续银行家算法演示？按'Y'或'y'继续,按'N'或'n'退出演示: \n"); getchar(); flag = getchar(); } }
