banker.cpp

操作系统中避免死锁——银行家算法的实现。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define  MAXPROC 5
#define  MAXRES 3

int Allocation[MAXPROC][MAXRES];
int Max[MAXPROC][MAXRES]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};
int Available[MAXRES];
int Need[MAXPROC][MAXRES];
int status[MAXPROC];//进程状态  就绪态、等待态和完成态 全局变量，自然初始化为0
int pnum = MAXPROC;//进程数
int rnum = MAXRES;//资源数
int request[MAXPROC];//用户请求
int safetyQueue[MAXPROC];
//看看是否满足申请条件
int Check(const int *need,const int *max)
{
	for(int i = 0; i < rnum; i++)
		if(need[i] > max[i])
			return 0;
	return 1;
}
//安全吗
int IsSafe()
{
	int Work[MAXRES];
	int Finish[MAXPROC];
	int count = 0;
	int i, j,k = 0;
	for(i = 0 ; i < rnum; i++)
        Work[i] =Available[i];
	for(i = 0; i< pnum;i++)
		Finish[i] = 0;
	i = 0;
	while (i < pnum)
	{
		if( Finish[i] == 0 && Check(Need[i],Work))
		{
			for(j = 0; j < rnum; j++)
			{
				Work[j] += Allocation[i][j];
			}
			Finish[i] = 1;
			safetyQueue[k++] = i;
			count++;
			i = 0;
			continue;
		}
		i++;
	}
	if (count < pnum )
		return 0;
	else
		return 1;
}
//资源请求
int ResRequest(int *request,int procid)
{
	int i,j;
	if(!Check(request,Need[procid]))
	{
		printf("资源请求多余需要，失败!\n");
		status[procid] = 1;
		return 0;
	}
	else if(!Check(request,Available))
	{
		printf("资源请求多于可用，失败!\n");
		status[procid] = 1;
		return 0;
	}
	else
	{
		int count = 0;
		
		status[procid] = 1;
		int temp1[3],temp2[3],temp3[3];
		
		for(i = 0; i < rnum; i++)
		{
			temp1[i] = Available[i];
			temp3[i] = Max[procid][i];
			Available[i] -= request[i];
			temp2[i] = Allocation[procid][i];
			Allocation[procid][i] += request[i];
			Need[procid][i] -= request[i];
			if(!Need[procid][i])//资源请求i满足
				count++;
		}
		
		if(count == rnum)//全满足
		{
			status[procid] = 2;
			for(j = 0; j < rnum ; j++)
			{
				Available[j] += Max[procid][j];
				Allocation[procid][j] = 0;
				Max[procid][j] = 0;
			}
		}
		
		if (!IsSafe())
		{
			for(i = 0; i < rnum; i++)//回滚操作
			{
				Available[i] = temp1[i];
				Allocation[procid][i] =temp2[i];
				Max[procid][i] = temp3[i];
				Need[procid][i] = Max[procid][i] - Allocation[procid][i];
			}
			printf("资源分配失败!\n");
			status[procid] = 1;
			return 0;
		}
		else
		{
			for(i = 0; i < pnum; i++)
			{
				if(status[i] == 1 && Check(Need[i],Available))
					status[i] = 0 ;
			}
			printf("资源分配成功\n");
			printf("一个可用的安全序列是\n");
			for(j = 0; j < pnum;j++)
			{
				printf("%d ",safetyQueue[j]);
			}
			printf("\n");
			if(status[procid] ==2)
				printf("....\nP%d 的资源释放\n",procid);
			return 1;
		}
		
	}
}

int RequestCheck(int *request,int procid)
{
    int i;
	if(!Check(request,Need[procid]))
	{
		printf("资源分配失败!\n");
		status[procid] = 1;
		return 0;
	}
	else if(!Check(request,Available))
	{
		printf("资源分配失败!\n");
		status[procid] = 1;
		return 0;
	}
	else
	{
		int count = 0;
		for(i = 0; i < rnum; i++)
		{
			
			Available[i] -= request[i];
			Allocation[procid][i] += request[i];
			Need[procid][i] -= request[i];
			if(!Need[procid][i])
				count++;
			status[procid] = 1;
		}
		if(count == rnum)
		{
			status[procid] = 2;
			for( int j = 0; j < rnum ; j++)
			{
				Available[j] += Max[procid][j];
				Allocation[procid][j] = 0;
				Max[procid][j] = 0;
			}
			for(int i = 0; i < pnum; i++)
			{
				if(status[i] == 1 && Check(Need[i],Available))
					status[i] = 0 ;
			}
		}
		printf("资源分配成功\n");
		if(status[procid] ==2)
			printf("....\nP%d 的资源释放\n",procid);
		return 1;
	}
}
//检查进程状态
int CheckState(const int *status,int *procid)
{
	int count = 0;
	int i;
	for(i = 0; i < pnum; i++)
	{
		if(status[i] == 0)//就绪的
		{
			*procid = i;
			return 0;
		}
		if(status[i] == 2)//完成的
		{
			count++;
		}
	}
	if(count == pnum)//都完成了
		return 2;
	else
		return 1;//等待
}

void Initialize()//初始化
{
    int i,j;
	int count;
	printf("进程的数目是%d:\n",pnum);
	printf("资源的数目是%d:\n",rnum);
	
	printf("输入资源的初始状态（目前可用量）.\n");
	for (i = 0; i < rnum; i++)
	{
		printf("Resouce %c:",i + 'A');
		scanf("%d",&Available[i]);
	}
	
	printf("输入进程状态\n");
	for (i = 0,count=0; i < pnum; count=0,i++)
	{
		printf("对于进程P%d:\n",i);		
		printf("已分配资源量: \n");
		for (j = 0; j < rnum; j++)
		{
			printf("Resources %c:",j + 'A');
			scanf("%d", &Allocation[i][j]);
			Need[i][j] = Max[i][j] - Allocation[i][j];
			if(Need[i][j] == 0)//完成一个
				count ++;
		}
		if(count == rnum)//全完了
		{
			status[i] = 2;
			for( j = 0; j < rnum ; j++)
			{
				Available[j] += Max[i][j];
				Allocation[i][j] = 0;
				Max[i][j] = 0;
				
			}
		}
	}
}
//处理进程procid
void Deal(int procid)
{
    int i;
	printf("目前可用资源量:\n");
	for( i = 0 ; i < rnum; i++)
	{
		printf("Resouce %c: %d\n",i + 'A',Available[i]);
	}
	printf("\n");	
	printf("目前的状态是:\n");
	printf("	  Max Allocation Need Available\n");
	for( i = 0 ; i < rnum; i++)
	{
		printf("Resouce %c:%-2d    %-2d	  %-2d    %-2d\n",i + 'A',Max[procid][i],
			Allocation[procid][i],Need[procid][i],Available[i]);
	}
	printf("输入进程 P%d的请求:\n",procid);
	for( i = 0 ; i < rnum; i++)
	{
		printf("Resouce %c:",i + 'A');
		scanf("%d",&request[i]);
	}
}

int main()
{
	
	int procid;//进程号
	int choice = 0;
	
	Initialize();
	printf("0. 银行家算法.\n");
	printf("1. 随机算法.\n");
	printf("请选择算法(0/1)\n");
	scanf("%d",&choice);
	while(choice != 0 && choice!=1)
	{
		printf("选错了，重选\n");
		scanf("%d",&choice);
	}
	while(CheckState(status,&procid) == 0)//有就绪的
	{
		if(choice == 0){
			Deal(procid);
			ResRequest(request,procid);
		}
		else{
			Deal(procid);
			RequestCheck(request,procid);
		}

	}
	if(CheckState(status,&procid) ==2)
	{
		printf("完成!\n");
		return 0;
	}
	else//大家都在等待，死锁了
		printf("郁闷，死锁了!\n");
	exit(-1);
}