• Exercice I. Ordonnanceurs classiques
  
• Exercice II. Implantation d'un ordonnanceur POSIX.4
  
• Exercice III. Ordonnancement à priorités fixes et méthode RM
  
• Corrections
  

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 oeuvre aisée de la méthode Rate Monotonic. L'étude de cet ordonnanceur est effectuée au travers d'un petit simulateur en C.

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

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.

   Programmes	Résultat
   test1.c	res1.txt
   test2.c	res2.txt

   
   
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 :

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.

   Programmes	Résultat
   test3.c	res3.txt
   test4.c	res4.txt

   
   
2. Vous utiliserez les programmes test3.c et test4.c ci-dessus pour valider votre solution.

Exercice II. Implantation d'un ordonnanceur POSIX.4

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é. 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 parmis 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é.

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.

   Programmes	Résultat
   test5.c	res5.txt
   test6.c	res6.txt
   test7.c	res7.txt

   
   
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

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.

   Programmes	Résultat
   test8.c	res8.txt
   test9.c	res9.txt
   test10.c	res10.txt

   
   
2. Vous utiliserez les programmes test8.c, test9.c et test10.c ci-dessus pour valider votre solution.

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

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 ?

   Programmes	Résultat
   test11.c	res11.txt
   test12.c	res12.txt

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. Executez 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 ?

Corrections

• Exercice I, question 2 : simu_posix.c-TS.
• Exercice II, question 1 : simu_posix.c-FIFO.
• Exercice II, question 2 : simu_posix.c-RR .
• Exercice III :
  • Question 1.
  • Question 3 : vehicule.c-SCHED_OTHER .
  • Question 4.
  • Question 5 : vehicule.c-SCHED_FIFO .