#include <string>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <conio.h>
#define TIMES 40
using namespace std;

class PCB{
	public:
		int id;
		int status;
		int needtime;
		int exectime;
		int waittime;
		int pri;
		PCB * next;

		PCB(int id,int time,int pri){
			this->id=id;
			status=0;
			needtime=time;
			exectime=0;
			waittime=0;
			this->pri=pri;
			next=NULL;
		}
};

PCB * head;
PCB * last;
PCB * exec;

PCB * NewPCB[TIMES];

int Random(int low,int high){
	return(low+rand()%(high-low+1));
}

void RandomEvent(){
	int id=1;
	for (int i=0;i<TIMES;i++){
		if (Random(0,10)>=8){
			NewPCB[i]=new PCB(id++,Random(1,5),Random(0,5));
		}else{
			NewPCB[i]=NULL;
		}
	}
}


void FCFS(){
	head=NULL;
	last=NULL;
	exec=NULL;
	PCB * pcb;
	cout<<"先來先服務調度算法:\n";
	for (int time=0;time<TIMES;time++){
		pcb=head;
		while(pcb){
			pcb->waittime++;
			pcb=pcb->next;
		}
		if (exec){
			exec->exectime++;
			if (exec->exectime>=exec->needtime){
				cout<<exec->id<<"結束，周轉時間："<<exec->exectime+exec->waittime<<"，帶權周轉時間："<<(exec->exectime+exec->waittime)/exec->needtime<<endl;
				exec=NULL;
			}
		}
		if (NewPCB[time]){
			if (!head){
				head=new PCB(*NewPCB[time]);
				last=head;
			}else{
				last->next=new PCB(*NewPCB[time]);
				last=last->next;
			}
			cout<<last->id<<"創建，需要時間："<<last->needtime<<"，優先級："<<last->pri<<endl;
		}
		if (!exec){
			if (head){
				exec=head;
				head=head->next;
				exec->next=NULL;
				cout<<exec->id<<"開始執行。"<<endl;
			}
		}
	}
}

void SPF(){
	head=NULL;
	last=NULL;
	exec=NULL;
	PCB * pcb;
	cout<<"\n短進程優先調度算法:\n";
	for (int time=0;time<TIMES;time++){
		pcb=head;
		while(pcb){
			pcb->waittime++;
			pcb=pcb->next;
		}
		if (exec){
			exec->exectime++;
			if (exec->exectime>=exec->needtime){
				cout<<exec->id<<"結束，周轉時間："<<exec->exectime+exec->waittime<<"，帶權周轉時間："<<(exec->exectime+exec->waittime)/exec->needtime<<endl;
				exec=NULL;
			}
		}
		if (NewPCB[time]){
			if (!head){
				head=new PCB(*NewPCB[time]);
				last=head;
			}else{
				last=NULL;
				pcb=head;
				while(pcb){
					if(NewPCB[time]->needtime<pcb->needtime){
						pcb=new PCB(*NewPCB[time]);
						if(!last){
							pcb->next=head;
							head=pcb;
						}else{
							pcb->next=last->next;
							last->next=pcb;
						}
						last=pcb;
						break;
					}
					last=pcb;
					pcb=pcb->next;
				}
				if (!pcb){
					last->next=new PCB(*NewPCB[time]);
					last=last->next;
				}
			}
			cout<<last->id<<"創建，需要時間："<<last->needtime<<"，優先級："<<last->pri<<endl;
		}
		if (!exec){
			if (head){
				exec=head;
				head=head->next;
				exec->next=NULL;
				cout<<exec->id<<"開始執行。"<<endl;
			}
		}
	}
}

void FPF(){
	head=NULL;
	last=NULL;
	exec=NULL;
	PCB * pcb;
	cout<<"\n高優先權優先調度算法:\n";
	for (int time=0;time<TIMES;time++){
		pcb=head;
		while(pcb){
			pcb->waittime++;
			pcb=pcb->next;
		}
		if (exec){
			exec->exectime++;			
			if (exec->exectime>=exec->needtime){
				cout<<exec->id<<"結束，周轉時間："<<exec->exectime+exec->waittime<<"，帶權周轉時間："<<(exec->exectime+exec->waittime)/exec->needtime<<endl;
				exec=NULL;
			}
		}
		if (NewPCB[time]){
			if (!head){
				head=new PCB(*NewPCB[time]);
				last=head;
			}else{
				last=NULL;
				pcb=head;
				while(pcb){
					if(NewPCB[time]->pri>pcb->pri){
						pcb=new PCB(*NewPCB[time]);
						if(!last){
							pcb->next=head;
							head=pcb;
						}else{
							pcb->next=last->next;
							last->next=pcb;
						}
						last=pcb;
						break;
					}
					last=pcb;
					pcb=pcb->next;
				}
				if (!pcb){
					last->next=new PCB(*NewPCB[time]);
					last=last->next;
				}
			}
			cout<<last->id<<"創建，需要時間："<<last->needtime<<"，優先級："<<last->pri<<endl;
		}
		if (!exec){
			if (head){
				exec=head;
				head=head->next;
				exec->next=NULL;
				cout<<exec->id<<"開始執行。"<<endl;
			}
		}
	}
}

void SortByResponseRate(){
	if (!head){
		return;
	}
	PCB * last;
	PCB * pcb;
	PCB * prevh;
	PCB * highest;
	
	last=head;
	highest=head;
	pcb=head->next;
	while(pcb){
		if (pcb->waittime/pcb->needtime>highest->waittime/highest->needtime){
			prevh=last;
			highest=pcb;
		}
		last=pcb;
		pcb=pcb->next;
	}
	if (highest==head){
		return;
	}else{
		prevh->next=highest->next;
		highest->next=head;
		head=highest;
	}

}

void HRF(){
	head=NULL;
	last=NULL;
	exec=NULL;
	PCB * pcb;
	cout<<"\n高響應比優先調度算法:\n";
	for (int time=0;time<TIMES;time++){
		pcb=head;
		while(pcb){
			pcb->waittime++;
			pcb=pcb->next;
		}
		if (exec){
			exec->exectime++;
			if (exec->exectime>=exec->needtime){
				cout<<exec->id<<"結束，周轉時間："<<exec->exectime+exec->waittime<<"，帶權周轉時間："<<(exec->exectime+exec->waittime)/exec->needtime<<endl;
				exec=NULL;
			}
		}
		if (NewPCB[time]){
			if (!head){
				head=new PCB(*NewPCB[time]);
				last=head;
			}else{
				last->next=new PCB(*NewPCB[time]);
				last=last->next;
			}
			cout<<last->id<<"創建，需要時間："<<last->needtime<<"，優先級："<<last->pri<<endl;
		}
		if (!exec){
			SortByResponseRate();
			if (head){
				exec=head;
				head=head->next;
				exec->next=NULL;
				cout<<exec->id<<"開始執行。"<<endl;
			}
		}
	}
}

void TSC(){
	head=NULL;
	last=NULL;
	exec=NULL;
	PCB * pcb;
	cout<<"\n時間輪轉調度算法:\n";
	for (int time=0;time<TIMES;time++){
		pcb=head;
		while(pcb){
			pcb->waittime++;
			pcb=pcb->next;
		}
		if (exec){
			exec->exectime++;
			if (exec->exectime>=exec->needtime){
				cout<<exec->id<<"結束，周轉時間："<<exec->exectime+exec->waittime<<"，帶權周轉時間："<<(exec->exectime+exec->waittime)/exec->needtime<<endl;
				exec=NULL;
			}
		}
		if (NewPCB[time]){
			if (!head){
				head=new PCB(*NewPCB[time]);
				last=head;
			}else{
				last->next=new PCB(*NewPCB[time]);
				last=last->next;
			}
			cout<<last->id<<"創建，需要時間："<<last->needtime<<"，優先級："<<last->pri<<endl;
		}
		if (!exec){
			if (head){
				exec=head;
				head=head->next;
				exec->next=NULL;
				cout<<exec->id<<"開始執行。"<<endl;
			}
		}else{
			if (head){
				last->next=exec;
				last=last->next;
				exec=head;
				head=head->next;
				exec->next=NULL;
				cout<<exec->id<<"開始執行。"<<endl;
			}
		}
	}
}

void MFQ(){
	PCB * q1=NULL;
	PCB * q2=NULL;
	PCB * q3=NULL;
	PCB * q4=NULL;
	PCB * pcb;
	int nextq;
	PCB * q1last=NULL;
	exec=NULL;
	cout<<"\n多級反饋隊列調度算法:\n";
	for (int time=0;time<TIMES;time++){
		pcb=q1;
		while(pcb){
			pcb->waittime++;
			pcb=pcb->next;
		}
		pcb=q2;
		while(pcb){
			pcb->waittime++;
			pcb=pcb->next;
		}
		pcb=q3;
		while(pcb){
			pcb->waittime++;
			pcb=pcb->next;
		}
		pcb=q4;
		while(pcb){
			pcb->waittime++;
			pcb=pcb->next;
		}
		if (exec){
			exec->exectime++;
			if (exec->exectime>=exec->needtime){
				cout<<exec->id<<"結束，周轉時間："<<exec->exectime+exec->waittime<<"，帶權周轉時間："<<(exec->exectime+exec->waittime)/exec->needtime<<endl;
				exec=NULL;
			}else{
				switch(nextq){
					case 2:
						if (!q2){
							q2=exec;
							pcb=NULL;
						}else{
							pcb=q2;
						}
						break;
					case 3:
						if (!q3){
							q3=exec;
							pcb=NULL;
						}else{
							pcb=q3;
						}
						break;
					case 4:
						if (!q4){
							q4=exec;
							pcb=NULL;
						}else{
							pcb=q4;
						}
						break;
					default:
						//ERROR
						break;
				}
				if (pcb){
					while(pcb->next){
						pcb=pcb->next;
					}
					pcb->next=exec;
				}
				exec=NULL;
			}
		}
		if (NewPCB[time]){
			if (!q1){
				q1=new PCB(*NewPCB[time]);
				q1last=q1;
			}else{
				q1last->next=new PCB(*NewPCB[time]);
				q1last=q1last->next;
			}
			cout<<q1last->id<<"創建，需要時間："<<q1last->needtime<<"，優先級："<<q1last->pri<<endl;
		}
		if (!exec){
			if (q1){
				exec=q1;
				q1=q1->next;
				exec->next=NULL;
				cout<<exec->id<<"開始執行。"<<endl;
				nextq=2;
				continue;
			}
			if (q2){
				exec=q2;
				q2=q2->next;
				exec->next=NULL;
				cout<<exec->id<<"開始執行。"<<endl;
				nextq=3;
				continue;
			}
			if (q3){
				exec=q3;
				q3=q3->next;
				exec->next=NULL;
				cout<<exec->id<<"開始執行。"<<endl;
				nextq=4;
				continue;
			}
			if (q4){
				exec=q4;
				q4=q4->next;
				exec->next=NULL;
				cout<<exec->id<<"開始執行。"<<endl;
				nextq=4;
				continue;
			}
		}
	}
}

void main(){
	srand(time(0));
	RandomEvent();
	int j=0;
	FCFS();
	SPF();
	FPF();
	HRF();
	TSC();
	MFQ();
	getch();
}