银行家算法.cpp

包含操作系统原理书籍中所提到的很多方法的实现函数

#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
const int TASK_RUNNING = 0;
const int TASK_SUCCEED = 1;
const int TASK_WAITTING = 2;
const int RLength = 10;
int Rcs_left = RLength;
ofstream ff("result.txt");
class pcb	
{
public:
	int p_pid;
	int p_stat;
	int p_apply;
	int p_occupy;
	bool p_issuc;
	int p_require;
	pcb(int id,int require)	
	{
		p_pid = id;
		p_require = require;
		p_stat = TASK_RUNNING;
		p_occupy = 0;
		p_issuc = false;
		p_apply = 0;
	}
	friend ostream & operator <<(ostream &cout,const pcb & p)	
	{
		cout<<p.p_pid<<'\t'<<p.p_stat<<'\t'<<p.p_require<<'\t'<<p.p_occupy
			<<endl;

		return cout;
	}
};

void rand(vector<int> &resource,vector<pcb> &pgrp);
void banker(vector<int> &resource,vector<pcb> &pgrp);
int  main()	
{
	vector<int> resource;
	vector<pcb> pgrp;
	
	vector<int>::iterator r;
	vector<pcb>::iterator p;
	
	cout<<"ENTER THE MAX NUMBER FOR THE REQUESTED RESOURCE:"<<endl;
	cout<<"ID\tREQUESTED"<<endl;
	ff<<"ENTER THE MAX NUMBER FOR THE REQUESTED RESOURCE:"<<endl;
	ff<<"ID\tREQUESTED"<<endl;

	int id,qty;
	for(int i(1);i<=4;i++)	
	{
		do	
		{
			cout<<i<<'\t';
			ff<<i<<'\t';
			cin>>qty;
			ff<<qty<<endl;
		}	while(qty>Rcs_left || qty<1);
		pgrp.insert(pgrp.begin(),pcb(i,qty));
	}
	
	//输入各进程申请的资源总量,以及初始化各个进程;
	
	cout<<"ALOGRITHM"<<endl 
		<<"Random(R)"<<'\t'
		<<"Banker(B)"<<endl
		<<"ANY OTHER KEY TO QUIT"<<endl;
	ff<<"ALOGRITHM"<<endl 
		<<"Random(R)"<<'\t'
		<<"Banker(B)"<<endl
		<<"ANY OTHER KEY TO QUIT"<<endl;
	char choice;
	cin>>choice;
	ff<<choice<<endl;
	if(choice == 'R'|| choice == 'r')
		rand(resource,pgrp);
	else if (choice == 'B' || choice == 'b')
		banker(resource,pgrp);
	else	
		return(0);
	return (1);
}

void rand(vector<int> &resource,vector<pcb> &pgrp)	
{
	vector<pcb>::iterator p,q;
	vector<pcb>::iterator current;
	vector<int>::iterator r;
	int temp;
	cout<<"NOW---------BANKER ALOGRITHM"<<endl;
	ff<<"NOW---------BANKER ALOGRITHM"<<endl;
	for(; ;)	
	{
		//select a TASK_RUNNIG process,maybe different from the former one;
		for(p=pgrp.begin();p!=pgrp.end();p++)	
		{
			if(p->p_stat == TASK_RUNNING)	
			{
				current = p;
				break;
			}
		}
		if(current->p_apply == 0)	
		{
			cout<<"ENTER THE APPLY FOR THE PROCESS\n"<<current->p_pid<<'\t';
			ff<<"ENTER THE APPLY FOR THE PROCESS\n"<<current->p_pid<<'\t';
			cin>>temp;
			ff<<temp<<endl;
			while(temp>p->p_require-p->p_occupy)	
			{
				cout<<"beyond the real need!"<<endl;
				cout<<"ENTER THE APPLY FOR THE PROCESS\n"<<current->p_pid<<'\t';
				ff<<"beyond the real need!"<<endl;
				ff<<"ENTER THE APPLY FOR THE PROCESS\n"<<current->p_pid<<'\t';
				cin>>temp;
				ff<<temp<<endl;
			}
			p->p_apply = temp;
		}
		
		//input the apply for the current process;
		if(current->p_apply	> Rcs_left)	
		{   //has problem
			//apply too much,please wait....
			current->p_stat = TASK_WAITTING;
			cout<<endl<<current->p_pid<<"is waitting\n";
			ff<<endl<<current->p_pid<<"is waitting\n";
			for(p=pgrp.begin();p!=pgrp.end();p++)	
			{	
				if(p->p_stat == TASK_RUNNING)	break;
			}
			if(p == pgrp.end())	
			{
				cout<<"LOCKED!!!"<<endl;
				ff<<"LOCKED!!!"<<endl;
				exit(1);
			}
			continue;
		}
		//满足该进程当前的申请
		resource.insert(resource.begin(),current->p_apply,current->p_pid);
		cout<<temp<<"\tresources are accepted for "<<p->p_pid<<endl;
		cout<<endl;
		ff<<temp<<"\tresources are accepted for "<<p->p_pid<<endl;
		ff<<endl;
		Rcs_left-=current->p_apply;
		current->p_occupy += current->p_apply;
		current->p_apply = 0;
		//看该进程是否已满足
		if(current->p_occupy < current->p_require)	
		{
			pcb proc(*current);
			pgrp.erase(current);
			pgrp.insert(pgrp.end(),proc);
			//current->p_apply = 0;
			//delete current and insert into the end
			continue;//go on and should select another process 
		}
		//succeed
		cout<<endl<<"process\t"<<p->p_pid<<"\thas succeed!!"<<endl;
		ff<<endl<<"process\t"<<p->p_pid<<"\thas succeed!!"<<endl;
		Rcs_left+=current->p_occupy;
		resource.clear();
		current->p_stat = TASK_SUCCEED;
		//current->p_apply = 0;
		for(p=pgrp.begin();p!=pgrp.end();p++)	
		{	
			if(p->p_stat == TASK_WAITTING)	
				break;
		}
		if(p==pgrp.end())	
		{
			for(q=pgrp.begin();q!=pgrp.end();q++)	
			{
				if(q->p_stat == TASK_RUNNING)
					break;
			}
			if(q == pgrp.end())	
			{
				cout<<"SUCCEED!!"<<endl;
				ff<<"SUCCEED!!"<<endl;
				exit(0);
			}
			else continue;
			//There is a process in the queue;
		}
		for(p=pgrp.begin();p!=pgrp.end();p++)	
		{	
			if(p->p_stat == TASK_WAITTING&&Rcs_left >= p->p_apply)	
				break;
		}
		if(p!=pgrp.end())	
		{
			p->p_stat = TASK_RUNNING;
			pcb proc(*p);
			pgrp.erase(p);
			pgrp.insert(pgrp.end(),proc);
			continue;
		}
		else	
		{
			cout<<"LOCKED!!!"<<endl;
			ff<<"LOCKED!!!"<<endl;
			exit(1);
		}
	}
}

void banker(vector<int> &resource,vector<pcb> &pgrp)	
{
	vector<pcb>::iterator p;
	vector<int>::iterator r;
	vector<pcb>::iterator current,q;
	pcb proc(0,0);
	int length;
	cout<<"NOW---------BANKER ALOGRITHM"<<endl;
	ff<<"NOW---------BANKER ALOGRITHM"<<endl;
	for(; ;)	
	{
		for(p=pgrp.begin();p!=pgrp.end();p++)	
		{
			if(p->p_stat == TASK_RUNNING)	
			{
				current = p;
				break;
			}
		}
		if(current->p_apply == 0)	
		{
			cout<<"ENTER THE APPLY FOR THE PROCESS \n "<<current->p_pid<<'\t';
			ff<<"ENTER THE APPLY FOR THE PROCESS \n "<<current->p_pid<<'\t';
			cin>>current->p_apply;
			ff<<current->p_apply<<endl;
			while(current->p_apply >current->p_require - current->p_occupy)	
			{
				cout<<cout<<"ENTER THE APPLY FOR THE PROCESS \n "<<current->p_pid<<'\t';
				ff<<cout<<"ENTER THE APPLY FOR THE PROCESS \n "<<current->p_pid<<'\t';
				cin>>current->p_apply;
				ff<<current->p_apply<<endl;
			}
		}
		if(current->p_apply > Rcs_left)	
		{
			current->p_stat = TASK_WAITTING;
			proc = *current;
			pgrp.erase(current);
			pgrp.insert(pgrp.end(),proc);
			cout<<endl<<p->p_pid<<" is waitting!"<<endl;
			ff<<endl<<p->p_pid<<" is waitting!"<<endl;
			continue;
		}
		//假定对申请资源的进程分配资源
		pcb backup(*current);
		//backup
		length = Rcs_left;
		current->p_occupy+=current->p_apply;
		length-=current->p_apply;
		if(current->p_occupy == current->p_require)	
			length += current->p_require;
		current->p_issuc = true;
		
		for(p=pgrp.begin();p!=pgrp.end();p++)	
		{
			if(p->p_stat == TASK_SUCCEED) continue;
			if(p == current&& p->p_issuc == true)
				continue;
			if((p->p_require - p->p_occupy)>length)		continue;
			else	
			{
				p->p_issuc = true;
				length+=p->p_occupy;
				continue;
			}
		}
		//检查是否还有标志位未设置的进程
		for(p=pgrp.begin();p!=pgrp.end();p++)	
		{
			if (p->p_issuc == false&&p->p_stat != TASK_SUCCEED)	break;
		}
		if( p != pgrp.end())	
		{
			current->p_occupy=backup.p_occupy;
			current->p_stat = TASK_WAITTING;
			cout<<endl<<current->p_pid<<" is waitting."<<endl;
			ff<<endl<<current->p_pid<<" is waitting."<<endl;
			proc = *current;
			pgrp.erase(current);
			pgrp.insert(pgrp.end(),proc);
			for(p=pgrp.begin();p!=pgrp.end();p++)
				p->p_issuc = false;
			continue;
		}
		//分配安全,可对进程进行实际的分配
		resource.insert(resource.end(),current->p_apply,current->p_pid);
		Rcs_left -= current->p_apply;
		cout<<endl<<current->p_pid<<" get "<<current->p_apply<<" resource(s)!"<<endl;
		ff<<endl<<current->p_pid<<" get "<<current->p_apply<<" resource(s)!"<<endl;
		current->p_apply = 0;
		if(current->p_occupy < current->p_require)	
		{
			proc = *current;
			pgrp.erase(current);
			pgrp.insert(pgrp.end(),proc);
			for(p=pgrp.begin();p!=pgrp.end();p++)
				p->p_issuc = false;
			continue;
		}
		current->p_stat = TASK_SUCCEED;
		current->p_occupy = 0;
		cout<<endl<<current->p_pid<<" has finished!!!"<<endl;
		ff<<endl<<current->p_pid<<" has finished!!!"<<endl;
		//归还全部系统资源
		resource.clear();
		Rcs_left+=current->p_require;
		for(p=pgrp.begin();p!=pgrp.end();p++)	
		{
			if(p->p_stat == TASK_WAITTING)		
				break;
		}
		if(p == pgrp.end())	
		{
			for(q=pgrp.begin();q!=pgrp.end();q++)	
			{
				if(q->p_stat == TASK_RUNNING)
					break;
			}
			if(q == pgrp.end())	
			{
				cout<<endl<<"SUCCEED!!"<<endl;
				ff<<endl<<"SUCCEED!!"<<endl;
				exit(0);
			}
			else 
				continue;
		}
		proc = *p;
		pgrp.erase(p);
		pgrp.insert(pgrp.end(),proc);
		p->p_stat = TASK_RUNNING;
		continue;
	}
}
/*  程序演示结果如下:
ENTER THE MAX NUMBER FOR THE REQUESTED RESOURCE:
ID	REQUESTED
1	3
2	5
3	7
4	9
ALOGRITHM
Random(R)	Banker(B)
ANY OTHER KEY TO QUIT
r
NOW---------BANKER ALOGRITHM
ENTER THE APPLY FOR THE PROCESS
4	2
2	resources are accepted for 4

ENTER THE APPLY FOR THE PROCESS
3	3
3	resources are accepted for 3

ENTER THE APPLY FOR THE PROCESS
2	5
5	resources are accepted for 2


process	2	has succeed!!
ENTER THE APPLY FOR THE PROCESS
1	2
2	resources are accepted for 1

ENTER THE APPLY FOR THE PROCESS
4	4

4is waitting
ENTER THE APPLY FOR THE PROCESS
3	2
2	resources are accepted for 3

ENTER THE APPLY FOR THE PROCESS
1	2
beyond the real need!
ENTER THE APPLY FOR THE PROCESS
1	1
1	resources are accepted for 1


process	1	has succeed!!
LOCKED!!!
  */