/***********************************************************************************
 * CSC 714 Project
 * ngholka Neha Gholkar 
 * Xluo6   Xiaoqing Luo
 * Power-aware scheduling for soft RT jobs
 * *********************************************************************************/


#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include "power.h"

//#define DEBUG_ENABLE
//#undef DEBUG_ENABLE

#ifdef DEBUG_ENABLE
#define DEBUG printf
#else
#define DEBUG 
#endif


// Array of induced tasks
tasks_t tasks[MAX_TASK];

// string to store messages
char str[32];

// flag to show missed deadline
int missDeadline = 0;

/********************************************************************************/
//added by xiaoqing


//QOS tracking
int DEADLINES_MISSED[WINDOW];
int JOBS_DROPPED[WINDOW];

//Penalties associated with deadline misses and job drops respectively
float alpha = 3;                   
float beta = 1;

//used in DVFS
float max_missing_ratio = 0.004; // Limitation on deadline misses
float max_rej_ratio = 0.001;     // Limitation on job rejections 
float P_of_QOS = 0.4;            

float num_periods_of_usefullness = 2;


//current Frequency of system
int cFrequency;

//current highest priority of the system
int cHighestPriority;

//running task
qnode runtask;

//number of priority queue
int num_priority = 0;

//ready queue
//assume at most 16 priorities and 1024 jobs per queue that can be in the ready state
qnode ready_queue_head[16]; 
qnode ready_queue_tail[16];

/*******************************************************************************/

//declaring the current system state
state_t state = {0};

// systems parameters
unsigned int startTime = 0, stopTime = 0;
unsigned int startDisplay=0;
unsigned int endDisplay=0;

//task behavior history
int *HIST;

qnode qHead = NULL;

int main(int argc, char *argv[])
{
    unsigned int i = 0;
    if (argc < 2)
    {
        printf("USAGE: .//power <input file>\n");
        exit(-1);
    }

    if(init_simulator(argv[1])==FALSE){
    	printf("initiate simulator false\n");
	exit(0);
    }
    


   /*if(init_state()==FALSE) 
	return FALSE;*/

    runSimulator();





    return 0;
}

/*Neha*/
void runSimulator()
{


   //Start Simulation
   //Initialize the QoS window
   InitQos();

   runScheduler();




}


void insert_ready_queue_tail(qnode tmp, int pri)
{
   //if empty

   //printf("\nAdding task %d with deadline %d pri = %d", tmp->taskid, tmp->deadline, pri);
   if(ready_queue_head[pri] == NULL && ready_queue_tail[pri] == NULL)
   {      
	ready_queue_head[pri] = ready_queue_tail[pri] = tmp;
   }
   else
   {
      ready_queue_tail[pri]->next = tmp;
      ready_queue_tail[pri]= tmp;
   }

   if( cHighestPriority > pri)  //lower number higher priority
   {
        cHighestPriority = pri;
   }


}


qnode delete_ready_queue_head(int pri)
{
   int tpri = pri;
   if(ready_queue_head[pri] == NULL)
   {	
      //printf("\n********Invalid access. There is no ready job for this priority**********\n");
      return NULL;
   }
   
   qnode temp = ready_queue_head[pri];
   ready_queue_head[pri]=ready_queue_head[pri]->next;

   if(ready_queue_head[pri] == NULL) ///dequeued the last job for this priority. queue is empty
   {
     ready_queue_tail[pri] = NULL; 

     //set cHighestPriority to the next highest priority
     if(cHighestPriority == pri)
     {
         while(ready_queue_head[pri] == NULL)
         {
           pri++;
         }
     }
     if(pri >= 16)
         cHighestPriority = 128;
     else
	cHighestPriority = pri;
   }
 
  // printf("\ndeleting task %d with deadline %d pri = %d", temp->taskid, temp->deadline, tpri);

  
   return temp;
}


qnode get_ready_queue_head(int pri)
{
  return ready_queue_head[pri]; 

}

qnode creatJobOfTask(int i)
{

   /*Create a new node temp*/
   qnode temp = (qnode) malloc (sizeof (struct qnode_t));
   temp->priority = tasks[i].priority;

	

   temp->taskid   = i;
   temp->state    = READY;
   temp->flag	  = 0;

   temp->execution_path = select_path(tasks[i].num_path);
   temp->execution_path = 0;

   temp->deadline = state.sys_time + tasks[i].deadline;
   
// temp->execution_left= tasks[i].exe_time[temp->execution_path][cFrequency]; 
   temp->execution_left = tasks[i].Fexec[temp->execution_path][cFrequency];

   ////time_left = qnode.deadline - state.sys_time always this tells us whether a job has missed its deadline
   temp->next     = NULL;   
   

   /*This job goes into the corresponding priority ready queue*/
   insert_ready_queue_tail(temp, tasks[i].priority);

   return temp;
   
  
}


/*Neha*/
void runScheduler()
{
   int i;
   while(1)
   {

     if(state.sys_time ==30000)
     break;

     // check whether any task has been released in this time instance
     for(i=0; i<state.num_tasks; i++)
     {
        //if a job has been released put it in the ready queue of its priorit
	if( (state.sys_time  - tasks[i].phase)  %  tasks[i].period == 0 )
        {
	    //add the job to its priority queue
            qnode temp =  creatJobOfTask(i);
                
            //printf("\n[%d]task %d released deadline = %d exe=%d\n",state.sys_time ,i, temp->deadline, temp->execution_left);

		
        }

     }
    


     /* check whether any task is running */
     if(runtask!=NULL)
     { ///system is busy running a job

        //update_timeleft for the running job
        runtask->execution_left--;   
        if(runtask->execution_left!=0)   //  job not finished
        {
                state.sys_time++;
   		
		/* Keep track of the QoS of the system - deadline misses and rejected jobs */
                UpdateQos();

	        continue;

        }
      
        //running job just finished its execution
    
        //printf("\n[%d]Task [%d] just finished.\n", state.sys_time, runtask->taskid);
        //printf("\ncHighestPriority = %d", cHighestPriority); 
       
     	cFrequency = DVFS();

        runtask = NULL;    
         
        //schedule new job outside this if block
       
     }  

     
     //runtask is null. Either a job has just finished or idle period
     if(cHighestPriority != 128)     ///atleast one ready job in the queue
     {
	 //printf("\ncHighestPriority = %d", cHighestPriority);   
 	 runtask = delete_ready_queue_head(cHighestPriority);         
//       printf("\n[%d]Task [%d] just started\n", state.sys_time, runtask->taskid); 
     }    

     //update system state
     if(runtask == NULL)
     {
         state.sys_prio = 128;
         state.running = IDLE;
         //printf(".");
     }
     else
     { 
        //printf("\n[%d]Task [%d] just started\n", state.sys_time, runtask->taskid);
        state.sys_prio = runtask->priority;
	state.running = BUSY;
     }

 

     // based on the system Qos decide whether to execute the next job or drop it       //// DROPPED
     //Increment the system timer
     state.sys_time++;
     UpdateQos();

   }


}





int init_simulator(char *fin)
{
  //initialize global variables
  //state.hyperperiod = 0;
  state.sys_time = 0;
  state.sim_time = 0;
  state.sys_prio = 128;
  state.running = IDLE;
  
  runtask = NULL;
  cFrequency=0;
  cHighestPriority = 128;
  
  
  memset (tasks, 0, sizeof(tasks_t)*MAX_TASK);

  if(parseFreq(fin)==FALSE) 
      return FALSE;

  int i;
  for(i=0; i<16; i++)
  {
     ready_queue_head[i] = NULL;
     ready_queue_tail[i] = NULL;
  }
      


  return TRUE;
}


int parseFreq(char *fn){  //added by xiaoqing
	FILE *fptr;
	char temp[MAX_LEN_STR];
	int ret;
	int ind, ind1, num, flag, record;
	char c;
	
	fptr = fopen(fn, "r");
	if(fptr==NULL){
		printf("- Error: Cannot open the input file\n");
		return FALSE;
	}
  
  	//initialize return value
  	ret=TRUE;
  	state.num_tasks=0;
	ind = 0;
	flag = 0;
	ind1 = 0;
	num = 0;
  	while(1){
  		c=fscanf(fptr, "%s", temp);
    		if(c==EOF && feof(fptr)) break;
    		if(c==EOF && ferror(fptr)){
      			printf("- Error occurs while reading input file\n");
      			ret=0;
      			break;
    		}

		if(strcmp(temp, "BEST")==0){
			ind = 0;
			flag = 0;
			record = 0; //record if the last row of a task
			continue;
		}
		if(strcmp(temp, "MIDDLE") == 0){
			ind = 0;
			flag += 1;
			continue;
		}
		if(strcmp(temp, "WORST")==0){
			ind = 0;
			flag += 1;
			record = 1;
			tasks[state.num_tasks].num_path = flag+1;
			continue;
		}
		if(ind < 15){
			if(record == 0){
				tasks[state.num_tasks].Fexec[flag][ind] = atoi(temp);
				ind += 1;
			}else{
				tasks[state.num_tasks].Fexec[flag][ind] = atoi(temp);
				ind += 1;
				if(ind == 15)
					state.num_tasks++;
			}
		}
		if(strcmp(temp, "Deadline") == 0){
			ind1 = 1;
			continue;	
		}
               
            
		switch(ind1){
			case 1:
				ind1 = 2;
				break;
			case 2:
				tasks[num].F = atoi(temp);
				ind1 = 3;
				break;
			case 3:
				tasks[num].phase = atoi(temp);
				ind1 = 4;
				break;
			case 4:
				tasks[num].period = atoi(temp);
				ind1 = 5;
				break;
    			case 5:
				tasks[num].priority = atoi(temp);
                                ind1 = 6;
                                break;                   
    
			case 6:
				tasks[num].deadline = atoi(temp);
				num += 1;
				ind1 = 1;   //changed here
				if(num == state.num_tasks)
					ind1 = 0;
        
			default:
				break;
		}
	}
	if(num != state.num_tasks){
		printf("error: unvalid input\n");
		exit(0);
	}
 
        /* Selection of the execution*/


	int i, j, k;
	for(k=0; k<state.num_tasks; k++){
		printf("\ntask%d best and worst:\n", k);
		for(j=0; j<tasks[k].num_path; j++){
			for(i=0; i<15; i++)
				printf(" %d", tasks[0].Fexec[j][i]);
			printf("\n");
		}
	}

	for(i=0; i<num; i++)
		printf("task %d: F->%d, phase->%d, period->%d, priority->%d deadline->%d\n", i, tasks[i].F, tasks[i].phase, tasks[i].period, tasks[i].priority, tasks[i].deadline);
     


	return ret;
}





//initiate Qos number, used in initiate states
int InitQos(){
       	int ret = 0;
	int i;
	for(i=0; i<WINDOW; i++){
		DEADLINES_MISSED[i] = 0;
		JOBS_DROPPED[i] = 0;
	}
	ret = 1;
	return ret;
}

/*Calculate the total number of deadline misses in the time window*/
int Calculate_miss(){
	int qos = 0, i;
	for(i=0; i<WINDOW; i++)
		qos += DEADLINES_MISSED[i];
	return qos;
}

/*Calculate the total number of rejected jobs in the time window*/
int Calculate_rej(){
	int rej = 0, i;
	for(i=0; i<WINDOW; i++)
		rej += JOBS_DROPPED[i];
	return rej;
}

/* calculate the QoS of the System */
int CalculateQos(){
	int qos = Calculate_miss();
	int rej = Calculate_rej();
	return alpha*qos + beta*rej;
}

/* update the Qos window record, only after the time unit finish, can calculate the correct 
 * result, and only consider about the ready queue and running task, this function is called after the sys_time++ */

void UpdateQos(){
	int i, j;
	int qos=0;
	if(runtask != NULL && runtask->state != OVER){ //if the runtask finish in the current time unit, state of this task need to be set "OVER" before this function called, and runtask need to be set to NULL untill next time get in the loop.
		if(runtask->deadline < state.sys_time){
			if(runtask->flag == 0){
				qos += 1;
				runtask->flag = 1;
				runtask->rec_time = state.sys_time;
			}
		}
	}

	// search from the ready queue
	for(i=0; i<16; i++){
		qnode temp = ready_queue_head[i]; //head of read queue i
		while(temp != NULL){
			if(temp->deadline < state.sys_time){
				if(temp->flag == 0){
					temp->flag = 1;
					temp->rec_time = state.sys_time;
					qos += 1;
				}
			}
			temp = temp->next;	
		}
	}
	DEADLINES_MISSED[state.sys_time%WINDOW] = qos;
	JOBS_DROPPED[state.sys_time%WINDOW] = 0;

        float print_cFrequency;
        switch(cFrequency)
	  {
	  case 0: print_cFrequency = 3.3;
	    break;
	  case 1: print_cFrequency = 3.1;
	    break;
	  case 2: print_cFrequency = 3.0;
	    break;
	  case 3: print_cFrequency = 2.8;
	    break;
	  case 4: print_cFrequency = 2.7;
	    break;
	  case 5: print_cFrequency = 2.5;
	    break;
	  case 6: print_cFrequency = 2.4;
	    break;
	  case 7: print_cFrequency = 2.2;
	    break;
	  case 8: print_cFrequency = 2.1;
	    break;
	  case 9: print_cFrequency = 1.9;
	    break;
	  case 10: print_cFrequency = 1.8;
	    break;
	  case 11: print_cFrequency = 1.6;
	    break;
	  case 12: print_cFrequency = 1.5;
	    break;
	  case 13: print_cFrequency = 1.3;
	    break;
	  case 14: print_cFrequency = 1.2;
	    break;
	  default: print_cFrequency = 0;


	  }


        if(state.sys_time % 100 == 0)
	  printf(" job: %d, miss: %d rej: %d, fre: %f\n", (runtask == NULL)?-1:runtask->taskid, Calculate_miss(),Calculate_rej(),print_cFrequency);
}


int select_path(int n){
	int index = 0;
	index = rand() % n;
	return index;
}


//delete first job in the ready queue
void drop_job(){
	qnode temp = delete_ready_queue_head(cHighestPriority);
	if(temp != NULL){
		JOBS_DROPPED[state.sys_time%WINDOW] = 1;
		if(temp->flag == 1 && state.sys_time-temp->rec_time <= WINDOW){
			if(DEADLINES_MISSED[temp->rec_time%WINDOW] > 0)
				DEADLINES_MISSED[temp->rec_time%WINDOW] -= 1;	
			}
		}
}


int DVFS(){

	//caculate the instant missing deadline
	int qos = CalculateQos();
        
        //printf("qos: %d, fre: %d\n", qos, cFrequency);

	//maximum allowable deadline misses
	int max_num_miss = WINDOW*max_missing_ratio;
	int max_num_rejections = WINDOW*max_rej_ratio;
	int i;

	 
	qnode temp = (cHighestPriority<128)?get_ready_queue_head(cHighestPriority):NULL;

	//if deadline misses  have already violated the limitation and if we can reject some jobs in the current window
        //reject a job
	if(Calculate_miss() >= max_num_miss && temp != NULL && Calculate_rej()<WINDOW*max_rej_ratio){
		printf("Job of task %d has been delete due to  bad system_Qos\n", temp->taskid);
		drop_job();
		return 0;
	}

	//We consider a binary usefullness function for all the tasks. 

 	//            1  in the num_periods_of_usefullness periods of Ti
	//f(Ti) =
	//            0  after num_periods_of_usefullness periods of Ti
		  
	if(temp != NULL){
		while(state.sys_time > temp->deadline && state.sys_time-(temp->deadline) > (tasks[temp->taskid].period)*num_periods_of_usefullness) {
			printf("Job of task %d has been delete because it is useless to execute this job: %d\n", temp->taskid, state.sys_time-(temp->deadline));
			drop_job();  // servicing this job request is now useless  hence just drop the job   /////////loop
			temp = (cHighestPriority<128)?get_ready_queue_head(cHighestPriority):NULL;
			if(temp == NULL)
				break;
		}
	}



	int qos_thresh = alpha*max_num_miss + beta*max_num_rejections;	
	
	//if there is no task release at the instant time of runtask finished, don't change the frequence 
	if(runtask == NULL)
		return cFrequency;




	/*Xiaoqing*/


	//in the situation of the runtask finished later than deadline
	if(runtask->deadline < state.sys_time){

		//if system_QoS of the system is close to the Worst case_System_QoS
		if(qos > qos_thresh*P_of_QOS){
			temp = (cHighestPriority<128)?get_ready_queue_head(cHighestPriority):NULL;
			if(temp != NULL){
				int worst_index = tasks[temp->taskid].num_path;
				int need_exec = runtask->deadline - state.sys_time + tasks[temp->taskid].Fexec[worst_index-1][cFrequency];


				// if next job can finished on time, do nothing
				if(state.sys_time+tasks[temp->taskid].Fexec[worst_index-1][cFrequency] <= temp->deadline)
					return cFrequency;


				// increase the frequence garateen the next job can finish on time
				for(i=0; i<15; i++){
					if(tasks[temp->taskid].Fexec[worst_index-1][i] > need_exec){
						if(i == 0)
							return 0;
						return i-1;
					}
				}

			}

			//if there is no job in the ready queue, keep the fre
			return cFrequency;
		}else{
			// if the missing deadline is avalibale, do nothing
			return cFrequency;
		}
	// in the situation of the runtask finished early than deadline
	}else{
		//if system_QoS of the system is close to the Worst case_System_QoS, do nothing	
		if(qos > qos_thresh*P_of_QOS)
			return cFrequency;

		// if system_QoS of the system is way below the Worst case_System_QoS decrease the frequency
		//qnode temp = (qnode)malloc(sizeof(struct qnode_t));
		qnode temp = (cHighestPriority<128)?get_ready_queue_head(cHighestPriority):NULL;
		if(temp != NULL){
			int worst_index = tasks[temp->taskid].num_path;
			int need_exec = runtask->deadline - state.sys_time + tasks[temp->taskid].Fexec[worst_index-1][cFrequency];


			for(i=0; i<15; i++){
				if(tasks[temp->taskid].Fexec[worst_index-1][i] > need_exec){
					return i;
				}
			}
			return 14;
		}
		return cFrequency;

	}






}


