#include <iostream.h>
#include <string.h>
#include <fstream.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

const int TIMESLICE = 1;//時間片
const int FINISH=0;//完成狀態(tài)
const int RUNNING=1;//運(yùn)行狀態(tài)
const int READY=2;//就緒狀態(tài)
const int IO=3;//io狀態(tài)
const int WAIT=4;//等待IO

typedef struct {
	long pid;
	char pname[10];
	int pstate;
	int pneedtime;
	int piostarttime;
	int pioneedtime;
	int ptime;
	int priority;
}pcbs;//pcb結(jié)構(gòu)

class pcbnode;
//隊(duì)列結(jié)點(diǎn)
class pcbnode
{
public:
	pcbs *pcb;
	pcbnode *link;
	pcbnode();
	~pcbnode();
	int run();//運(yùn)行操作
	int runend();//運(yùn)行結(jié)束？
	void runio();//IO操作
	int ioend();//io結(jié)束？
	int insertnode(pcbnode *p,pcbnode *q);//在q后插入結(jié)點(diǎn)p
	int deletenode(pcbnode *p,pcbnode *q);//刪除p結(jié)點(diǎn)，q為p的前驅(qū)
	int addnode(pcbnode *p);//增加結(jié)點(diǎn)
	int pcbnode::isio();//是否開始IO
};
pcbnode::pcbnode()
{
	pcb=0;
	link=0;
}
pcbnode::~pcbnode()
{
	if (link)
		delete link;
	if (pcb)
		pcb->pstate=FINISH;
}
int pcbnode::run()
{
	pcb->pstate = RUNNING;
	++(pcb->ptime);
	pcb->priority --;//優(yōu)先級降低
	return 0;
}
int pcbnode::runend()
{
	return (pcb->pneedtime <= pcb->ptime);
}
int pcbnode::isio()
{
	return (pcb->piostarttime == pcb->ptime && pcb->pioneedtime>0);
}
int pcbnode::ioend()
{
	return ((pcb->pioneedtime) <= 0);
}
void pcbnode::runio()
{
	pcb->pstate = IO;
	--(pcb->pioneedtime);
}
int pcbnode::addnode(pcbnode *p)
{
	pcbnode *q;
	q = this;
	p->pcb->pstate = READY;
	while(q->link)
	{
		q=q->link;
	}
	q->link=p;
	return 0;
}
int pcbnode::insertnode(pcbnode *p,pcbnode *q)
{
	p->link = q->link;
	q->link = p;
	return 0;
}
int pcbnode::deletenode(pcbnode *p,pcbnode *q)
{
	q->link = p->link;
	p->link = 0;
	return 0;
}
int randInt( int seed)
//隨即函數(shù)：產(chǎn)生不大于seed的正整數(shù)
{
	int r;
	r=rand();
	while ( r>seed || r<0 )
		r=rand();
	return r;
}
void newpcb1(pcbs *pcb, int order)//隨機(jī)生成進(jìn)程
{
	char buf[10];
	pcb->pid = order;
	strcpy(pcb->pname,"proc");
	itoa(order,buf,10);
	strcat(pcb->pname,buf);
	pcb->pneedtime = randInt(10);
	pcb->piostarttime = randInt(pcb->pneedtime);
	pcb->pioneedtime = randInt(10);
	pcb->ptime = 0;
	pcb->priority = randInt(10);
}
void newpcb2(pcbs *pcb,int porder)//手動生成進(jìn)程
{
	char buf[10];
	cout<<"Input the pid:          ";
	cin>>porder;
	pcb->pid = porder;
	strcpy(pcb->pname,"proc");
	itoa(porder,buf,10);
	strcat(pcb->pname,buf);
	cout<<"Input the pneedtime:    ";
	cin>>pcb->pneedtime;
	cout<<"Input the pioneedtime:  ";
	cin>>pcb->pioneedtime;
	cout<<"Input the priority:     ";
	cin>>pcb->priority;
	pcb->piostarttime = pcb->pioneedtime;
	pcb->ptime = 0;
}
void pprint(pcbs *pcb, int count)
{
//打印進(jìn)程狀態(tài)

	ofstream ofs("result.txt", ios::out|ios::app);
	cout<<"pcb:id name stat need iostart ioneed runtime pri"<<endl;
	ofs<<"pcb:id name stat need iostart ioneed runtime pri"<<endl;
	for (int i=0;i<count;i++)
	{
		cout<<pcb->pid<<','<< pcb->pname<<',';
		ofs<<pcb->pid<<','<< pcb->pname<<',';
		switch(pcb->pstate)
		{
case 3://IO
	cout<<"IO";
	ofs<<"IO";
	break;
case 1://RUNNING
	cout<<"RUNNING ";
	ofs<<"RUNNING ";
	break;
case 2://READY
	cout<<"READY";
	ofs<<"READY";
	break;
case 0://FINISH
	cout<<"FINISH";
	ofs<<"FINISH";
	break;
case 4://WAIT
	cout<<"WAIT";
	ofs<<"WAIT";
	break;
		}
		cout<<'"'<<pcb->pneedtime;
		ofs<<'"'<<pcb->pneedtime;
		cout<<'"'<<pcb->piostarttime<<'"'<<pcb->pioneedtime<<'"'<<pcb->ptime;
		ofs<<'"'<<pcb->piostarttime<<'"'<<pcb->pioneedtime<<'"'<<pcb->ptime;
		cout<<'"'<<pcb->priority;
		ofs<<'"'<<pcb->priority;
		cout<< endl;
		ofs<< endl;
		*pcb++;
	}
	ofs<<"---------------------------------------------"<<endl;
	cout<<"---------------------------------------------"<<endl;
}


void generalpriority(pcbs * pcb, int pcbsnum)
//普通的優(yōu)先調(diào)度
/*
* 從就緒隊(duì)列中取出最優(yōu)先的進(jìn)程送到運(yùn)行隊(duì)列
* 如果運(yùn)行結(jié)束或要執(zhí)行IO再重新調(diào)度
*/
{
	pcbnode running,ready,blocked;
	pcbnode *p,*f,*front;
	pcbnode *q;
/*將進(jìn)程表中的進(jìn)程加到就緒隊(duì)列中*/
	for ( int i=0;i<pcbsnum;i++)
	{
		p = new pcbnode;
		p->pcb = pcb+i;
		ready.addnode(p);
	}
	while(ready.link || running.link || blocked.link)
	{//判斷將運(yùn)行隊(duì)列中的進(jìn)程是否要io或結(jié)束
		if (running.link)
		{
			if (running.link->isio())
			{//需要IO?
				blocked.addnode(running.link);
				running.link->pcb->pstate = WAIT;
				running.link = 0;
			}
			else if (running.link->runend())
			{//運(yùn)行結(jié)束?
				p = running.link;
				running.link = 0;
				delete p;
			}
		}
		if (!running.link)
		{
			//當(dāng)運(yùn)行隊(duì)列為空
			//尋找最大的一個優(yōu)先級
			p = ready.link;
			q = p;
			f = &ready;
			front = f;
			if (p)
			{
				int maxpri = p->pcb->priority;
				while(p)
				{
					if (p->pcb->priority > maxpri)
					{
						maxpri = p->pcb->priority;
						front = f;
						q = p;
					}
					f = p;
					p = p->link;
				}
			}
			p = running.link;
			if (q)
			{
				running.addnode(q);
				ready.deletenode(q, front);
				q->pcb->pstate=RUNNING;
			}
		}
/*
* 將處理完IO的進(jìn)程送到就緒隊(duì)列
*/
		p = blocked.link;
		q = &blocked;
		if (p) 
		{
			int r;
			r = p->ioend();
			if (r) 
			{
				blocked.deletenode(p, q);
				ready.addnode(p);
				p=q->link;
			}
		}

/*
* 運(yùn)行進(jìn)程
*/
		p = running.link;
		q = &running;
		if (p)
		{
			int r;
			if (!(p->isio()))
				//is IO start?
				r=p->run();//RUN
		}
/*
* 進(jìn)行IO
*/
		p = blocked.link;
		q = &blocked;
		if (p)
			p->runio();
		//print proc state
		pprint(pcb, pcbsnum);
	}
}
void main()
{
	int i,pcbsnum;
	pcbs *pcblist;//進(jìn)程表
	remove("result.txt");
	cout<<"Frist,bulit the pcblist"<<endl;
	cout<<"Input the pcbsnum:   ";
	cin>>pcbsnum;
	pcblist = new pcbs[pcbsnum];//為進(jìn)程表分配空間
	cout<<"1.自動生成進(jìn)程 2.手動生成進(jìn)程:        ";
	cin>>i;
	if(i==1)
	for(int i = 0; i < pcbsnum; i++)
		newpcb1(pcblist+i, i);
	else for(int i = 0; i < pcbsnum; i++)
		newpcb2(pcblist+i, i);
	cout<<"Second,print the pcblist:"<<endl;
	pprint(pcblist, pcbsnum);
	cout<<"Third,print the pcb dispatch:"<<endl;
	getchar();
	generalpriority(pcblist,pcbsnum);
	
	delete pcblist;//釋放進(jìn)程空間
}