本文主要是介绍算法篇——银行家算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.引言
银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。
在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。
要解释银行家算法，必须先解释操作系统安全状态和不安全状态。
安全序列是指一个进程序列{P1，…，Pn}是安全的，即对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。
安全状态:
如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。
不安全状态:
不存在一个安全序列。不安全状态不一定导致死锁。
2.数据结构
- 可利用资源向量Available
是个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果Available[j]=K，则表示系统中现有Rj类资源K个。 - 最大需求矩阵Max
这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。 - 分配矩阵Allocation
这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的 数目为K。 - 需求矩阵Need。
这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。
Need[i,j]=Max[i,j]-Allocation[i,j]
3.算法原理
我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。
为保证资金的安全，银行家规定：
(1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客；
(2) 顾客可以分期贷款，但贷款的总数不能超过最大需求量；
(3) 当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款；
(4) 当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金.
操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。
4.源码实现
· bank.h
#include "string.h"
#include "iostream"
using namespace std;#define FALSE 0
#define TRUE 1
#define W 10
#define R 20//声明全局变量
int M ; //总进程数
int N ; //资源种类
int ALL_RESOURCE[3] ;//各种资源的数目总和
int MAX[4][3] ; //M个进程对N类资源最大资源需求量
int AVAILABLE[R]; //系统可用资源数
int ALLOCATION[4][3]; //M个进程已经得到N类资源的资源量
int NEED[W][R]; //M个进程还需要N类资源的资源量
int Request[R]; //请求资源个数//手动进行变量输入
void create()
{printf("请输入进程数： \n");scanf("%d",&M);printf("请输入资源种类数： \n");scanf("%d",&N);printf("请输入ALL_RESOURCE： \n");int i=0;for(i=0;i<N;++i){scanf("%d",&ALL_RESOURCE[i]);
}for(i=0;i<M;++i)
{int j=0;for(j=0;j<N;++j)scanf("%d",&MAX[i][j]);
}for(i=0;i<M;++i)
{int j=0;for(j=0;j<N;++j)scanf("%d",&ALLOCATION[i][j]);
}
}//通过输入计算出Availiable值；数据全部初始化完成
void init()
{int i = 0, j = 0, p;//初始化资源数量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;}}for (i = 0; i < M; i++)for (j = 0; j < N; j++)NEED[i][j] = MAX[i][j] - ALLOCATION[i][j];
}void showdata() //函数showdata,输出资源分配情况
{int i, j;cout << "各种资源的总数量(all):";cout << " [";for (j = 0; j<N; j++)cout << " " << ALL_RESOURCE[j];cout << " ]";cout << endl << endl;cout << "系统目前各种资源可用的数为(available):";cout << " [";for (j = 0; j<N; j++)cout << " " << AVAILABLE[j];cout << " ]";cout << endl << endl;cout << " 各进程已经得到的资源量(allocation): " << endl << endl;cout << " 资源0" << " 资源1" << " 资源2" << endl;for (i = 0; i<M; i++){cout << "进程p" << i << ": ";for (j = 0; j<N; j++)cout << ALLOCATION[i][j] << " ";cout << endl;}cout << endl;cout << " 各进程还需要的资源量(need):" << endl << endl;cout << " 资源0" << " 资源1" << " 资源2" << endl;for (i = 0; i<M; i++)for (i = 0; i<M; i++){cout << "进程p" << i << ": ";for (j = 0; j<N; j++)cout << NEED[i][j] << " ";;cout << endl;}cout << endl;
}
void changdata(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];}
}void rstordata(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];}
}int chkerr(int s) //函数chkerr,检查是否安全
{int WORK, FINISH[W];int i, j, k = 0;for (i = 0; i<M; i++)FINISH[i] = FALSE;for (j = 0; j<N; j++){WORK = AVAILABLE[j];i = s;//安全性检查核心代码do{if (FINISH[i] == FALSE&&NEED[i][j] <= WORK){WORK = WORK + ALLOCATION[i][j];FINISH[i] = TRUE;i = 0;}else{i++;}} while (i<M);for (i = 0; i<M; i++)if (FINISH[i] == FALSE){cout << endl;cout << " 系统不安全!!! 本次资源申请不成功!!!" << endl;cout << endl;return 1;}}cout << endl;cout << " 经安全性检查，系统安全，本次分配成功。" << endl;cout << endl;return 0;
}
void bank() //银行家算法主体
{int i = 0, j = 0;char flag = 'Y';while (flag == 'Y' || flag == 'y'){i = -1;while (i<0 || i >= M){cout << " 请输入需申请资源的进程号（从P0到P" << M - 1 << "，否则重输入!）:";cout << "P"; cin >> i;if (i<0 || i >= M)cout << " 输入的进程号不存在，重新输入!" << endl;}cout << " 请输入进程P" << i << "申请的资源数:" << endl;for (j = 0; j<N; j++){cout << " 资源" << j << ": ";cin >> Request[j];if (Request[j]>NEED[i][j]) //若请求的资源数大于进程还需要i类资源的资源量j{cout << " 进程P" << i << "申请的资源数大于进程P" << i << "还需要" << j << "类资源的资源量!";cout << "申请不合理，出错!请重新选择!" << endl << endl;flag = 'N';break;}else{if (Request[j]>AVAILABLE[j]) //若请求的资源数大于可用资源数{cout << " 进程P" << i << "申请的资源数大于系统可用" << j << "类资源的资源量!";cout << "申请不合理，出错!请重新选择!" << endl << endl;flag = 'N';break;}}}if (flag == 'Y' || flag == 'y'){changdata(i); //调用changdata(i)函数，改变资源数if (chkerr(i)) //若系统安全{rstordata(i); //调用rstordata(i)函数，恢复资源数showdata(); //输出资源分配情况}else //若系统不安全showdata(); //输出资源分配情况}else //若flag=N||flag=nshowdata();cout << endl;cout << " 是否继续银行家算法演示,按'Y'或'y'键继续,按'N'或'n'键退出演示: ";cin >> flag;}
}
· main.c
#include"bank.h"int main()
{create();init();showdata();bank();system("pause");return 0;
}
这篇关于算法篇——银行家算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
