deadlock.cpp

解决进程死锁的银行家算法,vc++2005

#include <iostream>
#include <iomanip>


using namespace std;

class bank
{
	int m,n;      //n为进程个数,m为资源种类数
	bool flag;		//标记是否使用银行家算法避免死锁
	int *available;     //可利用资源向量
	int **max;			//最大需求矩阵
	int **allocation;	//资源分配矩阵
	int **need;			//需求矩阵
	int index;			//当前有资源需求的进程号
	int *request;		//当前某个进程的资源需求向量
	int *safe;			//安全序列
public:
	bank(int a,int b,bool c)
	{
		m = b;
		n = a;
		flag = c;
		available = new int[m];
		request = new int[m];
		max = new int*[n];
		allocation = new int*[n];
		need = new int*[n];
		safe = new int[n];
		for(int i = 0;i < n;i++)
		{
			max[i] = new int[m];
			allocation[i] = new int[m];
			need[i] = new int[m];
		}
		for(int j = 0;j < n;j++)
		{
			for(int k = 0;k < m;k++)
				allocation[j][k]=0;
		}
		init();
	}
	~bank()
	{
		delete []available;
		delete []safe;
		for(int i = 0;i < n;i++)
		{
			delete []max[i];
			delete []allocation[i];
			delete []need[i];
		}
		delete []max;
		delete []allocation;
		delete []need;
	}
	//银行家算法
	void alloc()
	{
		bool mark = true;    //标志,若无错误则为true,否则为false
		for(int i = 0;i < m;i++)
		{
			if(request[i] > need[index][i])
			{
				cout<<"进程"<<index<<"需要的资源数超过他所宣布的最大值!"<<endl;
				mark = false;
				return;
			}
			if(request[i] > available[i])
			{
				cout<<"尚无足够资源分配给进程"<<index<<endl;
				mark = false;
				return;
			}
		}
		//如果无错误,则将资源分配
		if(mark)
		{
			for(int i = 0;i < m;i++)
			{
				available[i] -= request[i];
				allocation[index][i] += request[i];
				need[index][i] -= request[i];
			}
		}
		//检查安全性
		if(flag)
		{
			if(check())
			{
				cout<<"系统是安全的"<<endl;
				show();
			}
			else
			{
				cout<<"系统是不安全的"<<endl;
				for(int i = 0;i < m;i++)
				{
					available[i] += request[i];
					allocation[index][i] -= request[i];
					need[index][i] += request[i];
				}
			}
		}
		else
			show();
	}
	//安全性算法
	bool check()
	{
		int *work = new int[m];
		bool *finish = new bool[n];
		//初始化work和finish
		int i;
		for(i = 0;i < m;i++)
		{
			work[i] = available[i];
		}
		for(i = 0;i < n;i++)
			finish[i] = false;

		bool mark;
		int now;
		int k = 0;
		while(1)
		{
			now = -1;
			for(i = 0;i < n;i++)
			{
				mark = true;
				//寻找符合finish[i]=false,need[i][j]<=work[j]的进程
				if(finish[i] == false)
				{	
					for(int j = 0;j < m;j++)
					{
						if(need[i][j] > work[j])
						{
							mark = false;
							break;
						}
					}
					//如果找到进程,now保存进程号
					if(mark)
					{
						now = i;
						safe[k++] = i;
						break;
					}
				}
			}
			
			//找到后将work[j]的值增加allocation[now][i],并且将finish[now]置为true
			if(now != -1)
			{
				for(i = 0;i < m;i++)
					work[i] +=allocation[now][i];
				finish[now] = true;
			}
			else   //如果没找到进程则,检查是否所有进程的finish都为true,若都为true,则是安全状态,否则不是
			{
				for(i = 0;i < m;i++)
				{
					if(finish[i] != true)
					{
						delete []work;
						delete []finish;
						return false;
					}
				}
				delete []work;
				delete []finish;
				cout<<"安全序列为:";
				for(i = 0;i < n;i++)
					cout<<safe[i]<<" ";
				cout<<endl;
				return true;
			}
		}


	}
	void show()
	{
		cout.setf(ios::left);
		
		cout<<setw(10)<<"AVAILABLE";
		int i;
		for(i = 0;i < m;i++)
		{
			cout<<"资源"<<setw(6)<<i;
		}
		cout<<endl;
		cout<<setw(10)<<" ";
		for(i = 0;i < m;i++)
		{
				cout<<setw(10)<<available[i];
		}
		cout<<endl<<endl;



		cout<<setw(10)<<"MAX";
		for(i = 0;i < m;i++)
		{
			cout<<"资源"<<setw(6)<<i;
		}
		cout<<endl;
		for(i = 0;i < n;i++)
		{
			cout<<"进程"<<setw(6)<<i;
			for(int j = 0;j < m;j++)
			{
				cout<<setw(10)<<max[i][j];
			}
			cout<<endl;
		}
		cout<<endl;

		cout<<setw(10)<<"ALLOCATION";
		for(i = 0;i < m;i++)
		{
			cout<<" "<<"资源"<<setw(6)<<i;
		}
		cout<<endl;
		for(i = 0;i < n;i++)
		{
			cout<<"进程"<<setw(6)<<i;
			for(int j = 0;j < m;j++)
			{
				cout<<setw(10)<<allocation[i][j];
			}
			cout<<endl;
		}
		cout<<endl;
		cout<<setw(10)<<"NEED";
		for(i = 0;i < m;i++)
		{
			cout<<"资源"<<setw(6)<<i;
		}
		cout<<endl;
		for(i = 0;i < n;i++)
		{
			cout<<"进程"<<setw(6)<<i;
			for(int j = 0;j < m;j++)
			{
				cout<<setw(10)<<need[i][j];
			}
			cout<<endl;
		}
		cout<<endl;
		cout<<"///////////////////////////////////////////////////////////////////////"<<endl;
	}

	void init()
	{
		int i;
		for(i = 0;i < m;i++)
		{
			cout<<"请输入资源向量"<<i<<"的资源总数:";
			cin>>available[i];
		}
		for(i = 0;i < n;i++)
		{
			cout<<"请输入进程"<<i<<"所需的最大资源数分别是:";
			for(int j = 0;j < m;j++)
			{
				cin>>max[i][j];
				need[i][j] = max[i][j];
			}
		}
		
	}
	
	void inputRequest()
	{
		cout<<"请输入有资源请求的进程号:";
		cin>>index;
		cout<<"请输入该进程请求的资源向量:";
		for(int i = 0;i < m;i++)
		{
			cin>>request[i];
		}
	}

	
};




int main()
{
	int n,m;
	char in;
	bool flag;
	cout<<"请输入进程总数:";
	cin>>n;
	cout<<"请输入资源总数:";
	cin>>m;
	cout<<"请输入是否用银行家算法避免死锁(y/n):";
	cin>>in;
	if(in == 'y')
		flag = true;
	else
		flag = false;
	
	bank b(n,m,flag);
	while(1)
	{
		//b.show();
		b.inputRequest();
		b.alloc();
	}
	getchar();
	getchar();
	getchar();
	return 0;
}