banker.cpp

多用户银行家算法

//040640110 吴遐 银行家算法

#include "iostream.h"
#include "stdio.h"
#include "stdlib.h"

class Resource
{
private:
	int resource[3];  //3类资源

public:
	//资源的初始化
	Resource()
	{
		SetResource(0,0,0);
	}
	//设置各种资源数目
	Resource(int A,int B,int C)
	{
		SetResource(A,B,C);
	}
	void SetResource(int A,int B,int C)
	{
		resource[0] = A;
		resource[1] = B;
		resource[2] = C;
	}
	//判断资源
	int operator <=(Resource &ResourceCompare)
	{
		int j=1;
		for(int i=0; i<3; i++)//有3类资源
		{
			if(resource[i]>ResourceCompare.resource[i])
			{//存在的资源数 > 请求的资源数
				j = 0;
				break;
			}
		}
		return j;
	}
	//减少资源数
	Resource operator -=(Resource &ResourceSub)
	{
		for(int i=0; i<3; i++)
		{
			resource[i] -= ResourceSub.resource[i];
		}
		return *this;
	}
	//增加资源数
	Resource operator +=(Resource &ResourceAdd)
	{
		for(int i=0; i<3; i++)
		{
			resource[i] += ResourceAdd.resource[i];
		}
		return *this;
	}
	//输出资源信息
	void ResourcePrint()
	{
		cout << resource[0] << "  " << resource[1] << "  " << resource[2];
	}
};

class Process
{
private:
	char *Name;  //进程名称
	Resource *Max;  //最大需求资源
	Resource *Allocation;  //分配资源
	Resource *Need;  //需求资源
	Resource *Request;  //请求资源
	int Finish;  //完成标志

public:
	//进程的各类信息初始化
	Process()
	{
		Name = NULL;
		Max = NULL;
		Allocation = NULL;
		Need = NULL;
		Request = NULL;
		Finish = 0;
	}
	Process(char *Name1,int A1,int B1,int C1,int A2,int B2,int C2)
	{//1是Max，2是Allocation
		Name = Name1;
		Max = new Resource(A1,B1,C1);
		Allocation = new Resource(A2,B2,C2);
		Need = new Resource(A1-A2,B1-B2,C1-C2);
		Request=new Resource(0,0,0);
		Finish=0;
	}
	//请求资源
	void SetRequest(int A,int B,int C)
	{
		Request->SetResource(A,B,C);
	}
	void SetFinish()
	{
		Finish=1;  //如果分配资源后进程能完成，就置标志为1，代表已完成
	}
	void ResetFinish()
	{
		Finish=0;  //重置Finish
	}
	//返回进程的各类信息
	char *ReturnProcessName()
	{
		return Name;
	}
	Resource *ReturnMax()
	{
		return Max;
	}
	Resource *ReturnAllocation()
	{
		return Allocation;
	}
	Resource *ReturnNeed()
	{
		return Need;
	}
	Resource *ReturnRequest()
	{
		return Request;
	}
	int ReturnFinish()
	{
		return Finish;
	}
};


/**************************************************************************************/
/*                                    检查安全性                                      */
/**************************************************************************************/

int CheckSafe(Resource &Available,Process process[])
{
	int SafeList[5];  //记录安全序列的顺序
	int Search=1;  //搜索可以获得资源后顺利执行并完成的进程
	int CircleTime=0;  //循环次数
	int j=0;

	//n个进程如果有安全序列最多需要循环n次，就能找到一个安全序列
	while(Search&&CircleTime<5)
	{
		for(int i=0;i<5;i++)
		{
			if(process[i].ReturnFinish()==0 && *(process[i].ReturnNeed())<=Available)
			{
				//进程Pi可以获得资源，并释放分配给它的资源
				Available += *(process[i].ReturnAllocation());
		        process[i].SetFinish();  //置该进程的完成标志为1，表示该进程已完成
			    SafeList[j] = i;
			    j++;
			}
		}
		if(j==5)  //输出当前各个进程的状态
		{
            cout << "资源情况" << "\t  Work  " << "\t Need  " << "\t   Allocation" << "\tFinish" << endl
		         << "进    程" << "\tA  B  C " << "\tA  B  C" << "\t    A  B  C" << "\tA  B  C" << endl; 
			for(int i=0; i<5; i++)
			{
				cout << "  " << process[SafeList[i]].ReturnProcessName() << "      ";
				cout << "\t";
				Available.ResourcePrint();
                cout << "\t        ";
                process[SafeList[i]].ReturnNeed()->ResourcePrint();
				cout << "\t    ";
				process[SafeList[i]].ReturnAllocation()->ResourcePrint();
				cout << "\t true";
                Available += *(process[SafeList[i]].ReturnAllocation());
				cout << endl;
			}
			printf("********************************************************************************");
			return 1;
			break;
		}
		CircleTime++;
	}
	if(CircleTime==5)
	{
		return 0;
	}
}


/**************************************************************************************/
/*                                     主函数                                         */
/**************************************************************************************/

void main()
{
	int x;
	Process process[5];
	
	//书上的例子
	process[0] = Process("P0",7,5,3,0,1,0);
	process[1] = Process("P1",3,2,2,2,0,0);
	process[2] = Process("P2",9,0,2,3,0,2);
	process[3] = Process("P3",2,2,2,2,1,1);
	process[4] = Process("P4",4,3,3,0,0,2);
	Resource Available(3,3,2);  //进行此状态下的安全性检查

	printf("********************************************************************************");
	printf("\n");
	printf("                                  银行家算法                                  \n");
	printf("\n\n");
	printf("                                欢迎使用本程序!\n\n");
	printf("\n");
	printf("                                                         040640110 吴遐  \n");
	printf("********************************************************************************");
	
	printf ("\n\n  若想使用本程序请输入1,否则按任意键退出:  ");
	scanf ("%d",&x);

	if(x == 1) 
	{
		system("cls");
	    goto loop1;
	} 
	
	if (x!=1)
		goto loop2;

loop1:
	while(1)
	{
		cout << "资源情况" << "\t  Max  " << "\t   Allocation" << "\t   Need  " << "\t  Available" << endl
			 << "进    程" << "\tA  B  C" << "\t    A  B  C" << "\t  A  B  C" << "\t   A  B  C" << endl;          
		for(int i=0; i<5; i++)  //输出各个进程的初始状态
		{
			cout << "  " << process[i].ReturnProcessName() << "      ";
			cout << "\t";
			process[i].ReturnMax()->ResourcePrint();
			cout << "\t    ";
			process[i].ReturnAllocation()->ResourcePrint();
			cout << "\t  ";
			process[i].ReturnNeed()->ResourcePrint();
			if(i==0)
			{
				cout << "\t   ";
				Available.ResourcePrint();
			}
			cout << endl;
		}
		printf("********************************************************************************");

		//求是否处于安全状态
		int choice;
		bool finished = false;
		Resource tempAvailable,tempAllocation,tempNeed;
		if(!CheckSafe(Available,process))
			cout << "\t当前系统处于不安全状态。" << endl;
		else
		{
			cout << "\t当前系统处于安全状态。" << endl;
			while(!finished)//执行安全性检查，提供选择“1、P1请求资源”“2、P2请求资源”
			                //“3、P3请求资源”“4、P4请求资源”“5、P5请求资源”
			{//如果分配资源后，系统进入不安全状态，那么就撤销分配的资源
			 //还原该进程的属性，让该进程进入等待队
				cout << "\t0.P0请求资源，请按0" << endl
					 << "\t1.P1请求资源，请按1" << endl
					 << "\t2.P2请求资源，请按2" << endl
					 << "\t3.P3请求资源，请按3" << endl
					 << "\t4.P4请求资源，请按4" << endl
					 << "\t5.不再请求资源，退出，请按5" << endl;
				cout << "\t请输入:=>";
				cin >> choice;
				
				int A,B,C;
				int wait=0;  //如果有进程请求资源，但是可提供的资源又不够，就让它直接进行下一次循环
				switch(choice)
				{
				case 0:
					cout << "\t请输入请求向量Request(*,*,*):=>";
					cin >> A, cin >> B, cin >> C;
					process[0].SetRequest(A,B,C);
					if(*(process[0].ReturnRequest()) <= *(process[0].ReturnNeed()))
					{
						if(!(*(process[0].ReturnRequest()) <= Available))
						{
							cout << "\t系统尚无足够资源，P0须等待.\n" << endl;
							wait = 1;
						}
						else
						{//计算该进程的资源情况
							tempAvailable = Available;
							tempAllocation = *(process[0].ReturnAllocation());
							tempNeed = *(process[0].ReturnNeed());
							Available -= *(process[0].ReturnRequest());
							*(process[0].ReturnAllocation()) += *(process[0].ReturnRequest());
							*(process[0].ReturnNeed())-=*(process[0].ReturnRequest());
						}
					}
					else 
					{
						cout << "\t出错，所需要的资源已超过它所宣布的最大值．\n" << endl;
						wait = 1;
					}
					break;
 
				case 1:
					cout << "\t请输入请求向量Request(*,*,*):=>";
					cin >> A, cin >> B, cin >> C;
					process[1].SetRequest(A,B,C);
					if(*(process[1].ReturnRequest()) <= *(process[1].ReturnNeed()))
					{
						if(!(*(process[1].ReturnRequest()) <= Available))
						{
							cout << "\t系统尚无足够资源，P1须等待.\n" << endl;
							wait = 1;
						}
						else
						{//计算该进程的资源情况
							tempAvailable = Available;
							tempAllocation = *(process[1].ReturnAllocation());
							tempNeed = *(process[1].ReturnNeed());
							Available -= *(process[1].ReturnRequest());
							*(process[1].ReturnAllocation()) += *(process[1].ReturnRequest());
							*(process[1].ReturnNeed())-=*(process[1].ReturnRequest());
						}
					}
					else 
					{
						cout << "\t出错，所需要的资源已超过它所宣布的最大值．\n" << endl;
						wait = 1;
					}
					break;

				case 2:
					cout << "\t请输入请求向量Request(*,*,*):=>";
					cin >> A, cin >> B, cin >> C;
					process[1].SetRequest(A,B,C);
					if(*(process[1].ReturnRequest()) <= *(process[1].ReturnNeed()))
					{
						if(!(*(process[1].ReturnRequest()) <= Available))
						{
							cout << "\t系统尚无足够资源，P1须等待.\n" << endl;
							wait = 1;
						}
						else
						{//计算该进程的资源情况
							tempAvailable = Available;
							tempAllocation = *(process[1].ReturnAllocation());
							tempNeed = *(process[1].ReturnNeed());
							Available -= *(process[1].ReturnRequest());
							*(process[1].ReturnAllocation()) += *(process[1].ReturnRequest());
							*(process[1].ReturnNeed())-=*(process[1].ReturnRequest());
						}
					}
					else 
					{
						cout << "\t出错，所需要的资源已超过它所宣布的最大值．\n" << endl;
						wait = 1;
					}
					break;

				case 3:
					cout << "\t请输入请求向量Request(*,*,*):=>";
					cin >> A, cin >> B, cin >> C;
					process[1].SetRequest(A,B,C);
					if(*(process[1].ReturnRequest()) <= *(process[1].ReturnNeed()))
					{
						if(!(*(process[1].ReturnRequest()) <= Available))
						{
							cout << "\t系统尚无足够资源，P1须等待.\n" << endl;
							wait = 1;
						}
						else
						{//计算该进程的资源情况
							tempAvailable = Available;
							tempAllocation = *(process[1].ReturnAllocation());
							tempNeed = *(process[1].ReturnNeed());
							Available -= *(process[1].ReturnRequest());
							*(process[1].ReturnAllocation()) += *(process[1].ReturnRequest());
							*(process[1].ReturnNeed())-=*(process[1].ReturnRequest());
						}
					}
					else 
					{
						cout << "\t出错，所需要的资源已超过它所宣布的最大值．\n" << endl;
						wait = 1;
					}
					break;

				case 4:
					cout << "\t请输入请求向量Request(*,*,*):=>";
					cin >> A, cin >> B, cin >> C;
					process[1].SetRequest(A,B,C);
					if(*(process[1].ReturnRequest()) <= *(process[1].ReturnNeed()))
					{
						if(!(*(process[1].ReturnRequest()) <= Available))
						{
							cout << "\t系统尚无足够资源，P1须等待.\n" << endl;
							wait = 1;
						}
						else
						{//计算该进程的资源情况
							tempAvailable = Available;
							tempAllocation = *(process[1].ReturnAllocation());
							tempNeed = *(process[1].ReturnNeed());
							Available -= *(process[1].ReturnRequest());
							*(process[1].ReturnAllocation()) += *(process[1].ReturnRequest());
							*(process[1].ReturnNeed())-=*(process[1].ReturnRequest());
						}
					}
					else 
					{
						cout << "\t出错，所需要的资源已超过它所宣布的最大值．\n" << endl;
						wait = 1;
					}
					break;
			   
				case 5:
					goto loop2;
					break;
			   
				default:
					finished = true;
					break;
                }
				if(finished!=true && wait!=1)
				{
					if(!CheckSafe(Available,process))
					{
						cout << "\t当前系统处于不安全状态。进程"
							 << process[choice].ReturnProcessName()
							 << "进入等待。\n"<<endl;
						Available = tempAvailable;
						*(process[choice].ReturnAllocation()) = tempAllocation;
						*(process[choice].ReturnNeed()) = tempNeed;
					}
					else
						cout << "\t当前系统处于安全状态，资源分配成功．\n" << endl;
				}
            }
       }
    }

loop2:
	system("cls");
	printf("\n\n");
	printf("********************************************************************************");
	printf("\n\t\t\t***您已经选择退出,感谢使用!***\n\n");
	printf("********************************************************************************");
	printf("\n\n");
}
//下一步就是有某个进程请求资源，如果满足条件，先把资源分给它，再看系统是否处于安全状态  
//如果是，就可能有这样分配的循环，直到所有进程都能执行完，如果中途会出现不安全状态，就
//会回收已分配给进程的资源，让该进程进行等待。如果还有其他进程要分配资源，就继续下去。