algo.c 11.95 KiB
#include "algo.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <limits.h>
#include "util.h"
#include "list.h"
#include "tree.h"
#include "instance.h"
#include "schedule.h"
/********************************************************************
* event_key_t
********************************************************************/
/**
* @brief
* Une structure qui definit la clé de l'ensemble des événements.
*/
struct event_key_t {
int event_type; // 0 si l'événement correspond à la libération d'une tâche,
// 1 si l'événement correspond à la fin d'exécution d'une tâche
unsigned long event_time;
unsigned long processing_time; // par convention, 0 si l'événement correspond à la fin d'exécution d'une tâche
// sinon, la durée opératoire de la tâche qui va être libérée
char * task_id;
int machine; // par convention, 0 si l'événement correspond à la libération d'une tâche,
// sinon, la machine qui exécute la tâche de l'événement
};
/**
* @brief
* Une énumération qui définit le type d'évènement
*/
enum even_type_e {
EVT_LIBERATION = 0,
EVT_FIN_EXEC,
};
/**
* @brief
*
* @param[in] event_type
* @param[in] event_time
* @param[in] processing_time
* @param[in] task_id
* @param[in] machine
* @return struct event_key_t*
*/
struct event_key_t * new_event_key(int event_type, unsigned long event_time, unsigned long processing_time, char * task_id, int machine) {
struct event_key_t * key = malloc(sizeof(struct event_key_t));
key->event_type = event_type;
key->event_time = event_time;
key->processing_time = processing_time;
key->task_id = strdup(task_id);
key->machine = machine;
return key;
}
/**
* @brief
*
* @param[in] key
* @return int
*/
int get_event_type(const struct event_key_t * key) {
assert(key); return key->event_type;
}
/**
* @brief
*
* @param[in] key
* @return unsigned long
*/
unsigned long get_event_time(const struct event_key_t * key) {
assert(key);
return key->event_time;
}
/**
* @brief
*
* @param[in] key
* @return unsigned long
*/
unsigned long get_event_processing_time(const struct event_key_t * key) {
assert(key);
return key->processing_time;
}
/**
* @brief
*
* @param[in] key
* @return char*
*/
char * get_event_task_id(const struct event_key_t * key) {
assert(key);
return key->task_id;
}
/**
* @brief
*
* @param[in] key
* @return int
*/
int get_event_machine(const struct event_key_t * key) {
assert(key);
return key->machine;
}
/**
* @brief
*
* @param[in] key
*/
void view_event_key(const void * key) {
// A FAIRE
const struct event_key_t* ekey = (const struct event_key_t *) key;
printf("event type: %d, event time: %lu, processing time: %lu, task id: %s, machine: %d\n",
ekey->event_type, ekey->event_time, ekey->processing_time, ekey->task_id, ekey->machine);
}
/**
* @brief
*
* @param[in] key
*/
void delete_event_key(void * key) {
struct event_key_t* ekey = (struct event_key_t *) key;
free(ekey->task_id);
free(ekey);
}
/**
* @brief Comparer deux événements \p a et \p b.
* Les règles de comparaison sont données dans la présentation du cours.
*
* @param[in] a
* @param[in] b
* @return int
*/
int event_preceed(const void * a, const void * b) {
// A FAIRE
const struct event_key_t* Akey = (const struct event_key_t *) a;
const struct event_key_t* Bkey = (const struct event_key_t *) b;
if(Akey->event_time < Bkey->event_time) {
return 1;
}
else{ //tj = tk
//typej = arrivee et typek = fin d execution
if(get_event_type(Akey) == EVT_LIBERATION && get_event_type(Bkey) == EVT_FIN_EXEC ){
return 1;
} else if ((get_event_type(Akey) + get_event_type(Bkey)) == EVT_LIBERATION)
{
//typej = typek = arrivee et pj = pk et j < k
if(get_event_processing_time(Akey) == get_event_processing_time(Bkey)
&& strcmp(get_event_task_id(Akey), get_event_task_id(Bkey)) < 0){
return 1;
}
//typej = typek = arrivee et pj < pk
else if(get_event_processing_time(Akey) < get_event_processing_time(Bkey)){
return 1;
}
}
//typej = typek = fin d execution et mj < mk
else if((get_event_type(Akey) & get_event_type(Bkey) == EVT_FIN_EXEC) && get_event_machine(Akey) < get_event_machine(Bkey)){
return 1;
}
}
return 0;
}
/********************************************************************
* ready_task_key_t
********************************************************************/
/**
* @brief
* Une structure qui définit la clé de la file d'attente avec les "ready tasks".
*/
struct ready_task_key_t {
unsigned long remaining_processing_time;
char * task_id;
};
/**
* @brief
*
* @param[in] remaining_processing_time
* @param[in] task_id
* @return struct ready_task_key_t*
*/
struct ready_task_key_t * new_ready_task_key(unsigned long remaining_processing_time, char * task_id) {
// A FAIRE
struct ready_task_key_t *key = malloc(sizeof(struct ready_task_key_t));
key->remaining_processing_time = remaining_processing_time;
key->task_id = strdup(task_id);
return key;
}
/**
* @brief
* * @param[in] key
* @return unsigned long
*/
unsigned long get_ready_task_remaining_processing_time(const struct ready_task_key_t * key) {
// A FAIRE
assert(key);
return key->remaining_processing_time;
}
/**
* @brief
*
* @param[in] key
* @return char*
*/
char * get_ready_task_id(const struct ready_task_key_t * key) {
// A FAIRE
assert(key);
return key->task_id;
}
/**
* @brief
*
* @param[in] key
*/
void view_ready_task_key(const void * key) {
// A FAIRE
const struct ready_task_key_t *ready_key = (const struct ready_task_key_t *) key;
printf(" remaining processing time: %lu | task id: %s\n", ready_key->remaining_processing_time, ready_key->task_id);
}
/**
* @brief
*
* @param[in] key
*/
void delete_ready_task_key(void * key) {
// A FAIRE
struct ready_task_key_t *ready_key = (struct ready_task_key_t *) key;
free(ready_key->task_id);
free(ready_key);
}
/**
* @brief Comparer deux tâches \p a et \p b de la file d'attente afin de définir la tâche la plus prioritaire.
* Les deux paramètres d'entrée \p a et \p b sont de type struct ready_task_key_t *.
* Les règles de comparaison sont données dans la présentation du cours.
*
* @param[in] a
* @param[in] b
* @return int
*/
int ready_task_preceed(const void * a, const void * b) {
// A FAIRE
struct ready_task_key_t* ta = a;
struct ready_task_key_t* tb = b;
int res = get_ready_task_remaining_processing_time(b) - get_ready_task_remaining_processing_time(a);
if (res == 0)
return strcmp(get_ready_task_id(ta), get_ready_task_id(tb)) < 0;
else
return res > 0;
}
//note: peut etre utiliser strcmp pour comparer les chars ?
/********************************************************************
* The algorithm
********************************************************************/
struct schedule_t * create_schedule(Instance I, int num_m, int preemption, int balanced_tree) {
// A FINIR ! //initialisation
struct schedule_t* ordonnancement = new_schedule(num_m);
struct tree_t* ready_tasks = new_tree(balanced_tree, ready_task_preceed, view_ready_task_key, view_task, delete_ready_task_key, delete_task);
struct tree_t* event_tree = new_tree(balanced_tree, event_preceed, view_event_key, view_task, delete_event_key, delete_task);
//parcourir l'instance
struct list_node_t* node = get_list_head(I);
while(node != NULL){
struct task_t* task = (struct task_t*) get_list_node_data(node);
struct event_key_t* key = new_event_key(EVT_LIBERATION,
get_task_release_time(task), get_task_processing_time(task), get_task_id(task), 0);
tree_insert(event_tree, key, task);
node = get_successor(node);
}
while(get_tree_size(event_tree) != 0){
//Extraire de E l’ ́evenement e correspondant a l’instant t le plus petit
//a verfieier ?
struct tree_node_t* event_node = tree_min(get_root(event_tree)); // recuperation du node a l instant t le plus petit
struct event_key_t* event_key = (struct event_key_t*) get_tree_node_key(event_node);
struct task_t* task = (struct task_t*) get_tree_node_data(event_node); //recuperer la data et la cast en tache
// Si e concerne la libération d'une tache Tj
if (get_event_type(event_key) == EVT_LIBERATION) {
int machine = find_empty_machine(ordonnancement, get_event_time(event_key));
//si il existe une machine Mi libre en t alors
if (machine != -1) {
//Affecter Tj a Mi en t dans S
add_task_to_schedule(ordonnancement, task, machine, get_event_time(event_key), get_event_time(event_key) + get_event_processing_time(event_key));
//Ajouter dans E l’ evenement fin d’execution de la tache Tj
struct event_key_t* end_key = new_event_key(EVT_FIN_EXEC, get_event_time(event_key) + get_event_processing_time(event_key), get_event_processing_time(event_key), get_task_id(task), machine);
tree_insert(event_tree, end_key, task);
}
else if (preemption)
{
int end_time = (get_event_time(event_key) + get_event_processing_time(event_key));
int machine_inter = find_machine_to_interrupt(ordonnancement, get_event_time(event_key), get_event_processing_time(event_key));
if (machine_inter != -1) {
// Verif preemption de tache
struct task_t* caninterrupt = NULL;
struct list_node_t* walk = get_list_head(get_schedule_of_machine(ordonnancement, machine_inter));
while (walk) {
struct schedule_node_t* taskholder = get_list_node_data(walk);
if (get_schedule_node_end_time(taskholder) > end_time) {
caninterrupt = get_schedule_node_task(taskholder);
break;
}
walk = get_successor(walk);
}
// On peut preempter la tache et remplacer l'evenement de fin de tâche
if (caninterrupt) {
int timediff = preempt_task(ordonnancement, machine_inter, end_time);
tree_remove(event_tree, get_task_id(caninterrupt));
struct ready_task_key_t* interkey = new_ready_task_key(timediff, get_task_id(caninterrupt));
tree_insert(ready_tasks, interkey, caninterrupt);
add_task_to_schedule(ordonnancement, task, machine_inter, get_event_time(event_key), get_event_time(event_key) + get_event_processing_time(event_key));
struct event_key_t* end_key = new_event_key(EVT_FIN_EXEC, get_event_time(event_key) + get_event_processing_time(event_key), get_event_processing_time(event_key), get_task_id(task), machine_inter);
tree_insert(event_tree, end_key, task);
}
}
}
else {
//Ajouter Tj dans la file d’attente Q
tree_insert(ready_tasks, event_key, task); }
}
else if(get_event_type(event_key) == EVT_FIN_EXEC) { //sinon si e concerne la fin d’execution d’une tache Tj sur Mi alors
if(get_tree_size(ready_tasks) != 0){ ////si la file d’attente Q n’est pas vide
//Extraire de Q la tache Tk avec la duree la plus courte (regle SPT)
struct tree_node_t* shortest_node = tree_min(get_root(ready_tasks)); //pareil qu'en haut, a verifier
struct ready_task_key_t* shortest_task_key = (struct ready_task_key_t*) get_tree_node_key(shortest_node);
struct task_t* shortest_task = (struct task_t*) get_tree_node_data(shortest_node);
//Affecter Tk a Mi en t dans S
int machine = find_empty_machine(ordonnancement, get_event_time(event_key));
add_task_to_schedule(ordonnancement, shortest_task, machine, get_event_time(event_key), get_event_time(event_key) + get_event_processing_time(event_key));
//Ajouter dans E l’ ́evenement fin d’execution de la tache
struct event_key_t* end_key = new_event_key(EVT_FIN_EXEC, get_event_time(event_key) + get_event_processing_time(event_key), get_event_processing_time(event_key), get_task_id(task), machine);
tree_insert(event_tree, end_key, shortest_task);
if(get_tree_size(ready_tasks) != 0){
tree_remove(ready_tasks, shortest_task_key);
}
}
}
tree_remove(event_tree, event_key);
}
//fin de la fonction, libreation mem des arbres
delete_tree(event_tree, delete_event_key, NULL);
delete_tree(ready_tasks, delete_ready_task_key, NULL);
return ordonnancement;
}