/* Multi-purpose scheduler.
 *
 * Andreas van Cranenburgh 	(0440949)
 * Job P. Jonkergouw 		(5613949) 
 */

/* This file contains a bare bones skeleton for the scheduler function
   for the second assignment for the OSN course of the 2005 fall 
   semester.
   Author:

   G.D. van Albada
   Section Computational Science
   Universiteit van Amsterdam

   Date:
   October 23, 2003
   Modified:
   September 29, 2005
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#include "schedule.h"
#include "mem_alloc.h"

/* first come first serve scheduling (fit processes in memory until memory is
 * full, without skipping) */
#define FCFS 0 

/* first fit first serve scheduling (fit as many processes in memory as
 * possible, skipping ones that do not fit (yet)) */
#define FFFS 1 

/* shortest job first serve (in terms of memory) */
#define SJFS 2

/* be random (aka: lottery scheduling) */
#define MONTECARLO 3

/* all of the above, loop over each algorithm repeatedly */
#define MIXED 4

/* to be read from stdin */
int schedule_mode = -1;	

/* flag describing whether mixed mode is enabled. */
int mixed = 0;

/* when true, add ready processes to the front of the queue
 * (fairness would demand them to be queued at the back).
 * Adding them to the front gives low turnaround time but is 
 * unfair to other processes which have been waiting for longer. */
int front = -1;

/* flags for usage of time slices and priorities */
int slices = -1, priorities = -1;

/* This variable will simulate the allocatable memory */
static long memory[MEM_SIZE];


/* remove element from a doubly linked list */
void dequeue(pcb **queue, pcb **element) {
	/* grab the element out of the linked list by making previous and next
	 * point to each other instead of to 'element' */
	if ((*element)->prev != NULL) 
		(*element)->prev->next = (*element)->next;	
	if ((*element)->next != NULL)
		(*element)->next->prev = (*element)->prev;

	/* make queue point to next element */
	if (*queue == *element)
		*queue = (*element)->next; 

	/* detach element from queue */
	(*element)->next = NULL;
	(*element)->prev = NULL;
}

/* add *element to the back of *queue */
void enqueueBack(pcb **queue, pcb **element) {
	pcb *temp;
	
	if (*queue == NULL) { 
		/* if is empty make element first node */
		*queue = *element;
		(*queue)->prev = NULL;
		(*queue)->next = NULL;
	} else {
		/* look for end of queue */
		temp = *queue;
		while(temp->next != NULL)
			temp = temp->next; 
		
		(*element)->prev = temp;
		temp->next = *element;
	}
	(*element)->next = NULL;
}

void enqueueFront(pcb **queue, pcb **element) {
	if (*queue == NULL) { 
		/* if queue is empty make element first node */
		*queue = *element;
		(*queue)->prev = NULL;
		(*queue)->next = NULL;
	} else {
		(*element)->prev = NULL;
		(*element)->next = *queue;
		(*queue)->prev = *element;
		*queue = *element;
	}
}

/* The actual CPU scheduler is implemented here.
 * timeevent should be set to true when the scheduler is being called
 * because of a time slice that has ended. */
static void CPU_scheduler(int timeevent) {
	int length;
	double slice;
	pcb *temp = ready_proc, *temp1, *last;

	if (slices) {
		for (length = 0; temp != NULL; length++)
			temp = temp->next;

		/* length of slice is based on number of processes: */
		slice = 100.0 / length;
		set_slice(slice);

		/* if the scheduler was called because of a time event,
 		 * requeue current process and give the next process a go. */
		if (timeevent && ready_proc != NULL 
			&& ready_proc->next != NULL) {
			temp = ready_proc;
			dequeue(&ready_proc, &temp);
			enqueueBack(&ready_proc, &temp);

			double orig = ((our_admin *)temp->your_admin)->cputime;
			/* stop the cpu timer of the process whose slice just
			 * ended: */
			((our_admin *)temp->your_admin)->
				cputime = sim_time() - orig;
		}
	}

	if (priorities) {
		/* find last process, needed in next loop. */
		temp = ready_proc;
		if (temp == NULL) return;
		while (temp->next != NULL)
			temp = temp->next;
		last = temp;
		temp = ready_proc;
		/* iterate over all processes and move lower priority 
 		 * processes to the back of the queue (ie., sort) */
		while (temp != last) {
			if (((our_admin *)temp->your_admin)->priority == 0) {
				temp1 = temp->next;
				dequeue(&ready_proc, &temp);
				enqueueBack(&ready_proc, &temp); 
				temp = temp1;
			} else
				temp = temp->next;
		}
	}
}

/* The oh-so charitable multi-purpose high-level memory 
 * allocation scheduler (tm) follows: */
static void GiveMemory() {
	int index, length, a, n;
	pcb *proc1, *proc2, *proc3;
	
	proc1 = proc2 = proc3 = new_proc;

	/* iterate over different scheduling modes if enabled. */
	if (mixed)
		schedule_mode = (schedule_mode + 1) % 3;

	/* lottery scheduling needs to know length of queue. */
	if (schedule_mode == MONTECARLO)
		for (length = 0; proc3 != NULL; length++)
			proc3 = proc3->next;

	/* while the queue is not empty: */
	while (proc2) {
		/* Search for a new process that should be given memory. */

		/* shortest job first: */
		if (schedule_mode == SJFS) {
			while (proc1) {
				if (proc1->MEM_need < proc2->MEM_need)
					proc2 = proc1;
				proc1 = proc1->next;
			}

			/* Turning this off is better! This means that each
 			 * process is considered only once.  */
			/* proc1 = new_proc; */
		}
		
		/* draw a random process from the queue: */
		if (schedule_mode == MONTECARLO) {
			n = (int)(rand() % length);
			for (a = 0; a < n; a++)
				proc2 = proc2->next;
		}

		/* try to allocate memory */
		index = mem_get(proc2->MEM_need);
		if(index == -1) {
			/* bail-out behavior */
			if(schedule_mode == FFFS)
				proc2 = proc2->next;
			else
				break;

		} else if (index >= 0) {
			/* Allocation succeeded, now put in administration */
			proc2->MEM_base = index;

			/* move this process to the ready queue */
			dequeue(&new_proc, &proc2);
			length--;
			if (front)
				enqueueFront(&ready_proc, &proc2);
			else
				enqueueBack(&ready_proc, &proc2);
			
			/* add our admin struct. */	
			proc2->your_admin = (our_admin *)
				malloc(sizeof(our_admin));
			((our_admin *)proc2->your_admin)->
				cputime = sim_time();
			((our_admin *)proc2->your_admin)->cpuevents = 1;
			((our_admin *)proc2->your_admin)->iotime = 0;
			((our_admin *)proc2->your_admin)->ioevents = 0;
			/* initial priority is low: */
			((our_admin *)proc2->your_admin)->priority = 0;
			
			proc2 = new_proc;
       		}
	} 
}

/* Here we reclaim the memory of a process after it
  has finished */
static void ReclaimMemory() {
    pcb *proc;

    proc = defunct_proc;
    while (proc) {
        /* Free your own administrative structure if it exists */
        if (proc->your_admin) {
            free(proc->your_admin);
        }
        /* Free the simulated allocated memory */
        mem_free(proc->MEM_base);
        proc->MEM_base = -1;

        /* Call the function that cleans up the simulated process */
        rm_process(&proc);

        /* See if there are more processes to be removed */
        proc = defunct_proc;
    }
}

/* last process in io_proc is going to do IO, init timer */
static void InitIOTime() {
	pcb *temp = io_proc;
	while (temp->next != NULL)
		temp = temp-> next;
	double orig = ((our_admin *)temp->your_admin)->cputime;
	/* stop the cpu timer: */
	((our_admin *)temp->your_admin)->cputime = sim_time() - orig;

	/* start the io timer: */
	orig = ((our_admin *)temp->your_admin)->iotime;
	((our_admin *)temp->your_admin)->iotime = sim_time() - orig;
	((our_admin *)temp->your_admin)->ioevents++;
}

/* last process in ready_proc just finished doing IO, calculate time elapsed.
 * Also check if this process should be re-assigned to a new priority. */
static void GetIOTime() {
	pcb *temp = ready_proc;
	while (temp->next != NULL)
		temp = temp-> next;
	/* stop io timer: */
	double orig = ((our_admin *)temp->your_admin)->iotime;
	((our_admin *)temp->your_admin)->iotime = sim_time() - orig;

	/* restart cpu timer: */
	orig = ((our_admin *)temp->your_admin)->cputime;
	((our_admin *)temp->your_admin)->cputime = sim_time() - orig;
	((our_admin *)temp->your_admin)->cpuevents++;

	/* if this process is doing more IO than CPU, give it high priority: */
	if ((((our_admin *)temp->your_admin)->cputime /
		((our_admin *)temp->your_admin)->cpuevents) <
		1000 * (((our_admin *)temp->your_admin)->iotime /
		((our_admin *)temp->your_admin)->ioevents)) {
		
		((our_admin *)temp->your_admin)->priority = 1;
	} else {
		((our_admin *)temp->your_admin)->priority = 0;
	}

	/* 
	printf("cpu: %f, io: %f\n", 
		((our_admin *)temp->your_admin)->cputime /
		((our_admin *)temp->your_admin)->cpuevents,
		((our_admin *)temp->your_admin)->iotime /
		((our_admin *)temp->your_admin)->ioevents);
	*/
}

/* You may want to have the last word... */
 
static void my_finale() {
    /* Your very own code goes here */
}

/* The main scheduling routine */

void schedule(event_type event) {
    static int first = 1;
    if (first) {
        mem_init(memory);
        finale = my_finale;
        first = 0;

        /* our own initialisation code */
	srand( (unsigned int) time( NULL ));
	while(schedule_mode < 0 || schedule_mode > 4) {
		printf("Which scheduling algorithm to use?\n");
		printf(" (0=FCFS, 1=FFFS, 2=SJFS, 3=MonteCarlo,");
		printf(" 4=mixed): ");
		scanf("%d", &schedule_mode);
	}
	while(front != 0 && front != 1) {
		printf("\nWhere should processes be queued? \n");
		printf(" (0=back, 1=front; back is fair,");
		printf(" front is more responsive): ");
		scanf("%d", &front);
	}
	while(slices != 0 && slices != 1) {
		printf("\nEnable the setting of time slices? \n");
		printf(" (0=no, 1=yes; time slices cause more context");
		printf(" switches, but the system will be more responsive): ");
		scanf("%d", &slices);
	}
	while(priorities != 0 && priorities != 1) {
		printf("\nEnable assigning of priorities? \n");
		printf(" (0=no, 1=yes): ");
		scanf("%d", &priorities);
	}
	printf("\n");
	if (schedule_mode == 4)
		mixed = 1;
    }

    switch (event) {
    case NewProcess_event:
        GiveMemory();
        break;
    case Time_event:
        CPU_scheduler(1);
        break;
    case IO_event:
	InitIOTime();
        CPU_scheduler(0);
        break;
    case Ready_event:
	GetIOTime();
        break;
    case Finish_event:
        ReclaimMemory();
        GiveMemory();
        CPU_scheduler(0);
        break;
    default:
        printf("I cannot handle event nr. %d\n", event);
        break;
    }
}