首页 > 代码库 > 编程序模拟银行家算法

编程序模拟银行家算法

2024-11-11 08:39:01   202人阅读

一、编程序模拟银行家算法

1）对用银行家算法来避免死锁的方法有较深入的了解，给出系统的初始状态，模拟避免死锁的动态过程。


2）银行家算法中的数据结构

（1）可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。Available[j]=K，则表示系统中现有Rj类资源K个。

（2）最大需求矩阵Max。这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i，j]=K，则表示进程i需要Rj类资源的最大数目为K。

（3）分配矩阵Allocation。这也是一个n*m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i，j]=K，则表示进程i当前已分得Rj类资源的数目为K。

（4）需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i，j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。

上述三个矩阵存在如下关系：

 Need[i,j]= Max[i，j]- Allocation[i，j]


3）银行家算法

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

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

（2）如果Request[i，j]<=Available[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等待。


4）安全性算法

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

（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[i]+ Allocation[i，j]；

         Finish[i]=true；

         go to step 2；

（4）如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。





二、流程图

                                                          技术分享







三、源代码


#include<stdio.h>
#define M 3
#define N 4


int Available[M]={1,1,2};
int Max[N][M]=		 {3,2,2,6,1,3,3,1,4,4,2,2};
int Allocation[N][M]={1,0,0,5,1,1,2,1,1,0,0,2};
int Need[N][M]=		 {2,2,2,1,0,2,1,0,3,4,2,0};
int Request[N][M]= {1,1,0,1,0,1,3,1,4,4,2,2};

/*
int Available[M]={1,5,2,0};
int Max[N][M]=		 {0,0,1,2,1,7,5,0,2,3,5,6,0,6,5,2,0,6,5,6};
int Allocation[N][M]={0,0,1,2,1,0,0,0,1,3,5,4,0,6,3,2,0,0,1,4};
int Need[N][M]=		 {0,0,0,0,0,7,5,0,1,0,0,2,0,0,2,0,0,6,4,2};
int Request[N][M]=   {0,0,0,0,0,5,2,0,1,0,0,2,0,0,2,0,0,6,4,2};
*/


int isLessOrEqual(int *arry1,int *arry2)
{
	int i;
	for(i=0;i<M;i++)
	{
		if(arry1[i]>arry2[i])
		return 0;
	}
	return 1;
}

int isGreatOrEqual(int *arry1,int *arry2)
{
	int i;
	for(i=0;i<M;i++)
	{
		if(arry1[i]<arry2[i])
		return 0;
	}
	return 1;
}

void Sub(int *arry1,int *arry2)
{
	int i;
	for( i=0;i<M;i++)
		arry1[i]=arry1[i]-arry2[i];
}

void Sum(int *arry1,int *arry2)
{
	int i;
	for(i=0;i<M;i++)
		arry1[i]=arry1[i]+arry2[i];
}

int isEmpty(int *arry)
{
	int i=0;
	for(i=0;i<N;i++)
	if(arry[i]==0)
	return 0;
	return 1;
}

void showAvailable(int *arry)
{
	int i;
	for(i=0;i<M;i++)
	printf("%c ",'A'+i);	
	printf("\n");
	
	for(i=0;i<M;i++)
	printf("%d ",arry[i]);	
	printf("\n");
}

void show(int (*arry)[M])
{
	int i=0,j;
	printf("     ");
	for(i=0;i<M;i++)
	printf("%c ",'A'+i);
	printf("\n");
	
	for(i=0;i<N;i++)
	{
		printf("pid%d ",i); 
		for(j=0;j<M;j++)
		printf("%d ",arry[i][j]);
		printf("\n");
	}
	printf("\n");
}

int isSafe()
{
	int Work[M];
	int Finish[N];
	int i,j;
	
	printf("\n\n\t\t\t安全算法\n");
	 
	for(i=0;i<N;i++)
		Finish[i]=0;
		
	for( i=0;i<M;i++)
	Work[i]=Available[i];
	
	for(j=0;j<N;j++)
	{
		while(j<N&&Finish[j]==1)
		j++;
		
		if(j==N)
		{ 		 //3
			if(isEmpty(Finish))
			{
				printf("系统安全！"); 
				return 1;
			}
			else
			{
				printf("系统不安全！"); 
				return 0;
			}
		}
			
		if(isGreatOrEqual(Work,Need[j]))
		{   //2
			Sum(Work,Allocation[j]);
			printf("进程%d已满足,资源收回,银行家现剩下的各类的资源总数为\n",j);
			showAvailable(Work);
			printf("............\n\n");
			Finish[j]=1; 	
			j=-1;    //跳转到 1
		} 				
	}
	printf("系统不安全！"); 
	return 0;
}


int Banker(int process)
{
	int i=process;
	printf("银行家目前剩下的各类的资源总数为:\n");
	showAvailable(Available);
	
	printf("各进程对各类的资源的最大需求量为:\n");
	show(Max);
	
	printf("各进程已分配到的各类的资源为:\n");
	show(Allocation);
	
	printf("进程%d申请资源，申请的资源为:\n",i); 
	showAvailable(Request[i]);
	
	if(!isLessOrEqual(Request[i],Need[i]))
	{
		printf("申请的资源大于所需要的资源，有误!\n") ;
		return -1;
	} 
	
	if(!isLessOrEqual(Request[i],Available))
	{
		printf("申请的资源大于现有的资源，系统暂无足够资源!\n") ;
		return -2;
	}
	
	Sub(Available,Request[i]);
	Sum(Allocation[i],Request[i]);
	Sub(Need[i],Request[i]);
	
	if(!isSafe())
	{
		Sum(Available,Request[i]);
		Sub(Allocation[i],Request[i]);
		Sum(Need[i],Request[i]);
		printf("申请失败\n");
		return -1;
	}
	else
	{
		printf("申请成功\n");
 		return i;
 	}
}	

int main()
{
	 Banker(1);
	 return 0; 
}


编程序模拟银行家算法


联系
我们