hbj.cpp

题目：银行家算法 具体要求：屏幕提示：输入申请资源的进程和各资源数目

// bank_al.cpp : Defines the entry point for the console application.
//利用银行家算法预防死锁

#include "stdafx.h"
#include"iostream.h"
#include"fstream.h"、


//类的定义
///////////////////////////////////////////////////////////////////////////////////////
class node{
public:
	int name;  //进程名
	int *allocation;  //已分配资源
	int *need;  //总共所需资源
	int size;
	node *next;
	node(int n=3)
	{allocation=new int[n];
	need=new int[n];
	size=n;
	next=NULL;}
	~node(){
		delete [] allocation;
		delete [] need;
	}
	bool isenough(int *rest)
	{
	for(int i=0;i<size;i++)
		if(allocation[i]+rest[i]<need[i])
			return false;
	return true;
}

}
//函数说明


bool node::isenough(int *rest)
//////////////////////////////////////////////////////////////////////
class bankal{  //利用循环队列
private:
	node *fence; //指向队列中某一进程
	int *res_spare; // or *res_sum 所剩资源
	int length;  //进程总数
	int size;  //资源种数
public:
	bankal(int n=3);
	~bankal();
	void initialize();
	bool check(int nm,int *imp);
	void print();
};

//函数说明
bankal::bankal(int n){
	size=n;
	length=0;
	res_spare=new int[n];
	fence=NULL;
}

bankal::~bankal(){
	node *temp=fence;
	for(int i=0;i<length;i++){
		temp=fence;
		fence=fence->next;
		delete temp;
	}
	delete [] res_spare;
}

void bankal::initialize(){
	int i,nm=0;
	node *temp;
	ifstream myinf("data.txt",ios::in | ios::nocreate);
	if(myinf.fail()){
		cerr<<"error opening file wenfa\n";
		return;
	}
	//输入还可用资源
	for(i=0;i<size;i++)
		myinf>>res_spare[i];
	//输入进程，及其总共所需资源数和已分配资源数
	length=0;
	while(!myinf.eof()) {
		temp=new node(size);
		for(i=0;i<size;i++)
			myinf>>temp->need[i];
		for(i=0;i<size;i++)
			myinf>>temp->allocation[i];
		temp->name=nm;
		nm++;
		if(length==0){
			fence=temp;
			fence->next=fence;
		}
		else{
			temp->next=fence->next;
			fence->next=temp;
			fence=fence->next;
		}
		length++;
	}
}

bool bankal::check(int nm,int *imp){
	int i,j,endtag;
	int *restcopy,lcopy=length;
	node *head=NULL,*rear=NULL;
	node *tp=NULL,*pre=NULL;
	//步骤(2,3)
	restcopy=new int[size];
	for(j=0;j<size;j++){
		restcopy[j]=res_spare[j];
		if(restcopy[j]>=imp[j])
			restcopy[j]=restcopy[j]-imp[j];
		else{
			delete [] restcopy;
			cout<<"资源不足。"<<endl;
			return false;
		}
	}
	//步骤(1)
	while(fence->name!=nm && lcopy>0){
		fence=fence->next;
		lcopy--;
	}
	if(lcopy==0){ //即当未找到进程nm时
		cout<<"输入有误，不存在这个进程。"<<endl;
		delete [] restcopy;
		return false;
	}
	tp=fence;
	for(i=0,j=0;i<size;i++){
		if(tp->need[i]>=tp->allocation[i]+imp[i])
			j++;
	}
	if(j!=size){
		cout<<"它所请求的资源大于它总共所需的资源数。"<<endl;
		delete [] restcopy;
		return false;
	}
	//尝试分配给它,步骤(3)
	for(i=0;i<size;i++)
		tp->allocation[i]=tp->allocation[i]+imp[i];
    //步骤(4)
	lcopy=length;
	pre=fence;
	fence=fence->next;
	while(lcopy){
		endtag=1;
		for(i=0;i<lcopy;i++){
			if(fence->isenough(restcopy)){   //==true
				if(head==NULL)
					head=rear=fence;
				else
					rear=rear->next=fence;
				for(j=0;j<size;j++)
					restcopy[j]=restcopy[j]+fence->allocation[j];
				lcopy--;
				endtag=0;
				pre->next=fence->next;
				fence->next=NULL;
				fence=pre->next;
			}
			else{
				pre=fence;
				fence=fence->next;
			}
		}
		if(endtag==1){
			cout<<"分配后不可能再处于安全状态了。"<<endl;
			//撤消原分配
			if(head){  //head不为NULL时
				rear->next=fence->next;
				fence->next=head;
			}
	        for(i=0;i<size;i++)
		        tp->allocation[i]=tp->allocation[i]-imp[i];
			delete [] restcopy;
			return false;
		}
	}
	//能够分配请求资源后的处理
	delete [] restcopy;
	for(j=0;j<size;j++){
        res_spare[j]=res_spare[j]-imp[j];
	}
	//重新形成循环队列
	//也重新置fence的值，以便后面输出安全序列
	rear->next=head;
	fence=head;
	return true;
}


void bankal::print(){
	int i,j;
    //输出所剩资源数
	cout<<"spare resource\n( ";
	for(j=0;j<size;j++)
		cout<<res_spare[j]<<" ";
	cout<<")"<<endl;
    //输入进程，及其总共所需资源数和已分配资源数
	cout<<"name\tmax\t\tneed_resource\tget_resource"<<endl;
	for(i=0;i<length;i++){
		cout<<fence->name<<"\t( ";
		for(j=0;j<size;j++)
			cout<<fence->need[j]<<" ";
		cout<<")\t( ";
		for(j=0;j<size;j++)
			cout<<fence->need[j]-fence->allocation[j]<<" ";
		cout<<")\t( ";
		for(j=0;j<size;j++)
			cout<<fence->allocation[j]<<" ";
		cout<<")\t"<<endl;
    	fence=fence->next;
	}

}



///////////////////////主函数////////////////////////////////////
int main(int argc, char* argv[])
{
	int i,sum=3;//最大需求
	int *temp,nm;
	temp=new int[sum];
	bankal runba;
	runba.initialize();
	runba.print();
	//输入请求资源情况
	cout<<"输入请求资源情况（输入负数表示结束）。"<<endl;
	while(1){
		cout<<"输入进程名。"<<endl;
		cin>>nm;
		if(nm<0) break;  //结束
		cout<<"依次输入所请求的资源数"<<endl;
		for(i=0;i<sum;i++)
			cin>>temp[i];
		if(runba.check(nm,temp)){
			//可以响应资源的请求
			cout<<"可以响应资源的请求，其安全队列如下："<<endl;
			runba.print();
		}
		else{
			cout<<"不可以响应资源的请求。"<<endl; //不可以响应资源的请求
		}
	}
	return 0;
}