Dans ce TD vous allez implémenter différents algorithmes d’ordonnancement étudiés en cours: FCFS, RR, SJF, SRTF; et dans la dernière partie des algorithmes d’ordonnancement temps réel: EDF et RM.

Paquets à installer

Pour pouvoir générer le rapport en LaTeX du simulateur il faut installer les paquets avec la commande suivante,

$ sudo apt-get install --no-install-recommends texlive-fonts-recommended texlive-latex-base texlive-generic-recommended texlive-pstricks texlive-latex-extra texlive-lang-french

Notation

Ce TD est noté. Le travail doit être fait individuellement. Vous pouvez discuter avec d’autres camarades des techniques abordés dans ce TD, mais il est strictement interdit de donner la réponse aux exercices.

Simulateur d’Ordonnancement

Un simulateur d’ordonnancement vous est fourni. Récupérez le à ici.

Pour le décompresser dans votre répertoire TD4, vous utiliserez les commandes suivantes:

    $ cd TD4/
    $ wget https://www.sifflez.org/lectures/SEA/scheduler.tar.gz
    $ tar xvf scheduler.tar.gz
    $ git add *
    $ git commit -m "Simulateur d'ordonnancement fourni"
    $ git push origin master

Ce simulateur d’ordonnancement possède plusieurs commandes. La commande make vous permets de compiler le simulateur et make clean d’effacer les fichiers générés.

La commande make simulate_fcfs vous permets de simuler l’ordonnanceur fcfs. Vous pouvez remplacer fcfs par l’ordonnanceur de votre choix (rr, sjf ou srtf). Lorsque vous exécutez make simulate_fcfs, un fichier preview.ps est crée. Il contient les résultats de votre simulation, vous pouvez l’ouvrir avec la commande evince preview.ps.

Enfin, la commande make rapport vous permets de simuler les quatre ordonnanceurs et de générer le fichier final rapport.ps. Une fois que vous aurez terminé le TD n’oubliez pas de lancer cette commande pour vérifier vos résultats.

Partie I: Ordonnanceurs

1. Modifiez le fichier rapport.tex et changez le champ author avec vos noms et prénoms.

2. Testez la commande make rapport.

Le simulateur est composé de plusieurs fichiers:

• sched.h: décrit les différents types utilisés.
  • tproc: définit un processus, il comporte un pid, un temps d’activation, une durée d’exécution (length) et un champ remaining pour savoir à tout instant combien de temps il reste à exécuter.
  • tnode: un nœud dans une liste chaînée de processus
  • tlist: une liste chaînée de processus
  • tstats: une structure pour comptabiliser différentes métriques (temps de complétion, attente et réponse).
  • tproc: est un type pointeur de fonctions pour les fonctions d’ordonnancement
  • un ensemble de fonctions pour manipuler les listes de processus sont également définies
• list.c: contient l’implémentation des fonction manipulant les listes de processus
  • add: permet d’ajouter un processus en fin de liste
  • del: permet de supprimer un processus
  • Pour l de type tlist*, l->first et l->last permettent d’accéder au premier et dernier éléments de la liste
  • Pour n de type tnode*, n->next permet d’accéder à l’élément suivant dans la liste et n->proc retourne la structure processus.
• sched.c: contient la logique du simulateur
  • ready est une liste avec les processus prêts et proc contient tous les autres processus
  • main: décode les arguments en ligne de commande et charge la description des tâches depuis le fichier task_description.h. Les tâches dans task_description.h sont exactement celles données en exemple en cours. Au départ main ajoute toutes les tâches dans la liste proc. Puis main appelle simulate pour lancer la simulation.
  • simulate: c’est le cœur du simulateur. La boucle externe gère le temps. À chaque pas de temps, les actions suivantes sont déclenchées:
    • On active les processus dont la date d’activation est atteinte. C’est à dire on les déplace de la liste procs vers la liste ready.
    • Si des processus sont prêts, on appelle la fonction scheduler (qui pointe vers un des ordonnanceurs rr, fcfs, etc.)
    • La fonction scheduler choisit un processus qu’elle retourne. Elle écrit également dans delta le nombre d’unités de temps pendant lesquelles le processus sera exécuté.
    • On augmente donc l’horloge de delta.
    • Enfin on supprime les tâches completées (dont le champ remaining est à zéro).
  • randomscheduler: c’est un ordonnanceur exemple
  • fcfs, rr, sjf, srtf: ces fonctions implémentent différents ordonnanceurs. Pour l’instant elles appellent toutes, randomscheduler.

3. Étudiez le code du simulateur, prenez du temps sur cette question car elle vous aidera pour la suite. Il n’y a rien à rendre pour cette question, mais elle est très importante!

4. Décrire le fonctionnement de randomscheduler dans un fichier randomscheduler.txt que vous commiterez dans git.

5. Implémentez la fonction fcfs. Vérifiez que vous trouvez le même ordonnancement qu’en cours.

6. Implémentez la fonction rr. Vérifiez que vous trouvez le même ordonnancement qu’en cours.

7. Implémentez la fonction sjf. Vérifiez que vous trouvez le même ordonnancement qu’en cours.

8. Implémentez la fonction srtf. Vérifiez que vous trouvez le même ordonnancement qu’en cours.

Partie II: Métriques

Vous remarquerez que les statistiques dans l’objet stats sont toujours à zéro.

Votre implémentation doit être indépendante de la fonction d’ordonnancement choisie. Elle ne doit donc pas modifier les fonctions fcfs, rr, sjf et srtf. Vous ne devez normalement modifier que la fonction simulate.

9. Modifiez le simulateur pour comptabiliser le temps total de complétion.

10. Modifiez le simulateur pour comptabiliser le temps total de réponse.

11. Modifiez le simulateur pour comptabiliser le temps total d’attente.

12. Est-ce que les propriétés décrites en cours sont vérifiées ? Écrivez votre réponse dans le fichier proprietes.txt que vous commiterez dans git.

Partie III: Ordonnancement Temps-Réel

Dans cette nous allons étendre le simulateur d’ordonanncement de manière à tester les deux algorithmes d’ordonnancement temps réel étudiés en cours: RM et EDF.

13. Rajoutez une nouvelle cible au Makefile pour générer un fichier rapport avec les ordonnanceurs rm et edf,

rapport_tr: rm.tex rm.source edf.tex edf.source
    latex rapport_tr.tex
    dvips rapport_tr.dvi -f > rapport_tr.ps
    evince rapport_tr.ps

14. Créez également le fichier rapport_tr.tex avec le contenu ci-dessous, remplacez “Prénom Nom” par votre nom.

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais]{babel}
\usepackage{rtsched}
\usepackage{fullpage}
\usepackage{color}
\usepackage{listings}

\author{Prénom Nom}

\lstset{ %
language=C, 
belowcaptionskip=1\baselineskip,
breaklines=true,
frame=L,
xleftmargin=\parindent,
language=C,
showstringspaces=false,
basicstyle=\ttfamily,
keywordstyle=\bfseries\color{green!40!black},
commentstyle=\itshape\color{purple!40!black},
identifierstyle=\color{black},
stringstyle=\color{orange},
numbers=left,
}

\title{T7: Ordonnancement TR}

\begin{document}
\maketitle

\section{RM}
\input{rm.tex}
\lstinputlisting{rm.source}
\section{EDF}
\input{edf.tex}
\lstinputlisting{edf.source}

\end{document}

On travaillera avec des tâches périodiques, dont l’échéance est égale à la période.

15. Pour gérer des tâches temps réel, nous allons modifier la structure tproc de manière à rajouter un champ représentant la periode de chaque tâche. Faites les modifications nécessaires dans le code de manière à que chaque tâche ait un champ period.

    • Si ce champ vaut 0, la tâche est apériodique.
    • Si ce champ vaut t différent de zéro, alors la tâche est périodique de période t.

Pour la suite, les algorithmes RM et EDF ne marcheront que sur des tâches périodiques. Néanmoins, lorsque vous faites des modifications dans le simulateur, vous devrez vous assurer que le code marche encore pour les tâches apériodiques sur les autres ordonnanceurs.

16. Modifiez le fichier task_description.h, de manière à simuler le système de tâches suivant:

int max_time = 40;
tproc tasks[] = {
     //pid  //activation  //length  //remaining  //period
    {1,     0,            1,        1,           3       },
    {2,     0,            1,        1,           4       },
    {3,     0,            2,        2,           6       },
};

17. Modifiez la fonction simulate de manière à gérer les tâches périodiques. Chaque fois qu’une tâche finit, si elle est périodique il faut la redémarrer. Pour cela, il faudra mettre à jour ses champs activation et remaining et la rajouter à la liste des tâches.

18. Implémentez l’ordonnanceur EDF vu en cours.

19. Implémentez l’ordonnanceur RM vu en cours.

20. Testez les différents systèmes de tâches présentés en cours. Obtenez vous les mêmes résultats que moi ?

21. Modifiez la fonction simulate de manière à afficher en rouge l’exécution d’une tâche qui ne satisfait pas son échéance. Pour modifier la couleur d’une exécution de tâche vous pouvez remplacer

            \\TaskExecution{%d}{%d}{%d}
        ```
    
    par
    

    \\TaskExecution[color=red]{%d}{%d}{%d}

    ```

22. Proposez et testez un système de tâche qui est ordonnançable avec EDF et qui n’est pas ordonnançable avec RM.