本文目的

上一章节已经详细的向大家介绍过死锁（学习笔记-死锁的详细介绍）本文旨在向大家详细的介绍避免死锁的经典算法-银行家算法。

什么是银行家算法

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

算法原理

我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。

为保证资金的安全，银行家规定：

(1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客；

(2) 顾客可以分期贷款，但贷款的总数不能超过最大需求量；

(3) 当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款；

(4) 当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金.

操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。

算法思想

银行家算法：银行家算法是从当前状态出发，按照系统各类资源剩余量逐个检查各进程需要申请的资源量，找到一个各类资源申请量均小于等于系统剩余资源量的进程P1。然后分配给该P1进程所请求的资源，假定P1完成工作后归还其占有的所有资源，更新系统剩余资源状态并且移除进程列表中的P1，进而检查下一个能完成工作的客户，......。如果所有客户都能完成工作，则找到一个安全序列，银行家才是安全的。若找不到这样的安全序列，则当前状态不安全。

数据结构

可利用资源向量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]

应用示例

（1）可用资源为（3,3,2），依次与P0-P4比较，在比较到P1时，发现可用资源满足P1的需要资源，将P1加入安全序列；

（2）P1归还资源后，可用资源为（5,3,2）从上到下依次比较，在比较到P3时，发现可用资源满足P3的需要资源，将P3加入安全序列；

（3）P3归还资源后，可用资源为（7,4,3）,除去已经加入到安全序列的进程，其余进程从上到下依次比较，在比较到P0时，发现可用资源满足P0的需要资源，将P0加入安全序列；

（4）P0归还资源后，可用资源为（7,5,3）,除去已经加入到安全序列的进程，其余进程从上到下依次比较，在比较到P2时，发现可用资源满足P2的需要资源，将P2加入安全序列；

（5）P2归还资源后，可用资源为（10,5,5）,除去已经加入到安全序列的进程，其余进程从上到下依次比较，发现可用资源满足P4的需要资源，将P4加入安全序列.

到目前为止，安全序列已经整合出来：P1,P3,P0,P2,P4。实际上P1和P3可以位置互换。

算法设计

在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配 。因此，对资源的分配要给予合理的规划。

银行家算法

设Request i是进程Pi的申请向量，如果Request i[j]=K,则表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：

1) 如果Request i[j]<=Need[i,j]，便转向步骤2）；否则认为出错，因为它所需要的资源数已经超过它所宣布的最大值。

2) 如果Request i[j]<=Available[i,j]，便转向步骤3）；否则，表示尚无足够资源，Pi需等待。

3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：

Available[j]:=Available[j]-Request i[j];

Allocation[i,j]:=Allocation[i,j]+Request i[j];

Need[i,j]:=Need[i,j]-Request i[j];

4) 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

安全性算法

系统所执行的安全性算法可描述如下：

1) 设置两个向量

①　工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work：=Available。

②　Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]:=false;当有足够资源分配给进程时，再令Finish[i]:=ture.

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[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

流程图

代码实现

代码流程图如下：

#include <STRING.H>#include <stdio.h>#include <stdlib.h>#include <CONIO.H> /*用到了getch()*/#defineM5 /*进程数*/#defineN3 /*资源数*/#defineFALSE0#defineTRUE1/*M个进程对N类资源最大资源需求量*/intMAX[M][N] = { { 7, 5, 3 }, { 3, 2, 2 }, { 9, 0, 2 }, { 2, 2, 2 }, { 4, 3, 3 } };/*系统可用资源数*/intAVAILABLE[N] = { 10, 5, 7 };/*M个进程已分配到的N类数量*/intALLOCATION[M][N] = { { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 } };/*M个进程已经得到N类资源的资源量*/intNEED[M][N] = { { 7, 5, 3 }, { 3, 2, 2 }, { 9, 0, 2 }, { 2, 2, 2 }, { 4, 3, 3 } };/*M个进程还需要N类资源的资源量*/intRequest[N] = { 0, 0, 0 };voidmain(){	inti = 0, j = 0;	charflag;	voidshowdata();	voidchangdata( int );	voidrstordata( int );	intchkerr();	showdata();enter:	{		printf( "请输入需申请资源的进程号（从0到" );		printf( "%d", M - 1 );		printf( "）:" );		scanf( "%d", &i );	}	if ( i < 0 || i >= M )	{		printf( "输入的进程号不存在，重新输入!\n" );		gotoenter;	}err:	{		printf( "请输入进程" );		printf( "%d", i );		printf( "申请的资源数\n" );		printf( "类别:ABC\n" );		printf( "" );		for ( j = 0; j < N; j++ )		{			scanf( "%d", &Request[j] );			if ( Request[j] > NEED[i][j] )			{				printf( "%d", i );				printf( "号进程" );				printf( "申请的资源数>进程" );				printf( "%d", i );				printf( "还需要" );				printf( "%d", j );				printf( "类资源的资源量!申请不合理，出错!请重新选择!\n" );				gotoerr;			}else  {				if ( Request[j] > AVAILABLE[j] )				{					printf( "进程" );					printf( "%d", i );					printf( "申请的资源数大于系统可用" );					printf( "%d", j );					printf( "类资源的资源量!申请不合理，出错!请重新选择!\n" );					gotoerr;				}			}		}	}	changdata( i );	if ( chkerr() )	{		rstordata( i );		showdata();	}else		showdata();	printf( "\n" );	printf( "按'y'或'Y'键继续,否则退出\n" );	flag = getch();	if ( flag == 'y' || flag == 'Y' )	{		gotoenter;	}else  {		exit( 0 );	}}/*显示数组*/voidshowdata(){	inti, j;	printf( "系统可用资源向量:\n" );	printf( "***Available***\n" );	printf( "资源类别:ABC\n" );	printf( "资源数目:" );	for ( j = 0; j < N; j++ )	{		printf( "%d", AVAILABLE[j] );	}	printf( "\n" );	printf( "\n" );	printf( "各进程还需要的资源量:\n" );	printf( "******Need******\n" );	printf( "资源类别:ABC\n" );	for ( i = 0; i < M; i++ )	{		printf( "" );		printf( "%d", i );		printf( "号进程:" );		for ( j = 0; j < N; j++ )		{			printf( "%d", NEED[i][j] );		}		printf( "\n" );	}	printf( "\n" );	printf( "各进程已经得到的资源量:\n" );	printf( "***Allocation***\n" );	printf( "资源类别:ABC\n" );	for ( i = 0; i < M; i++ )	{		printf( "" );		printf( "%d", i );		printf( "号进程:" );/*printf(":\n");*/		for ( j = 0; j < N; j++ )		{			printf( "%d", ALLOCATION[i][j] );		}		printf( "\n" );	}	printf( "\n" );}/*系统对进程请求响应，资源向量改变*/voidchangdata( intk ){	intj;	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];	}}/*资源向量改变*/voidrstordata( intk ){	intj;	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];	}}/*安全性检查函数*/intchkerr()                                     /* 在假定分配资源的情况下检查系统的安全性 */{	intWORK[N], FINISH[M], temp[M];         /* temp[]用来记录进程安全执行的顺序 */	inti, j, m, k = 0, count;	for ( i = 0; i < M; i++ )		FINISH[i] = FALSE;	for ( j = 0; j < N; j++ )		WORK[j] = AVAILABLE[j];         /* 把可利用资源数赋给WORK[] */	for ( i = 0; i < M; i++ )	{		count = 0;		for ( j = 0; j < N; j++ )			if ( FINISH[i] == FALSE && NEED[i][j] <= WORK[j] )				count++;		if ( count == N )               /* 当进程各类资源都满足NEED<=WORK时 */		{			for ( m = 0; m < N; m++ )				WORK[m] = WORK[m] + ALLOCATION[i][m];			FINISH[i]	= TRUE;			temp[k]		= i;    /* 记录下满足条件的进程 */			k++;			i = -1;		}	}	for ( i = 0; i < M; i++ )		if ( FINISH[i] == FALSE )		{			printf( "系统不安全!!!本次资源申请不成功!!!\n" );			return1;		}	printf( "\n" );	printf( "经安全性检查，系统安全，本次分配成功。\n" );	printf( "\n" );	printf( "本次安全序列：" );	for ( i = 0; i < M; i++ ) /* 打印安全系统的进程调用顺序 */	{		printf( "进程" );		printf( "%d", temp[i] );		if ( i < M - 1 )			printf( "->" );	}	printf( "\n" );	return0;}

本文的初衷为学习笔记的分享，部分图文来源于网络，如侵，联删。