// SJF.cpp : Defines the entry point for the console application.
//

#include "dos.h"
#include "stdlib.h"
#include "stdio.h"
#include "string.h"
#include "conio.h"
#include "math.h"
#include "time.h"
#define getpch(type) (type*)malloc(sizeof(type)) 
#define NULL 0 
struct jcb { /* 定義作業控制塊jcb */ 
	char outername[10]; //外部標識符
	int  innername; //內部標識符
	char state[10]; //記錄三種基本狀態
	int arrivetime; //到達時間
	int servetime;  //需要服務時間
	int CPUtime;     //已用CPU時間
	int finishtime;  //完成時間
	int cycletime;   //周轉時間
	float weighttime;  //帶權周轉時間
	bool flag;
	int waittime;//等待時間
	float weight;//優先權(響應比)
	struct jcb* next; 
}*ready=NULL,*block=NULL,*p;//就緒隊列,阻塞隊列和當前作業
typedef struct jcb JCB;
JCB *first=NULL,fir[3][5];//作業到達時間隊列
int blocktime,counting;//時間片中止時間
char how[10];
float avecycletime,aveweighttime;//平均周轉時間,平均帶權周轉時間

void FIFCsort(JCB *pt)//先來先服務
{
	JCB *ptr;
	if((ready==NULL)||(pt->arrivetime<ready->arrivetime))
	{
		pt->next=ready;
		ready=pt;
	}
	else//插入隊尾
	{
		ptr=ready;
		while(ptr->next!=NULL)
			ptr=ptr->next;
		ptr->next=pt;
	}
}

void SJFsort(JCB *pt)//設置最短作業優先就緒隊列 
{
	JCB *ptr;
	if((ready==NULL)||((pt->servetime-pt->CPUtime)<(ready->servetime-ready->CPUtime)))//最短作業設置在隊首為就緒
	{
		pt->next=ready;
		ready=pt;
	}
	else
	{
		ptr=ready;
		while(ptr->next!=NULL)//插入隊列中
		{
			if((pt->servetime-pt->CPUtime)<(ptr->next->servetime-ready->CPUtime))
			{
				pt->next=ptr->next;
				ptr->next=pt;
				break;
			}
			ptr=ptr->next;
		}
		if(ptr->next==NULL)//插入隊尾
			ptr->next=pt;
	}
}

void HighResponseSort(JCB *pt)
{
	JCB *ptr;
	if((ready==NULL)||(pt->weight > ready->weight))//高響應比優先+先來先服務設置在隊首為就緒
	{
		pt->next=ready;
		ready=pt;
	}
	else
	{
		ptr=ready;
		while(ptr->next!=NULL)//插入隊列中
		{
			if((pt->weight>ptr->next->weight)||(pt->weight==ptr->next->weight&&pt->arrivetime<ptr->next->arrivetime))
			{
				pt->next=ptr->next;
				ptr->next=pt;
				break;
			}
			ptr=ptr->next;
		}
		if(ptr->next==NULL)//插入隊尾
			ptr->next=pt;
	}
}

void ArriveTimeSort(JCB *pt)
{
	JCB *ptr;
	if(pt->servetime==0)
	{
		free(pt);
	}
	else if((first==NULL)||((pt->arrivetime)<(first->arrivetime)))//設置在隊首為就緒
	{
		pt->next=first;
		first=pt;
	}
	else
	{
		ptr=first;
		while(ptr->next!=NULL)//插入隊列中
		{
			if((pt->arrivetime<ptr->next->arrivetime))
			{
				pt->next=ptr->next;
				ptr->next=pt;
				break;
			}
			ptr=ptr->next;
		}
		if(ptr->next==NULL)//插入隊尾
			ptr->next=pt;
	}
}

void DeleteList(JCB *pt)
{
	free(pt);
}

bool detective(char a[],int &x)//將字符型轉換成數字型
{
    int len;x=0;
	for(int i=0;a[i]!='\0';i++)
	{
		if(a[i]<'0'||a[i]>'9')//濾去其它字符
			return 0;
	}
	len=i;
	for(int j=len-1;j>=0;j--)//轉成整數
	{
		    x+=(a[j]-'0')*(int)pow(10,len-j-1);
	}
	return 1;
}

void ClearList(JCB *pt)//清零
{
	JCB *p=pt;
	while(p!=NULL)
	{
		p->CPUtime=0;p->waittime=0;p->weight=0;
		strcpy(p->state,"Wait"); 
		p->finishtime=0;
		p->cycletime=0;
		p->weighttime=0;
		p=p->next;
	}
}

void CreateProcess() /* 建立作業控制塊函數*/ 
{ 
	int i,num=5;char ch[10];char order[10];
	printf("請指定初始化方式(按y自己設定,任意鍵隨機設定):");
	scanf("%s",&order);
	srand(time(0));//種子
	for(i=0;i<num;i++) 
	{ 
		printf("\n %d號作業",i); 
		p=getpch(JCB); 		
		if(order[0]=='y')
		{
			printf("輸入作業名:"); 
			scanf("%s",&p->outername); 	
			printf("作業到達時間:");
			loop:scanf("%s",&ch);
	        if(!detective(ch,p->arrivetime))//判斷是否輸入為數字型
			{
		       printf("請重新輸入以1為單位的整型數:"); 
		       goto loop;
			}
			printf("作業需要服務時間:");
			loop1:scanf("%s",&ch);
	        if(!detective(ch,p->servetime))//判斷是否輸入為數字型
			{
		       printf("請重新輸入以1為單位的整型數:"); 
		       goto loop1;
			}
		}
		else
		{
			printf("作業名:");
			p->outername[0]='a'+i;
			p->outername[1]='\0';
			printf("%s\n",p->outername);
			printf("作業到達時間:");
			p->arrivetime=rand()%10;
			printf("%d",p->arrivetime);
			printf("作業需要服務時間:");
			p->servetime=rand()%10;
			printf("%d\n",p->servetime);
		}
		p->innername=i;		
        p->CPUtime=0;p->waittime=0;p->weight=0;
		strcpy(p->state,"Wait"); 
		p->finishtime=0;
		p->cycletime=0;
		p->weighttime=0;
		p->next=NULL; 
		ArriveTimeSort(p);
	} 
} 

void PrintProcessQueue(JCB *pt)
{
	JCB *ptr=pt;
	printf("作業名|到達時間|服務時間|作業狀態|響應比|完成時間|周轉時間|帶權周轉時間\n");
	while(ptr!=NULL)
	{ 
		printf("%s",ptr->outername);
		printf("       ");
		printf("%d",ptr->arrivetime); 
		printf("       ");
		printf("%d",ptr->servetime);
		printf("        ");
		printf("%s ",ptr->state);
		printf("%d ",ptr->waittime);
		printf("%f",ptr->weight);
        printf("     %d",ptr->finishtime);
		printf("     %d",ptr->cycletime);
		printf("       %f\n",ptr->weighttime);
		ptr=ptr->next;
	}
}

void SetWeight()//冒泡算法重新調整就緒隊列
{
	JCB *ptr=ready,*pt=ready,*p,*q=ready,*pc;
	while(pt!=NULL&&pt->flag!=0)
	{
		pt->flag=0;
		pt=pt->next;
	}
	while(ptr!=NULL)
	{
		if(ptr==ready) 
		{
			if(ptr->flag==0)
			{
				p=ready;
				ready=ptr->next;
				p->next=0;
				p->waittime++;
				p->weight=(float)(p->waittime+p->servetime)/p->servetime;
				p->flag=1;
				pc=first;
				while(pc!=NULL)
				{
					if(pc->innername==p->innername)
					{
						pc->waittime=p->waittime;
						pc->weight=p->weight;
					}
					pc=pc->next;
				}
				HighResponseSort(p);
				ptr=ready;
			}
			else
				q=ptr;ptr=ptr->next;
		}
		else 
		{
			if(q->next!=NULL&&q->next->flag==0)
			{
				p=q->next;
				q->next=q->next->next;
				p->next=0;
				p->waittime++;
				p->weight=(float)(p->waittime+p->servetime)/p->servetime;
				p->flag=1;
				pc=first;
				while(pc!=NULL)
				{
					if(pc->innername==p->innername)
					{
						pc->waittime=p->waittime;
						pc->weight=p->weight;
						break;
					}
					pc=pc->next;
				}
				HighResponseSort(p);
				ptr=ready;				
			}
			else
				q=ptr;ptr=ptr->next;
		}
	}
}

void AttemperProcess(int start,int time,char a)//一個時間片內的作業調度
{
	if(block!=NULL)
	{
		printf("\n... ...作業[%s]喚醒... ...",block->outername);
		p=block;
		switch(a)//進入就緒隊列
		{
		case '2':
			FIFCsort(p);
			break;
		case '3':
			SJFsort(p);
			break;
		case '4':
			HighResponseSort(p);
			break;
		default:
			break;
		}		
		strcpy(block->state,"Wait");
		block=NULL;
	}
    JCB *execute=ready;JCB *ptr;
	printf("\n\t->->->->作業[%s]正在調度中... ...\n",execute->outername);
	ready=ready->next;
	if(ready!=NULL&&a=='4')
		SetWeight();
	for(int i=start+1;i<start+time+1;i++)
	{
		printf("\t\t... ...第%d個CPU時鐘周期... ...\n",i);
		(execute->CPUtime)++;
		ptr=first;
		while(ptr!=NULL)
		{
			if(ptr->innername==execute->innername)
			{
				ptr->CPUtime=execute->CPUtime;
				break;
			}
			ptr=ptr->next;
		}
		if(execute->CPUtime==execute->servetime)//結束作業
		{
			printf("\n... ...作業[%s]完成... ...",execute->outername);
			execute->finishtime=i;
			printf("完成時間:%d\t",i);
			execute->cycletime=i-execute->arrivetime;
			printf("周轉時間:%d\t",execute->cycletime);
			avecycletime+=execute->cycletime;
			execute->weighttime=(float)execute->cycletime/execute->servetime;
			printf("帶權周轉時間:%f\n",execute->weighttime);
			aveweighttime+=execute->weighttime;
			strcpy(execute->state,"Finish");			
			blocktime=i-start;counting++;
			ptr=first;
			while(ptr!=NULL)
			{
				if(ptr->innername==execute->innername)
				{
					ptr->finishtime=i;
					ptr->cycletime=execute->cycletime;
					ptr->weighttime=execute->weighttime;
					strcpy(ptr->state,"Finish");
					break;
				}
				ptr=ptr->next;
			}
			printf("... ...任意鍵繼續... ...");
			free(execute);
			getch();
			break;
		}	
		if(how[0]=='y')
		for(int delay1=0;delay1<10000;delay1++)
			for(int delay2=0;delay2<20000;delay2++);
	}
	if(i==start+time+1)//進入阻塞狀態
	{
		block=getpch(JCB);block=execute;block->next=NULL;
		printf("\n... ...作業[%s]阻塞... ...",block->outername);
		strcpy(block->state,"Block");
		if(how[0]=='y')
		for(int delay1=0;delay1<20000;delay1++)
			for(int delay2=0;delay2<20000;delay2++);
	}
}

void Attemper(int cyctime,char abc)
{
	int time=0,tim;
	JCB *ptr,*q;
	printf("請指定執行方式(按y觀察模式,任意鍵快速執行):");
	scanf("%s",&how);
	system("cls");
	blocktime=time=0;ptr=first;avecycletime=aveweighttime=0;counting=0;	
	tim=first->arrivetime;//準入口
	while(1)//時間片輪轉,輪轉時間為2
	{
		if(how[0]=='y')
		{
			system("cls");
			printf("\n  作業隊列為:\n");
			PrintProcessQueue(first);
			printf("\n  就緒隊列為:\n");
			PrintProcessQueue(ready);
		}
		printf("\n------------------------------------------------------------------------");
		while(ptr!=NULL&&time==ptr->arrivetime)
		{
			q=getpch(JCB);
			*q=*ptr;
			ptr=ptr->next;				 
			q->next=0;
			switch(abc)
			{
			case '2':
				FIFCsort(q);
				break;
			case '3':
				SJFsort(q);//進入就緒隊列
				break;
			case '4':
				HighResponseSort(q);
				break;
			default:
				break;
			}			
			printf("\n... ...新作業[%s]進入... ...",q->outername);
		}
		if(time<first->arrivetime)
		{
			printf("\n\t\t... ...第%d個CPU時鐘周期... ...\n",time+1);
			if(ready!=NULL&&abc=='4')
				SetWeight();
		}
		if(how[0]=='y')
		for(int delay1=0;delay1<10000;delay1++)
			for(int delay2=0;delay2<20000;delay2++);
		if((ready!=NULL||block!=NULL)&&((time-tim)%cyctime==0||blocktime!=cyctime&&blocktime!=0))
		{
			if((blocktime!=cyctime&&blocktime!=0))
				tim+=blocktime;
			blocktime=0;
			AttemperProcess(time,cyctime,abc);					
			if(block==NULL&&ready==NULL&&ptr==NULL)//隊列為空
			{
				printf("\n\n!!! !!!所有作業已經完成!!! !!!\n\n");
				avecycletime=avecycletime/counting;
				printf("\t平均周轉時間:%f\t",avecycletime);
				aveweighttime=aveweighttime/counting;
				printf("平均帶權周轉時間:%f\n\n",aveweighttime);
				break;
			}
		}
		else
		{
			if(ready!=NULL&&abc=='4')		
				SetWeight();
		}
		++time;
	}
}

void SaveList(JCB *pt,int n)
{
	JCB *ptr=pt;int i=0;
	while(ptr!=NULL)
	{
		fir[n][i]=*ptr;
		ptr=ptr->next;
		i++;
	}
}

void RestoreList(JCB *pt,int n)
{
	JCB *ptr=pt;int i=0;
	while(ptr!=NULL)
	{
		*ptr=fir[n][i];
		ptr=ptr->next;
		i++;
	}
}

int main(int argc, char* argv[])
{
	char ch[10],order[10];ch[0]='1';int cyctime=2;
	float a[3],b[3];int i;
	printf("\n-----------------------作業調度算法演示程序-----------------------\n");
	printf("\n\t\t制作者是軟件2班李建康,謝謝使用!\n\n\n");
	while(1)
	{
		switch(ch[0])
		{
		case '1':
			printf("... ...作業初始化... ...\n");
			if(first!=NULL)
				DeleteList(first);
			first=NULL;
            CreateProcess();
			printf("\n  作業隊列為:\n");
			PrintProcessQueue(first);
			for(i=0;i<3;i++)
			{
				a[i]=0;b[i]=0;
			}
			printf("\n... ...任意鍵繼續... ...\n");		    
			getch(); 
			break;
		case '2':
			system("cls");
			printf("\t\t... ...模擬先來先服務作業調度... ...\n\n");						
		    Attemper(cyctime,ch[0]);
			a[0]=avecycletime;b[0]=aveweighttime;
            SaveList(first,0);
			printf("\n... ...任意鍵繼續... ...");
			getch();
			break;
		case '3':
			system("cls");
			printf("\t\t... ...模擬最短作業優先作業調度... ...\n\n");		
		    Attemper(cyctime,ch[0]);
			a[1]=avecycletime;b[1]=aveweighttime;
			SaveList(first,1);
			printf("\n... ...任意鍵繼續... ...");		    
			getch();
			break;
		case '4':
			system("cls");
			printf("\t\t... ...模擬高響應比優先作業調度... ...\n\n");			
		    Attemper(cyctime,ch[0]);
			a[2]=avecycletime;b[2]=aveweighttime;
			SaveList(first,2);
			printf("\n... ...任意鍵繼續... ...");		    
			getch();
			break;
		case '5':
			system("cls");
			printf("... ...算法分析... ...\n");
			printf("\n  先來先服務作業隊列為:\n");
			RestoreList(first,0);
			PrintProcessQueue(first);
			printf("  最短作業優先作業隊列為:\n");
			RestoreList(first,1);
			PrintProcessQueue(fir[1]);
			printf("  高響應比優先作業隊列為:\n");
			RestoreList(first,2);
			PrintProcessQueue(fir[2]);
			printf("------------------------------------------------------------------------");
			printf("\t\t\t先來先服務\t最短作業優先\t高響應比優先\n");
			printf("平均周轉時間:\t\t%f\t%f\t%f\n",a[0],a[1],a[2]);
			printf("平均帶權周轉時間:\t%f\t%f\t%f",b[0],b[1],b[2]);
			printf("\n... ...任意鍵繼續... ...");		    
			getch();
			break;
		case '6':
			printf("\n... ...重新設置時間片的長度:");
            loop2:scanf("%s",&order);
	        if(!detective(order,cyctime))//判斷是否輸入為數字型
			{
		        printf("請重新輸入以1為單位的整型數:"); 
		        goto loop2;
			}
			printf("\n... ...任意鍵繼續... ...");
			if(cyctime==0)
				cyctime=1;
			getch();
	        break;
		case '7':
			DeleteList(ready);
			DeleteList(first);
			DeleteList(block);
			return 0;
			break;
		default:
			break;
		}
		if(first==NULL)
		{
			system("cls");
			continue;
		}
		ClearList(first);
		system("cls");
		printf("\n-----------------------作業調度算法演示程序-----------------------\n");
		printf("\n\t\t制作者是軟件2班李建康,謝謝使用!\n\n");
		printf("\n\t\t1.重新初始化作業");
		printf("\n\t\t2.模擬先來先服務作業調度");
		printf("\n\t\t3.模擬最短作業優先作業調度");
		printf("\n\t\t4.模擬響應比高者優先作業調度");
		printf("\n\t\t5.算法分析");
		printf("\n\t\t6.重新設置時間片的長度(默認為2)");
		printf("\n\t\t7.結束演示\n");
        printf("您的選擇是:");
		scanf("%s",&ch);
	}
	return 1;
}