Licence CC BY-NC-SA

Multitasking

Publié :

Après la Programmation Orientée Objet, nous en venons au second point essentiel de la partie IV : le multitasking. Si vous n'avez jamais entendu parler de multitasking, peut-être avez-vous déjà entendu parler de multithreading, de parallélisme, de programmation multi-tâche, de programmation concurrente ou de programmation temps réel ? Non ? Alors sachez que le but de ce chapitre est de réaliser un programme capable d'effectuer plusieurs tâches «en même temps» et non plus successivement, c'est-à-dire de réaliser ses tâches en parallèle et non en série.

Contrairement à la POO, qui consistait avant tout à changer l'organisation de notre code pour mieux le structurer, la programmation temps réel va vous obliger à changer votre façon de programmer et penser vos programmes en y faisant intervenir la notion de temps et en vous obligeant à anticiper les interactions possibles entre les différentes tâches. Il vous faudra également comprendre le fonctionnement du processeur. Attention, ce chapitre est très dense et complexe, ce qui nécessitera peut-être plusieurs lectures.

Enfin, si Ada ne fut pas un précurseur de la POO, sachez que le multitasking est un atout majeur et ancien du langage. C'est notamment pour ses capacités à gérer plusieurs tâches à la fois tout en conservant sa grande fiabilité qu'Ada est apprécié dans les technologies comme le nucléaire ou l'aéronautique. Cet atout a même inspiré d'autres langages.

Parallélisme, tâches et types tâches

Multitasking ou l'art de faire plusieurs tâches à la fois

Quel est l'intérêt de ce multitasking ? J'ai jamais vu de programmes qui faisaient plusieurs choses différentes «en même temps». :(

Détrompez-vous ! En ce moment même, vous utilisez assurément un programme multitâche : votre système d'exploitation ! Que vous utilisiez Windows, MacOS ou une distribution Linux, votre système d'exploitation est bien obligé de pouvoir gérer plusieurs tâches en même temps : même si vous lancez un jeu, un navigateur internet et une messagerie mail, votre système d'exploitation n'arrête pas pour autant de fonctionner, de se mettre à jour ou de supporter votre antivirus. Et il effectue ces tâches «en même temps». Le multitasking est donc un composant essentiel de l'informatique moderne.

Bon, pour le système d'exploitation d'accord. Mais à mon niveau, je ne vais pas programmer un OS ! Quel intérêt de faire plusieurs choses en même temps ? Autant les faire successivement, ça reviendra au même, non?

La fusée de zozor

Prenons comme exemple un domaine très friand de programmation en temps réel : l'aérospatiale ! Vous devez rédiger un programme d'aide au pilotage pour la fameuse fusée Z123 pilotée par Zozor. Votre programme doit régulièrement contrôler les capteurs de pression, d'altitude, de température, de vitesse… afficher les valeurs lues et permettre à Zozor de rectifier ces paramètres pour éviter le crash ou l'explosion en plein vol. Si nous procédons comme d'habitude nous aurons le schéma suivant :

Programme linéaire

Logique n'est-ce pas ? Sauf que le temps que votre programme vérifie la pression, l'altitude ou la vitesse peuvent chuter. Et Zozor devra de plus valider la pression alors que l'urgence serait plutôt de redresser la fusée et de mettre les gaz. Un schéma similaire à celui-ce serait préférable :

Programmes parallèles

Le programme contrôle tous les capteurs en même temps, affiche les valeurs en temps réel et permet de rectifier certains paramètres sans bloquer le reste du système. C'est la réussite assurée pour la Z123.

Eh bien, dans ce cas, il n'y a qu'à réaliser plusieurs programmes, un pour la pression, un autre pour la vitesse, un autre pour l'altitude…

Ce pourrait être une bonne idée, mais encore une fois, ce n'est pas réaliste : si Zozor rectifie sa trajectoire en augmentant l'altitude, cela impliquera une augmentation de la vitesse et surtout, le système ne devra pas s'affoler de voir la pression atmosphérique ou la température extérieure baisser. Bref, ces différentes tâches manipulent des variables communes et il est donc préférable de les rassembler dans un même programme plutôt que de les dissocier.

Les tâches en Ada

Créer une tâche

Vous avez compris le principe et l'objectif ? Bien, passons alors à la mise en œuvre. Une tâche se déclare en Ada avec le mot clé TASK et fonctionne un peu comme une procédure ou une fonction. Cependant, vous devrez préalablement définir sa spécification avant de rédiger son corps. Continuons avec l'exemple de la fusée Z123 :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
with ada.text_io ;             use ada.text_io ; 

procedure Z123 is

   altitude, vitesse : integer := 0 ; 

   --Nous déclarerons les tâches ici

begin            --La procédure principale se chargera de simuler le décollage
   put_line("3 ... 2 ... 1 ... Decollage !") ; 
   while altitude < 10_000 loop
      if altitude < 1000
         then vitesse  := vitesse + 5 ;
              altitude := altitude + 5 ; 
         else altitude := altitude + 10 ; 
      end if ; 
   end loop ; 
   put_line("Decollage reussi !") ; 
end Z123 ;

La procédure Z123 est notre première tâche : la tâche principale. Elle se charge d'augmenter l'altitude et la vitesse au fur et à mesure. Voici maintenant comment nous allons déclarer deux tâches chargées de vérifier l'altitude et la vitesse de la fusée :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
task Verif_Altitude ; 

task body Verif_Altitude is
begin
   loop
      put_line("Altitude de" & integer'image(altitude) & " metres") ; 
   end loop ; 
end Verif_Altitude ; 

         ---------

task Verif_Vitesse ; 

task body Verif_Vitesse is
begin
   loop
      put_line("Vitesse de" & integer'image(vitesse) & " km / H") ; 
   end loop ; 
end Verif_Vitesse ;

Vous pouvez remarquer que ces tâches sont déclarées à la façon des packages : d'abord la spécification avec le mot-clé TASK puis le corps avec les mots TASK BODY. Et d'ailleurs ce dernier ressemble beaucoup à une procédure.

Ces deux tâches commenceront à s'exécuter dès l'instruction BEGIN de la procédure Z123.

Avorter une tâche

Compilez et exécutez ce code et là… c'est le drame ! Les lignes d'affichage défilent à une vitesse ahurissante. Aucun moyen de savoir ce qui se passe et le programme n'en finit pas ! Le problème, c'est que la tâche principale ne prendra fin qu'à l'arrêt des deux tâches Verif_Altitude() et Verif_Vitesse(). Or ces deux tâches ont pour but de vérifier aussi longtemps que possible l'altitude et la vitesse. Il faudrait donc que la procédure principale mette fin à ces deux tâches. Pour cela, il suffit d'utiliser le mot clé ABORT dès que ces tâches ne sont plus nécessaires : on dit alors que l'on fait avorter nos tâches :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
with ada.text_io ;             use ada.text_io ; 

procedure Z123 is

   altitude, vitesse : integer := 0 ; 
   task Verif_Altitude ; 

   task body Verif_Altitude is
   begin
      loop
         put_line("Altitude de" & integer'image(altitude) & " metres") ; 
      end loop ; 
   end Verif_Altitude ; 

   task Verif_Vitesse ; 

   task body Verif_Vitesse is
   begin
      loop
         put_line("Vitesse de" & integer'image(vitesse) & " km / H") ; 
      end loop ; 
   end Verif_Vitesse ;

begin
   put_line("3 ... 2 ... 1 ... Decollage !") ; 
   while altitude < 10_000 loop
      if altitude < 1000
         then vitesse  := vitesse + 5 ;
              altitude := altitude + 5 ; 
         else altitude := altitude + 10 ; 
      end if ; 
   end loop ; 
   put_line("Decollage reussi !") ; 
   abort Verif_Altitude ;
   abort Verif_Vitesse ;
end Z123 ;

Temporiser vos tâches

Bon, cette fois notre programme prend fin, le décollage de la fusée de Zozor a bien eu lieu mais on n'a le temps de rien voir. Quand le programme prend fin, on voit seulement que l'altitude est de 10 000 mètres et la vitesse de 1000 km/H.

Et encore ! Ça ne fait jamais deux fois la même chose ! Des fois, la vitesse ou l'altitude (ou même les deux) valent 0 alors que le décollage est soit-disant réussi ! o_O

Je reviendrai sur ce problème plus tard lorsque nous évoquerons le fonctionnement du processeur. Commençons déjà par régler le problème de la vitesse. Nous allons faire patienter nos deux tâches quelques instants (un dixième de seconde pour être précis) avant de faire un affichage. Cela nous laissera le temps de lire les informations. Pour cela, nous allons utiliser l'instruction DELAY. Celle-ci prend en paramètre un nombre décimal à virgule fixe correspondant au nombre de secondes d'attente :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
task Verif_Altitude ; 

task body Verif_Altitude is
begin
   loop
      delay 0.1 ; 
      put_line("Altitude de" & integer'image(altitude) & " metres") ; 
   end loop ; 
end Verif_Altitude ; 

task Verif_Vitesse ; 

task body Verif_Vitesse is
begin
   loop
      delay 0.1 ; 
      put_line("Vitesse de" & integer'image(vitesse) & " km / H") ; 
   end loop ; 
end Verif_Vitesse ;

Et pour éviter que le décollage ne soit terminé avant que le moindre affichage n'ait eu lieu, nous allons également temporiser le décollage en attendant un centième de seconde avant l'incrémentation :

1
2
3
4
5
6
7
8
while altitude < 10_000 loop
   delay 0.01 ; 
   if altitude < 1000
      then vitesse  := vitesse + 5 ;
           altitude := altitude + 5 ; 
      else altitude := altitude + 10 ; 
   end if ; 
end loop ;

Z123.adb

Cette fois, tout se passe comme prévu : la vitesse augmente jusqu'à stagner à 1000 km/H, l'altitude augmente jusqu'à atteindre 10 000 mètres, mettant alors fin au programme de décollage.

Temporiser jusqu'à…

Une autre possibilité est d'utiliser la combinaison de deux instructions : « DELAY UNTIL ### ; » où ### est de type Time. Cela signifie «attendre jusqu'à une date précise». Vous aurez alors besoin soit du package Ada.calendar soit de Ada.Real_Time. Tous deux définissent un type Time et une fonction clock vous permettant d'obtenir la date actuelle. Ainsi, vous pourrez définir une constante Delai_Attente de type duration et l'utiliser pour temporiser vos programmes. Reprenons par exemple la tâche Verif_Vitesse :

1
2
3
4
5
6
7
8
task body Verif_Vitesse is
   Delai_Attente : Duration := 0.1 ; 
begin
   loop
      delay until (clock + Delai_Attente) ;
      put_line("Vitesse de" & integer'image(vitesse) & " km / H") ; 
   end loop ; 
end Verif_Vitesse ;

Le principe est assez similaire. Au lieu d'attendre qu'un certain temps se soit écoulé, on attend un moment précis (une heure précise, un jour précis…). Vue la structure actuelle de notre code, vous comprendrez que cette solution n'est pas la mieux adaptée à notre problème.

Le type tâche

C'est sympa, mais c'est pas un peu redondant d'écrire deux tâches aussi similaires ? Et puis tu n'as pas expliqué le problème d'affichage d'altitude. :o

Vous allez devoir attendre encore un peu pour comprendre cette bizarrerie. En revanche, je peux vous éviter ce problème de redondance. Nous allons pour cela définir un type tâche. Nous allons en profiter au passage pour essayer d'améliorer l'affichage et arriver à ceci :

1
2
3
3 ... 2 ... 1 ... Decollage !
Altitude (en m)         Vitesse (en km/H) 
      8790                    800

Ce sera le retour du package NT_Console que nous avions utilisé lors du TP sur le jeu du serpent. Je vous préviens tout de suite : vous allez de nouveau être confronté à une bizarrerie que je n'expliquerai pas tout de suite (comment ça je fuis devant la difficulté ? :p ). Nous n'allons donc définir qu'un seul type de tâche appelé Task_Verif. Celle-ci affichera le contenu d'une variable à un endroit précis. Il nous suffira ensuite de définir deux tâches Verif_altitude et Verif_vitesse de type Task_Verif. Voici comment déclarer notre type tâche :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
task type Task_Verif(var : integer ; x : X_Pos ; y : Y_Pos) ;

task body Task_Verif is
begin
   loop
      delay 0.1 ;
      GOTO_XY(x,y) ;
      put(var) ;
   end loop ;
end Task_Verif ;

Notez bien deux choses : l'ajout du mot TYPE lors de la spécification tout d'abord, l'absence de paramètres pour le corps ensuite. Et voici ce que devient notre programme Z123 :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
with ada.text_io ;             use ada.text_io ;
with ada.integer_text_io ;     use ada.integer_text_io ;
with NT_Console ;              use NT_Console ;

procedure Z123 is

   -- Déclaration du type Task_Verif

   altitude : integer := 0 ;
   Verif_Altitude : Task_Verif(altitude,0,2) ;

   vitesse : integer := 0 ;
   Verif_Vitesse  : Task_Verif(vitesse,25,2) ;

begin
   GOTO_XY(0,0) ; put("3 ... 2 ... 1 ... Decollage !") ;
   GOTO_XY(0,1) ; put("Altitude (en m) ") ;
   GOTO_XY(25,1) ; put("Vitesse (en km/H) ") ;

   while altitude < 10_000 loop
      delay 0.01 ;
      if altitude < 1000
         then vitesse  := vitesse + 5 ;
              altitude := altitude + 5 ;
         else altitude := altitude + 10 ;
      end if ;
   end loop ;
   GOTO_XY(0,3) ; put_line("Decollage reussi !") ;
   abort Verif_Altitude ;
   abort Verif_Vitesse ;
end Z123 ;

En procédant de la sorte, nous nous épargnons toute redondance et il est possible de créer, rapidement et facilement, une tâche pour contrôler la pression, la température ou tout autre paramètre.

Euh… la vitesse et l'altitude n'augmentent plus, c'est normal ? :o

Oui, c'est normal ! Car j'ai rédigé ce code pour attirer votre attention sur un point particulier : une tâche n'est pas une procédure ou une fonction que l'on appellerait de manière régulière. Elle n'a pas de paramètres en modes IN, OUT ou IN OUT. Je sais, vous vous dites : « pourtant, on a bien initialiser Verif_Altitude avec la variable altitude ! ». Mais cette variable n'a servi qu'à l'initialisation : la variable altitude valait 0 lorsque l'on a initialisé Verif_Altitude, donc son paramètre val vaudra 0, un point c'est tout. La modification de altitude ne modifiera pas pour autant le paramètre val. Comment résoudre ce problème ? Eh bien, il y a toujours les pointeurs !

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
with ada.text_io ;             use ada.text_io ;
with ada.integer_text_io ;     use ada.integer_text_io ;
with NT_Console ;              use NT_Console ;

procedure Z123 is

   task type Verif(var : access integer ; x : X_Pos ; y : Y_Pos) ;

   task body Verif is
   begin
      loop
         delay 0.1 ;
         GOTO_XY(x,y) ;
         put(var.all) ;
      end loop ;
   end Verif ;

   altitude : aliased integer := 0 ;
   Verif_Altitude : Verif(altitude'access,0,2) ;

   vitesse : aliased integer := 0 ;
   Verif_Vitesse  : Verif(vitesse'access,25,2) ;

begin
   ...

Le pointeur ne change jamais de valeur, il contient toujours l'adresse de sa cible. Ainsi nous réglons ce problème. Mais il en reste encore un : l'affichage de l'altitude et de la vitesse est plutôt… bizarre. Au lieu d'afficher deux valeurs, le programme en affiche 4 ! Pourquoi ? C'est ce que nous allons expliquer dans la prochaine partie.

Communication inter-tâche directe

Le parallélisme, comment ça marche ?

Round-Robin ou «l'effet tourniquet»

Pour comprendre d'où viennent les bizarreries rencontrées lors de ces quelques essais, vous devez comprendre qu'un ordinateur n'est pas plus intelligent que vous : il ne peut pas faire deux choses en même temps. Alors comment fait-il pour donner cette impression ? Eh bien, il va vite.

Plus sérieusement, imaginez que votre ordinateur doive faire tourner votre système d'exploitation (OS), votre navigateur internet, un antivirus et un jeu de foot. Il ne peut tout faire en même temps, il va donc exécuter l'OS pendant un laps de temps très court. Une fois ce délai écoulé (on parle de Time Out), il mettra cette tâche en mémoire pour s'occuper rapidement du navigateur qu'il placera à son tour en mémoire. Il fera de même avec l'antivirus et votre jeu de foot. Que se passe-t-il ensuite ? Eh bien il sort votre OS de la mémoire pour l'exécuter à nouveau durant un court instant avant de le remettre en mémoire et d'en sortir le navigateur internet, etc. Cette méthode est appelée tourniquet ou round-robin en anglais, ou encore balayage cyclique. C'est le principe du dessin animé : en faisant défiler rapidement des images statiques, on fait croire à un mouvement. Nous avons donc l'impression, pauvres humains que nous sommes, que l'ordinateur effectue plusieurs tâches en même temps.

Le balayage cyclique ou tourniquet

Mais comment l'ordinateur sait-il quelle tâche il doit retirer de la mémoire ?

Vous vous souvenez des TAD ? Vous vous souvenez des files et du système FIFO ? Eh bien notre processeur utilise lui-aussi une file : une file de processus. À chaque fois, il pioche dans la file (dequeue), en sort un processus, le traite durant un certain laps de temps puis l'enfile à nouveau (requeue). Nous apporterons des nuances un peu plus tard.

Sections critiques

Ah d'accord… mais je ne vois pas le rapport avec nos problèmes d'affichage. :(

C'est simple. Nos tâches sont (mal)traitées par le processeur de la même manière que les processus. Elles peuvent être interrompues à n'importe quel moment pour être remises en fin de file d'attente. Et pendant qu'elles attendent dans leur file, une autre tâche est traitée qui, elle, reprend son travail là où elle s'était arrêtée. L'idéal serait que les tâches s'alternent de la manière suivante (a représente l'altitude, v la vitesse de la fusée):

Programme principal

Tâche Verif_Altitude

Tâche Verif_Vitesse

v=10 ; a = 10

-

-

-

placement du curseur colonne 0 afficher a = 10

-

-

-

placement du curseur colonne 25 afficher v = 10

v=15 ; a = 20

-

-

-

placement du curseur colonne 0 afficher a = 20

-

-

-

placement du curseur colonne 25 afficher v = 15

Mais cela ne se passe pas toujours aussi bien et l'enchaînement peut alors ressembler à ça :

Programme principal

Tâche Verif_Altitude

Tâche Verif_Vitesse

v=10 ; a = 10

-

-

-

placement du curseur colonne 0

-

-

-

placement du curseur colonne 25 afficher v = 10

v=15 ; a = 20

-

-

-

afficher a = 20 placement du curseur colonne 0 afficher a = 20

-

-

-

placement du curseur colonne 25 afficher v = 15

Quelle importance me direz-vous ? Eh bien le soucis qui va se poser, c'est que lorsque Verif_Altitude() va afficher que a vaut 20, le curseur sera au-delà de la colonne 25 ! Il aura été placé en colonne 25, puis déplacé pour afficher v, mais n'aura pas été remis en colonne 0 avant d'afficher a. D'où l'apparition d'un troisième nombre. Un quatrième apparaîtra si ce phénomène se produit avec Verif_Vitesse().

Ce problème ne semble pas si grave, ce n'est jamais que de l'affichage ! Et pourtant, c'est le problème majeur du multitasking : le partage et l'accès aux ressource (ici l'écran). Prenons un autre exemple. Supposons que nous ayons créé un type tâche Task_Pilotage permettant de régler vitesse et altitude de la fusée Z123. Nous créeons deux tâches : Pilote et Copilote. Que va-t-il se passer si le pilote et le copilote décident tous deux en même temps de réduire un peu la vitesse ? La Z123 risque fort de freiner en plein ciel. :p Et cela n'a rien d'illogique : supposons que le la tâche pilote lise la valeur de la vitesse avant d'être interrompue. La tâche copilote prend le relai et décide de baisser la vitesse avant d'être à son tour interrompue. La tâche pilote reprend les commandes et affiche la valeur-vitesse lue précédemment. Sauf que la vitesse a entre-temps diminué. Et le pilote ne le saura pas. Conclusion : le pilote va ralentir, pensant sa vitesse trop haute, alors que le copilote s'en est déjà chargé. Résultat : «Houston, we've had a problem».

Lorsque vous concevez une tâche, vous devez donc réfléchir à ce que l'on appelle les sections critiques (et comme c'est le problème principal, vous DEVEZ ABSOLUMENT y penser). Elles sont faciles à repérer, ce sont les zones de code faisant intervenir des ressources partagées avec d'autres tâches.

Une solution directe : le Rendez-vous

Une première solution pour régler ce problème consiste à faire communiquer nos tâches entre elles directement afin qu'elles se synchronisent. Ainsi, il suffirait que la procédure principale (qui est une tâche elle aussi, je le rappelle), indique aux deux autres à quel moment elles peuvent intervenir sans risquer d'engendrer des comportements erratiques. La procédure principale va donc fixer un rendez-vous à ses sous-tâches (le terme anglais est tout simplement Rendez-vous, mais avec l'accent british ^^ ) : «tu interviendras à tel moment et tu feras telle chose».

Comment cela se traduit-il au niveau du traitement par le processeur ? Deux cas de figures se posent :

  • soit la procédure principale est en avance sur les tâches auxquelles elle demande d'intervenir. Auquel cas, la procédure principale sera mise en attente, le temps que les tâches aient terminé leur propres instructions et aient exécuté les instruction demandées par la procédure principale. Après quoi, tout reprendra comme à l'accoutumée.

Mise en attente de la procédure principale

  • soit la procédure principale est en retard sur ses tâches filles. Ces dernières ayant effectué leurs instructions propres seront mises en attente d'un appel venant de la procédure principale.

Mise en attente des tâches filles

Les entrées

Les rendez-vous permettent donc à une tâche de recevoir des ordres de l'extérieur. Nous allons pouvoir concevoir des tâches qui ne seront plus hermétiques mais qui seront dotées de points d'entrée. Ainsi, notre type Task_Verif étant chargé d'afficher une valeur, nous allons créer une entrée appelée Affichage. Cette entrée devra être spécifiée dans la spécification du type tâche et se déclare à l'aide du mot-clé ENTRY :

1
2
3
task type Task_Verif(var : access integer ; x : X_Pos ; y : Y_Pos) is
   entry affichage ; 
end Task_Verif ;

Cette entrée ne sera en définitive qu'une sorte de sous-procédure attendant le rendez-vous. Attention toutefois, la syntaxe du corps est différente :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
task body Task_Verif is
begin
   loop
      accept affichage do
         delay 0.01 ; 
         GOTO_XY(x,y) ;
         put(var.all) ;
      end affichage ; 
   end loop ;
end Task_Verif ;

Comprenez cette syntaxe de la manière suivante : «lorsque la tâche (TASK) accepte (ACCEPT) l'entrée (ENTRY) affichage, elle doit faire (DO) ceci». Maintenant, si vous lancez votre programme, vous vous rendrez compte que vos deux tâches ne font plus rien, et pour cause, elles attendent qu'un rendez-vous leur soit fixé via l'entrée Affichage. Nous allons donc modifier la procédure principale à son tour :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
while altitude < 10_000 loop
   delay 0.01 ;
   if altitude < 1000
      then vitesse  := vitesse + 5 ;
           altitude := altitude + 5 ;
      else altitude := altitude + 10 ;
   end if ;
   Verif_Vitesse.affichage ; 
   Verif_Altitude.affichage ; 
end loop ;

Compilez, testez : tout fonctionne à merveille ! Les tâches exécutent correctement l'affichage puisqu'elles sont appelées à un moment précis et ne rendent la main qu'après avoir achevé leur entrée. Une remarque toutefois, il aurait été possible de «déparamétrer» notre type tâche pour paramétrer son entrée. Ce qui aurait évité l'usage d'un pointeur mais nous aurait obligé à spécifier les paramètres au sein de la procédure principale (et en bon fainéant, j'ai préféré la première solution ^^ ) :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
task type Task_Verif is
   entry affichage(var : integer ; x : X_Pos ; y : Y_Pos) ; 
end Task_Verif ;

task body Task_Verif is
begin
   loop
      accept affichage(var : integer ; x : X_Pos ; y : Y_Pos) do
         delay 0.01 ; 
         GOTO_XY(x,y) ;
         put(var) ;
      end affichage ; 
   end loop ;
end Task_Verif ;
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
while altitude < 10_000 loop
   delay 0.01 ;
   if altitude < 1000
      then vitesse  := vitesse + 5 ;
           altitude := altitude + 5 ;
      else altitude := altitude + 10 ;
   end if ;
   Verif_Vitesse.affichage(vitesse,25,2) ; 
   Verif_Altitude.affichage(altitude,0,2) ; 
end loop ;

Les synchronisations sélectives

Améliorons encore nos tâches. Nous allons proposer désormais deux affichages : un normal et un d'urgence qui sera activé lorsque la vitesse dépassera 800 km/H et l'altitude 6000 m. Cette nouvelle entrée appelée simplement Urgence affichera la valeur en rouge. La spécification du type tâche est évidente :

1
2
3
4
task type Task_Verif(var : access integer ; x : X_Pos ; y : Y_Pos) is
   entry affichage ; 
   entry urgence ; 
end Task_Verif ;

Je veux bien, mais comment faire pour appeler cette entrée ? Si notre tâche attend l'entrée affichage, elle n'acceptera pas l'entrée Urgence et tout le monde va rester bloqué !

C'est bien vrai, la pire solution serait d'écrire le corps suivant :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
task body Task_Verif is
begin
   loop
      accept affichage do
         delay 0.01 ; 
         GOTO_XY(x,y) ;
         put(var.all) ;
      end affichage ; 
      accept urgence do
         delay 0.01 ; 
         set_foreground(light_red) ; 
         GOTO_XY(x,y) ;
         put(var.all) ;
         set_foreground(gray) ; 
      end urgence ; 
   end loop ;
end Task_Verif ;

Au premier affichage, tout irait bien, mais ensuite, la tâche attendrait nécessairement un affichage d'urgence, ce qui ne risque pas d'arriver au décollage de la fusée. Il faut donc que la tâche propose une alternative, qu'elle se mette en attente d'une ou plusieurs entrées. C'est le rôle de l'instruction de sélection. Nous allons donc écrire :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
task body Task_Verif is
begin
   loop
      select
         accept affichage do
            delay 0.01 ; 
            GOTO_XY(x,y) ;
            put(var.all) ;
         end affichage ; 
      or
         accept urgence do
            delay 0.01 ; 
            set_foreground(light_red) ; 
            GOTO_XY(x,y) ;
            put(var.all) ;
            set_foreground(gray) ; 
         end urgence ; 
      end select ; 
   end loop ;
end Task_Verif ;

Notre tâche attend donc que l'une ou l'autre des entrées soit appelée et elle sélectionnera alors celle désirée. Il ne reste plus qu'à modifier notre procédure principale :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
while altitude < 10_000 loop
   delay 0.01 ;
   if altitude < 1000
      then vitesse  := vitesse + 5 ;
           altitude := altitude + 5 ;
      else altitude := altitude + 10 ;
   end if ;
   if vitesse <= 800
      then Verif_Vitesse.affichage ; 
      else Verif_Vitesse.urgence ; 
   end if ; 
   if altitude <= 6000
      then Verif_Altitude.affichage ; 
      else Verif_Altitude.urgence ; 
   end if ; 
end loop ;

L'instruction SELECT ne doit pas être confondue avec une instruction IF, son rôle n'est pas d'orienter vers telle ou telle entrée (quoique) mais bien de proposer d'attendre l'acceptation d'une entrée parmi plusieurs, le choix étant laissé à la tâche appelante. On parle d'attente sélective.

Gardes et compléments

Si l'instruction SELECT n'est pas une instruction IF, elle peut toutefois imposer certaines conditions : cesser d'attendre ou lever une exception si l'attente devient trop longue, n'accepter une entrée que sous certaines conditions… Le but recherché n'est pas alors de faire un tri parmi les entrées mais d'éviter des blocages (on parle plus exactement de famine), des levées d'exceptions ou des comportements non désirés. Ces conditions apportées à notre attente sélective sont appelées gardes.

Garde conditionnelle

Commençons par imposer une condition toute simple : l'entrée urgence ne pourra être activée que pour une valeur strictement positive : on ne va pas tirer la sonnette d'alarme pour un appareil à l'arrêt. Cela se fera tout simplement avec l'instruction WHEN :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
task body Task_Verif is
begin
   loop
      select
         accept affichage do
            delay 0.01 ; 
            GOTO_XY(x,y) ;
            put(var.all) ;
         end affichage ; 
      or when var.all > 0
         accept urgence do
            delay 0.01 ; 
            set_foreground(light_red) ; 
            GOTO_XY(x,y) ;
            put(var.all) ;
            set_foreground(gray) ; 
         end urgence ; 
      end select ; 
   end loop ;
end Task_Verif ;

Garde temporelle

Mais que se passera-t-il si la procédure principale demande à employer l'entrée urgence avec une variable nulle ? Ça ne risque pas de bloquer ?

Ce n'est pas que ça risque de bloquer… ça VA bloquer à coup sûr. Pour éviter tout phénomène d'interblocage, il est possible d'ajouter une garde prenant en compte le temps d'attente : au delà de 3 secondes d'attente, on exécute une entrée particulière (par exemple, on arrête la tâche proprement). Pour définir le temps d'attente, nous allons réutiliser l'instruction DELAY.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
task body Task_Verif is
begin
   loop
      select
         accept affichage do
            delay 0.01 ; 
            GOTO_XY(x,y) ;
            put(var.all) ;
         end affichage ; 
      or when var.all > 0
         accept urgence do
            delay 0.01 ; 
            set_foreground(light_red) ; 
            GOTO_XY(x,y) ;
            put(var.all) ;
            set_foreground(gray) ; 
         end urgence ; 
      or delay 3.0 ; 
         exit ; 
      end select ; 
   end loop ;
end Task_Verif ;

À ce sujet, il est possible d'utiliser l'instruction ELSE plutôt que OR. Par exemple si nous écrivons le code ci-dessous (qui déclenchera une exception TASKING_ERROR) :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
task body Task_Verif is
begin
   loop
      select
         accept affichage do
            delay 0.01 ; 
            GOTO_XY(x,y) ;
            put(var.all) ;
         end affichage ; 
      or when var.all > 0
         accept urgence do
            delay 0.01 ; 
            set_foreground(light_red) ; 
            GOTO_XY(x,y) ;
            put(var.all) ;
            set_foreground(gray) ; 
         end urgence ; 
      else 
         exit ; 
      end select ; 
   end loop ;
end Task_Verif ;

Les tâches de type Task_Verif regarderons si une demande d'affichage ou d'affichage d'urgence a été demandé. Si tel n'est pas le cas, alors (ELSE) elles sortiront de la boucle avec EXIT. Cela revient à écrire une instruction OR DELAY 0.0 à la différence qu'avec ELSE, le temps durant lequel la tâche est inactive en mémoire n'est pas décompté.

Instruction de terminaison

Plutôt que d'avorter les tâches durant notre programme principal, pourquoi ne pas faire en sorte que celles-ci mettent fin elle-même proprement à leur exécution ? Cela est rendu possible avec l'instruction TERMINATE. Je vous conseille donc, à chaque attente sélective, d'ajouter une clause TERMINATE, cela évitera que vos programmes n'aient pas de fin parce que vous avez négligé d'avorter toutes vos tâches :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
task body Task_Verif is
begin
   loop
      select
         accept affichage do
            delay 0.01 ; 
            GOTO_XY(x,y) ;
            put(var.all) ;
         end affichage ; 
      or when var.all > 0
         accept urgence do
            delay 0.01 ; 
            set_foreground(light_red) ; 
            GOTO_XY(x,y) ;
            put(var.all) ;
            set_foreground(gray) ; 
         end urgence ; 
      or 
         terminate ;  
      end select ; 
   end loop ;
end Task_Verif ;

Communication inter-tâche indirecte

Les types protégés

Une seconde façon d'éviter tout problème sur les ressources lié au parallélisme est de s'assurer que l'accès à ces ressources soit protégé et que jamais deux tâches ne puissent y accéder en même temps. Avant de pouvoir lire ou écrire une ressource partagée, toute tâche devra demander une autorisation au programme principal. Une fois le travail d'écriture ou de lecture effectué, la tâche «rendra» son autorisation, libérant ainsi l'accès à la ressource pour d'autres tâches. Il s'agit du principe d'exclusion mutuelle, aussi appelé Mutex. La Mutex peut bien entendu être réalisée en Ada, grâce aux types protégés ou PROTECTED.

Il s'agit d'un format de type particulier dans lequel il est possible de déclarer les variables protégées, mais aussi des entrées, des fonctions ou des procédures ainsi qu'une partie privée. Les fonctions, procédures et entrées déclarées dans un type protégé sont toutes en exclusion mutuelle. De plus, les entrées peuvent être bloquantes car elles doivent être munies d'une garde. Les fonctions seront généralement utilisées pour lire les données protégées, les procédures et entrées pour les écrire.

Pour mieux comprendre, reprenons l'exemple de notre affichage de fusée à la base. Supprimons les entrées et toute communication entre notre programme principal et les tâches. Notre procédure Z123 se résumera donc à ceci :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
with ada.text_io ;             use ada.text_io ;
with ada.integer_text_io ;     use ada.integer_text_io ;
with NT_Console ;              use NT_Console ;

procedure Z123 is

      -------------------------------------------
      --Nous déclarerons ici notre type protégé--
      -------------------------------------------


      -----------------------------------------
      --Nous déclarerons ici notre type tâche--
      -----------------------------------------

begin
   GOTO_XY(0,0) ; put("3 ... 2 ... 1 ... Decollage !") ;
   GOTO_XY(0,1) ; put("Altitude (en m) ") ;
   GOTO_XY(25,1) ; put("Vitesse (en km/H) ") ;

   while altitude < 10_000 loop
      delay 0.01 ;
      if altitude < 1000
         then vitesse  := vitesse + 10 ;
              altitude := altitude + 10 ;
         else altitude := altitude + 50 ;
      end if ;
   end loop ;
   abort Verif_Vitesse ;
   abort Verif_Altitude ; 
   GOTO_XY(0,3) ; put_line("Decollage reussi !") ;
end Z123 ;

Notre type tâche sera lui aussi simplifié : plus d'attente sélective, plus d'entrées, juste une affichage à un endroit précis :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
--notre type tâche
task type Verif(var : access integer ; x : X_Pos ; y : Y_Pos) ;

task body Verif is
begin
   loop
      delay 0.01 ;
      GOTO_XY(x,y) ;
      put(var.all) ;
   end loop ;
end Verif ;


--et nos variables
altitude : aliased integer := 0 ;
Verif_Altitude : Verif(altitude'access,0,2) ;
vitesse : aliased integer := 0 ;
Verif_Vitesse  : Verif(vitesse'access,25,2) ;

Nous allons ensuite pouvoir déclarer un type protégé, que nous appellerons T_Ecran et une variable Ecran de type T_Ecran. Voici un schéma de ce fameux type :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
--D'abord les spécifications
   protected type T_Ecran(paramètres éventuels) is
      entry truc ; 
      procedure bidule ;
      function machin ; 
   private
      MaVariable : UnTypeDeVariable ;
      --autres déclarations privées
   end T_Ecran ; 


--Ensuite le corps du type
   protected body T_Ecran is
      entry truc when une_condition is
      begin
         ...
      end truc ; 

      procedure bidule is
      begin
         ...
      end bidule ; 

      function machin is
      begin
         ...
      return ...
      end machin ; 
   end T_Ecran ; 

--Enfin, notre objet protégé
   Ecran : T_Ecran(paramètres) ;

Pourquoi tu n'as pas détaillé ton type T_Ecran ? Je dois tout compléter moi-même ?

Non, je compte bien détailler tout cela sans trop tarder, je me contentais juste de vous présenter un plan de la déclaration d'un type protégé. Car il y a plusieurs façons d'utiliser ces types protégés, chaque façon dispose de ses propres avantages et inconvénients, mais aucune n'est parfaite. Je ne compte pas détailler toutes les méthodes possibles et imaginables ; je préfère me concentrer sur deux méthodes parmi les plus connues : les sémaphores et les moniteurs. La programmation concurrente est un vaste pan de l'informatique, passionnant mais que ce tutoriel n'a pas vocation à couvrir. :)

Les sémaphores

Un peu d'Histoire

Le principe des sémaphores fut inventé par le mathématicien et informaticien néerlandais Edsger Wybe Dijkstra en 1968. Mort en 2002, Dijkstra aura auparavant marqué la seconde moitié du XXème siècle par le rôle qu'il a joué dans le développement de l'informatique en temps que science.

Edsger Wybe Dijkstra

Source: Wikipedia

Inventeur des sémaphores, Dijkstra s'intéressa à la programmation concurrente (nous reviendrons plus tard sur son apport) ainsi qu'à l'algorithmique. Un célèbre algorithme publié en 1959 (notamment étudié en filière économique et social en France) porte son nom : l'algorithme de Dijkstra permet de déterminer un plus court chemin en théorie des graphes (si cela ne vous parle pas, dites-vous que son algorithme permet à votre GPS de connaître la route la plus courte ou la moins chère entre Paris et Lyon).

Il apporta également sa contribution au développement du langage de programmation Algol. Ce langage, très structuré en comparaison des langages de l'époque, permettant la récursivité, donnera par la suite naissance au langage Pascal, langage dont s'inspirera le Français Jean Ichbiah pour élaborer le langage Ada à la demande du département de la Défense américain. Le langage Ada est donc l'un des héritiers de ce grand Monsieur (ce qui explique en bonne partie sa structure claire et sa rigueur).

De quoi parle-t-on ?

Un sémaphore est, dans la vie courante, un avertisseur. Prenez par exemple des feux de signalisation pour les trains, vous savez, ceux qui font ding-ding-ding… eh bien ce sont des sémaphores. Ils avertissent de la présence ou non d'un train. De même, en espagnol comme en italien, un feu tricolore est appelé semáforo ou semaforo (sans accent). Bref en informatique, le but d'un sémaphore sera de bloquer les tâches avant une section critique de manière à n'en laisser passer qu'un certain nombre à la fois. Les sémaphores se chargeront de compter le nombre d'accès restants à une ressource (pour notre écran, seule une tâche pourra y accéder) et de jouer le rôle de feu tricolore. Lorsqu'une tâche arrivera devant une section critique, le sémaphore regardera le nombre de places libres :

  • Si ce nombre vaut 0, alors la tâche est mise en attente.
  • Sinon, le sémaphore se contentera de décrémenter son compteur de places libres.

Une fois que la tâche aura effectué son travail en section critique, le sémaphore n'aura plus qu'à incrémenter son compteur de places libres afin de libérer l'accès à d'autres tâches en attente. La première opération est généralement notée P. C'est l'initiale du mot Proberen qui signifie tester en néerlandais. La seconde opération est généralement notée V pour Verhogen (incrémenter). Comme je me doute que, hormis les tulipes et les moulins, vous ne connaissez pas grand chose aux Pays-Bas, voici une petite astuce pour retenir les noms de ces deux opérations : P est également l'initiale de «Puis-je ? » ou de Prendre et V l'initiale de «Vas-y ! » ou Vendre. Compris ? Alors passons à la mise en œuvre.

Mise en œuvre en Ada

Si nous souhaitons réaliser un sémaphore, notre type protégé T_Ecran devra donc contenir une variable privée compteur (il serait inutile et dangereux que quelqu'un puisse y accéder sans employer les opérations P et V). Nous l'initialiserons automatiquement à 1 (car seulement une seule tâche à la fois pourra accéder à l'écran), mais il est bien sûr possible de l'initialiser via un paramètre. L'opération P devra être réalisée par une entrée pour permettre la mise en attente des tâches. Pour ne pas être mise en attente, il suffira que le compteur n'indique pas zéros places restantes. Il n'est toutefois pas nécessaire que V soit une entrée mais plutôt une simple procédure. En effet, il n'y a aucun besoin de mettre en attente une tâche qui souhaite libérer une ressource et l'opération V n'a besoin d'aucune précondition. Voici donc ce que donnerait notre type protégé :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
--les spécifications
   protected type T_Ecran is
      entry P ;
      procedure V ;
   private
      compteur : integer := 1 ;
   end T_Ecran ;

--le corps
   protected body T_Ecran is
      entry P when compteur > 0 is     --une condition DOIT être spécifiée
      begin
         compteur := compteur - 1 ;
      end P ;

      procedure V is
      begin
         compteur := compteur + 1 ;
      end V ;
   end T_Ecran ;

--la variable protégée
   Ecran : T_Ecran ;

Désormais, nous n'avons plus qu'à revoir le corps de notre type tâche Task_Verif afin de positionner notre sémaphore autour de la section critique :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
task body Verif is
begin
   loop
      delay 0.01 ;
      Ecran.P ;           --Puis-je accéder à la section critique ? Juste un petit moment, svp. 
         GOTO_XY(x,y) ;
         put(var.all) ;
      Ecran.V ;           --Tu as fini ? Alors Vas-y, sors de la section critique et continue !
   end loop ;
end Verif ;

Avantages et inconvénients

L'avantage des sémaphores est avant-tout leur simplicité : simple à comprendre et donc simple à mettre en œuvre. Et ce n'est pas un atout négligeable dans un domaine aussi compliqué que la programmation concurrente. Qui plus est, les sémaphores sont peu coûteux en ressources comme le temps processeur.

L'inconvénient est que si un programmeur oublie malencontreusement de libérer une ressource avec l'opération V, celle-ci deviendra inaccessible, conduisant à ce que l'on appelle un interblocage. De même, la ressource en elle-même n'est pas protégée, un mauvais programmeur oubliant d'utiliser l'entrée P réalisera un programme sans mutex qui amènera très certainement à de sacrées surprises. Autre inconvénient, la première tâche arrivant au sémaphore s'empare de la ressource partagée et bloque donc les autres : aucune priorité n'est prise en compte. Les sémaphores sont donc un outil simple, pratique mais qui ne répond pas à toutes les attentes. Venons-en donc aux moniteurs.

Les moniteurs

Encore un peu d'Histoire

Les moniteurs, autre outil de synchronisation, furent quant à eux inventés par le britannique Sir Charles Antony Richard Hoare en 1974. Vous avez déjà eu affaire à cet éminent professeur, car il est l'inventeur du fameux Quick Sort, l'algorithme de tri rapide que nous avions étudier en début de partie IV avec tant d'autres.

Sir Charles Antony Richard Hoare

Source: Wikipedia

Mais ce n'est pas tout. Hoare a également élaboré toute une logique, la logique de Hoare, qui permet de raisonner sur les programmes et algorithmes d'une façon très mathématique, permettant ainsi de traquer d'éventuelles erreurs ou de prouver qu'un algorithme fait effectivement ce qu'il est attendu qu'il fasse.

Eh oui, l'informatique est une science, ne l'oubliez pas. Et comme le disait Hoare : «Il y a deux manières pour construire un logiciel : ou bien on le fait si simple qu’il n’y a à l’évidence pas de défauts, ou bien on le fait si compliqué qu’aucun défaut n’est évident. La première méthode est de loin la plus difficile.»

Principe du moniteur

Le principe du moniteur est de protéger les ressources partagées en encapsulant les sections critiques de manière à ce que les tâches n'y aient plus accès. On rejoint l'idée de l'encapsulation chère à la POO : les données brutes ne sont plus accessibles, on fournit par contre les méthodes pour la manipuler. Mais, toujours pour éviter des accès multiples à cette ressource, on ajoute à ces méthodes quelques conditions, ce que l'on appelle un verrou de mutex.

Les moniteurs permettent ainsi une gestion de plus haut niveau que les sémaphores. D'autant plus que le langage Ada, via ses types PROTECTED gèrera lui-même les mises en attente ou les réveils de tâches. Notre type T_Ecran, s'il est conçu tel un moniteur, ressemblera à ceci :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
protected type T_Ecran is
   entry affichage(var : access integer ; x : X_Pos ; y : Y_Pos) ; 
private
   compteur : integer := 1 ;
end T_Ecran ;

protected body T_Ecran is
   entry affichage(var : access integer ; x : X_Pos ; y : Y_Pos) when compteur > 0 is
   begin
      compteur := compteur - 1 ;
      GOTO_XY(x,y) ;
      put(var.all) ;
      compteur := compteur + 1 ;
   end affichage ; 
end T_Ecran ;

Ecran : T_Ecran ;

Facile n'est-ce pas ? Et attendez de voir ce que devient notre type tâche :

1
2
3
4
5
6
7
8
9
task type Verif(var : access integer ; x : X_Pos ; y : Y_Pos) ;

task body Verif is
begin
   loop
      delay 0.01 ;
      Ecran.affichage(var,x,y) ; 
   end loop ;
end Verif ;

Cela devient extrêmement simple, non ? Et pourtant les moniteurs sont normalement plus complexes à comprendre que les sémaphores car il faut gérer des signaux de mise en attente ou de réactivation de tâches. Heureusement pour nous, le type PROTECTED du langage Ada agit à la façon d'un moniteur ce qui nous décharge de bien des tracas en réglant bon nombre de soucis de sécurité. Et nous pouvons encore améliorer ce code en nous débarrassant de la variable compteur à incrémenter/décrémenter. Nous allons modifier la garde de l'entrée Affichage() pour ne nous concentrer que sur le nombre de tâches en attente. Nous allons pour cela utiliser l'attribut « 'count » :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
protected type T_Ecran is
   entry affichage(var : access integer ; x : X_Pos ; y : Y_Pos) ; 
end T_Ecran ;

protected body T_Ecran is
   entry affichage(var : access integer ; x : X_Pos ; y : Y_Pos) when affichage'count = 0 is
   begin
      GOTO_XY(x,y) ;
      put(var.all) ;
   end affichage ; 
end T_Ecran ;

Ecran : T_Ecran ;

Compléments : priorités et POO

Priorités

Complément sur le tourniquet

Il est temps désormais de compléter ce que nous avons dit sur le tourniquet. Vous vous souvenez, je vous ai expliqué comment l'ordinateur faisait pour gérer soit-disant «en même temps» un système d'exploitation (OS), un navigateur internet, un antivirus et un jeu de foot. Je vous avais expliqué qu'il faisait tourner l'OS pendant quelques millisecondes avant de le placer dans une file d'attente en mémoire, file d'attente gérée sur le mode FIFO (First In First Out). Avant d'avoir de nouveau accès au processeur, votre OS devrait donc attendre que celui-ci ait traité le navigateur internet, puis l'antivirus et enfin le jeu de foot.

Eh bien je vous ai dit des bêtises (pour la bonne cause rassurez-vous). Car il est évident que tous ces logiciels ne fonctionneraient pas sans le système d'exploitation. Celui-ci est primordial au bon fonctionnement de l'ordinateur, contrairement à l'antivirus qui, la plupart du temps, n'a rien de particulier à faire. Il n'est donc pas judicieux que l'antivirus et l'OS aient le même temps d'accès au processeur alors qu'il n'ont pas la même charge de travail. On dit qu'ils n'ont pas la même priorité. C'est pourquoi nos ordinateurs utilisent plutôt un système de tourniquet à priorité.

Comment faire pour que le système d'exploitation soit prioritaire puisqu'on utilise une file et donc le principe FIFO ?

L'idée est en fait d'utiliser plusieurs tourniquets et non un seul. On attribue un tourniquet à chaque niveau de priorité. Reprenons notre exemple précédent avec trois niveaux de priorité : 0 pour l'antivirus, 1 pour le jeu de foot et le navigateur internet, 2 pour le système d'exploitation. Les processus de priorité 2 (en rouge sur le schéma) obtiendront 50% du temps processeur, ceux de priorité 1 (en orange) auront 30% et ceux de priorité 0 (en vert) auront 20%. Ce qui nous donne le schéma suivant :

Tourniquet à priorité

On peut ainsi voir que le système d'exploitation apparaît bien plus souvent que le navigateur internet ou le jeu de foot par exemple.

Un nouveau pragma

La priorité d'une tâche peut être fixée de manière statique grâce à une directive de compilateur. Vous vous souvenez ? Les fameux PRAGMA. Nous ferons appel ici au PRAGMA Priority. Celui-ci permet de fixer la priorité d'une tâche de manière statique : nous définirons la priorité lors des spécifications de la tâche une fois pour toute. Le langage Ada accepte des niveaux de priorités allant de 0 à 30, 30 étant le niveau de priorité maximal. Nous allons également faire appel à un nouveau package : System. Attention ! Pas Ada.system, mais System tout court ! Ce package nous permet d'utiliser un type Priority de type Integer, ainsi qu'une constante Default_Priority qui définit une priorité par défaut de 15.

1
2
3
4
5
6
7
8
9
WITH System ;      USE System ; 
   ...
TASK TYPE T_Tache(P : Priority) IS
   PRAGMA Priority(P) ; 
END T_Tache ; 

TASK BODY T_Tache IS
   ...
END T_Tache ;

Le PRAGMA Priority peut également être utilisé avec la procédure principale. Par défaut, une tâche hérite de la priorité de la tâche qui l'a appelée. C'est-à-dire que si une tâche de priorité 10 déclare des sous-tâches, celles-ci auront une priorité de 10, à moins d'utiliser le PRAGMA Priority.

Et il n'est pas possible de modifier la priorité d'une tâche en cours d'exécution ?

Bien sûr que si. Prenez l'exemple dont nous parlions précédemment. L'antivirus n'est pas un processus prioritaire la plupart du temps… sauf lorsque vous tentez d'accéder à une page web ou à un fichier. L'antivirus commence alors son analyse et il est préférable que cette analyse se fasse rapidement afin de ne pas bloquer ou ralentir les processus ayant besoin de ladite page web ou dudit fichier. Pour effectuer tout changement de priorité, vous devrez faire appel au package Ada.Dynamic_Priorities. Celui-ci définit deux méthodes dont voici les spécifications simplifiées (pour plus de précision, le package porte le nom a-dynpri.ads) :

1
2
3
4
5
procedure Set_Priority(P : Priority;
                       T : Task_Id := Current_Task);

function Get_Priority(T : Task_Id := Current_Task)
  return Priority;

La procédure Set_priority permet de fixer dynamiquement la priorité P de la tâche T (notez que si vous ne renseignez pas le paramètre T, alors Set_priority s'applique par défaut à la tâche qui l'appelle). La fonction Get_priority permet quant à elle de récupérer la priorité d'une tâche (là encore, si le paramètre n'est pas renseigné, c'est la tâche en cours qui est utilisée). Toutefois, n'abusez pas des changements de priorité : ce sont des opérations lourdes. Changer régulièrement la priorité d'une tâche pour l'accélérer peut ainsi avoir comme conséquence improbable de la ralentir.

Un dernier PRAGMA pour la route

Tant que nous parlons des directives de compilateur, en voici une dernière : le PRAGMA Storage_size. Celui-ci permet de définir la taille (en octets) de l'espace mémoire alloué à une tâche. Par exemple :

1
2
3
TASK TYPE T_Tache(P : Priority) IS
   PRAGMA Storage_Size(500 * 2**10) ; 
END T_Tache ;

Chaque tâche de type T_Tache aura ainsi droit à une taille de $500 \times 2^{10}$ octets soit $500$ ko. Si votre ordinateur ne peut allouer 500 ko lors de la déclaration de la tâche, une exception STORAGE_ERROR sera levée.

Quand la programmation orientée objet rejoint la programmation concurrente

INTERFACE, TASK et PROTECTED

Poussons le vice toujours plus loin. Vous avez remarqué que pour appeler l'entrée d'un type protégé, il fallait utiliser une écriture pointée : Objet_Protege.Entree. Cela rappelle la POO non ? Eh bien sachez qu'il est possible de concevoir vos tâches ou vos types protégés «façon objet». Ada nous permet ainsi de faire appel aux notions d'héritage ou d'abstraction comme nous le faisions avec des types étiquetés. Pour déclarer un type tâche ou protégé qui puisse être dérivé, nous devrons le définir comme INTERFACE, ce qui nous donnerait ainsi :

1
2
TYPE T_Tache_Mere IS TASK INTERFACE ; 
TYPE T_Protege_Pere IS PROTECTED INTERFACE ;

L'implémentation se fait comme nous en avions l'habitude :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
--------------------------
--   Types interfaces   --
--------------------------
TYPE T_Tache_Mere1 IS TASK INTERFACE ; 
TYPE T_Tache_Mere2 IS TASK INTERFACE ; 


-----------------------
--   Types dérivés   --
-----------------------
TYPE T_Tache_Fille1 IS NEW T_Tache_Mere1 AND T_Tache_Mere2 ; 

   -- OU 

TYPE T_Tache_Fille2 IS NEW T_Tache_Mere1 AND T_Tache_Mere2 WITH
   ... --écrire ici les différentes entrées de la tâche fille
END T_Tache_Fille2 ;

Les types tâches filles (mais c'est également valables pour des types protégés fils) héritent ainsi de toutes les méthodes (abstraites nécessairement) s'appliquant aux types tâches mères.

Le type SYNCHRONIZED

Mais le langage Ada pousse le vice encore plus loin en termes d'abstraction ! Il est possible de créer un type racine INTERFACE sans savoir s'il sera implémenté par un type tâche ou un type protégé. Il s'agit du type SYNCHRONIZED ! Un type synchronisé peut soit être une tâche soit un type protégé. Il est donc nécessairement abstrait, et le mot SYNCHRONIZED ne s'utilisera donc jamais sans le mot INTERFACE :

1
TYPE T_Synchro IS SYNCHRONIZED INTERFACE ;

Il pourra donc être implémenté de différentes façons, permettant par polymorphisme d'utiliser une même méthode pour des tâches ou des types protégés :

1
2
TYPE T_Tache_Fille IS NEW T_Tache_Mere AND T_Synchro ;
TYPE T_Protege_Fils IS NEW T_Protege_Pere AND T_Synchro ;

Programme multitâche et processeur multicœur (Ada 2012 uniquement)

Depuis plusieurs années, les progrès des processeurs ne se font plus seulement sur leur cadence mais surtout sur leur nombre de cœurs. Vous avez sûrement entendu parlé de processeur Dualcore ou Quadcore ? Ils sont en fait composés de deux ou quatre cœurs, c'est à dire de deux ou quatre processeurs. Ces cœurs se répartissent la charge de travail afin de gagner en efficacité, même si un processeur double-cœur ne va pas deux fois plus vite qu'un simple-cœur. Ce nouveau développement des processeurs a ainsi poussé le langage Ada à évoluer. La norme Ada2012 propose ainsi quelques nouveautés dont un package appelé System.Multiprocessors. Celui-ci propose ainsi la fonction :

1
FUNCTION Number_Of_CPUs RETURN CPU ;

Cette fonction renvoie le nombre de processeurs disponibles (CPU est l'abréviation de Central Processing Unit, soit Processeur). Mais surtout, vous pouvez attribuer un processeur spécifique à une tâche ou un type tâche lors de sa spécification :

1
2
TASK TYPE T_Tache 
   WITH CPU => 2 ;

Ainsi, toutes les tâches de type T_Tache seront attribuées au processeur numéro 2. Les cœurs sont numérotés à partir de 1, mais si vous indiquez que CPU vaut 0, alors la tâche pourra être exécutée par n'importe quel cœur.

Exercices fondamentaux

Nous avons jusque là abordé le multitasking sous un angle ludique. Mais tous les cas de parallélisme ne sont pas aussi simples. Pour nous entraîner, nous allons maintenant résoudre trois problèmes classiques de programmation concurrente : le problème des producteurs et consommateurs, le problème des lecteurs et écrivains et le dîner des philosophes. Pour information, les deux derniers sont des problèmes qui furent à la fois posés et résolus par Edsger Dijkstra.

Modèle des producteurs et consommateurs

Énoncé

Le modèle producteur-consommateur, ou problème du buffer à capacité limitée, est un cas typique : certaines tâches créent des documents, des données qui sont stockées en mémoire en attendant que d'autres tâches viennent les utiliser. C'est typiquement ce qui se passe avec une imprimante : plusieurs utilisateurs peuvent lancer une impression, les documents sont alors placés dans une file d'attente appelée le spool jusqu'à ce que l'imprimante ait fini son travail en cours et puisse les traiter, les uns après les autres. Le problème qui se pose, c'est que l'espace-mémoire dédié à ce stockage temporaire que l'on nomme tampon ou buffer, a une capacité limitée et qu'il est en accès partagé.

Et qui dit ressource partagée dit problème de synchronisation. Voici typiquement ce qu'il faudrait éviter, on a indiqué par «Time Out» les coupures opérées par le tourniquet pour passer d'une tâche à l'autre :

Producteur

Consommateur

Accès au tampon Incrémentation de la taille du tampon (taille vaut 1) Time Out

-

-

Taille = 1 donc accès au tampon Décrémentation de la taille du tampon (taille vaut 0) Retrait des données Sortie du tampon Time Out

Ajout de données Sortie du tampon

-

On voit apparaître une erreur grave : lorsque le consommateur accède au tampon, la taille de ce dernier vaut théoriquement 1, sauf que ce dernier est encore vide dans les faits. Le retrait de données entraînera automatiquement une erreur. Nous devrons donc protéger le tampon, et j'ai décidé que nous allions le faire grâce à un moniteur.

Donc votre mission, si vous l'acceptez, sera de créer un type tâche Producteur et un type tâche Consommateur. Le premier ajoutera dans un conteneur (doubly_linked_list, vector, file à vous de choisir) des caractères tirés au hasard. Attention, la taille de ce conteneur devra être limitée : imaginez un agriculteur qui rangerait 5000 bottes de foin dans un hangar prévu pour 2000, ce n'est pas possible. Le buffer est limité ! Le second type de tâche retirera les caractères de votre conteneur, à condition bien sûr qu'il ne soit pas vide. Pour être certain que les caractères ont bien été retirés, chaque consommateur enregistrera son caractère dans un fichier spécifique. Tout cela ne durera qu'un certain temps, disons quelques secondes. Compris ? Alors à vous de jouer.

Solution

Voici une solution possible au problème des producteurs-consommateurs :

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
WITH Ada.Text_IO ;                              USE Ada.Text_IO ; 
WITH Ada.Calendar ;                             USE Ada.Calendar ; 
with ada.Containers.Doubly_Linked_Lists ; 
WITH Ada.Numerics.Discrete_Random ; 

procedure prod_cons is

      --PACKAGES

   SUBTYPE Chara IS Character RANGE 'a'..'z' ;
   PACKAGE P_Lists IS NEW Ada.Containers.Doubly_Linked_Lists(Chara) ; 
   USE P_Lists ; 
   PACKAGE P_Random IS NEW Ada.Numerics.Discrete_Random(Chara) ; 
   USE P_Random ; 
   
      --TYPE T_STOCK--

   PROTECTED TYPE T_Stock(Stock_Max_Size : integer := 10) IS
      ENTRY Deposer(C : Character) ; 
      ENTRY Retirer(name : string) ;
   PRIVATE
      Stock_Size : Integer := 0 ; 
      Stock : List ; 
   END T_Stock ; 
      
   PROTECTED BODY T_Stock IS
      ENTRY Deposer(C : Character) WHEN Stock_Size < Stock_Max_Size IS
      BEGIN
         Stock_Size := Stock_Size +1 ; 
         Stock.append(C) ; 
      END Deposer ;
      
      ENTRY Retirer(Name : String) WHEN  Stock_Size >0  IS
         F : File_Type ; 
         c : character ; 
      BEGIN
         open(F,Append_File,name) ; 
         C := Stock.First_Element ; 
         Stock.delete_first ; 
         Stock_Size := Stock_Size - 1 ;
         put(F,c) ; 
         close(F) ; 
      END Retirer ;
   END T_Stock ; 
   
   Hangar : T_Stock ; 

      --TYPE PRODUCTEUR--

   TASK TYPE T_Prod ; 
   
   TASK BODY T_Prod IS
      G : Generator ; 
      c : character ; 
   BEGIN
      reset(g) ; 
      LOOP
         c := random(g) ;
         Hangar.Deposer(C) ; 
         put(c) ; 
      END LOOP ;
   END T_Prod ; 
   
   P1, P2 : T_Prod ; 
   
      --TYPE CONSOMMATEUR--

   TASK TYPE T_Cons(nb: integer) ; 
   
   TASK BODY T_Cons IS
      F : File_Type ; 
      name : string := "docs/conso" & integer'image(nb) & ".txt" ; 
   BEGIN
      Create(F,In_File,name) ; 
      Close(F) ; 
      LOOP
         Hangar.retirer(name) ; 
      END LOOP ; 
   END T_Cons ; 

   C1 : T_Cons(1) ; 
   C2 : T_Cons(2) ; 
   C3 : T_Cons(3) ; 

      --VARIABLES POUR PROGRAMME PRINCIPAL--

   D : Duration := 4.0 ; 
   T : Time := clock ; 

BEGIN

   WHILE Clock < T + D LOOP
      NULL ; 
   END LOOP ; 
   
   ABORT P1 ; 
   ABORT P2 ; 
   ABORT C1 ; 
   ABORT C2 ; 
   ABORT C3 ; 
   
end prod_cons ;

Modèle des lecteurs et rédacteurs

Énoncé

Second cas typique, le modèle lecteurs/rédacteurs. Vous disposez d'un unique fichier (par exemple un annuaire contenant des numéros de téléphone à 10 chiffres) et plusieurs tâches tentent d'y accéder «en même temps». Certaines pour lire ce fichier (ce sont les lecteurs), d'autres pour y écrire de nouveaux numéros (ce sont les… suspense… rédacteurs). Imaginez les ennuis si un vendeur de téléphone tente de vous attribuer un numéro de portable alors même qu'un de ses collègues à l'autre bout du magasin (ou chez un concurrent) est en train de modifier la base de données. Votre vendeur pourrait vous attribuer un faux numéro composé à partir de deux numéros, ou vous attribuer un numéro que son collègue vient tout juste d'attribuer ! Bref, il faut protéger le fichier.

Les règles sont simples : il est possible à autant de personnes que possible de lire le fichier. En revanche, seule une personne à la fois peut y écrire et bien sûr il est impossible de lire et d'écrire en même temps. De plus, si deux tâches tentent d'accéder au fichier, un lecteur et un rédacteur, alors c'est le rédacteur qui aura la priorité ou, pour être plus clair, il ne devra pas être interrompu par un lecteur.

Ce problème avait été posé et résolu par E. Dijkstra. La solution qu'il proposait faisait appel aux sémaphores, et nous allons donc nous aussi faire appel aux sémaphores. Pour éviter tout problème sur l'accès au fichier, nous aurons besoin de deux entrées P (P_lecture et P_écriture), de deux procédures V (V_lecture et V_écriture) et donc de deux compteurs (Nb_lecteur et Nb_redacteur) . Cela nous fait ainsi quatre appels possibles. Pour centraliser et clarifier tout cela, je vous propose de ne plus avoir que deux appels (P et V) auxquels nous fournirons en paramètre le type d'accès désiré (lecture ou écriture). Nous utiliserons ainsi un nouveau mot-clé : REQUEUE. Celui-ci a pour effet et ré-enfiler la tâche dans la liste d'attente d'une nouvelle tâche. Ainsi, l'entrée P, donnerait quelque-chose comme ceci :

1
2
3
4
5
6
7
ENTRY P(acces : T_acces) IS
BEGIN
   IF Acces = Lecture 
      THEN REQUEUE P_Lecture ; 
      ELSE REQUEUE P_Ecriture ;
   END IF; 
END P ;

Attention toutefois, un Time Out peut intervenir une fois cette entrée exécutée. Imaginez qu'une tâche souhaite écrire dans le fichier, l'entrée P redirigera notre rédacteur vers la file d'attente de l'entrée P_Ecriture. Maintenant, si un Time Out intervient au profit d'un lecteur, l'entrée P le redirigera vers P_Lecture, lui permettant ainsi de griller la priorité au rédacteur ! Conclusion : ne vous contentez pas de copier-coller le code ci-dessus.

Votre mission est donc de créer des tâches qui liront un fichier contenant une liste de numéros de téléphone pour en afficher une dizaine à l'écran. Vous créerez également des tâches qui enrichiront le fichier. Restera ensuite à créer un type protégé T_Fichier pour gérer les accès et les priorités. Le code fourni en solution propose un générateur de numéros de téléphone à 10 chiffres.

Solution

Le code proposé protège l'accès au fichier (ce qui était le but de l'exercice) mais pas l'accès à l'écran pour ne pas alourdir la solution.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
WITH Ada.Text_IO ;          USE Ada.Text_IO ; 
with ada.Numerics.Discrete_Random ; 

PROCEDURE Lecteur_Redacteur IS

   SUBTYPE Chiffre IS Integer RANGE 0..9 ; 
   PACKAGE P_Random IS NEW Ada.Numerics.Discrete_Random(Chiffre) ; 
   USE P_Random ; 
   g : generator ; 

      -------------------------------
      --   GÉNÉRATION DU FICHIER   --
      -------------------------------

   procedure generate_file(name : string) is
      F : File_Type ; 
   BEGIN
      Create(F,out_File,"./docs/" & name & ".txt") ; 
      reset(g) ; 
      FOR J IN 1..20 LOOP
            put(f,'0') ; 
         FOR I IN 1..9 LOOP
            put(f,integer'image(Random(G))(2)) ; 
         END LOOP ;
         new_line(f) ; 
      end loop ;
      close(f) ; 
   END Generate_File ;
   
      -------------------------------------
      --   LECTURE-ÉCRITURE DU FICHIER   --
      -------------------------------------

   PROCEDURE Read(Name : String ; line : integer := 1) IS
      F : File_type ; 
   BEGIN
      Open(F,In_File,"./docs/" & Name & ".txt") ; 
      IF Line > 1 
            THEN Skip_Line(F,Count(Line-1)) ; 
      END IF; 
      Put_Line(Get_Line(F)) ; 
      close(f) ;
   END Read ; 

   PROCEDURE Write(Name : String) IS
      F : File_Type ; 
   BEGIN
      open(F,append_File,"./docs/" & name & ".txt") ; 
      put(f,'0') ; 
      FOR I IN 1..9 LOOP
         put(f,integer'image(Random(G))(2)) ; 
      END LOOP ;
      new_line(f) ; 
      close(f) ; 
   END Write ; 

      ----------------------
      --   TYPE PROTÈGE   --
      ----------------------

   TYPE T_Acces IS (Lecture,Ecriture) ;

   PROTECTED TYPE T_Fichier IS
      ENTRY P(acces : T_acces) ; 
      PROCEDURE V(acces : T_acces) ; 
   PRIVATE
      ENTRY P_Lecture ; 
      ENTRY P_Ecriture ;
      PROCEDURE V_Lecture ; 
      PROCEDURE V_Ecriture ; 
      Nb_Lecteur, Nb_Redacteur : Integer := 0 ; 
      ecriture_en_cours : boolean := false ; 
   END T_Fichier ;
   
   PROTECTED BODY T_Fichier IS
      
      ENTRY P(acces : T_acces) WHEN not ecriture_en_cours IS
      BEGIN
         IF Acces = Lecture 
            THEN REQUEUE P_Lecture ; 
            ELSE Ecriture_En_Cours := True ; 
                 REQUEUE P_Ecriture ;
         END IF; 
      END P ; 
      
      PROCEDURE V(Acces : T_Acces) IS
      BEGIN
         IF Acces = Lecture 
            THEN V_Lecture ; 
            ELSE V_Ecriture ;
                 Ecriture_En_Cours := False ; 
         END IF; 
      END V ; 

      ENTRY P_Lecture WHEN Nb_Redacteur = 0 IS
      BEGIN
         Nb_Lecteur := Nb_Lecteur + 1 ;
      END P_Lecture ; 
      

      ENTRY P_Ecriture WHEN Nb_Redacteur = 0 AND Nb_Lecteur = 0 IS
      BEGIN
         Nb_Redacteur := 1 ; 
      END P_Ecriture ; 
      
      PROCEDURE V_Lecture IS
      BEGIN
         Nb_Lecteur := Nb_Lecteur - 1 ;
      END V_Lecture ; 
      
      PROCEDURE V_Ecriture IS
      BEGIN
         Nb_Redacteur := 0 ; 
      END V_Ecriture ; 
      
   END T_Fichier; 
   
   Fichier : T_Fichier ; 
   File_Name : String := "numeros" ; 
   
      ----------------------
      --   TYPES TÂCHES   --
      ----------------------

   TASK TYPE T_Lecteur ;
   TASK BODY T_Lecteur IS
   BEGIN
      FOR I IN 1..10 LOOP
         Fichier.P(lecture) ; 
         DELAY 0.5 ; 
         Read(File_Name,I) ; 
         Fichier.V(lecture) ; 
      END LOOP ; 
   END T_Lecteur ; 
   
   L1,L2 : T_Lecteur ;

   TASK TYPE T_Redacteur ;
   TASK BODY T_Redacteur IS
   BEGIN
      FOR I IN 1..10 LOOP
         Fichier.P(ecriture) ;
         Write(File_Name) ;
         Fichier.V(ecriture) ; 
      END LOOP ; 
   END T_Redacteur ; 
   
   R1, R2 : T_Redacteur ; 

BEGIN
   --generate_file(File_Name) ; 
   null ; 
END Lecteur_Redacteur ;

Le dîner des philosophes

Énoncé

Le dernier problème, le dîner des philosophes, est un grand classique de programmation concurrente. Inventé lui aussi par E.Dijkstra, ce problème d'algorithmique met en avant les problèmes d'interblocage et d'ordonnancement. Le problème est le suivant : cinq philosophes se réunissent autour d'une table ronde pour manger et disserter. Chacun dispose d'une assiette de spaghettis et d'une fourchette située à gauche de l'assiette. Mais pour manger, un philosophe doit disposer de deux fourchettes, il doit donc en emprunter une à son voisin de droite. La situation est problématique mais heureusement les philosophes ont également pour habitude de penser, laissant ainsi du temps aux autres pour manger. Un philosophe peut exécuter quatre actions :

  • Penser durant un temps indéterminé.
  • Prendre une fourchette.
  • Rendre une fourchette.
  • Manger, là encore durant un temps indéterminé.

Le but du jeu est de faire en sorte que le maximum de philosophes puisse manger en même temps et qu'il n'y ait pas d'interblocage. Exemple simple d'interblocage : si chaque philosophe prend sa fourchette gauche, aucun ne pourra prendre de fourchette droite et tous mourront de faim. Ce genre de situation peut être mis en évidence en insérant régulièrement des instructions DELAY dans votre algorithme.

Notre programme ne tournera que durant un temps imparti, disons 10 secondes. Et pour nous assurer que nos philosophes ne meurent pas de faim, nous enregistrerons leurs temps de réflexion et de repas dans un fichier texte : un philosophe qui n'aurait réfléchi que 0,4 secondes et mangé 0,8 secondes a très certainement été confronté à un phénomène de famine : tous les couverts étaient pris et notre philosophe est mort précocement. D'ailleurs, il serait bon que les temps de réflexion ou de repas soient aléatoires mais ne dépassent pas la seconde.

La solution consistant a mesurer le temps d'attente et à libérer la fourchette gauche si l'on ne parvient pas à obtenir la fourchette droite en temps voulu est particulièrement mauvaise. Il faut donc concevoir efficacement votre algorithme.

Solution

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
WITH Ada.Text_IO ;                   USE Ada.Text_IO ;
WITH Ada.Calendar ;                  USE Ada.Calendar ;
WITH Ada.Numerics.Discrete_Random ;



PROCEDURE Diner_Des_Philosophes IS

      -------------------------
      --      ALÉATOIRE      --
      -------------------------

   SUBTYPE T_Duree IS integer RANGE 0..1000 ;
   PACKAGE P_Random IS NEW Ada.Numerics.discrete_Random(T_Duree) ;
   USE P_Random ;
   g : generator ;

      ---------------------------------------
      --      CONSTANTES DU PROGRAMME      --
      ---------------------------------------
   
   type Philosophe_Name is (PLATON, SOCRATE, ARISTOTE, EPICURE, PYTHAGORE) ;            --les noms de nos philosophes
   Nb_Philosophes : CONSTANT Natural := Philosophe_Name'Pos(Philosophe_Name'Last) +1  ; --le nombre de philosophes
         --T_Index est l'intervalle 0..4 pour les différents indices
         --il s'agit d'un type modulaire pour faciliter le calcul de l'indice suivant
   type T_Index is mod Nb_Philosophes ;
   Type T_Boolean_Array is array(T_Index) of Boolean ;

      -------------------------------
      --      TYPE FOURCHETTE      --
      -------------------------------

   PROTECTED TYPE T_Fourchette IS
         --P : prendre les fourchettes si possible
         --Le paramètre est un type de sorte que
         --P n'est pas une entrée mais une famille d'entrées
      ENTRY P(T_Index) ;
         --V : rendre les fourchettes
      PROCEDURE V(gauche : T_Index) ;
   PRIVATE
      Libre : T_Boolean_Array := (OTHERS =>True) ;
   END T_Fourchette ;

            -----------------

   PROTECTED BODY T_Fourchette IS
         --Notez bien la notation particulière des paramètres ! ! !
      ENTRY P(for gauche in T_Index) when Libre(Gauche) and libre(gauche+1) IS
      BEGIN
         Libre(Gauche) := False ;
         Libre(Gauche+1) := False ; 
      END P ;

      PROCEDURE V(gauche : T_Index) IS
      BEGIN
         Libre(Gauche) := True ;
         Libre(Gauche + 1) := True ;
      END V ;

   END T_Fourchette ;

            -----------------

   Fourchette : T_Fourchette ;

      -------------------------------
      --      TYPE PHILOSOPHE      --
      -------------------------------

   TASK TYPE T_Philosophe(Numero: T_Index) ;
   
            -----------------

   TASK BODY T_Philosophe IS
      Name : constant String := Philosophe_Name'Image(Philosophe_Name'Val(Numero)) ;   --On extrait le nom à partir du numéro
      Duree : Duration ;                                                               --Durée aléatoire de la réflexion ou du repas
      Temps : Duration := 0.0 ;                                                        --Temps d'activité total
      F : File_Type ;                                                                  --Tout sera enregsitré dans un fichier
   BEGIN
         --Préparatifs
      create(F,out_file,"./docs/" & Name & ".txt") ; 
         --Boucle principale 
      LOOP
            --Période de réflexion du philosophe
         Duree := Duration(Random(G))/1000.0 ;
         Temps := Temps + Duree ; 
         put_line(F,name & " pense pendant " & Duration'image(duree) & "s soit " & Duration'image(Temps) & "s d'activite.") ;
         DELAY Duree ; 
            --Période où le philosophe mange
         Fourchette.P(Numero) ; 
         Duree := Duration(Random(G))/1000.0 ;
         Temps := Temps + Duree ; 
         Put_Line(F,Name & " mange pendant " & Duration'image(duree) & "s soit " & Duration'image(Temps) & "s d'activite.") ;
         DELAY Duree ;
         Fourchette.V(Numero) ; 
      END LOOP ;
   END T_Philosophe ;

            -----------------

      --On utilisera un tableau pour gérer les philosophes
      --Mais comme ceux-ci doivent être contraints par un numéro
      --Nous utiliserons un tableau de pointeurs sur philosophes
   TYPE T_Philosophe_access is access T_Philosophe ;
   TYPE T_Philosophe_Array IS ARRAY(T_Index) OF T_Philosophe_Access ;
   Philosophe : T_Philosophe_Array ;

            -----------------

   T : CONSTANT Time := Clock + 10.0 ;   --indique le temps d'execution du programme
   
      -----------------------------------
      --      PROGRAMME PRINCIPAL      --
      -----------------------------------

BEGIN
   Reset(G) ;
      --Création des tâches Philosophes (allocation dynamique)
   FOR I IN T_Index LOOP
      Philosophe(I) := NEW T_Philosophe(I) ;
   END LOOP ;

      --Boucle principale permettant de faire tourner le programme 10 secondes
   WHILE Clock < T LOOP
      null ;
   END LOOP ;

      --Avortement des tâches Philosophes    
   FOR I IN T_Index LOOP
      abort philosophe(i).all ;
   END LOOP ;

END Diner_Des_Philosophes ;

Commentaires concernant la solution proposée

La solution que je vous propose apporte plusieurs nouveautés. Tout d'abord, au lieu de créer cinq variables tâches distinctes elles ont toutes été réunies dans un tableau.

Mais pourquoi avoir utilisé un tableau de pointeurs sur philosophes au lieu d'un tableau de philosophes ? Tu te compliques la vie ! o_O

Vous avez du remarquer que mon type T_Philosophe n'est pas contraint, il dépend d'un paramètre (numéro). Or, il est impossible de déclarer un tableau contenant des éléments d'un type non contraint. D'où l'usage des pointeurs (cela devrait vous rappeler les chapitres de POO). Ensuite, mes tâches ont besoin d'un générateur G pour s'exécuter. Or, il est préférable que G soit réinitialisé avec reset() avant que les tâches ne débutent. En utilisant les pointeurs, mes tâches ne commencent qu'à partir du moment où j'écris « Philosophe(I) := NEW T_Philosophe(I) » et non à partir de BEGIN ! Cela permet de retarder leur démarrage. Notez d'ailleurs que si vous utilisiez Ada.Unchecked_Deallocation sur l'un de ces pointeurs, cela mettre fin à la tâche pointée, un peu violemment d'ailleurs :-° .

Autre particularité, les fourchettes et les philosophes sont placés autour d'une table RONDE ! Et je rappelle qu'un cercle n'a ni début ni fin. Autrement dit, les numéros des fourchettes et philosophes sont 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1… d'où l'emploi d'un type modulaire pour les numéroter. C'est vrai que je n'ai pas beaucoup utilisé ces types jusque là, mais ils se justifiait totalement dans ce cas. Ainsi, il suffit de calculer gauche + 1 pour connaître l'indice de la fourchette de droite, même si la fourchette de gauche a le numéro 4 !

Troisième remarque : vous avez sûrement noté qu'il est impossible que la garde d'une entrée utilise un paramètre de la même entrée. Impossible d'écrire par exemple : ENTRY P(n : integer) WHEN n > 0 IS. Or nous n'allons pas rédiger une entrée P pour chaque fourchette ! La solution consiste à créer une famille d'entrées en inscrivant en paramètre non pas une variable mais un type :

1
2
3
4
--Spécifications : on n'inscrit que le type, à la manière des intervalles pour les tableaux
   ENTRY P(Integer) WHEN n > 0 ;
--Corps, on indique l'intervalle dans lequel varie notre variable, à la manière des boucles
   ENTRY P(for n in integer) WHEN n > 0 IS

C'est avec ces trois exercices fondamentaux que s'achève notre chapitre sur le multitasking. Il y aurait encore beaucoup à dire car la programmation multitâche est un vaste domaine côtoyant les avancées en matière de processeur. Mais je préfère cesser mes développements pour ne pas trop m'éloigner de notre sujet (le langage Ada) et ne pas alourdir davantage un chapitre déjà compliqué.


En résumé :

  • Les TASK permettent d'adopter une tactique non plus linéaire mais multitâche.
  • Vous devez réfléchir aux problèmes de synchronisation pour concevoir votre algorithme, c'est-à-dire prendre en compte le déroulement et les interruptions de nombreuses tâches simultanées .
  • La synchronisation peut se faire directement via les ENTRY ou indirectement via les types PROTECTED ou SYNCHRONIZED.
  • Les types protégés permettent d'encapsuler dans un bloc PRIVATE vos informations sensibles et d'embarquer les entrées, procédures ou fonctions nécessaires.
  • Il est possible de combiner Programmation orientée objet et Programmation concurrente grâce aux types SYNCHRONIZED, introduit par la norme Ada2005.