Cycle d'ingénieur : GECSI

Semestre : 3
Professeur : Mohamed EL KHAILI

TP n°1 : Structure d’ordonnancement

« HPF et Rate Monotonic »

L'objectif du TP est d'étudier un ordonnanceur à priorités fixes, et en particulier, celui proposé dans
le standard POSIX.4. Ce type d'ordonnanceur est présent dans presque tous les systèmes
d'exploitation et permet une mise en œuvre aisée de la méthode Rate Monotonic. L'étude de cet
ordonnanceur est effectuée au travers d'un petit simulateur en C.

Manipulation I. Ordonnanceurs classiques

Avant de commencer le TP, nous présentons le fonctionnement de ce petit simulateur grâce à deux
ordonnanceurs classiques. Le simulateur est constitué de deux composants :
1. Les fichiers file_de_taches.h et file_de_taches.c qui contiennent la définition
des tâches et des files d'attente. Les informations d'une tâche sont contenues dans un
descripteur de tâches (cf. structure desc_tache). Ces structures sont arrangées en tableau
pour finalement constituer les files d'attente de tâches. Une tâche a un nom symbolique et est
définie par une capacité, une priorité et un instant à partir duquel elle devient prête. Une file
d'attente est décrite par une structure de type file_de_taches. La mise à jour des files
d'attente peut être effectuée par la fonction inserer_file_de_taches qui insère un
élément en queue de liste et retirer_file_de_taches qui retire l'élément en tête de
liste. En outre, la fonction inserer_file_de_taches_ordonnees permet d'insérer
les éléments dans la file dans l'ordre croissant de leur date d'arrivée dans le système.
2. Les fichiers simu_posix.h et simu_posix.c qui contiennent le simulateur à
proprement dit. Le simulateur ordonnance le jeu de tâches contenu dans une ou plusieurs
files d'attente. Il modélise le temps par un entier (la variable horloge). Incrémenter cette
variable correspond à faire avancer le temps d'une unité. Le travail du simulateur consiste
alors à déterminer quelle tâche exécuter pour chaque unité de temps. Les fichiers
simu_posix.h et simu_posix.c contiennent les fonctions suivantes :
 La fonction init_simu() qui initialise le simulateur.
 La fonction tache_aperiodique() qui ajoute dans la ou les files d'attente les
tâches à ordonnancer.
 La fonction ordonnance() qui lance le simulateur. Cette fonction appelle, pour
un nombre de fois donné, la fonction faire_un_pas(). La fonction
faire_un_pas() simule l'ordonnancement pendant une unité de temps.

Question 1 : Ordonnancement de la plus haute priorité d'abord

Dans un premier temps, on vous demande de regarder comment le simulateur fonctionne.
L'ordonnancement implanté dans cette version du simulateur effectue une élection HPF (Highest
TP Structure d’ordonnancement HPF et RM Pr. Mohamed EL KHAILI 1
Priority First) simple On suppose ici qu'il n'existe pas deux tâches ayant une priorité identique. Le
simulateur mémorise les tâches dans deux files d'attente :
1. La file pretes où sont stockées toutes les tâches prêtes.
2. La file bloquees où sont stockées toutes les tâches non prêtes.

Le résultat produit par le simulateur consiste en un affichage à l'écran de la tâche élue pour chaque
unité de temps. On vous demande de :
1. Récuperez les fichiers file_de_taches.h, file_de_taches.c, simu_posix.h
et simu_posix.c qui constituent le simulateur.
2. Récuperez les fichiers test1.c et test2.c. Ceux-ci constituent le jeu d'essai du simulateur.
Chaque jeu d'essai, après avoir initialisé le simulateur (fonction init_simu()), crée un
certain nombre de tâches (fonction tache_aperiodique()), puis lance le simulateur
(fonction ordonnance()).
3. Vous devez compiler puis tester ces deux programmes. Pour ce faire, vous pouvez utiliser le
Makefile suivant : tapez make test1 test2 pour construire la bibliothèque et les
exécutables.
4. Lancez les deux programmes test1 et test2 puis comparez l'ordonnancement généré par
rapport aux tâches passées en entrée du simulateur (cf.tableau ci-dessus). Concernant le
simulateur, vous regarderez plus précisément la fonction faire_un_pas() qui effectue
l'élection de la tâche à chaque instant de la vie du système.

Question 2 : Ordonnancement de type "temps partagé"

On vous demande maintenant de modifier le simulateur. Dans cette question, nous supposons que
toutes les tâches vont être ordonnancées selon le temps processeur qu'elles ont consommé : la tâche
ayant le moins consommé de temps processeur est celle dont la priorité est la plus forte.
L'algorithme est donc à priorité variable (ou dynamique). On fait l'hypothèse que le quantum de
temps utilisé par l'ordonnanceur est d'une unité de temps. En d'autres termes, une tâche à qui l'on a
alloué le processeur, le conserve pendant une unité de temps, puis, une phase d'élection est à
nouveau effectuée. Comme précédemment, les tâches sont stockées dans les files d'attente pretes
et bloquees.
On vous demande :
1. De modifier la fonction faire_un_pas() du fichier simu_posix.c pour que cette
fois-ci, le choix de la tâche à exécuter soit fait sur le critère du temps processeur consommé.
Seule la fonction faire_un_pas() est à modifier.
2. Vous utiliserez les programmes test3.c et test4.c ci-dessus pour valider votre
solution.

Manipulation II. Implantation d'un ordonnanceur POSIX.4

Nous allons maintenant implanter un ordonnanceur POSIX.4. Nous commencons par décrire les
services d'ordonnancement offerts par cette norme (cf. livre de Gallmeister pour plus de détails).
POSIX.4 offre un ordonnancement à priorités fixes. Ce type d'ordonnanceur affecte le processeur à
la tâche prête de plus haute priorité . POSIX.4 impose la présence d'au moins 32 niveaux de
priorité (le niveau de priorité dont le numéro est le plus élevé correspond à celui qui est le plus
prioritaire). Ainsi, sur Linux, il existe 100 niveaux de priorité (de 0 à 99).
A chaque priorité est associée une file d'attente où sont stockées toutes les tâches de même priorité.
TP Structure d’ordonnancement HPF et RM Pr. Mohamed EL KHAILI 2
En effet, contrairement au premier exercice, il n'est pas rare dans une application d'avoir plusieurs
tâches de même priorité : pour qu'une application soit portable, il faut alors qu'il n'existe aucune
ambiguité sur le choix des tâches. C'est pourquoi, la norme POSIX.4 propose la notion de politique
: le classement des tâches dans une file donnée est choisi selon une politique : la politique permet
donc de choisir une tâche parmi un ensemble de tâches de même priorité.
POSIX.4 propose 3 politiques :
1. SCHED_FIFO. Les tâches sont insérées en queue de liste. La tâche en tête de liste obtient le
processeur lorsque celui-ci devient libre. La tâche élue libère le processeur seulement dans
trois cas : lorsqu'elle se termine, lorsqu'elle devient bloquée (ex : E/S), lorsqu'elle libère
volontairement le processeur.
2. SCHED_RR. Le comportement de cette politique est proche de celui de SCHED_FIFO mais
cette fois, une tâche en cours d'exécution ne peut pas dépasser un temps maximal (quantum).
Au bout de ce temps, la tâche libère le processeur et est placée en queue de liste.
3. SCHED_OTHER. Elle dépend de l'implantation des services POSIX.4 sur une machine
donnée. La norme ne spécifie donc rien sur son mode de fonctionnement. Sur Linux, cette
politique correspond à l'ordonnancement temps partagé.

Une implantation de POSIX.4 doit préciser pour chaque politique les niveaux de priorité autorisés
pour la politique en question. Ainsi, sur Linux, le niveau de priorité 0 est dédié à la politique
SCHED_OTHER et les niveaux de priorité 1 à 99 aux politiques SCHED_FIFO et SCHED_RR. Le
simulateur de ce TP offre les mêmes niveaux de priorité.

Question 1 : Implantation de la politique SCHED_FIFO

On vous demande maintenant d'implanter un ordonnanceur POSIX.4 utilisant uniquement la
politique SCHED_FIFO : une file d'attente est associée par priorité et on suppose que toutes les
tâches sont gérées par la politique SCHED_FIFO. On rappelle que si plusieurs tâches possèdent
une priorité identique et quelles sont gérées selon la politique SCHED_FIFO, alors la tâche qui
prend le processeur est celle en tête de liste. La tâche élue relache le processeur lorqu'elle
devient bloquée (dans ce cas, elle est placée en queue de file) ou à sa terminaison (dans ce cas,
elle est supprimée de la liste des tâches prètes).
Vous utiliserez le fichier simu_posix.c-FIFO suivant.
On vous demande :
1. De modifier la fonction faire_un_pas() du fichier simu_posix.c pour que, si
plusieurs tâches de même priorité soient présentes dans le système, la politique
SCHED_FIFO soit appliquée. Seule la fonction faire_un_pas() est à modifier. La zone
à modifier est signalée par des étoiles.
2. Vous utiliserez les programmes test5.c, test6.c et test7.c ci-dessus pour valider
votre solution.

Question 2 : Implantation de la politique SCHED_RR

Dans cette question, on vous demande d'implanter la politique SCHED_RR. Il est conseillé de partir
du fichier simu_posix.c de la question précédente (n'oubliez pas de le sauvegarder avant!).
Comme dans la question 1, on utilise ici une file d'attente par priorité. On rappelle que la politique
SCHED_RR est proche de SCHED_FIFO mais diffère par le fait que la tâche en tête de liste
conserve le processeur pendant une durée ne dépassant pas un quantum. Une fois ce quantum
expiré, la tâche est déplacée en queue de liste. Nous supposerons ici que le quantum est d'une
unité de temps. Pour la manipulation des files d'attente, vous disposez des fonctions
TP Structure d’ordonnancement HPF et RM Pr. Mohamed EL KHAILI 3
retirer_file_de_taches et inserer_file_de_taches.
On vous demande :
1. De modifier la fonction faire_un_pas() du fichier simu_posix.c pour que cette
fois-ci, la tâche élue libère le processeur une fois le quantum expiré. Seule la fonction
faire_un_pas() est à modifier.
2. Vous utiliserez les programmes test8.c, test9.c et test10.c ci-dessus pour valider
votre solution.

Manipulation III. Ordonnancement à priorités fixes et méthode RM

On souhaite maintenant exécuter sur le simulateur un jeu de tâches périodiques conforme au modèle
de Lui et Layland. Pour ce faire, on met à votre disposition la version suivante des fichiers
simu_posix.h-PERIODIQUE, et simu_posix.c-PERIODIQUE. Cette dernière version est
capable d'ordonnancer un jeu de tâches selon les politiques SCHED_OTHER et SCHED_FIFO. La
priorité des tâches SCHED_OTHER est fixée à 0. Celle des tâches SCHED_FIFO peut varier de 1 à
99.
L'application temps réel ciblée est une application embarquée dans un véhicule automobile.
L'application offre des services de navigation (recherche d'itinéraires optimum en temps, en
distance, etc). Elle est constituée de trois tâches périodiques indépendantes :
1. La première traite les informations émises par des satellites GPS. Elle est invoquée toutes les
600 ms. Chaque activation nécessite 80 ms de temps processeur.
2. La seconde tâche consulte un gyroscope qui permet d'évaluer la direction prise par
l'automobile. Sa période est de 100 ms. Son temps d'exécution est borné par 60 ms.
3. Enfin, la dernière tâche lit le compteur de roues toutes les 300 ms. Cette opération nécessite
60 ms de temps processeur.

Questions :
1. On souhaite utiliser la méthode RM (mode préemptif) pour ordonnancer cette application.
Associez à chaque tâche une priorité conforme à Rate Monotonic. On prendra 1 unité de
temps du simulateur = 10 ms de l'application. Vérifier que l'application est ordonnançable.
Toutes les tâches démarrent en même temps (à la date 0 du simulateur). On suppose les
échéances égales aux périodes. Dessinez l'ordonnancement généré sur la période d'étude.
2. Dans un premier temps, on vous demande de regarder le fonctionnement de cette nouvelle
version du simulateur. Vous n'avez aucune ligne de code à ajouter. Compilez et testez le
simulateur avec le jeu d'essais ci-dessous. Comment et où le caractère périodique des tâches
est gérée dans le simulateur ?
3. Complétez et compilez le programme vehicule.c. Ce programme simule l'application décrite
ci-dessus. Dans un premier temps, vous affecterez la priorité 0 à toutes les tâches (ce qui,
implicitement, leurs affectent la politique SCHED_OTHER).
4. Exécutez l'application et notez l'ordonnancement généré. Les contraintes temporelles sont-
elles respectées ?
5. Modifiez le programme vehicule.c de sorte qu'à chaque tâche soit affectée la priorité
déterminée par Rate Monotonic. De façon à utiliser la politique SCHED_FIFO, vous devez
affecter des priorités dans la fourchette de valeur de 1 à 99. Exécutez cette application, puis,
comparez l'ordonnancement généré par rapport à celui qui été prévu dans la question 1 et
celui généré dans la question 4. Que constatez-vous ?

TP Structure d’ordonnancement HPF et RM Pr. Mohamed EL KHAILI 4