//      實驗二 作業調度
//   單道批處理系統的作業等待模擬程序
//   采用先來先服務(FCFS),最短作業優先(SJF)的作業調度算法
//   Copyright 2008 , by freedomer

#include "stdio.h" 
#include <stdlib.h> 
#include <conio.h> 
#define getjcb(type) (type*)malloc(sizeof(type)) 
#define NULL 0 

struct jcb {					    /*定義作業控制塊JCB */ 
	char name[10];                  /*作業名*/
	char state;                     /*作業狀態*/
	int need_t;                     /*作業需要運行時間*/
	int submit_t;                   /*作業提交時刻*/
	struct jcb* link; 
}*ready=NULL,*p; 

typedef struct jcb JCB; 

int choose;                         /*選擇算法記錄*/

int begin_t=0,                      /*開始運行時刻,設定第一個作業的為0時刻*/
    finish_t;                       /*完成時刻*/
float turnover_t,                   /*周轉時間*/
	  with_t,                       /*帶權時間*/
	  sumturnover_t=0.0,            /*各個作業周轉時間和*/
      sumwith_t=0.0,                /*各個作業帶權時間和*/
	  advturnover_t,                /*平均周轉時間*/
	  advwith_t;                    /*平均帶權時間*/

void sort() {						/*建立作業用某個算法進行排列函數*/ 
	JCB *first, *second; 
	int insert=0; 
	if(choose==1) {                     /*FCFS算法*/
		if((ready==NULL)||((p->submit_t)<(ready->submit_t))) {
										/*提交時間最早者,插入隊首*/  
			p->link=ready; 
			ready=p; 
		} 
		else {                          /*作業比較提交時間,插入適當的位置中*/  
		first=ready; 
		second=first->link; 
		while(second!=NULL) { 
			if((p->submit_t)<(second->submit_t)) {
										/*若插入作業比當前作業提交時間早,*/ 
										/*插入到當前作業前面*/ 
				p->link=second; 
				first->link=p; 
				second=NULL; 
				insert=1; 
			} 
			else {                      /*插入作業提交時間最晚,則插入到隊尾*/ 
				first=first->link; 
				second=second->link; 
			} 
		} 
		if(insert==0) 
			first->link=p; 
		} 
	}
	else if(choose==2) {                /*SJF算法*/
		if((ready==NULL)||((p->need_t)<(ready->need_t))) {
										/*運行時間最少者,插入隊首*/  
			p->link=ready; 
			ready=p; 
		} 
		else {                          /*作業比較運行時間,插入適當的位置中*/  
		first=ready; 
		second=first->link; 
		while(second!=NULL) { 
			if((p->need_t)<(second->need_t)) {
										/*若插入作業比當前作業運行時間更少,*/ 
										/*插入到當前作業前面*/ 
				p->link=second; 
				first->link=p; 
				second=NULL; 
				insert=1; 
			} 
			else {                      /*插入作業運行時間最多,則插入到隊尾*/ 
				first=first->link; 
				second=second->link; 
			} 
		} 
		if(insert==0) 
			first->link=p; 
		} 
	}
} 


void input() {						/*建立初始化作業控制塊函數*/  
	int i,jobnum; 
	printf("\n 請輸入要調度的作業個數?"); 
	scanf("%d",&jobnum); 
	for(i=0;i<jobnum;i++)  { 
		printf("\n 作業號No.%d:\n",i); 
		p=getjcb(JCB); 
		printf("\t 輸入作業名:"); 
		scanf("%s",p->name);  
		printf("\t 輸入作業所需的運行時間:"); 
		scanf("%d",&p->need_t); 
		p->submit_t=i;               /*提交時間根據輸入順序累加1*/
		p->state='w'; 
		p->link=NULL; 
		sort();                      /*調用sort函數*/ 
	} 
} 


int space() {
	int l=0; JCB* pr=ready; 
	while(pr!=NULL) { 
		l++; 
		pr=pr->link; 
	} 
	return(l); 
} 


void disp(JCB * pr) {                 /*建立作業顯示函數,用于顯示當前作業*/ 
	printf("\n qname \t state \t needtime \t submittime \n"); 
	printf("|%s\t",pr->name); 
	printf("|%c\t",pr->state); 	
	printf("|%d\t\t",pr->need_t); 
	printf("|%d:00",pr->submit_t);
	printf("\n"); 
}

 
void check() {                        /*建立作業查看函數 */  
	JCB* pr; 
	printf("\n **** 當前正在運行的作業是:%s",p->name); 
									  /*顯示當前運行作業*/ 
	disp(p); 
	pr=ready; 
	printf("\n ****當前就緒隊列狀態為:\n"); 
	                                  /*顯示就緒隊列狀態*/ 
	while(pr!=NULL) { 
		disp(pr); 
		pr=pr->link; 
	} 
} 


void destroy() {                      /*建立作業撤消函數(作業運行結束,撤消作業)*/ 
	printf("\n 作業 [%s] 已完成.\n",p->name);
	printf("此作業的相關時間如下:\n");
	printf("開始時刻:%d:00\n",begin_t);
	printf("完成時刻:%d:00\n",finish_t);
	printf("周轉時間:%.3f\n",turnover_t);
	printf("帶權周轉時間:%.3f\n",with_t);
	begin_t=begin_t+p->need_t;        /*下個作業的開始時間=前一個作業開始時間+其運行時間*/
	free(p);
	p->link=NULL;
}

 
void running() {                      /*計算在運行的作業的相應的時間，并將它釋放*/  
	finish_t=begin_t+p->need_t; 
	turnover_t=finish_t-p->submit_t;
	with_t=turnover_t/p->need_t;
    sumturnover_t+=turnover_t;
	sumwith_t+=with_t;
	destroy();                        /*調用destroy函數*/ 
	
} 

void main() {                         /*主函數*/ 
	int len,h=0; 
	char ch; 
	printf("\n\n\t1.先來先服務算法(FCFS)\n\n\t2.最短作業優先算法(SJF)\n");
	printf("\n請選擇所需要的算法...\n");
	scanf("%d",&choose);
	if((choose!=1)&&(choose!=2)) {
		printf("選擇錯誤!\n");
		exit;
	}
	else {
		input(); 
		len=space(); 
		while((len!=0)&&(ready!=NULL)) { 
			ch=getchar(); 
			h++; 
			printf("\n The execute number:%d \n",h); 
			p=ready; 
			ready=p->link; 
			p->link=NULL; 
			p->state='R'; 
			check(); 
			running(); 
			printf("\n 按任一鍵繼續......"); 
			ch=getchar(); 
		} 
		printf("\n **所有作業都已經完成.**\n這組作業的相關時間如下:\n");
		advturnover_t=sumturnover_t/len;      /*組平均周轉時間*/
		advwith_t=sumwith_t/len;              /*組帶權平均周轉時間*/
		printf("組平均周轉時間:%.3f\n組帶權平均周轉時間:%.3f\n",advturnover_t,advwith_t);
		ch=getchar(); 
	}
}