Cliquer ici pour imprimer

TP1 - Implémentation du test d'ordonnancabilité pour PFP

L'objectif de ce TP est d'implémenter en C l’analyse d'ordonnançabilité pour les systèmes à priorité fixe préemptifs.

Représenter un Taskset

Dans un fichier taskset.h proposez une structure de donnée permettant de représenter un système de $n$ tâches avec les paramètres $C_i$, $D_i$ et $T_i$. Pour simplifier, nous considérerons le temps comme discret et les valeurs des paramètres des tâches comme des entiers.

Ajoutez ensuite une fonction Taskset* read_taskset(FILE * f); pour lire un taskset depuis un fichier en respectant le format de fichiers :

n # nombre de tache
C1 D1 T1 # parametres de la tache 1
C2 D2 T2 # parametres de la tache 2
... # etc
Cn Dn Tn # parametres de la tache n

La fonction renverra un pointeur vers un taskset alloué dynamiquement, ou NULL en cas d'erreur (fichier mal formé, etc). La fonction affichera également des messages sur la sortie d'erreurs standard (stderr) en cas d'erreurs.

Ajoutez les fonctions void free_taskset(Taskset*); qui libère la mémoire allouée dans read_taskset() et void print_taskset(Taskset*); qui affiche sur la sortie standard le taskset dont l'adresse est passée en paramètre.

Le code de la fonction devra se trouver dans un fichier taskset.c. Une fonction main() sera écrite dans un fichier test.c. Vous proposerez un makefile permettant de compiler votre programme, avec les options -ansi -pedantic -Wall.

Vous pouvez vous référer à ce tutoriel pour la lecture dans un fichier : https://c.developpez.com/cours/poly-c/?page=page_7 et celui ci pour la compilation séparée / makefile : https://gl.developpez.com/tutoriel/outil/makefile/

Condition de charge

Dans des fichiers fa.h / fa.c ajoutez les fonctions :

  • float load(Taskset*); qui calcule la charge du système
  • int is_feasible(Taskset*); qui renvoie 0 lorsque la charge est plus grande que 1, et une autre valeur dans le cas contraire
  • int is_implicit_deadline(Taskset*); qui renvoie 0 si le système n'est pas à échéances implicites, et 1 si il l'est
  • Taskset* any_2_RM(Taskset*); qui modifie un taskset pour réordonner les taches avec l'assignation de priorités RM
  • int is_RM_schedulable(Taskset*); qui renvoie 0 lorsque la condition de charge permet de conclure que le système n'est pas ordonnancable avec RM, 1 si la condition de charge permet de conclure que le système est ordonnancable avec RM, -1 si la condition de charge ne permet pas de conclure.

Analyse du pire temps de réponse

Ajoutez les fonctions :

  • int get_busy_period(Taskset* t, int i);, qui renvoie la busy period de la tâche i. Cette fonction renvoie -1 si la charge est supérieure à 1.
  • int get_nb_critical_job(Taskset* ts, int i, int bp);, qui renvoie le nombre d’instance de la tâche i comprise dans la busy period
  • int get_response_time(Taskset* ts, int i, int k);, qui renvoie le temps de réponse de l’instance k de la tâche i
  • int get_worst_case_response_time(Taskset* ts, int i);, qui renvoie le pire temps de réponse de la tâche i

Vous pourrez avantageusement ajouter une fonction int w(Taskset* t, int i, int t); qui renvoie la demande de niveau $i$ entre $0$ et $t$. Cette fonction vous sera utile pour get_busy_period(); et get_response_time();.

Modifiez ensuite la fonction int is_RM_schedulable(Taskset*); pour qu'elle renvoie 1 lorsque le système est ordonnancable avec RM et 0 dans le cas contraire. la fonction get_worst_case_response_time() ne devra être appelée que si la condition de charge ne suffit pas à conclure.

Ajoutez une fonction similaire int is_schedulable(Taskset*);. La seule différence est qu'elle ne modifie pas le taskset si les priorités ne respectent pas l'ordre RM.

Tester

Proposez des fichiers de tests, incluant les taskset vus en cours et en TD et compléter test.c pour qu'il propose l'analyse de ces taskset.