死锁避免.c

死锁避免——银行家算法的模拟实现

#include "string.h" 
#include "stdio.h" 
#include "stdlib.h"
#include "time.h" 
#include "conio.h" 
#include "dos.h" 
#define m 7				//资源类型的种类
#define n 1000			//系统进程的个数

int head;				//正在运行的第一条进程
int length;				//已有进程个数
int Available[m];		//长度为m的向量表示每种资源的现有实例的数量
int Max[n][m];			//n*m矩阵定义每个进程的最大需求
int Allocation[n][m];	//n*m矩阵定义每个进程现在所分配的各种资源类型的实例数量
int Need[n][m];			//n*m矩阵表示每个进程还需要的剩余的资源
int Request[n][m];		//n*m矩阵，表示当前各进程的资源请求情况
int Work[m];			//初始化Work=Available
int Finish[n];			//该进程是否能完成 
int Max_Available[m];	//初始时最大可用资源数
int SafeRoad[n];		//记录安全队列

void Creat_Available()							//初始化资源数
{
	int j;
	srand((unsigned)time(NULL));				//用系统时间当种子，对随机生成资源类型个数
	for(j=0;j<m;j++)
	{
		Available[j]=(rand()%10)+1;				//产生1-10的随机数
		Max_Available[j]=Available[j];
	}
}

void Creat_Process()							//初始化的三个随机进程
{
	int i,j,flag;
	srand((unsigned)time(NULL));				
	for(i=0;i<3;i++)
	{
		for(j=0;j<m;j++)
		{
			do
			{
				flag=0;							//标记生成的进程资源需求量必须少于系统设定
				Max[i][j]=rand()%10;
				if(Max[i][j]<=Available[j])
				{
					flag=1;
				}
			}while(flag!=1);
		}
		length+=1;
	}	
}

void Release()									//查看有没能释放的资源
{
	int i,j,flag=0;
	printf("查看有没能释放的资源...\n");
	for(i=head;i<length;i++)
	{
		flag=0;
		for(j=0;j<m;j++)
		{
			if(Need[i][j]!=0)
			{
				flag=1;
			}
		}
		if(flag==0)
		{
			printf("进程%d已获得所有需要资源，模拟当作它完成，释放其资源。该程序所有数据清零\n",i);
			for(j=0;j<m;j++)
			{
				Max[i][j]=0;
				Available[j]=Available[j]+Allocation[i][j];
				Allocation[i][j]=0;
			}
		}
	}
}


void Print()
{
	int i,j,k;
	printf("\n\n\tAllocation 各进程资源分配图\n");
	printf("----------------------------------------------------------\n");
	printf("\tA\tB\tC\tD\tE\tF\tG\n");
	for(i=head;i<length;i++)
	{
		printf("P%d",i);
		for(j=0;j<m;j++)
		{
			printf("\t%d",Allocation[i][j]);
		}
		printf("\n");
	}
	printf("----------------------------------------------------------\n");
	printf("\n\n\tMax 各进程最大需求资源\n");
	printf("----------------------------------------------------------\n");
	printf("\tA\tB\tC\tD\tE\tF\tG\n");
	for(i=head;i<length;i++)
	{
		printf("P%d",i);
		for(j=0;j<m;j++)
		{
			printf("\t%d",Max[i][j]);
		}
		printf("\n");
	}
	printf("----------------------------------------------------------\n");
	printf("\n\n\tAvailable 现在可用的资源\n");
	printf("----------------------------------------------------------\n");
	printf("\tA\tB\tC\tD\tE\tF\tG\n");
	for(j=0;j<m;j++)
	{
		printf("\t%d",Available[j]);
	}
	printf("\n----------------------------------------------------------\n");
	printf("\n\n\tNeed 各进程还需要资源\n");
	printf("----------------------------------------------------------\n");
	printf("\tA\tB\tC\tD\tE\tF\tG\n");
	for(i=head;i<length;i++)
	{
		printf("P%d",i);
		for(j=0;j<m;j++)
		{
			printf("\t%d",Need[i][j]);
		}
		printf("\n");
	}
	printf("----------------------------------------------------------\n");
	printf("其中一条安全顺序路径为:<");
	for(k=0;k<length;k++)
	{
		printf("P%d,",SafeRoad[k]);
	}
	printf(">\n");
}


int check_safe()					//安全性算法
{
	int i,j,k=0,safe_flag=0,cmp_flag,change_flag;
	int temp[n];
	for(k=0;k<length;k++)
	{
		temp[k]=SafeRoad[k];			//安全顺序记录备份
	}
	k=0;
	printf("开始检测系统的安全性...\n");
	for(j=0;j<m;j++)					//第一步，Work=Available且所有Finish[i]=0
	{	
		Work[j]=Available[j];		
	}
	for(i=0;i<length;i++)
	{
		Finish[i]=0;
	}
	do
	{
		change_flag=0;
		for(i=head;i<length;i++)
		{
			change_flag=0;
			cmp_flag=0;
			for(j=0;j<m;j++)
			{
				if(Need[i][j]>Work[j])
				{
					cmp_flag=1;								//若需求Need中有个资源输大于能提供资源数Work则做标记
				}										
			}
			if((cmp_flag!=1)&&(Finish[i]!=1))				//第二步，找到满足Finish[i]=0且Need[i]<=Work条件的进程
			{
				for(j=0;j<m;j++)							//第三步，释放能完成进程的资源Work=Work+Allocation，且标记该进程Finish[i]=1
				{
					Work[j]=Work[j]+Allocation[i][j];		
				}
				Finish[i]=1;
				SafeRoad[k]=i;
				k+=1;
			//	printf("saferoad:%d,k=%d\n",SafeRoad[k],k);
				change_flag=1;
			}
		}
	}while(change_flag==1);									//若第二步找不到有满足条件的进程
	for(i=head;i<length;i++)								//则搜索所有i，若有Finish[i]=0则会发生死锁
	{
	//	printf("%d:%d ",i,Finish[i]);
		if(Finish[i]==0)
		{
			safe_flag=1;					//1为不安全，0为安全
			for(k=0;k<length;k++)
			{
				temp[k]=SafeRoad[k];		//原来那条走不通拿回备份
			}					
		}
	}
	//printf("flag=%d",safe_flag);
	return(safe_flag);
}

int check_request(int i)							//检测资源请求能否通过
{
	int j,cmp_flag=0,cmp_flag2=0,check_flag=0;
	printf("开始验证资源请求...\n");
	for(j=0;j<m;j++)
	{
		if(Request[i][j]>Need[i][j])				//第一步检测Request[i]是否少于等于Need[i]
		{
			cmp_flag=1;
		}
	}
	if(cmp_flag==1)				
	{
		check_flag=1;
		printf("出错！请求资源大于进程本身需求资源。\n");
	}
	else							
	{
		for(j=0;j<m;j++)
		{
			if(Request[i][j]>Available[j]) cmp_flag2=1;		//第二步检测Request[i]是否少于等于Available
		}
		if(cmp_flag2==1)
		{
			check_flag=1;
			printf("出错！现时没有足够的可用资源\n");
		}
	}
	return(check_flag);
}


void request_resource()				//资源请求算法
{
	int i,j,check_flag,safe_flag=0;
	//for(i=0;i<length;i++)
	//{
	//	for(j=0;j<m;j++)
	//	{
	//		Request[i][j]=Allocation[i][j];
	//	}
	//}
	do
	{
		printf("请正确输入要请求资源的进程号（0-%d）:",length-1);
		scanf("%d",&i);
	}while(i<0||i>=length);
	printf("\n\n\tAvailable 现在可用的资源\n");
	printf("----------------------------------------------------------\n");
	printf("\tA\tB\tC\tD\tE\tF\tG\n");
	for(j=0;j<m;j++)
	{
		printf("\t%d",Available[j]);
	}
	printf("\n----------------------------------------------------------\n");
	printf("\n\n\tNeed 进程p%d还需要资源\n",i);
	printf("----------------------------------------------------------\n");
	printf("\tA\tB\tC\tD\tE\tF\tG\n");
	for(j=0;j<m;j++)
	{
		printf("\t%d",Need[i][j]);
	}
	printf("\n----------------------------------------------------------\n");
	printf("请输入请求各资源的个数（格式例子：1 2 3 4 5 6 7）\n");
	for(j=0;j<m;j++)
	{
		scanf("%d",&Request[i][j]);
	//	Request[i][j]=Request[i][j]+temp[m];
	}
	check_flag=check_request(i);
	if(check_flag==0)
	{
		for(j=0;j<m;j++)
		{
			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];
		}
		Release();
		safe_flag=check_safe();
		if(safe_flag==1) 
		{
			printf("\n系统不安全！\n");
			for(j=0;j<m;j++)
			{
				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];
			}
			printf("进程申请没被通过。\n");
		}
		else 
		{
			
			printf("\n系统安全！\n");
		}
	}
	else printf("进程申请没被通过。\n");
	
	
	
	printf("现在的资源情况为...（按下空格键继续演示）\n");
	getch();
	Print();
}

void Creat_Request()							//随机生成一个进程的资源请求
{
	int i,j,flag,check_flag,safe_flag=0;;
	srand((unsigned)time(NULL));
	do
	{
		i=rand()%1000;
	}while(i<head||i>=length);
	for(j=0;j<m;j++)
	{
		do
		{
			flag=0;								//标记生成的进程资源申请量必须少于当时进程需求量
			Request[i][j]=rand()%10;
			if(Request[i][j]<=Need[i][j])
			{
				flag=1;
			}
		}while(flag!=1);
	}
	printf("\nRequest 随机生成的进程资源需求图为\n");
	printf("----------------------------------------------------------\n");
	printf("\tA\tB\tC\tD\tE\tF\tG\np%d",i);
	for(j=0;j<m;j++)
	{
		printf("\t%d",Request[i][j]);
	}
	printf("\n----------------------------------------------------------\n");
	printf("按下空格键继续演示\n");
	getch();
	check_flag=check_request(i);
	if(check_flag==0)
	{
		for(j=0;j<m;j++)
		{
			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];
		}
		Release();
		safe_flag=check_safe();
		if(safe_flag==1) 
		{
			printf("\n系统不安全！\n");
			for(j=0;j<m;j++)
			{
				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];
			}
			printf("进程申请没被通过。\n");
		}
		else 
		{
			
			printf("\n系统安全！\n");
		}
	}
	else printf("进程申请没被通过。\n");
	
	
	
	printf("现在的资源情况为...（按下空格键继续演示）\n");
	getch();
	Print();
}

void Add_Process()			//随机增加一个新的进程需求向量
{
	int i,j,flag;
	i=length;
	for(j=0;j<m;j++)
		{
			do
			{
				flag=0;							//标记生成的进程资源需求量必须少于系统设定
				Max[i][j]=rand()%10;
				Need[i][j]=Max[i][j];
				if(Max[i][j]<=Max_Available[j])
				{
					flag=1;
				}
			}while(flag!=1);
		}
	length+=1;
}



void main()
{
	int i,j,safe_flag,choice;
	printf("\n模拟死锁避免，银行家算法\n");
	
	safe_flag=0;
	printf("正在初始化随机状况.......\n");
	Creat_Available();
	Creat_Process();
	SafeRoad[0]=1;
	SafeRoad[1]=2;
	SafeRoad[2]=3;
	for(i=head;i<length;i++)
	{
		for(j=0;j<m;j++)
		{
			Available[j]=Available[j]-Allocation[i][j];
			Need[i][j]=Max[i][j]-Allocation[i][j];
		}
	}
	Print();
	safe_flag=check_safe();
	if(safe_flag==1) printf("\n系统不安全！\n");
	else printf("\n系统安全！\n");
	for(;;)
	{
		do
		{
			printf("1、重新初始化 。\n2、手动请求资源。 \n3、随机请求资源。 \n4、随机生成新进程。 \n5、退出。");
			printf("\n\n请输入正确的选项：");
			scanf("%d",&choice);
			switch(choice)
			{
			case 1:
				printf("正在初始化随机状况.......\n");
				length=0;
				Creat_Available();
				Creat_Process();
				for(i=head;i<length;i++)
				{
					for(j=0;j<m;j++)
					{
						Allocation[i][j]=0;
						Need[i][j]=Max[i][j]-Allocation[i][j];
					}
				}
				SafeRoad[0]=1;
				SafeRoad[1]=2;
				SafeRoad[2]=3;
				Print();
				break;
			case 2:
				request_resource();
				break;
			case 3:
				Creat_Request();
				break;
			case 4:
				Add_Process();
				SafeRoad[length-1]=length-1;
				Print();
				break;
			case 5:
				exit(0);
			}
		}while(choice!=5);
	}
}