resouredivide.cpp

死锁的避免 此源码为操作系统设计与实践的实验作业

#include<iostream>
#include<vector>
#include<iterator>
#include<fstream>


using namespace std;

enum STATE {RUN,WAIT,FINISH};

const int PROMAX = 4;

const int RESMAX = 10;

class PCB
{
public :
	int pid;													//进程的标识号      
	int curreq;			              		//进程当前申请的资源数
	int allreq;			             		  //进程所需资源的总数
	int havreq;												//进程当前拥有的资源数
	STATE state;											//进程当前的状态RUN：运行，WAIT：等待，FINISH：完成
	PCB(int pid,int allreq)
	{
		this->pid=pid;
		this->allreq=allreq;
		havreq=0;
		curreq=0;
		state=RUN;
	}
	friend ostream& operator <<(ostream &out,const PCB& p)
	{
		out<<p.pid<<'\t'<<p.state<<'\t'<<p.allreq<<'\t'<<p.havreq<<endl;
		return out;
	}
};


bool mark(int curres,vector<PCB>& pcb,int k,int n)
{
	int i;
//若当前队列长度为0则分配一定合理
	if (n==0) return true;						
//若待排队列的长度为一则说明已生成了一组排列，对其进行判断
	if (k==1) 
	{
		vector<PCB>::iterator it;				
		for (it=pcb.begin();it!=pcb.end();it++)
		{
			if ((it->allreq - it->havreq )> curres)	return false;
			curres+=it->havreq;
		}
		return true;
	}
//若待排长度不为一，则让待排长度减一，递归调用
	for (i=n-k;i<n;i++)
	{
		PCB sw=pcb[i];
		pcb[i]=pcb[n-k];
		pcb[n-k]=sw;
//若照到一种合适的排列方式则立即返回真值，表明可以分配给该进程所要的资源
		if (mark(curres,pcb,k-1,n)) return true;
		sw=pcb[i];
		pcb[i]=pcb[n-k];
		pcb[n-k]=sw;
	}
//若没有任何一种排列合适，则返回假值，表明不可以分配给该进程所要的资源
	return false;
}

bool bankjudge(int curres,vector<PCB> &vpcb,vector<PCB>::iterator &current)
{
	PCB pro(*current);
	vector<PCB> tpcb;
	vector<PCB>::iterator it;
	current->havreq+=current->curreq;
	curres-=current->curreq;
	
	if (current->havreq==current->allreq) {
		curres+=current->allreq;
		current->state=FINISH;
	}

	for (it=vpcb.begin();it!=vpcb.end();it++)
		if (it->state!=FINISH) tpcb.push_back(PCB(*it));
	
	if (!mark(curres,tpcb,tpcb.size(),tpcb.size()))
	{
		current->havreq=pro.havreq;
		current->state=WAIT;
		tpcb.clear();
		return false;
	}
	tpcb.clear();
	return true;
}

void bank(vector<PCB> &vpcb)
{
	vector<PCB>::iterator it,current;
	cout<<"algorithm bank() starting"<<endl;
	int curresource=RESMAX;
	while(true)
	{
		for (it=vpcb.begin();it!=vpcb.end();it++)
			if (it->state==RUN)
			{
				current=it;
				break;
			}
		if (it==vpcb.end()) 
			for (it=vpcb.begin();it!=vpcb.end();it++)
				if (it->state==WAIT)
				{
					current=it;
					break;
				}

		if (current->curreq==0)
		{
			cout<<"please input the apply for process :"<<current->pid<<'\t';
			cin>>current->curreq;
			while (current->curreq>current->allreq-current->havreq)
			{
				cout<<"beyond the real need!"<<endl;
				cout<<"please input the apply for process :"<<current->pid<<'\t';
				cin>>current->curreq;
			}
			
		}
		if (curresource<current->curreq)
		{
			current->state=WAIT;
			cout<<"Process: "<<current->pid<<" is waiting!"<<endl;
			PCB p=*current;
			vpcb.erase(current);
			vpcb.push_back(p);
			continue;
		}
		
		if (!bankjudge(curresource,vpcb,current)) 
		{
			cout<<endl<<"Process: "<<current->pid<<" is waiting!"<<endl;
			PCB p=*current;
			vpcb.erase(current);
			vpcb.push_back(p);
			continue;
		}

		cout<<endl<<"Process :"<<current->pid<<" get "<<current->curreq<<" resources!"<<endl;

		curresource-=current->curreq;
		current->curreq=0;
		if (current->havreq==current->allreq) 
		{
			current->state=FINISH;
			cout<<"Process : "<<current->pid<<" has finished!"<<endl;
			curresource+=current->allreq;
			current->havreq=0;
		}
		for (it=vpcb.begin();it!=vpcb.end();it++)
			if (it->state!=FINISH) break;
		if (it==vpcb.end()) 
		{
			cout<<"Succeed!"<<endl;
			return ;
		}
		PCB p=*current;
		vpcb.erase(current);
		vpcb.push_back(p);	
	}
		
	
}

bool randomjudge(int curres,vector<PCB> &vpcb,vector<PCB>::iterator &current)
{
	if (curres<current->curreq) return false;
	current->havreq+=current->curreq;
	return true;
}
void random(vector<PCB> &vpcb)
{
	vector<PCB>::iterator it,current;
	cout<<"algorithm random() starting"<<endl;
	int curresource=RESMAX;
	while(true)
	{
		for (it=vpcb.begin();it!=vpcb.end();it++)
			if (it->state==RUN)
			{
				current=it;
				break;
			}
		if (it==vpcb.end()) 
		{				
			cout<<"Locked!"<<endl;
			return ;
		}	
		if (current->curreq==0)
		{
			cout<<"please input the apply for process :"<<current->pid<<'\t';
			cin>>current->curreq;
			while (current->curreq>current->allreq-current->havreq)
			{
				cout<<"beyond the real need!"<<endl;
				cout<<"please input the apply for process :"<<current->pid<<'\t';
				cin>>current->curreq;
			}
			
		}

		if (!randomjudge(curresource,vpcb,current)) 
		{
			cout<<endl<<"Process: "<<current->pid<<" is waiting!"<<endl;
			PCB p=*current;
			vpcb.erase(current);
			vpcb.push_back(p);
			continue;
		}

		cout<<endl<<"Process :"<<current->pid<<" get "<<current->curreq<<" resources!"<<endl;
		
		curresource-=current->curreq;
		current->curreq=0;
		if (current->havreq==current->allreq) 
		{
			current->state=FINISH;
			cout<<"Process : "<<current->pid<<" has finished!"<<endl;
			curresource+=current->allreq;
			current->havreq=0;
		}
		for (it=vpcb.begin();it!=vpcb.end();it++)
			if (it->state!=FINISH) break;
		if (it==vpcb.end()) 
		{
			cout<<"Succeed!"<<endl;
			return ;
		}
		
		for (it=vpcb.begin();it!=vpcb.end();it++)
			if (it->state!=WAIT&&it->state!=FINISH) break;
		if (it==vpcb.end()||curresource==0)
		{
			cout<<"LOCKED!"<<endl;
			return ;
		}
		PCB p=*current;
		vpcb.erase(current);
		vpcb.push_back(p);	
	}
}
int main()
{
	vector<PCB> vpcb;
	char opt;
	cout<<"please input the algorithm you select."<<endl;
	cout<<"Random(R) or Bank(B)?"; 
	cin>>opt;
	cout<<"Please input the max number for requested resource"<<endl;
	for (int i=0;i<PROMAX;i++)
	{
		int qty;
		do 
		{
		cout<<i<<'\t';
		cin>>qty;
		cout<<endl;
		} while (qty<1 || qty>RESMAX);
		vpcb.push_back(PCB(i,qty));
	}
	if (opt=='R' || opt=='r') random(vpcb);	
	if (opt=='B' || opt=='b') bank(vpcb);
	return 0;
}