Scheduler simulator

gentasks.c

/*
 * gentasks.c
 *
 * Driver code for A#3, CSC 360 Summer 2014
 *
 * Prepared by: Michael Zastre (University of Victoria) 2014
 */

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


#define SHORT_TASK_MIN 3
#define SHORT_TASK_MAX 20
#define LONG_TASK_MIN  100
#define LONG_TASK_MAX  250
#define SHORT_LONG_THRESHOLD 0.8

#define SHORT_LOW_PRIORITY 0
#define SHORT_HIGH_PRIORITY 1
#define SHORT_LOW_HIGH_THRESHOLD 0.3

#define LONG_LOW_PRIORITY 3
#define LONG_HIGH_PRIORITY 2
#define LONG_LOW_HIGH_THRESHOLD 0.9

#define ARRIVAL_TIME_RANGE_LARGE 15
#define ARRIVAL_TIME_RANGE_SMALL 5
#define LARGE_SMALL_THRESHOLD 0.5



float generate_task_length()
{
    float short_long_choice = rand();
    float length = rand();

    if ((short_long_choice / RAND_MAX) > SHORT_LONG_THRESHOLD) {
        return (length / RAND_MAX * (LONG_TASK_MAX - LONG_TASK_MIN) + LONG_TASK_MIN);
    } else {
        return (length / RAND_MAX * (SHORT_TASK_MAX - SHORT_TASK_MIN) + SHORT_TASK_MIN);
    }
}


int generate_priority(float length)
{
    float high_low_choice = rand();
    
    high_low_choice /= RAND_MAX;

    if (length <= SHORT_TASK_MAX) {
        if  (high_low_choice < SHORT_LOW_HIGH_THRESHOLD) {
            return SHORT_LOW_PRIORITY;
        } else {
            return SHORT_HIGH_PRIORITY;
        }
    }

    if (length >= LONG_TASK_MIN) {
        if (high_low_choice < LONG_LOW_HIGH_THRESHOLD) {
            return LONG_LOW_PRIORITY;
        } else {
            return LONG_HIGH_PRIORITY;
        }
    }

    /*
     * Why the dickens are we here???
     */
    assert(0);
}


int generate_arrival_interval()
{
    float large_small_choice = rand();
    large_small_choice /= RAND_MAX;

    float length = rand();

    if (large_small_choice < LARGE_SMALL_THRESHOLD) {
        return (int)(length / RAND_MAX * (ARRIVAL_TIME_RANGE_SMALL - 1) + 1);
    } else {
        return (int)(length / RAND_MAX * (ARRIVAL_TIME_RANGE_LARGE - 1) + 1);
    }
}

int main(int argc, char *argv[]) {
    int i;

    if (argc < 3) {
        fprintf(stderr, "usage: %s <number of tasks> <random seed>\n", argv[0]);
        exit(1); 
    }
   
    int num_tasks = atoi(argv[1]);
    int random_seed = atoi(argv[2]);
    srand(random_seed);

    int   task_arrival_time = 0;
    float task_length = 0.0;
    int   task_priority = 0;
    for (i = 0; i < num_tasks; i++) {
        task_arrival_time += generate_arrival_interval();
        task_length = generate_task_length();
        task_priority = generate_priority(task_length);

        printf("%d %d %.1f %d\n", i, task_arrival_time, task_length, task_priority);
    }

    exit(0);
}

Makefile

#
# "makefile" for the CPU scheduler simulation.
#

CC=gcc
CFLAGS=-c -Wall -g -W -std=c99 -ansi -pedantic

all: gentasks simsched

gentasks.o: gentasks.c
	$(CC) $(CFLAGS) gentasks.c

simsched.o: simsched.c
	$(CC) $(CFLAGS) simsched.c

gentasks: gentasks.o
	$(CC) gentasks.o -o gentasks

simsched: simsched.o
	$(CC) simsched.o -o simsched

clean:
	rm -rf *.o gentasks simsched

run.sh

#!/bin/bash
make
num_tasks=`date +%N`
num_tasks=$(echo $num_tasks | sed 's/^0*//')
num_tasks=$(((($num_tasks%3))+4))
random_seed=`date +%N`
random_seed=$(echo $random_seed | sed 's/^0*//')
echo 'num_tasks: '$num_tasks
echo 'rand_seed: '$random_seed
./gentasks $num_tasks $random_seed | ./simsched > fcfs.txt
./gentasks $num_tasks $random_seed | ./simsched -a PS > ps.txt
./gentasks $num_tasks $random_seed | ./simsched -a RR -q 4 > rr.txt
./gentasks $num_tasks $random_seed | ./simsched -a STRIDE -q 1 > stride_q1.txt
./gentasks $num_tasks $random_seed | ./simsched -a STRIDE -q 4 > stride_q4.txt

simsched.c

/*
 * cpusched.c
 *
 * Skeleton code for solution to A#3, CSC 360, Summer 2014
 *
 * Prepared by: Michael Zastre (University of Victoria) 2014
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <limits.h>

#define MAX_LINE_LENGTH 100

#define FCFS	0
#define PS		1
#define RR		2
#define STRIDE	3

#define PRIORITY_LEVELS 4


/*
 * Stores raw event data from the input,
 * and has spots for per-task statistics.
 * You may want to modify this if you wish
 * to store other per-task statistics in
 * the same spot.
 */

typedef struct Task_t {
	int number;
	int arrival_time;
	float length;
	int priority;
	int current_quantum;
	float meter;

	float waiting;
	float finish_time;
	int schedulings;
	float cpu_cycles;
} task_t; 

typedef struct Vector_t
{
	int* data;
	int current_size;
	int total_length;
}vector_t;

typedef struct Node_t
{
	int data;
	struct Node_t* next;
}node_t;

typedef struct List_t
{
	node_t* head;
	node_t* tail;
}list_t;

/*
 * Some function prototypes.
 */

void read_task_data(void);
void init_simulation_data(int);
void first_come_first_serve(void);
void stride_scheduling(int);
void priority_scheduling(void);
void rr_scheduling(int);
void run_simulation(int, int);
void compute_and_print_stats(void);

void vector_init(vector_t*, int);
void vector_print(vector_t*);
void vector_free(vector_t*);
void vector_populate(vector_t*);
void vector_insert(vector_t*, int);
void vector_remove(vector_t*, int);
int vector_empty(vector_t* vector);
int vector_choose_task (vector_t* vector);

void list_init(list_t*);
void list_print(list_t*);
void list_free(list_t*);
void list_populate(list_t*);
void list_insert(list_t*,int);
int list_remove(list_t*);
int list_empty(list_t*);

int vector_task_min_meter(vector_t*);
float vector_min_meter(vector_t*);
int vector_choose_task(vector_t*);

/*
 * Some global vars.
 */
int num_tasks = 0;
task_t *tasks = NULL;

void read_task_data()
{
	int max_tasks = 2;
	int  in_task_num, in_task_arrival, in_task_priority;
	float in_task_length;
	

	assert( tasks == NULL );

	tasks = (task_t *)malloc(sizeof(task_t) * max_tasks);
	if (tasks == NULL) {
		fprintf(stderr, "error: malloc failure in read_task_data()\n");
		exit(1);
	}
	num_tasks = 0;

	/* Given the format of the input is strictly formatted,
	 * we can used fscanf .
	 */
	while (!feof(stdin)) {
		fscanf(stdin, "%d %d %f %d\n", &in_task_num,
			&in_task_arrival, &in_task_length, &in_task_priority);
		assert(num_tasks == in_task_num);
		tasks[num_tasks].number			= in_task_num;
		tasks[num_tasks].arrival_time	= in_task_arrival;
		tasks[num_tasks].length			= in_task_length;
		tasks[num_tasks].priority		= in_task_priority;
/*
		fprintf(stdout, "%2d %3d %5.1f %d\n",
			num_tasks,
			tasks[num_tasks].arrival_time,
			tasks[num_tasks].length,
			tasks[num_tasks].priority);
*/
		num_tasks++;
		if (num_tasks >= max_tasks) {
			max_tasks *= 2;
			tasks = (task_t *)realloc(tasks, sizeof(task_t) * max_tasks);
			if (tasks == NULL) {
				fprintf(stderr, "error: realloc failure in read_task_data()\n");
				exit(1);
			} 
		}
	}
}

void init_simulation_data(int algorithm)
{
	int i;
	for (i = 0; i < num_tasks; i++) {
		tasks[i].finish_time = 0.0;
		tasks[i].schedulings = 0;
		tasks[i].current_quantum = 0;
		tasks[i].cpu_cycles = 0.0;
		if (algorithm == STRIDE)
			tasks[i].meter = 0.0;
	}
}

void first_come_first_serve() 
{
	int current_task = 0;
	int current_tick = 0;

	for (;;) {
		current_tick++;

		if (current_task >= num_tasks) {
			break;
		}

		/*
		 * Is there even a job here???
		 */
		if (tasks[current_task].arrival_time > current_tick-1) {
			continue;
		}

		tasks[current_task].cpu_cycles += 1.0;
		
		if (tasks[current_task].cpu_cycles >= tasks[current_task].length) {
			float quantum_fragment = tasks[current_task].cpu_cycles -
				tasks[current_task].length;
			tasks[current_task].cpu_cycles = tasks[current_task].length;
			tasks[current_task].finish_time = current_tick - quantum_fragment;
			tasks[current_task].schedulings = 1;
			tasks[current_task].waiting = tasks[current_task].finish_time - tasks[current_task].arrival_time - tasks[current_task].length;
			if (tasks[current_task].waiting < 0)
				tasks[current_task].waiting = 0;
/*
			printf("%2d %3d %5.1f %5.1f %5.1f\n",
				current_task,
				tasks[current_task].arrival_time,
				tasks[current_task].length,
				tasks[current_task].waiting,
				tasks[current_task].finish_time);
*/
			current_task+=1;
			if (current_task > num_tasks) {
				break;
			}
			tasks[current_task].cpu_cycles += quantum_fragment;
		}
	}
}

void stride_scheduling(int quantum)
{
	const unsigned long int bigInt = 4294967295UL;

	int current_tick = 0;
	int current_task = 0;
	int previous_task = 0;
	int next_task = 0;
	int last_task = tasks[num_tasks].arrival_time;
	vector_t running_vector;
	unsigned long int temp_meter = 0;
	
	vector_init (&running_vector, num_tasks);

	while (1)
	{
		current_tick++;
/*
		printf("\n[%d]\n", current_tick);
*/

		if (next_task >= num_tasks &&
			current_tick > last_task &&
			vector_empty(&running_vector))
			break;

		/* If there is a new task arriving,
		 * add to the vector,
		 * Choose the next task,
		 * Schedule if necessary. */
		if (tasks[next_task].arrival_time <= current_tick &&
			next_task < num_tasks)
		{
/*
			printf("Task %d(%d) arrived at time %d\n", next_task, tasks[next_task].priority, current_tick);
*/

			/* Giving the new task the min meter in the list */
			tasks[next_task].meter = vector_min_meter (&running_vector);

			/* Adding new task to the running vector */
			vector_insert (&running_vector, next_task);
			next_task ++;

			/* Choose the task to run on cpu */
			current_task = vector_task_min_meter (&running_vector);

			/* If the next task to run on cpu is different than the one that just used the cpu,
			 * that means the previous task are going to be schedule */ 
			if (current_task != previous_task)
				tasks[previous_task].schedulings += 1;
			previous_task = current_task;
		}

		/* If there is a task to run on cpu, else cpu is idle*/
		if (vector_empty(&running_vector))
		{
/*
			printf("Empty!\n");
*/
			continue;
		}
		
		/* If the task reached its the quantum,
		 * and it did not finish,
		 * choose the task with the least meter */
		if (tasks[current_task].current_quantum >= quantum &&
			tasks[current_task].cpu_cycles < tasks[current_task].length &&
			current_task != vector_task_min_meter (&running_vector))
		{
			tasks[current_task].schedulings += 1;
			tasks[current_task].current_quantum = 0;
			current_task = vector_task_min_meter (&running_vector);
		}

		tasks[current_task].cpu_cycles += 1.0;
		tasks[current_task].current_quantum += 1;
/*		
		printf("bigInt %lu\n", bigInt);
		printf("%d\n", tasks[current_task].priority);
		printf("temp_meter %lu\n", temp_meter);
*/
		temp_meter = bigInt/(PRIORITY_LEVELS - tasks[current_task].priority);
		tasks[current_task].meter += (float) temp_meter/bigInt;
/*
		printf("Task %d[%4.1f](%d) missing %5.1f\n", current_task, tasks[current_task].meter, tasks[current_task].current_quantum, tasks[current_task].length - tasks[current_task].cpu_cycles);
*/

		/* If the current task finished */
		if (tasks[current_task].cpu_cycles >= tasks[current_task].length)
		{
			/* Did it use all of the cycle? */
			float quantum_fragment = tasks[current_task].cpu_cycles - tasks[current_task].length;

			/* Store data to do per task statistics */
			tasks[current_task].cpu_cycles = tasks[current_task].length;
/*
			printf("Quantum %5.1f\n", quantum_fragment);
*/
			tasks[current_task].finish_time = current_tick - quantum_fragment + 1;
			tasks[current_task].schedulings += 1;
			tasks[current_task].waiting = tasks[current_task].finish_time - tasks[current_task].arrival_time - tasks[current_task].length;
			if (tasks[current_task].waiting < 0)
				tasks[current_task].waiting = 0;
/*
			printf("%2d %3d %5.1f %5.1f %5.1f\n",
				current_task,
				tasks[current_task].arrival_time,
				tasks[current_task].length,
				tasks[current_task].waiting,
				tasks[current_task].finish_time);
*/
			/* Removing the task that just finished from the running list */
			vector_remove(&running_vector, current_task);

			/* If there is no more tasks to be served, finish it */
			if (next_task > num_tasks &&
				current_tick > last_task &&
				vector_empty(&running_vector))
				break;

			/* Choose the next task to run */
			if (!vector_empty(&running_vector))
			{
				current_task = vector_choose_task (&running_vector);
				tasks[current_task].cpu_cycles += quantum_fragment;
			}
		}
	}
}

void priority_scheduling()
{
	int current_tick = 0;
	int current_task = 0;
	int previous_task = 0;
	int next_task = 0;
	int last_task = tasks[num_tasks].arrival_time;
	vector_t running_vector;
	
	vector_init (&running_vector, num_tasks);

	while (1)
	{
		current_tick++;
/*
		printf("\n[%d]\n", current_tick);
*/
		if (next_task >= num_tasks &&
			current_tick > last_task &&
			vector_empty(&running_vector))
			break;

		/* If there is a new task arriving,
		 * add to the vector,
		 * Choose the next task,
		 * Schedule if necessary. */
		if (tasks[next_task].arrival_time <= current_tick &&
			next_task < num_tasks)
		{
/*
			printf("Arrives task %d(%d)\n", next_task, tasks[next_task].priority);
*/
			/* Adding new task to the running vector */
			vector_insert (&running_vector, next_task);
			next_task ++;

			/* Choose the task to run on cpu */
			current_task = vector_choose_task (&running_vector);

			/* If the next task to run on cpu is different than the one that just used the cpu,
			 * that means the previous task are going to be schedule */ 
			if (current_task != previous_task)
				tasks[previous_task].schedulings += 1;
			previous_task = current_task;
		}

		/* If there is a task to run on cpu, else cpu is idle*/
		if (vector_empty(&running_vector))
		{
/*
			printf("Empty!\n");
*/
			continue;
		}
		
		tasks[current_task].cpu_cycles += 1.0;
/*
		printf("Missing %5.1f to task %d(%d)\n", tasks[current_task].length - tasks[current_task].cpu_cycles, current_task, tasks[current_task].priority);
*/

		/* If the current task finished */
		if (tasks[current_task].cpu_cycles >= tasks[current_task].length)
		{
			/* Did it use all of the cycle? */
			float quantum_fragment = tasks[current_task].cpu_cycles - tasks[current_task].length;

			/* Store data to do per task statistics */
			tasks[current_task].cpu_cycles = tasks[current_task].length;
			tasks[current_task].finish_time = current_tick - quantum_fragment + 1;
			tasks[current_task].schedulings += 1;
			tasks[current_task].waiting = tasks[current_task].finish_time - tasks[current_task].arrival_time - tasks[current_task].length;
			if (tasks[current_task].waiting < 0)
				tasks[current_task].waiting = 0;
/*
			printf("%2d %3d %5.1f %5.1f %5.1f\n",
				current_task,
				tasks[current_task].arrival_time,
				tasks[current_task].length,
				tasks[current_task].waiting,
				tasks[current_task].finish_time);
*/
			/* Removing the task that just finished from the running list */
			vector_remove(&running_vector, current_task);

			/* If there is no more tasks to be served, finish it */
			if (next_task > num_tasks &&
				current_tick > last_task &&
				vector_empty(&running_vector))
				break;

			/* Choose the next task to run */
			if (!vector_empty(&running_vector))
			{
				current_task = vector_choose_task (&running_vector);
				tasks[current_task].cpu_cycles += quantum_fragment;
			}
		}
	}
}

void rr_scheduling(int quantum)
{
	int current_tick = 0;
	int next_task = 0;
	int current_task = 0;
	int last_task = tasks[num_tasks].arrival_time;
	list_t running_list;
	
	list_init (&running_list);

	while (1)
	{
		current_tick++;
/*
		printf("\n[%d]\n", current_tick);
*/

		if (next_task >= num_tasks &&
			current_tick > last_task &&
			list_empty(&running_list))
			break;

		/* If there is a new task arriving,
		 * add to the list.*/
		if (tasks[next_task].arrival_time <= current_tick &&
			next_task < num_tasks)
		{
/*
			printf("Task %d(%d) arrived at time %d\n", next_task, tasks[next_task].priority, current_tick);
*/

			/* Adding new task to the running list */
			list_insert (&running_list, next_task);
			next_task ++;
		}

		/* If there is a task to run on cpu, else cpu is idle*/
		if (list_empty(&running_list))
		{
/*
			printf("Empty!\n");
*/
			continue;
		}
		
		/* If the task reached its the quantum,
		 * and it did not finish,
		 * and the running list has some task waiting besides that task,
		 * remove from the running list and add to the end */
		if (tasks[current_task].current_quantum >= quantum &&
			tasks[current_task].cpu_cycles < tasks[current_task].length &&
			running_list.head->next != NULL)
		{
			tasks[current_task].schedulings += 1;
			tasks[current_task].current_quantum = 0;
			list_insert(&running_list, list_remove(&running_list));
			current_task = running_list.head->data;
		}

		tasks[current_task].cpu_cycles += 1.0;
		tasks[current_task].current_quantum += 1;
/*
		printf("Task %d(%d) missing %5.1f\n", current_task, tasks[current_task].current_quantum, tasks[current_task].length - tasks[current_task].cpu_cycles);
*/

		/* If the current task finished */
		if (tasks[current_task].cpu_cycles >= tasks[current_task].length)
		{
			/* Did it use all of the cycle? */
			float quantum_fragment = tasks[current_task].cpu_cycles - tasks[current_task].length;

			/* Store data to do per task statistics */
			tasks[current_task].cpu_cycles = tasks[current_task].length;
/*
			printf("Quantum %5.1f\n", quantum_fragment);
*/
			tasks[current_task].finish_time = current_tick - quantum_fragment + 1;
			tasks[current_task].schedulings += 1;
			tasks[current_task].waiting = tasks[current_task].finish_time - tasks[current_task].arrival_time - tasks[current_task].length;
			if (tasks[current_task].waiting < 0)
				tasks[current_task].waiting = 0;
/*
			printf("%2d %3d %5.1f %5.1f %5.1f\n",
				current_task,
				tasks[current_task].arrival_time,
				tasks[current_task].length,
				tasks[current_task].waiting,
				tasks[current_task].finish_time);
*/
			/* Removing the task that just finished from the running list */
			list_remove(&running_list);

			/* If there is no more tasks to be served, finish it */
			if (next_task >= num_tasks &&
				current_tick > last_task &&
				list_empty(&running_list))
				break;

			if (!list_empty(&running_list))
				current_task = running_list.head->data;
		}
	}
}

void run_simulation(int algorithm, int quantum)
{
	switch(algorithm) {
		case STRIDE:
			stride_scheduling(quantum);
			break;
		case PS:
			priority_scheduling();
			break;
		case RR:
			rr_scheduling(quantum);
			break;
		case FCFS:
		default:
			first_come_first_serve();
			break;
	}
}

void compute_and_print_stats()
{
	int tasks_at_level[PRIORITY_LEVELS] = {0,};
	float response_at_level[PRIORITY_LEVELS] = {0.0, };
	int scheduling_events = 0;
	int i;

	printf("\n");

	for (i = 0; i < num_tasks; i++) {
		tasks_at_level[tasks[i].priority]++;
		response_at_level[tasks[i].priority] += 
			tasks[i].finish_time - (tasks[i].arrival_time * 1.0);
		scheduling_events += tasks[i].schedulings;

		printf("Task %2d: cpu time (%5.1f), response time (%6.1f), waiting (%6.1f), schedulings (%3d)\n",
			i, tasks[i].length,
			tasks[i].finish_time - tasks[i].arrival_time,
			tasks[i].waiting,
			tasks[i].schedulings);
			
	}

	printf("\n");

	if (num_tasks > 0) {
		for (i = 0; i < PRIORITY_LEVELS; i++) {
			if (tasks_at_level[i] == 0) {
				response_at_level[i] = 0.0;
			} else {
				response_at_level[i] /= tasks_at_level[i];
			}
			printf("Priority level %d: average response time (%5.1f)\n",
				i, response_at_level[i]);
		}
	}

	printf ("Total number of scheduling events: %d\n", scheduling_events);
}


int main(int argc, char *argv[])
{
	int i = 0;
	int algorithm = FCFS;
	int quantum = 1;

	for (i = 1; i < argc; i++) {
		if (strcmp(argv[i], "-q") == 0) {
			i++;
			quantum = atoi(argv[i]);
		} else if (strcmp(argv[i], "-a") == 0) {
			i++;
			if (strcmp(argv[i], "FCFS") == 0) {
				algorithm = FCFS;
			} else if (strcmp(argv[i], "PS") == 0) {
				algorithm = PS;
			} else if (strcmp(argv[i], "RR") == 0) {
				algorithm = RR;
			} else if (strcmp(argv[i], "STRIDE") == 0) {
				algorithm = STRIDE;
			}
		}
	}
		 
	read_task_data();

	if (num_tasks == 0) {
		fprintf(stderr,"%s: no tasks for the simulation\n", argv[0]);
		exit(1);
	}

	init_simulation_data(algorithm);
	run_simulation(algorithm, quantum);
	compute_and_print_stats();

	exit(0);
}


int vector_empty(vector_t* vector)
{
	return vector->current_size == 0;
}

void vector_remove (vector_t* vector, int task)
{
	int i;
	int j;

	assert (vector != NULL);
/*
	printf("Removing (%d)!\n",task);
	printf("Vector Size: %d(%d)\n", vector->current_size, vector->total_length);
*/

	if (vector->current_size <= 0)
	{
		printf("Trying to remove element in an empty vector\n");
		return ;
	}

	for (i = 0; i < vector->current_size; ++i)
	{
		if (vector->data[i] == task)
		{
			for (j = i; j < vector->current_size; ++j)
			{
				vector->data[j] = vector->data[j+1];
			}

			vector->current_size --;
			break;
		}
	}
/*
	vector_print(vector);
*/

	return ;
}

void vector_insert (vector_t* vector, int data)
{
	char errStr [44];
	assert (vector != NULL);
/*
	printf("Inserting (%d)!\n", data);
	printf("Vector Size: %d(%d)\n", vector->current_size, vector->total_length);
*/
	vector->data[vector->current_size] = data;
	vector->current_size++;
	if (vector->current_size > vector->total_length)
	{
		vector->total_length *= 2;
		vector->data = (int*) realloc (vector->data,sizeof(int)*vector->total_length);
		if (vector->data == NULL)
		{
			sprintf (errStr, "malloc failure in vector_insert(vector*,%d):", data);
			perror(errStr);
			exit (0);
		}
	}

/*
	vector_print(vector);
*/

	return ;
}

void vector_init (vector_t* vector, int length)
{
	char errStr [44];
	assert (vector != NULL);

	vector->total_length = length;
	vector->current_size = 0;
	vector->data = (int*) malloc (sizeof(int)*vector->total_length);

	if (vector->data == NULL)
	{
		sprintf (errStr, "malloc failure in vector_init(vector*,%d):", length);
		perror(errStr);
		exit (0);
	}

	return ;
}

void vector_print (vector_t* vector)
{
	int i;
	assert (vector != NULL);
	for (i = 0; i < vector->current_size; ++i)
		printf("%d (%d) | ", vector->data[i], tasks[vector->data[i]].priority);
	printf("\n");

	return ;
}

void vector_free (vector_t* vector)
{
	assert (vector != NULL);

	if (vector->data != NULL)
		free (vector->data);

	return ;
}

int list_empty(list_t* list)
{
	return list->head == NULL;
}

int list_remove (list_t* list)
{
	node_t* temp;
	int data;

	assert (list != NULL);

	if (list->head == NULL)
	{
		fprintf(stderr, "Trying to remove a node_t from an empty list!\n");
		return -1;
	}

	temp = list->head;
	list->head = list->head->next;
	data = temp->data;
	free (temp);

	return data;
}

void list_insert (list_t* list, int data)
{
	node_t* newNode;
	char errStr [44];

	assert (list != NULL);

	newNode = (node_t*) malloc (sizeof(node_t));

	if (newNode == NULL)
	{
		sprintf (errStr, "malloc failure in list_insert(list*,%d):", data);
		perror(errStr);
		exit (0);
	}

	newNode->data = data;
	newNode->next = NULL;

	if (list->head == NULL)
	{
		list->head = newNode;
		list->tail = newNode;
	}
	else
	{
		list->tail->next = newNode;
		list->tail = newNode;
	}

	return ;
}

void list_populate (list_t* list)
{
	assert (list != NULL);
	printf("Populating List\n");
	list_insert(list,4);
	list_insert(list,3);
	list_insert(list,2);
	list_insert(list,1);
	list_insert(list,0);

	return ;
}

void list_init (list_t* list)
{
	list->head = NULL;
	list->tail = NULL;

	return ;
}

void list_print (list_t* list)
{
	node_t* next;
	assert (list != NULL);
	next = list->head;

	while (next != NULL)
	{
		printf("%d\n", next->data);
		next = next->next;
	}

	return ;
}

void list_free (list_t* list)
{
	node_t* next;

	assert (list != NULL);
	next = list->head;

	while (next != NULL)
	{
		list->head = list->head->next;
		free (next);
		next = list->head;
	}

	return ;
}

int vector_choose_task (vector_t* vector)
{
	int i;
	int best;

	for (i = 0; i < vector->current_size; ++i)
	{
		if (i == 0)
			best = vector->data[0];
		else
			if (tasks[best].priority > tasks[vector->data[i]].priority)
				best = vector->data[i];
	}
/*
	vector_print (vector);
	printf("Choosing %d(%d)\n", best, tasks[best].priority);
*/

	return best;
}

int vector_task_min_meter (vector_t* vector)
{
	int i;
	float min_meter;
	int min_task;
	for (i = 0; i < vector->current_size; ++i)
	{
		if (i == 0)
		{
			min_task = vector->data[i];
			min_meter = tasks[vector->data[i]].meter;
		}
		else
		{
			if (tasks[vector->data[i]].meter < min_meter)
			{
				min_meter = tasks[vector->data[i]].meter;
				min_task = vector->data[i];
			}
		}
	}

	return min_task;
}

float vector_min_meter (vector_t* vector)
{
	float min_meter;
	int i;

	if (vector_empty (vector))
		return 0.0;

	for (i = 0; i < vector->current_size; ++i)
	{
		if (i == 0)
			min_meter = tasks[vector->data[i]].meter;
		else
			if (tasks[vector->data[i]].meter < min_meter)
				min_meter = tasks[vector->data[i]].meter;
	}

	return min_meter;
}