银行家算法的设计与实现

admin管理员组

文章数量:1290230

银行家算法的设计与实现

• • 一、定义
  • 二、算法的数据结构
  • 三、算法
  • • • 1、银行家算法
      • 2、安全性算法
      • 3、算法流程图
  • 四、代码实现

一、定义

银行家算法（ B a n k e r ’ s A l g o r i t h m Banker’s Algorithm Banker’sAlgorithm）是一个避免死锁（ D e a d l o c k Deadlock Deadlock）的著名算法。在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。

---

二、算法的数据结构

为了实现银行家算法，在系统中必须设置这样四个数据结构，分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配，以及所有进程还需要多少资源的情况。

① 可利用资源向量 A v a i l a b l e Available Available。这是一个含有 m m m 个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果 A v a i l a b l e [ j ] = K Available[j] = K Available[j]=K，则表示系统中现 R j R_j Rj​类资源 K K K个。
② 最大需求矩阵 M a x Max Max。这是一个 n × m n×m n×m 的矩阵，它定义了系统中 n n n 个进程中的每个进程对 m m m类资源的最大需求。如果 M a x [ i , j ] = K Max[i,j] = K Max[i,j]=K，则表示进程 i i i 需要 R j R_j Rj​ 类资源的最大数目为 K K K。
③ 分配矩阵 A l l o c a t i o n Allocation Allocation。这也是一个 n × m n×m n×m 的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果 A l l o c a t i o n [ i , j ] = K Allocation[i,j] = K Allocation[i,j]=K，则表示进程 i i i 当前己分得 R j R_j Rj​类资源的数目为 K K K。
④ 需求矩阵 N e e d Need Need。这也是一个 n × m n×m n×m 的矩阵，用以表示每一个进程尚需的各类资源数。如果 N e e d [ i , j ] = K Need[i,j] = K Need[i,j]=K，则表示进程 i i i 还需要 R j R_j Rj​类资源 K K K个方能完成其任务。

上述三个矩阵间存在下述关系：
　　　　　　　　　　　 N e e d [ i , j ] = M a x [ i , j ] − A l l o c a t i o n [ i , j ] Need[i,j] = Max[i,j] - Allocation[i, j] Need[i,j]=Max[i,j]−Allocation[i,j]
　　　　　

---

三、算法

1、银行家算法

R e q u e s t i Request_i Requesti​ 是进程 P i P_i Pi​ 的请求向量，如果 R e q u e s t i [ j ] = K Request_i[j] = K Requesti​[j]=K，表示进程 P i P_i Pi​ 需要 K K K个 R j R_j Rj​ 类型的资源。 当 P i P_i Pi​ 发出资源请求后，系统按下述步骤进行检査：
(1) 如果 R e q u e s t i [ j ] ≤ N e e d [ i , j ] Requesti[j] ≤ Need[i,j] Requesti[j]≤Need[i,j]（请求资源数小于尚需的资源数），便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
(2) 如果 R e q u e s t i [ j ] ≤ A v a i l a b l e [ j ] Requesti[j] ≤ Available[j] Requesti[j]≤Available[j]（请求资源小于现有资源），便转向步骤(3)；否则，表示尚无足够资源， P i P_i Pi​ 须等待。
(3) 系统试探着把资源分配给进程 P i P_i Pi​，并修改下面数据结构中的数值
　　　 A v a i l a b l e [ j ] = A v a i l a b l e [ j ] − R e q u e s t i [ j ] Available[j] = Available[j] - Request_i[j] Available[j]=Available[j]−Requesti​[j];
　　　 A l l o c a t i o n [ i , j ] = A l l o c a t i o n [ i , j ] + R e q u e s t i [ j ] Allocation[i,j] = Allocation[i,j] + Request_i[j] Allocation[i,j]=Allocation[i,j]+Requesti​[j];
　　　 N e e d [ i , j ] = N e e d [ i , j ] − R e q u e s t i [ j ] Need[i,j] = Need[i,j] - Request_i[j] Need[i,j]=Need[i,j]−Requesti​[j];
(4) 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程 P i P_i Pi​，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程 P i P_i Pi​ 等待。

---

2、安全性算法

系统所执行的安全性算法可描述如下：
(1) 设置两个向量：① 工作向量 W o r k Work Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有 m m m个元素，在执行安全算法开始时， W o r k = A v a i l a b l e Work = Available Work=Available；② F i n i s h Finish Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做 F i n i s h [ i ] = f a l s e Finish[i] = false Finish[i]=false；当有足够资源分配给进程时，再令 F i n i s h [ i ] = t r u e Finish[i] = true Finish[i]=true。
(2) 从进程集合中找到一个能满足下述条件的进程
　　　① F i n i s h [ i ] = f a l s e Finish[i] = false Finish[i]=false;
　　　② N e e d [ i , j ] ≤ W o r k [ j ] Need[i,j] ≤ Work[j] Need[i,j]≤Work[j];
若找到，执行步骤(3)，否则，执行步骤(4)。
(3 )当进程 P i P_i Pi​ 获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行:
　　　 W o r k [ j ] = W o r k [ j ] + A l l o c a t i o n [ i , j ] Work[j] = Work[j] + Allocation[i,j] Work[j]=Work[j]+Allocation[i,j];
　　　 F i n i s h [ i ] = t r u e Finish[i] = true Finish[i]=true;
　　　 g o go go t o to to s t e p step step ( 2 ) (2) (2); (用 w h i l e while while语句实现)
(4) 如果所有进程的 F i n i s h [ i ] = t r u e Finish[i] =true Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

---

3、算法流程图

---

四、代码实现

#include<stdio.h>
//资源种类数 
#define resourceNum 3
//进程总数 
#define processNum  5

//可利用资源向量available[i]表示系统中现有i类资源个数 
int available[resourceNum]={3,3,2};
//最大资源矩阵maxRequest[i][j]表示进程i需要j类资源的最大数目
int maxRequest[processNum][resourceNum]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};
//可分配矩阵allocation[i][j]表示进程i当前已分得j类资源的数目
int allocation[processNum][resourceNum]={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};
//需求矩阵need[i][j]表示进程i需要j类资源的最大数目
int need[processNum][resourceNum]={{7,4,3},{1,2,2},{6,0,0},{0,1,1},{4,3,1}};
//是否安全
bool Finish[processNum];
//安全进程序列号
int safeSeries[processNum]={0,0,0,0,0};
//进程请求资源量
int request[resourceNum];
//资源数量计数
int num;

//打印输出系统信息
void showInfo()
{
	printf("\n------------------------------------------------------------------------------------\n");  
	printf("当前系统各类资源剩余：");
    for(int j = 0; j < resourceNum; j++)
	{
        printf("%d ",available[j]);
    }
    printf("\n\n当前系统资源情况：\n");
    printf(" PID\t Max\t\tAllocation\t Need\n");
    for(int i = 0; i < processNum; i++)
	{
        printf(" P%d\t",i);
        
        //打印最大资源矩阵maxRequest
        for(int j = 0; j < resourceNum; j++)
            printf("%2d",maxRequest[i][j]);
        printf("\t\t");
        
        //打印可分配矩阵allocation
        for(int j = 0; j < resourceNum; j++)
            printf("%2d",allocation[i][j]);
        printf("\t\t");
        
        //打印需求矩阵need
        for(int j = 0; j < resourceNum; j++)
            printf("%2d",need[i][j]);
        printf("\n");
    }
}

//打印安全检查信息
void SafeInfo(int *work, int i)
{
    int j;
    printf(" P%d\t",i);
    //打印工作向量work 
    for(j = 0; j < resourceNum; j++) 
        printf("%2d",work[j]);
    printf("\t\t");
    
    //打印需求矩阵need 
    for(j = 0; j < resourceNum; j++)
        printf("%2d",need[i][j]);
    printf("\t\t");
    
    //打印可分配矩阵allocation 
    for(j = 0; j < resourceNum; j++)
        printf("%2d",allocation[i][j]);
	printf("\t\t");
    
    //打印work + allocation 
    for(j = 0; j < resourceNum; j++)
        printf("%2d",allocation[i][j]+work[j]);
    printf("\n");
}

//判断一个进程的所需资源是否全为零
bool isAllZero(int kang)
{
	num = 0;
	for(int i = 0; i < resourceNum; i++ )
		if(need[kang][i] == 0)
			num ++; 
	
	if(num == resourceNum)
		return true;
	else
		return false; 
}

//安全检查
bool isSafe()
{
	bool flag = true; 
	int safeIndex = 0;	//安全进程个数 
	int allFinish = 0;	//可需资源为0的进程数 
	//工作变量work：系统可提供给进程继续运行所需的各类资源数目 
    int work[resourceNum] = {0};
	int r = 0;	//进程序号 
	int temp = 0;	//辅助判断所有进程是否全部分配完成 
	
	//预分配为了保护available
    for(int i = 0; i < resourceNum; i++)		
        work[i] = available[i];	
    
	//把未完成进程置为false
    for(int i = 0; i < processNum; i++)
	{
		bool result = isAllZero(i);
		if(result == true)
		{
			Finish[i] = true;
			allFinish++;
		}
		else
			Finish[i] = false;
    }
	//预分配开始
    while(allFinish != processNum)
	{
		num = 0;
		//检测进程所需资源是否符合剩余资源 
        for(int i = 0; i < resourceNum; i++)
			if(need[r][i] <= work[i] && Finish[r] == false)
				num ++;			

		//符合 
		if(num == resourceNum)
		{		
			if(flag)
			{
				flag = false;
				printf("\n系统安全情况分析：\n");
				printf(" PID\t Work\t\t Need\t \tAllocation\tWork+Allocation\n");
			} 
			SafeInfo(work,r);
			//释放资源 
			for(int i = 0; i < resourceNum; i++ )
				work[i] = work[i] + allocation[r][i];
				
			allFinish ++;
			safeSeries[safeIndex] = r;
			safeIndex ++;
			Finish[r] = true;
		}
		r ++;	
		if(r >= processNum)
		{
			r = r % processNum;
			if(temp == allFinish)
				break;
			temp = allFinish;
		}		
    }	
	//判断系统是否安全
	for(int i = 0; i < processNum; i++)
	{
		if(Finish[i] == false)
		{
			printf("\n当前系统不安全！\n\n");
			return false;	
		}
	}
	//打印安全序列
	printf("\n当前系统安全！\n\n安全序列为：");
	
	//打印安全序列 
	for(int i = 0; i < allFinish; i++)
		printf("%d ",safeSeries[i]);
    return true;
}

//主函数
int main()
{
	//输入的进程序号 
    int curProcess = 0;
    //用于控制输入内容的准确性（非字符） 
	int a = -1;
    showInfo(); 
	bool isStart = isSafe();
	//用户输入或者预设系统资源分配合理才能继续进行进程分配工作
    while(isStart)
	{
		//限制用户输入，以防用户输入大于进程数量的数字，以及输入其他字符（乱输是不允许的）
      	do
		{ 
			if(curProcess >= processNum || a == 0)
			{
				printf("\n请不要输入超出进程数量的值或者其他字符：\n");
				while(getchar() != '\n');//清空缓冲区 
				a = -1;
			}
			printf("\n------------------------------------------------------------------------------------\n");
			printf("\n输入要分配的进程：");
			a = scanf("%d",&curProcess);
			printf("\n");

		}while(curProcess >= processNum || a == 0);
		
		//限制用户输入，此处只接受数字，以防用户输入其他字符（乱输是不允许的）
		for(int i = 0; i < resourceNum; i++)
		{
			do
			{
				if(a == 0)
				{
					printf("\n请不要输入除数字以外的其他字符，请重新输入：\n");
					while(getchar() != '\n');//清空缓冲区	
					a = -1;
				}
				printf("请输入要分配给进程 P%d 的第 %d 类资源：",curProcess,i+1);
				a = scanf("%d", &request[i]);
			}while( a == 0);
		}

		//判断用户输入的分配是否合理，如果合理，开始进行预分配
		num  = 0;
        for(int i = 0; i < resourceNum; i++)
		{
            if(request[i] <= need[curProcess][i] && request[i] <= available[i])
				num ++;
            else
			{
				printf("\n发生错误！可能原因如下：\n(1)您请求分配的资源可能大于该进程的某些资源的最大需要！\n(2)系统所剩的资源已经不足了！\n");
				break;
			}
        }
        
        //合理 
        if(num == resourceNum)
		{	
			num = 0;	
            for(int j = 0; j < resourceNum; j++)
			{
				//分配资源
                available[j] = available[j] - request[j];
                allocation[curProcess][j] = allocation[curProcess][j] + request[j];
                need[curProcess][j] = need[curProcess][j] - request[j];
				//记录分配以后，是否该进程需要值为0了
				if(need[curProcess][j] == 0)
					num ++;
            }
			//如果分配以后出现该进程对所有资源的需求为0了，即刻释放该进程占用资源（视为完成）
			if(num == resourceNum)
			{
				//释放已完成资源
				for(int i = 0; i < resourceNum; i++ )
					available[i] = available[i] + allocation[curProcess][i];
				printf("\n\n本次分配进程 P%d 完成,该进程占用资源全部释放完毕！\n",curProcess);
			}
			else
				//资源分配可以不用一次性满足进程需求
				printf("\n\n本次分配进程 P%d 未完成！\n",curProcess);

			showInfo();

			//预分配完成以后，判断该系统是否安全，若安全，则可继续进行分配，若不安全，将已经分配的资源换回来
            if(!isSafe())
			{ 	  
				for(int j = 0; j < resourceNum; j++)
				{
					available[j] = available[j] + request[j];
					allocation[curProcess][j] = allocation[curProcess][j] - request[j];
					need[curProcess][j] = need[curProcess][j] +request[j];
				}
				printf("资源不足，等待中...\n\n分配失败！\n");				
            }
        }
    }
}

---

示例：

---

①

---

②

---

③

---

需要转载请标明出处

本文标签： 银行家算法