// bank_al.cpp : Defines the entry point for the console application.
//利用銀行家算法預(yù)防死鎖

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


//類的定義
///////////////////////////////////////////////////////////////////////////////////////
class node{
public:
	int name;  //進(jìn)程名
	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;
}

}
//函數(shù)說(shuō)明


bool node::isenough(int *rest)
//////////////////////////////////////////////////////////////////////
class bankal{  //利用循環(huán)隊(duì)列
private:
	node *fence; //指向隊(duì)列中某一進(jìn)程
	int *res_spare; // or *res_sum 所剩資源
	int length;  //進(jìn)程總數(shù)
	int size;  //資源種數(shù)
public:
	bankal(int n=3);
	~bankal();
	void initialize();
	bool check(int nm,int *imp);
	void print();
};

//函數(shù)說(shuō)明
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];
	//輸入進(jìn)程，及其總共所需資源數(shù)和已分配資源數(shù)
	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){ //即當(dāng)未找到進(jìn)程nm時(shí)
		cout<<"輸入有誤，不存在這個(gè)進(jìn)程。"<<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<<"它所請(qǐng)求的資源大于它總共所需的資源數(shù)。"<<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<<"分配后不可能再處于安全狀態(tài)了。"<<endl;
			//撤消原分配
			if(head){  //head不為NULL時(shí)
				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;
		}
	}
	//能夠分配請(qǐng)求資源后的處理
	delete [] restcopy;
	for(j=0;j<size;j++){
        res_spare[j]=res_spare[j]-imp[j];
	}
	//重新形成循環(huán)隊(duì)列
	//也重新置fence的值，以便后面輸出安全序列
	rear->next=head;
	fence=head;
	return true;
}


void bankal::print(){
	int i,j;
    //輸出所剩資源數(shù)
	cout<<"spare resource\n( ";
	for(j=0;j<size;j++)
		cout<<res_spare[j]<<" ";
	cout<<")"<<endl;
    //輸入進(jìn)程，及其總共所需資源數(shù)和已分配資源數(shù)
	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;
	}

}



///////////////////////主函數(shù)////////////////////////////////////
int main(int argc, char* argv[])
{
	int i,sum=3;//最大需求
	int *temp,nm;
	temp=new int[sum];
	bankal runba;
	runba.initialize();
	runba.print();
	//輸入請(qǐng)求資源情況
	cout<<"輸入請(qǐng)求資源情況（輸入負(fù)數(shù)表示結(jié)束）。"<<endl;
	while(1){
		cout<<"輸入進(jìn)程名。"<<endl;
		cin>>nm;
		if(nm<0) break;  //結(jié)束
		cout<<"依次輸入所請(qǐng)求的資源數(shù)"<<endl;
		for(i=0;i<sum;i++)
			cin>>temp[i];
		if(runba.check(nm,temp)){
			//可以響應(yīng)資源的請(qǐng)求
			cout<<"可以響應(yīng)資源的請(qǐng)求，其安全隊(duì)列如下："<<endl;
			runba.print();
		}
		else{
			cout<<"不可以響應(yīng)資源的請(qǐng)求。"<<endl; //不可以響應(yīng)資源的請(qǐng)求
		}
	}
	return 0;
}