Le langage Ada

F. Singhoff, D. Massé, L. Nana





A partir des machines Linux standards lancées via VirtualBox, pour accéder au compilateur GNAT, ouvrez simplement un shell sur la machine Linux une fois lancée.


Vous diposez ici d'un livre complet sur le langage Ada .


I. Langage et types abstraits



Exercice 1 : Hello world

Récupérez le fichier hello.adb. Compilez le programme grâce à la commande :

gnatmake -g hello



Quels sont les fichiers générés par gnatmake ?


Exercice 2 : les entrées sorties

  1. Récupérez, compilez et testez le programme lire.adb.
  2. Modifiez le programme lire.adb afin de saisir et afficher un type dérivé (nommé angle_degre) du type entier dont les valeurs sont comprises entre 0 et +360.
  3. Dans ce programme modifié, si vous saisissez une chaîne de caractères à la place d'un angle_degre, que se passe t il ?
  4. Ecrire un package Ada angles qui encapsule le code nécessaire à la saisie/affichage des types angle_degre et angle_radian. angle_radian est un type dérivé de float dont les valeurs sont comprises entre 0.0 et +2.0*PI ou PI est une constante fixée à la valeur 3.1456. La spécification de ce paquetage doit contenir le prototype des méthodes Get et Put alors que le corps du paquetage doit contenir leur mise en oeuvre grâce à text_io. Modifiez le programme écrit dans la question 3 afin qu'il utilise le package angles.


Exercice 3 : moyenne d'une suite de nombres


Ecrire un programme Ada qui :



Exercice 4 : paquetage générique : la calculatrice polonaise

Soient les fichiers : piles.ads, piles.adb, et test_pile.adb. Ces fichiers implantent une calculatrice polonaise.

  1. Etudiez et testez les trois fichiers ci-dessus.
  2. Ajoutez deux fonctionnalités : la première implante l'opération de division, la deuxième permet d'inverser le contenu de la pile.
  3. Ajoutez une procédure permettant d'afficher le contenu de la pile.
  4. Dans la correction, quel est le sens de private. Avec la VERSION 1, comment peut on déclarer deux piles ? Avec la VERSION 2, comment peut on déclarer deux piles ? Quelles sont les différences sur ce point entre les deux versions ?



II. Concurrence : tâches, synchronisation et communications


Exercice 5 : tâches anonymes


Ecrire un programme Ada constitué de deux tâches : les tâches tic et tac. Chaque tâche utilise un compteur commun (variable globale à la procédure principale de type entière) et effectue les traitements suivants :



La procédure principale contient une seule instruction qui consiste à initialiser le compteur à zéro.


Exercice 6 : notion de rendez-vous


On souhaite modifier le programme précédent en lui ajoutant une troisième tâche que l'on nommera mutex. L'interface de cette tâche comporte deux entrées : P et V (entrées sans paramètre).


Exercice 7 : types tâches, allocation statique et dynamique
Question 1 :

Ecrire un programme Ada qui :

  1. définit un type tâche element.
  2. déclare statiquement 10 tâches de type element.
  3. Le corps du type tâche element doit afficher un message quelconque à l'écran toutes les secondes.

Question 2 :

Modifier votre programme précédent de sorte que les tâches soient toutes allouées dynamiquement.

En dehors de l'allocation mémoire de la tâche, le comportement du programme de la question 2 est différent du programme de la question 1 : expliquez.


Exercice 8 : rendez-vous avec paramètres, l'instruction select

On souhaite écrire une tâche qui gère une mémoire de calculatrice. Cette mémoire est un entier initialisé à zéro. Les autres tâches consultent et modifient cette mémoire grâce à l'interface suivante: 

task type memoire is 
        entry ajouter(num : in integer);
        entry soustraire(num : in integer);
        entry consulter(num : out integer);
end memoire;
L'entrée ajouter (resp. soustraire) permet d'ajouter (resp. de retrancher) un entier à la mémoire. L'entrée consulter permet de connaître la valeur courante de la mémoire.

  1. Ecrire le corps de la tâche mémoire. Pour simplifier, dans un premier temps, on suppose que la tâche mémoire accepte les rendez vous dans cet ordre : ajouter, soustraire, consulter, et ainsi de suite.
  2. Modifier le corps de la tâche afin qu'elle puisse accepter les rendez-vous dans un ordre quelconque.
  3. Donner une procédure principale illustrant l'utilisation de la tâche mémoire avec une seule tâche de ce type.
  4. Modifier le programme précédent en déclarant un tableau de cases mémoire.




Exercice 9 : types protégés, producteur consommateur

On cherche dans cet exercice à implanter un producteurs/consommateurs. Producteurs et consommateurs échangent des données via un tampon. Le tampon peut mémoriser quatre entiers maximum. Un producteur insère les données entier par entier. Un consommateur retire les données entier par entier. Le tampon est géré de façon FIFO. Avec Ada, un tel tampon est implanté par un tableau d'entiers.

  1. Dans un premier temps, on vous demande de proposer un programme Ada qui implante cette synchronisation pour un seul producteur et un seul consommateur. Pour ce faire :
  2. Modifier votre programme de sorte que plusieurs consommateurs et plusieurs producteurs puissent manipuler le tampon. On suppose toujours que le producteur insère les données entier par entier et que le consommateur retire les données entier par entier. Le tampon est toujours géré de façon FIFO.
  3. Une autre façon d'implanter un producteur-consommateur consiste à directement implanter le tableau au sein du type protégé. Proposez un dernier programme utilisant un type protégé qui offre un accès synchronisé à un tampon. La signature du type protégé est la suivante : 

    Taille_Buffer : constant Integer :=4;
type Buffer_Type is array (1..Taille_Buffer) of Integer;
   
protected type Buffer is
   entry Produire(Val : in Integer);
   entry Consommer(Val : in out Integer);
private
   -- Les donnees du tampon
   Data : Buffer_Type;
   -- Indices de production et consommation
   Index_Cons : Integer :=1;
   Index_Prod : Integer :=1;
   -- Nombre d'element dans le tampon
   Nb_Element : Integer:=0;
end Buffer;


    Le type protégé doit donc :
    1. offrir dans sa partie publique deux entrées permettant de lire et d'écrire un entier dans/depuis le tampon déclaré au sein du type protégé.
    2. stocker dans sa partie privée le tableau d'entier ainsi que les indices permettant aux producteurs et consommateurs d'accéder à leurs données.



III. Temps réel



Dans l'exercice 10, la compilation croisée d'un programme Ada pour une cible RTEMS/Leon est présentée. Par la suite, dans les exercices 11 et 12, on regarde comment implanter une application temps réel avec Ada.



Exercice 10 : compilation-croisée

Dans cet exercice, on va comparer les Runtimes "Linux/Intel 386" et "RTEMS/Leon". Soit les fichiers suivants. Récupérez ces fichiers et stockez les dans un répertoire unique.

  1. Compilez le programme hello.adb avec la commande gnatmake -g hello.adb.
  2. Lancez la commande file hello : que signifit les différentes informations affichées ?
  3. Lancez le programme et vérifiez que le programme réalise effectivement la sortie écran attendue.


  4. On utilise maintenant une autre Runtime pour exécuter ce programme simple : une runtime destinée à exécuter des programmes Ada sur un processor Leon hébergeant le système d'exploitation temps réel RTEMS. Pour ce faire:
  5. Récupérez le fichier rtems.bash, puis, tapez la commande source rtems.bash. Vous avez maintenant accès à un environnement Ada pour processor Leon.
  6. Compilez à nouveau le programme hello.adb mais avec cette nouvelle commande: 
    make clean
make
  7. Cette nouvelle compilation produit un exécutable nommé hello.obj.
  8. Lancez la commande file hello.obj. Que signifit les différentes informations affichées ?
  9. Lancez le programme hello.obj dans le shell courant. Que se passe t il ? Pourquoi ?
  10. Pour être exécuté, ce programme doit être lancé sur une carte Leon/RTEMS. N'ayant pas ce type de carte, nous allons utiliser le simulateur tsim (logiciel donné gracieusement par la société Gaisler Research, http://www.gaisler.com) :



Exercice 11 : ordonnancement à priorité fixe


Attention : pour cet exercice, vous devez utiliser le compilateur Ada pour Leon/RTEMS ainsi que le simulateur tsim.
Dans cet exercice, nous allons manipuler l'ordonnancement à priorité fixe avec Ada. Récupérez ces fichiers et stockez les dans un répertoire unique nommé EXO11.

  1. Regardez le fichier gnat.adc. Quelle est la signification des divers pragmas spécifiés dans ce fichier ?
  2. Dans le programme scheduling.adb, affectez la priorité 12 à la tâche Tache_A, la priorité 11 à la tâche Tache_B et la priorité 13 à la procédure principale.
  3. Compilez le programme scheduling.adb avec la commande make.
  4. Observez l'ordonnancement de ces tâches grâce à tsim.
  5. Changez les priorités des tâches en affectant un niveau de priorité identique pour toutes les tâches, puis, en inversant les niveaux de priorités. A chaque fois, exécutez le programme et regardez les différents ordonnancements générés.
  6. Ajouter dans la boucle de chaque tâche l'instruction delay 1.0. A quoi sert cette instruction ? Exécutez à nouveau le programme : que constatez vous concernant l'ordonnancement des tâches ?


Exercice 12 : mise en oeuvre d'un jeu de tâches périodiques

Attention : pour cet exercice, vous devez utiliser le compilateur Ada pour Leon/RTEMS ainsi que le simulateur tsim.


  1. Soient trois tâches périodiques dont les paramètres sont :
  2. Donner le chronogramme d'ordonnancement de ces tâches sur la période d'étude. On suppose ici un ordonnancement à priorité fixe préemptif avec une affectation des priorités selon Rate Monotonic.
  3. Récupérez ces fichiers et stockez les dans un répertoire unique nommé EXO12.
  4. On vous demande de compléter ces programmes afin de créer les tâches périodiques ordonnancées selon la méthode Rate Monotonic. On vous demande de compléter la procédure principale (fichier periodiques.adb) ainsi que le fichier generic_periodic_task.adb. Les zones à compléter sont signalées par des étoiles.
    Le travail à faire concernant la procédure principale est le suivant : Le travail à faire concernant generic_periodic_task.adb est le suivant :
  5. Vous testerez l'application avec tsim.




IV. Exercices supplémentaires





Exercice 13 : les exceptions Ada



On souhaite expérimenter, dans cet exercice, les exceptions Ada.

On vous demande d'écrire un programme qui permet à l'utilisateur de saisir des commandes à envoyer vers un robot. Les commandes sont définies de la façon suivante :

type commandes is (a_droite, a_gauche, avancer, reculer);

Le programme doit :

Exercice 14 : tableaux non contraints

  1. Soit le programme tab.adb qui résume les principaux attributs concernant les tableaux contraints ou non. Qu'affichera ce programme à l'écran ? Expliquer le rôle de chaque attribut utilisé ?
  2. Soit un paquetage qui permet de multiplier des matrices. La spécification de ce package est contenue dans le fichier matrices.ads. Ecrire l'implémentation du package matrice.adb.
  3. Testez le package matrices.ads avec ce programme.




Exercice 15 : table de hachage



Soit la spécification Ada du package hashs.ads : 

with Ada.Strings.Unbounded;
use Ada.Strings.Unbounded;



generic
   Size : Positive := 100;  
   type Data_Type is private; 

   with function Compute_Hash (
         Key  : in     Unbounded_String ) 
     return Natural; 
   with procedure Put (
         D : Data_Type ); 


package Hashs is


   type Hash is private; 


   procedure Initialize (
         H : in out Hash ); 

   procedure Add (
         H     : in out Hash;             
         Key   : in     Unbounded_String; 
         D     : in     Data_Type         ); 

   function Consult (
         H     : in     Hash;            
         Key   : in     Unbounded_String ) 
     return Data_Type; 

   procedure Put (
         H : in     Hash ); 


   -- Exception levee par "Consult" si la clef
   -- n'est pas trouve dans la table
   -- 
   Data_Not_Found : exception;


private


   type Cell; 
   type Link is access Cell; 


   type Cell is 
      record 
         Next   : Link;  
         Key    : Unbounded_String;  
         A_Data : Data_Type;  
      end record; 


   type Hash is array (1 .. Size) of Link; 


end Hashs;


Fonctionnement de l'application :

On souhaite mettre en oeuvre un paquetage générique implantant une table de hash. Ce paquetage est utilisé par un programme qui stocke un dictionnaire.

Une table de hash est une structure de donnée permettant d'accéder rapidement a des données. Ici, il s'agit d'un tableau de taille fixe. Une liste chaînée est associée à chaque entrée de ce tableau (cf. figure ci-dessous).


Figure 1. Une table de hachage utilisant une liste pour la gestion des collisions


L'information a mémoriser est constituée d'une clef associée à une information. Ainsi, dans l'exemple du dictionnaire, le clef constitue le mot à mémoriser et l'information constitue la définition de ce mot.
On suppose dans cet exercice que la clef est une chaîne de caractères. A partir de la clef, on calcule un indice dans le tableau. La fonction qui calcule l'indice est appelée "fonction de hachage". Lorsque l'application de la fonction de hachage sur deux clefs différentes implique le stockage de deux informations sur le même indice du tableau, on utilise une liste chaînée pour stocker les informations au même indice du tableau : on parle alors de "collision".

Ainsi dans l'exemple de la Figure 1, la fonction de hachage utilisée appliquée à la clef "Zone" renvoit l'indice 4, à la clef "Sigle" renvoit 5, "Décalé" renvoit 6, ...

La paquetage Ada que nous cherchons à écrire peut utiliser n'importe quelle fonction de hachage grâce au paramètre compute_hash. En outre, le paquetage peut mémoriser n'importe quel type de données et autorise la modification de la taille de la table lors de l'instanciation du paquetage.




Travail à faire:

  1. Récupérez le fichier test_hashs.adb. et hashs.ads.
    test_hashs.adb est un exemple d'utilisation du paquetage générique. La fonction de hachage utilisée ici est basée sur la taille de la clef.
  2. Ecrire l'implantation du package hashs.adb. Les procédures/fonctions à écrire sont les suivantes :
    1. Add : ajoute dans la table H l'information D avec le clef Key.
    2. Consult : retourne l'information associée à la clef Key dans la table H .
    3. Initialize : vide la table H (initialise chaque entrée de la table à null )
    4. Put : sortie à l'écran du contenu de la table (clef et donnée associées).
  3. Testez votre paquetage avec la procédure principale test_hashs.adb.
  4. Modifiez ces unités de programme de sorte que le paquetage hashs.ads/adb puisse utiliser des clefs de n'importe quel type, et non pas seulement des chaines de caractères.




Exercice 16, synchronisation par rendez-vous : le pipe-line

On souhaite écrire un programme Ada qui convertit un nombre de la base 10 à la base 2. Cette conversion est effectuée grâce à un pipe-line de 8 étages. Chage étage est une tâche Ada. L'interface d'un étage est la suivante : 

  type Etage; 
  type Etage_Ptr is access Etage; 

  task type Etage is
      entry Etage_Suivant (
            Tache : in     Etage_Ptr ); 
      entry Divise (
            Valeur : in     Natural ); 
  end Etage;

Chaque étage/tâche contient deux entrées :

Ecrire le corps de la tâche Etage ainsi qu'une procédure principale qui
  1. Alloue dynamiquement et initialise un pipe-line de 8 étages.
  2. Permet la saisie d'un nombre entier en base 10 et envoie ce nombre au premier étage du pipe-line afin de le convertir.



Exercice 17 : statistiques

On vous demande d'écrire un programme permettant à un opérateur de mémoriser le nombre d'homme et de femme qui rentrent dans un centre commercial.

Le programme Ada est constitué de trois tâches : d'une tâche nommée horloge, d'une tâche nommée moyenne et de la procédure principale.

La tâche moyenne contient trois entrées :

  1. L'entrée un_homme permet à la procédure principale d'indiquer à la tâche moyenne qu'un homme vient d'entrer dans le centre commercial.
  2. L'entrée une_femme permet à la procédure principale d'indiquer à la tâche moyenne qu'une femme vient d'entrer dans le centre commercial.
  3. L'entrée seconde permet à la tâche moyenne de mesurer le temps qui s'écoule depuis le début de la mesure.

La tâche horloge invoque approximativement toutes les secondes l'entrée seconde de la tâche moyenne afin d'avertir cette derniere qu'un seconde vient de s'écouler.

A chaque fois que les entrées un_homme et une_femme sont invoquées, la tâche moyenne doit afficher le nombre moyen, par seconde, d'homme et de femme entrés dans le centre commercial.

Enfin, la procédure principale permet à l'opérateur de saisir l'arrivée d'un homme, ou d'une femme.


Exercice 18 : simulation de stations

On souhaite écrire un programme qui simule, par des tâches Ada, des machines (ou stations) qui échangent des messages. Le programme est constitué d'une procédure principale qui saisit des entiers et envoie chaque entier à l'ensemble des stations. Les stations sont simulées par des tâches dont l'interface est la suivante : 


  
   task type Station is
      entry Numero (
            Num : in     Integer ); 
      entry Recevoir_Message (
            Msg : in     Integer ); 
   end Station;


Votre programme doit fonctionner de la façon suivante :




Exercice 19 : Tri concurrent d'un tableau

Première partie : paquetage générique

Dans cet exercice, on se propose d'étudier un paquetage permettant de manipuler des tableaux. On considère un paquetage défini par l'interface suivante : 

package tables is 

        size : constant natural := 10;

        type table_range is range 1..size;
        type table is array (table_range) of integer;

        procedure initialize(tab : in out table, val : in integer);
        procedure put(tab : in table);
        procedure sort(tab : in out table); 
end tables;



Le paquetage décrit un type tableau sur lequel trois opérations peuvent être effectuées : initialisation, affichage et tri. La procédure initialize affecte à chaque élément du tableau la valeur val. La procédure put effectue l'affichage du tableau sur la sortie standard. Enfin, la procédure sort trie dans l'ordre croissant les éléments du tableau.



La méthode de tri fonctionne de la façon suivante :

  1. On compare deux éléments adjacents du tableau et on échange leur contenu s'ils ne sont pas correctement ordonnés.
  2. L'opération(1) est effectuée séquentiellement sur tous les éléments du tableau.
  3. On recommence l'opération (2) lorsqu'au moins une permutation a été effectuée à l'itération précédente.


Question 1.1 : Donnez l'implantation du paquetage ci-dessus.



On souhaite construire un nouveau paquetage tables qui fonctionne pour tous les types (scalaire ou non, numérique ou non). Ce paquetage générique doit offrir les mêmes fonctionnalités que le paquetage tables initial et doit être paramétré par la taille du tableau.



Question 1.2 : Donnez la spécification et l'implantation du paquetage générique.



Deuxième partie : tri parallèle version 1

L'algorithme de tri choisi étant peu efficace, on souhaite modifier le paquetage tables afin de bénéficier d'une éventuelle machine d'exécution multi-processeurs. Pour ce faire, le tri va être réalisé par plusieurs tâches Ada. On divise un tableau en N partitions (N étant un paramètre supplémentaire du paquetage générique). Pour simplifier, on suppose que la taille du tableau est multiple de N. Chaque partition est triée par une tâche selon l'algorithme décrit dans la première partie. Lorsque toutes les tâches ont terminé de trier leur partition, la procédure sort effectue un interclassement des partitions triées afin d'obtenir finalement le tableau trié.



Question 2.1 : Ecrire la procedure sort_partitions, dont la signature est : 

procedure sort_partitions(tab : in out table; from, to : table_range);
La procédure sort_partitions trie les éléments du tableau tab compris entre les éléments from et to (from et to sont inclus dans le tri).



Question 2.2 : On suppose que la procédure d'interclassement des partitions triées est donnée. Sa signature est la suivante : 

procedure merge_partitions(sorted_table : in out table; sorted_partitions : in table);
merge_partitions prend en entrée un tableau sorted_partitions contenant des partitions triées et renvoit dans sorted_table un tableau complètement trié.

Proposer une nouvelle implantation de la procédure sort afin d'effectuer le tri comme il est décrit ci-dessus. Vous n'utiliserez pas d'objet ou de type protégé.



Troisième partie : tri parallèle version 2

La technique de tri précédente est pénalisée par le temps nécessaire à l'interclassement des partitions. En effet, cette dernière opération reste séquentielle et l'on souhaite augmenter encore le parallélisme de la procedure sort.

On découpe toujours le tableau en N partitions. Chaque partition continue a être triée par une tâche.

Toutefois, dans cette nouvelle version, les extrémités de chaque partition sont partagées entre les tâches adjacentes. Ainsi : Les cases 5,6,10 et 11 sont donc partagées par plusieurs tâches (cf. figure ci-dessus). Avec cette nouvelle méthode, la procédure sort n'a plus besoin d'interclasser les différentes partitions.

Question 3.1 Donnez une implantation de la procédure sort afin d'effectuer le tri comme il est décrit ci-dessus. Vous n'utiliserez pas d'objet ou de type protégé.




Exercice 20 : Arbre binaire et paquetages génériques

Dans cet exercice, nous explorons les arbres binaires en Ada.



Question 1 :

Ajouter dans le paquetage arbre.ads une procédure put qui affiche les informations de tous les noeuds d'un arbre. Le procédure put doit parcourir l'arbre binaire de façon similaire à la fonction somme. Vous donnerez une procédure principale permettant de tester votre procédure.

Question 2 :

Le paquetage arbre.ads de cet exercice permet de mémoriser des informations de type integer uniquement.

Proposez une version générique de ce paquetage permettant d'étendre son utilisation à d'autres types de données pour lesquels les opérations d'affectation et de comparaison sont possibles (entiers, réels, ....). Le paquetage a fournir pour cette question doit contenir la procédure Put et la fonction somme. Vous donnerez une procédure principale permettant de tester votre paquetage générique sur un arbre dont les noeuds mémorisent des valeurs de type réel. Notez que la fonction somme utilise l'opérateur + qui n'est disponible que pour quelques types susceptibles d'être utilisés pour l'instanciation (integer, float, ...) et qui devra être remplacé par un paramètre du générique.



Exercice 21 : Parallélisation d'un programme Ada

Dans cet exercice, nous regardons comment transformer un programme séquentiel en un ensemble de tâches Ada afin d'améliorer les performances du programme.

Récupérer puis compiler et tester ce programme Ce programme fait la somme de deux matrices A et B, puis, mémorise le résultat de cette opération dans la matrice C avant de l'afficher à l'écran.

Dans ce programme, une matrice est un tableau à deux dimmensions comportant 3 lignes et 3 colonnes. Notez comment en Ada nous accédons à un élément dans un tableau à deux dimmensions : A(i,j) permet de récupérer l'élément en ligne i et en colonne j du tableau A. Enfin, la procédure add_ligne permet d'ajouter une ligne donnée de deux matrices Operande1 et Operande2, puis, de mémoriser le résultat dans une matrice Resultat.

On vous demande de modifier ce programme afin d'exécuter l'addition de chaque ligne des matrices par une tâche Ada différente. Ceci doit permettre d'accélerer les calculs lorsque la matrice est grande. Pour ce faire, on vous demande d'implanter le fonctionnement ci-dessous.

La procédure principale doit appliquer l'algorithme suivant :



Exercice 22 : mise en oeuvre d'une FIFO


La spécification ci-dessous décrit un type abstrait générique implantant une file d'attente de type FIFO. On rappelle que dans une FIFO, les éléments à insérer le sont en queue de la FIFO et les éléments à retirer le sont en tête de la FIFO.

L'interface ci-dessous est paramétrée par deux informations : la taille maximale de la FIFO qui est par défaut de 10000 éléments et le type des éléments stockés dans la FIFO. 
generic 
        type element is private;
        size : natural := 10000;
        ****  à eventuellement compléter ****
		
package fifo is 
		
        procedure inserer_en_queue(e : in element);
        procedure retirer_en_tete(e : out element);
        procedure put;
        procedure clean;
		
end fifo;


Question 1 :



Question 2 :

Le paquetage ci-dessus a été concu pour être utilisé sans tâche Ada, en dehors de la procédure principale. Quels problèmes classiques posent l'accès direct à une instance du paquetage fifo par plusieurs tâches ? Vous décrirez un scénario d'ordonnancement qui illustre ces problèmes.

Question 3 :

Proposez un nouveau programme Ada utilisant une nouvelle version du paquetage ci-dessus et constitué de 5 tâches :





Projet noté 2015/2016 : mise en oeuvre de protocoles d'héritage de priorité



L'objectif du projet est d'implanter un logiciel pour simuler l'ordonnancement d'un jeu de tâches périodiques manipulant des resources partagées. On vous donne une première version de ce logiciel. Ce logiciel est constitué de plusieurs paquetages et permet d'ordonnancer un ensemble de tâches périodiques selon Rate Monotonic. Le logiciel est disponible ici.

Pour compiler et exécuter ce programme, vous devez utiliser le compilateur sur Linux qui est accessible par la commande suivante :

source ada.csh.



Ce programme est composé des paquetages suivants:

La procédure principale main est un exemple d'utilisation de ces paquetages. Ce programme définit 3 tâches pour lesquelles l'ordonnancement va être calculé.

Travail à faire:

Pour ce projet:

Question 1 : test du simulateur

  1. On suppose un jeu de tâches périodiques défini par les paramètres suivants: S1=S2=S3=0, P1=5, C1=1, P2=10, C2=3, P3=30 et C3=8. Calculer manuellement l'ordonnancement selon un algorithme preemptif Rate Monotonic. Le jeu de tâches est il ordonnançable ?
  2. Modifiez main.adb afin d'exécuter le jeu de tâches ci-dessus, compilez et testez ce programme. Vérifiez que l'ordonnancement généré par ce programme est identique à celui que vous aviez calculé à la main lors de la question précédente.
  3. Dans la procédure principale main.adb et le fichier scheduler.adb, trouvez :
Question 2 : implanter la prise en compte de ressource partagée avec des sémaphores

Modifier le programme afin d'implanter le concept de sémaphore. On cherche ici à simuler un ensemble de tâches périodiques accédant à une ressource critique protégée par un sémaphore. Chaque sémaphore doit permettre d'établir une section critique. On suppose dans cette question que les sémaphores n'implante pas d'héritage de priorité. Vous expliquerez votre mise en oeuvre dans votre rapport. Par ailleurs, vous testerez votre programme avec au moins trois jeux de tâches dont un au moins qui conduit à une inversion de priorité. Vous décrirez ces jeux de tâches et leur ordonnancement dans votre rapport. Pour chaque ordonnancement calculé, l'outil doit aussi indiqué les instants où les ressources partagées sont allouées et libérées ; c-à-d quand le sémaphore est alloué, libéré et quand une tâche est bloquée sur un sémaphore modélisant une ressource déjà allouée.

Pour rappel : le cours d'ordonnancement ainsi que le TD associé contient un exemple de jeu de tâche conduisant à une inversion de priorité.

Question 3 : implantation de PIP et de PCP

Pour cette dernière question, on vous demande d'implanter les protocoles PIP et PCP dans le simulateur. Ces protocoles sont décrits dans ce document. Vous pouvez lire ce document afin d'étudier ces deux protocoles avant de les implanter dans votre simulateur. Par ailleurs, pour rappel, le cours d'ordonnancement ainsi que le TD associé contient un exemple d'ordonnancement PIP (exercice 9) ainsi qu'un exemple avec PCP (exercice 12). Vous avez le droit d'utiliser toute ressource documentaire afin de comprendre comment fonctionne PIP et PCP.

Pour cette dernière question, on vous demande d'ajouter dans votre rapport:





Projet noté 2013/2014 : mise en oeuvre d'un serveur apériodique



L'objectif du projet est d'implanter un logiciel pour simuler l'ordonnancement d'un jeu de tâches apériodiques grâce à divers serveurs de tâches apériodiques. On vous donne une première version de ce logiciel. Ce logiciel est constitué de plusieurs paquetages et permet d'ordonnancer un ensemble de tâches périodiques. Le logiciel est disponible ici.

Pour compiler et exécuter ce programme, vous devez utiliser le compilateur sur Linux qui est accessible par la commande suivante :

source ada.csh.



Ce programme doit être exécuté sur Linux.

Ce programme est composé des paquetages suivants:

La procédure principale main est un exemple d'utilisation de ces paquetages. Ce programme définit 3 tâches ordonnancées selon Rate Monotonic.

Travail à faire:

Pour ce projet: Question 1 : test du simulateur

  1. On suppose un jeu de tâches périodiques défini par les paramètres suivants: S1=S2=S3=0, P1=5, C1=1, P2=10, C2=3, P3=30 et C3=8. Calculer l'ordonnancement selon un algorithme preemptif Rate Monotonic. Le jeu de tâches est il ordonnançable ?
  2. Modifiez main.adb afin d'exécuter le jeu de tâches ci-dessus, compilez et testez ce programme. Vérifiez que l'ordonnancement généré par ce programme est identique à celui que vous aviez calculé à la main lors de la question précédente.
  3. Dans la procédure principale main.adb et le fichier scheduler.adb, trouvez :
Question 2 : implanter le serveur à scrutation

Modifier le programme afin d'implanter le serveur à scrutation (ou "polling server"). On rappelle que le serveur à scrutation ordonnance des tâches apériodiques de la façon suivante (cf page 20 du cours sur l'ordonancement temps réel):
  1. Le serveur exécute les tâches apériodiques arrivées avant le reveil du serveur.
  2. Si au réveil du serveur, aucune tâche apériodique n'est présente, alors le serveur ne consomme aucune unité de temps.
  3. A chacun de ses réveils, le serveur ne peut consommer plus que sa capacité, et ce quelque soit le nombre de tâches apériodiques présentes dans le système.
Vous expliquerez votre mise en oeuvre dans votre rapport. Par ailleurs, vous testerez votre programme avec au moins trois jeux de tâches. Vous décrirez ces jeux de tâches et leur ordonnancement dans votre rapport.

Question 3 : implanter un nouveau serveur apériodique

Pour cette dernière question, on vous demande d'implanter un autre serveur de tâches apériodiques. Il existe plusieurs autres serveurs décrits dans ce document. On vous demande de lire ce document, de choisir un serveur de tâches apériodiques, de le comprendre et de l'implanter dans ce logiciel. Cet article présente plusieurs serveurs apériodiques: le "polling server" (ou serveur à scrutation), le "priority exchange server" et le "deferrable server". Vous pouvez choisir d'implanter soit le "priority exchange server" soit le "deferrable server".

Pour cette dernière question, on vous demande:



Projet noté 2011/2012 : mise en oeuvre d'un outil de réseaux de Petri

L'objectif de ce projet est de réviser les parties Réseaux de Petri et Ada de l'UE STR. Pour ce faire, on vous demande de réaliser un outil d'analyse des Réseaux de Petri.

Objectif de l'outil à réaliser


Le logiciel à réaliser doit offrir les fonctionnalités permettant:

Structure d'un fichier stockant un Rdp



Figure 2. Exemple de réseau de Petri




On suppose que les réseaux de Petri à analyser sont stockés dans des fichiers XML ayant la structure suivante :

Ainsi, le Rdp de la figure 2 sera décrit par un fichier contenant la description suivante : 

<petrinet>
   <place> P1 1 </place>
   <place> P2 0 </place>
   <place> P3 2 </place>

   <transition> T1 </transition>
   <transition> T2 </transition>
   <transition> T3 </transition>
   <transition> T4 </transition>

   <arrow> P1 T1 </arrow>
   <arrow> T1 P2 </arrow>
   <arrow> P2 T2 </arrow>
   <arrow> T2 P1 </arrow>
   <arrow> P1 T3 </arrow>
   <arrow> P2 T3 </arrow>
   <arrow> T3 P3 </arrow>
   <arrow> P3 T4 </arrow>
   <arrow> T4 P1 </arrow>
</petrinet>



Matériel disponible


Pour réaliser votre projet, vous disposez des ressources suivantes : Vous trouverez toutes ces informations à partir de l'URL : 
http://beru.univ-brest.fr/~singhoff/DOC/LANG/ADA/


Organisation et évaluation du travail


Vous travaillerez en groupe de 4 étudiants. Chaque étudiant est responsable d'une partie du projet. Ainsi: Une démonstration sera organisée début février. La date sera communiquée après l'élaboration des emplois du temps du semestre 8. Le jour de la démonstration, chaque groupe devra livrer :


Vous serez évalué selon les critères suivants (dans le désordre) :



Projet noté 2019/2020 : mise en oeuvre d'un simulateur d'ordonnancement



L'objectif de ce travail est de développer un logiciel permettant de simuler des algorithmes d'ordonnancement temps réel. Ce logiciel est composé de plusieurs paquetages disponibles dans le répertoire.

Pour compiler ce programme, vous pouvez utiliser gnatmake ou GPS par exemple. Si vous ne disposez pas de compilateur Ada sur votre machine, vous en trouverez ici pour Windows et Linux.

Ce logiciel est composé des unités de programmes suivantes:

La procédure principale example et le paquetage my_subprograms constitue un exemple d'utilisation de ce simulateur:
  1. Le paquetage my_subprograms contient le code de chaque tâche périodique. Ce code est exécuté pour simuler une unité de temps. Il s'agit ici d'un simple affichage.
  2. La procédure principale example définit trois tâches périodiques ordonnancées par Rate Monotonic.


Travail à faire:

La note de ce projet constituera la note de CC de l'UE STR. Vous pouvez travailler seul ou en binôme. Vous devez envoyer votre travail par email à singhoff@univ-brest.fr et nana@univ-brest.fr au plus tard pour le lundi 4 mai. Vous serez évalués selon les critères suivants : Question 1 : prise en main du simulateur

  1. Soit le jeu de tâches défini par S1=S2=S3=0, P1=5, C1=1, P2=10, C2=3, P3=30 et C3=8. Dessiner le chronogramme de l'ordonnancement de ces trois tâches selon Rate Monotonic en mode préemptif. Ce jeu de tâche est il ordonnançable ?
  2. Compiler et exécuter le programme example.adb. Comparer le résultat de la simulation avec votre chronogramme dessiné dans la question précédente.
  3. Dans le programme example.adb, identifier où et comment sont initialisées les tâches du système à simuler, où et comment est sélectionnée la tâche à exécuter, où et comment les réveils périodiques des tâches sont implantés.
Question 2 : implantation de l'algorithme EDF

Ajouter une procédure au simulateur afin de calculer un ordonnancement EDF. Vous donnerez obligatoirement un jeu de tests (c'est à dire des jeux de tâches avec l'ordonnancement attendu sous la forme d'un chronogramme ainsi que l'ordonnancement obtenu par le simulateur). Votre simulateur devra supporter des tâches périodiques, apériodiques et sporadiques. Une tâche apériodique est une tâche qui n'est réveillée qu'une seule fois: elle arrive dans le système à un instant donné, effectue un traitement, puis disparait. Une tâche sporadique a un comportement similaire à une tâche périodique. Comme une tâche périodique, une tâche sporadique est réveillée plusieurs fois. Toutefois, son délai entre deux réveils successifs n'est pas spécifié par une période. Dans le cas d'une tâche sporadique, seul un délai minimum entre deux réveils de la tâche est spécifié. Lors de l'exécution (ou de la simulation) d'une tâche sporadique, deux réveils successifs d'une tâche peuvent être éloignés d'un délai plus grand que ce délai minimum.

Question 3 : implantation d'un nouvel algorithme d'ordonnancement

On vous demande d'implanter un nouvel algorithme dans cet environnement de simulation. L'algorithme à implanter est l'algorithme MUF. Cet algorithme est décrit dans l'article de Stewart et Khosla. On vous demande de lire cet article, d'étudier le fonctionnement de MUF puis de l'implanter dans l'environnement de simulation. Comme pour EDF, vous joindrez à votre solution un jeu de tests.





V. Utiliser gdb avec Ada

Soit le programme Ada test_gdb.adb :