Systèmes d’Exploitation – Mini-Projet 2

Dans ce MP 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.

Rendu du projet

La date de rendu est fixée au dimanche 12 avril à 23:59.

Lisez attentivement les instructions de rendu suivantes:

Utilisation de Git

Pour ce MP il faut travailler dans le repertoire MP2.

Le serveur de rendu git est inaccessible pendant la période de fermeture de l’université. Vous ne pourrez donc faire un push de vos commits sur le serveur de rendu. Vous pouvez éventuellement utiliser votre propre serveur git (eg. serveur privé sur gitlab.com, mais merci de ne pas mettre votre travail sur un serveur git publique.

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 MP est noté. Le travail doit être fait individuellement. Vous pouvez discuter avec d’autres camarades des techniques abordés dans ce MP, 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 MP2, vous utiliserez les commandes suivantes:

    $ cd MP2/
    $ 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 MP 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:

  1. É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!

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

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

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

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

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

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

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

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

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

  1. 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
  1. Créez également le fichier rapport_tr.tex avec le contenu ci-dessous, remplacez “Premier Nom et Deuxième Nom” par vos deux noms.
\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais]{babel}
\usepackage{rtsched}
\usepackage{fullpage}
\usepackage{color}
\usepackage{listings}

\author{Premier Nom et Deuxième 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.

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

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.

  1. 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       },
};
  1. 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.

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

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

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

  5. 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}
  6. Proposez et testez un système de tâche qui est ordonnançable avec EDF et qui n’est pas ordonnançable avec RM.