TP - 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.

Analyse Théorique¶

Soit le jeu de tâches \(\Psi = \{ \tau_1(C_1=3,D_1=5,T_1=5),\tau_2(2,8,9),\tau_3(2,4,12)\}\).

Dessinez le chronogramme de l'ordonnancement de \(\Psi\) avec DM sur l'intervalle \([0,15[\) en supposant une activation synchrone à \(t=0\) de toutes les tâches (ou regardez avec DrawSchedule ou Cheddar).
\(\Psi\) est il ordonnançable par un algorithme à priorités fixes ?
On veut modifier les échéances des tâches pour obtenir \(\Psi^*\) ordonnançable avec RM sans modifier les périodes. Pour cela, calculez les pires temps de réponse de chaque tâche.

Programmation¶

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 et celui ci pour la compilation séparée / makefile.

Indice

Vous pouvez toujours allez voir le code de DrawSchedule sur gitlab pour trouver de l'inspiration...

Condition de charge¶

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

float load(Taskset*); qui calcule la charge du système

Rappels

\(U=\displaystyle\sum_{\forall_i} \frac{C_i}{T_i}\)

int is_feasible(Taskset*); qui renvoie 0 lorsque la charge est plus grande que 1, et une autre valeur dans le cas contraire

Rappels

\(U \leq 1\) est une condition nécessaire de faisabilité

int is_implicit_deadline(Taskset*); qui renvoie 0 si le système n'est pas à échéances implicites, et 1 si il l'est

Rappels

Un système à échéances implicite est un système respectant la condition \(\forall_i D_i = T_i\)

int is_constrained_deadline(Taskset*); qui renvoie 0 si le système n'est pas à échéances contraintes, et 1 si il l'est

Rappels

Un système à échéances contraintes est un système respectant la condition \(\forall_i D_i \leq T_i\)

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.

Rappels

Une condition suffisante pour l'ordonnancabilité avec RM d'un système à échéances implicites est \(U < n(2^{1/n}-1)\)

[bonus] Taskset* any_2_DM(Taskset*); qui modifie un taskset pour réordonner les taches avec l'assignation de priorités DM
[bonus] int is_DM_schedulable(Taskset*); qui renvoie 0 lorsque la condition de charge permet de conclure que le système n'est pas ordonnancable avec DM, 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.

Rappels

Une condition suffisante pour l'ordonnancabilité avec DM d'un système à échéances contraintes est \(\sum_{\forall_i} \frac{C_i}{D_i} < n(2^{1/n}-1)\)

Analyse du pire temps de réponse¶

Ajoutez les fonctions :

int w(Taskset* t, int i, int t); qui renvoie la demande de niveau \(i\) entre \(0\) et \(t\).

Rappels

\(w_i(t) = \displaystyle\sum_{\forall_{k \leq i}} \left \lceil \frac{t}{T_k} \right \rceil \times C_k\)

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.

Rappels

\(BP_i=\displaystyle\min_{t>0} \text{ t.q. } w_i(t) = t\)

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

Rappels

\(Q_i = \left \lceil \frac{BP_i}{T_i} \right \rceil\)

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

Rappels

Si \(i>1\), \(F_i^j= \displaystyle\min_{t>0} \text{ t.q. } w_{i-1}(t) + j \times C_i = t\)
Sinon \(F_1^j = (j-1) \times T_1 + C_1\)
\(R_i^j=F_i^j - (j-1)\times T_i\)

int get_worst_case_response_time(Taskset* ts, int i);, qui renvoie le pire temps de réponse de la tâche i

Rappels

\(R_i = \displaystyle\max_{\forall_{j \leq Q_i}} R_i^j\)

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¶

Vérifiez que votre programme donne les mêmes résultats que votre analyse théorique.