IMPLEMENTATION DE REFLEX

Télécharger le fichier original (Mémoire de fin d’études)

Glouton

L’objectif de Glouton, réalisée par Louis Mandel, était de formaliser les m´mécanismes mis en place dans Simple en une sémantique claire et d’implémenter le plus directement possible cette sémantique. Les principales caractéristiques de Glouton sont :
• l’utilisation de deux classes par instruction. Initialement, le programme donn´e a` la machine n’est pas ex´ecutable, c’est un arbre de syntaxe abstraite (AST) qui d´ecrit le comportement du programme. Quand le programme est charg´e dans la machine, il est imm´ediatement traduit en instruction ex´ecutable. A la diﬀ´erence de Simple qui casse la structure du programme au fur et a` mesure de son activation, Glouton le fait au moment du chargement du programme.
• l’introduction de la notion de groupe. Un groupe est une structure qui contrˆole un ensemble d’instructions et qui est l’interface avec l’environnement. Les nœuds de l’arbre du programme ex´ecutable sont des groupes et non des instructions. Il y a plusieurs types de groupes :
• le Groupe qui est la structure de base d’un groupe. Une s´equence Seq(p1,p2) cr´ee un groupe qui contient les instructions du programme p1 et signale que la continuation est le programme ex´ecutable retourn´ par p2. Une boucle est une s´equence dont la continuation est son propre groupe. Un groupe est cr´e´ pour chacune des branches des instructions binaires (Kill, If, When).
• le GroupeKill qui regroupe toutes les instructions et sous-groupes a` pr´eempter. Ce groupe enregistre sa configuration ev´enementielle si elle n’est pas satisfaite. D`es que cette configuration est satisfaite, le groupe est enregistr´ dans celui de plus haut niveau pour ˆetre rappel´ a` la fin de l’instant et ainsi pr´eempter son contenu et mettre le handler dans les instructions a` ex´ecuter a` l’instant suivant.
• le GroupeLoc qui regroupe toutes les instructions qui sont a` ex´ecuter dans le contexte d’un ev´enement local. Une g´en´eration d’´ev´enement est eﬀectu´ee directement dans son groupe qui g´en`ere a` son tour l’´ev´enement dans le groupe local le plus proche du sien. Si l’´ev´enement g´en´er´ ne correspond pas a` l’´ev´enement local du groupe, la g´en´eration remonte le long de l’arbre, de groupe local en groupe local, jusqu’au groupe de plus haut niveau.
• le GroupeLink qui regroupe toutes les instructions dont l’ex´ecution doit ˆetre associ´ee a` un objet. Comme pour les ev´enements, quand une instruction veut connaˆıtre l’objet qui lui est associ´e, elle interroge son groupe qui lui indique le GroupeLink le plus proche et ce dernier lui retourne l’objet concern´.
• le GroupeTop qui est le groupe de plus haut niveau dans la machine r´eactive. Ce groupe est particulier car il correspond aussi `a l’environnement d’ex´ecution. Il contient la table des ev´enements et le bool´een indiquant la fin de l’instant.
• la modification de la s´emantique de Until pour en faire une instruction Kill. Apr`es la traduction de l’AST en programme ex´ecutable, cette instruction donne naissance a` un groupe soumis a` la pr´eemption. D`es que sa configuration est satisfaite, l’instruction s’enregistre dans une file du groupe racine d´edi´ee aux pr´eemptions, pour ˆetre r´eveill´ee a` la fin de l’instant pour r´ealiser cet pr´eemption.
• la disparition de l’instruction Control dans le programme ex´ecutable. Pendant la tra-duction de l’AST vers le programme ex´ecutable, l’instruction Control est remplac´ee par un Await sur l’´ev´enement de contrˆole. Ensuite, l’´ev´enement de contrˆole est propag´e dans toutes les branches du programme contrˆol´e pour modifier tous les points d’arrˆet potentiels, c’est-a`-dire les instructions Stop et les instructions ev´enementielles. Toutes les instructions Stop sont automatiquement suivies par une instruction Await utilisant l’´ev´enement de contrˆole. De mˆeme, les configurations ev´enementielles des instructions soumises au contrˆole sont remplac´ees par une conjonction de cette configuration et de l’´ev´enement de contrˆole. Il y a une exception a` cela, c’est l’instruction When dont l’´evaluation se fait dans l’instant de son ex´ecution. When est dans ce cas pr´ec´ed´ee par une instruction Await sur l’´ev´enement de contrˆole.
• la fin de l’instant est d´eclar´ee a` la fois par un bool´een et par l’interm´ediaire de la g´en´eration de l’´ev´enement « eoi ». Les configurations de toutes les instructions ev´ene-mentielles qui d´ependent de la fin de l’instant, c’est-a`-dire celles concern´ees par une absence d’´ev´enement et celles des instructions When sont modifi´ees. Elles sont remplac´ees par une conjonction compos´ee de leur configuration initiale et d’une disjonction de l’´ev´enement « eoi » et d’un ev´enement « true » g´en´er´ a` chaque d´ebut d’instant. Puisque la fin de l’instant est consid´er´ee comme un ev´enement, Glouton dispose aussi d’une file dans laquelle toutes les instructions qui d´ependent de la fin de l’instant seront enregistr´ees. Ces derni`eres seront r´eveill´ees pour ˆetre evalu´ees a` la fin de l’instant.
L’impl´ementation actuelle de Glouton donne des performances comparables a` celle de Simple. L’inconv´enient de cette impl´ementation par rapport aux autres versions de Junior est qu’elle ne dispose pas encore de l’instruction Freezable. Un des probl`emes pos´e par de cette instruction est le fait que le programme est modifi´e pour faire disparaˆıtre l’instruction de contrˆole. Dans le cas d’une pr´eemption simple, cela ne pose pas de probl`eme, puisqu’il n’est pas n´ecessaire de r´ecup´erer le r´esidu du programme pr´eempt´. Par contre, dans le cas de Freezable, le r´esidu du programme gel´ ne doit pas contenir les modifications li´ees a` une instruction Control qui ne serait pas gel´ee. Un autre inconv´enient est que Glouton ne dispose pas de m´ecanisme de nettoyage de la table d’´ev´enements.
Enfin, nous pouvons noter que, en Glouton, les g´en´erations externes d’´ev´enements dans une safe-machine sont uniquement prises en compte a` l’instant suivant, contrairement aux autres imp ´ementations de Junior qui prennent en compte ces g´en´erations au cours de l’instant si l’´ev´enement a et´ g´en´er´ avant la fin de celui-ci.

Implementation de Reflex

Pour r´ealiser l’impl´ementation de notre s´emantique, nous partons de l’impl´ementation de Storm en lui appliquant des modifications qui se caract´erisent par une r´eduction de la profondeur de l’arbre due au remplacement du format binaire des instructions Par et Seq par leur format N-aire, par une meilleure gestion ev´enementielle et par l’ajout de l’attente passive inter-instant.

Instructions N-aire

Dans les impl´ementations pr´esent´ees pr´ec´edemment, les instructions Par et Seq sont des instructions binaires. Pour les versions Simple et Glouton, il existe des instructions suppl´ementaires appel´ees MultPar et MultSeq. Les instructions Par disparaissent durant la premi`ere activation pour Simple ou durant l’ajout `a la machine pour Glouton pour rem-plir les diﬀ´erentes files d’attente du syst`eme. En Rewrite, Replace et Storm, Par et Seq sont conserv´ees pour garder la structure du programme, Rewrite se permettant de simplifier l’arbre au fur et `a mesure que les diﬀ´erentes branches se terminent.
La mani`ere de construire des programmes reste exactement la mˆeme qu’en Junior . L’in-terface de programmation Ic dispose des mˆemes m´ethodes (Program Seq(Program p1, Pro gram p2) ou Program Seq(Program[] p)). Au moment de la construction, l’objet Seq va tester si les programmes qui lui sont pass´es sont eux-mˆemes des objets de type Seq. Si c’est le cas, les listes de l’instruction Seq parent et des sous-instructions Seq sont concat´en´ees. Il en est de mˆeme pour l’instruction Par avec des sous-instructions de type Par. Le r´esultat du programme d´ecrit dans la table 4.8 est une instruction Par unique conte-nant les programmes P1, P2, P3, P4. Si un de ces programmes d´ebute par une instruction Par, la liste des branches de cette sous-instruction Par est absorb´ee par le Par de plus haut niveau. Il faut tout de mˆeme noter qu’en fusionnant les listes des instructions Par imbriqu´ees.

IMPLEMENTATION DE REFLEX

Programme écrit avec des instructions Par imbriquées

La sémantique du programme est légèrement modifiée (ce n’est pas le cas pour l’instruction Seq). Si l’on consid`ere la s´emantique de l’instruction Par (cf. section 3.7) de fa¸con rigoureuse, la remont´ee des sous-instructions d’une instruction Par imbriqu´ee dans l’instruction Par de niveau sup´erieur modifie l’ordonnancement des tˆaches. D’apr`es la s´emantique, une instruction Par ne retourne un statut que si toutes ses sous-instructions sont dans un ´etat qui ne peut plus ´evoluer. En suivant la s´emantique, l’exemple du code pr´ec´edent ex´ecute d’abord le pro-gramme P1 ou la composition parall`ele des programmes P2 et la composition parall`ele de P3 et P4. Or, la remont´ee de ces sous-instructions les place au mˆeme niveau que les autres d´ej`a contenues dans l’instruction Par. Il n’est alors plus n´ecessaire d’attendre qu’un sous-groupe d’instructions ne puisse plus ´evoluer pour ex´ecuter les autres branches du Par de haut niveau. En faisant remonter ces quatre programmes, l’ex´ecution des branches peut ˆetre ordonnanc´e dans n’importe quel ordre, comme, par exemple, P2, P4, P1 et P3.
L’impl´ementation de l’instruction Par n’utilise pas quatre listes (R, W , LW et S) comme dans la s´emantique (cf. section 3.7) mais cinq. Une liste suppl´ementaire permet de stocker les instructions qui ont termin´ees leur ex´ecution. La liste n’´etait pas pr´esente dans la s´emantique, puisque nous avons d´ecrit celle-ci comme fonctionnant ”`a la Rewrite” pour des raisons de sim-plification (les boucles sont repr´esent´ees, de fa¸con r´ecursive, comme une s´equence entre le corps de la boucle et la boucle elle-mˆeme, sans m´ethode de r´einitialisation). Comme nous l’avons vu, la s´emantique de notre instruction Par ´equivaut a` un programme Close(Par(…)) en Sugar-Cubes, le but ´etant de finir localement l’ex´ecution des sous-instructions de l’instruction Par avant de retourner le statut. Ceci permet d’eﬀectuer beaucoup moins de micro-´etapes globales et donc moins de parcours de l’arbre. L’algorithme d´efini dans la m´ethode ❜② rewrite() consiste alors en ceci :
• si la fin de l’instant n’a pas et´ d´eclar´ee, les instructions de la liste des instructions a` ex´ecuter au cours de l’instant sont ex´ecut´ees tant que la liste n’est pas vide, dans l’ordre dans lequel elles sont enregistr´ees dans la liste (les instructions ne sont pas prises au hasard comme dans la s´emantique). Selon le statut retourn´ par leur ex´ecution, les instructions sont d´eplac´ees vers les listes correspondant au statut de retour. Ladisparition du statut SUSP garantit qu’il n’est pas possible d’ex´ecuter en boucle la mˆeme instruction.
• si la fin de l’instant a et´ d´eclar´ee, on fait de mˆeme sur la liste des instructions ayant retourn´ WAIT. Cette ex´ecution ne retourne que des statuts STOP ou LONGWAIT, ce qui garantit que nous n’allons pas boucler ind´efiniment.
• a` la fin de cette derni`ere ex´ecution, il ne peut y avoir des ´el´ements que dans les listes des instructions ayant retourn´ TERM, STOP ou LONGWAIT. Il ne reste donc plus qu’`a pr´eparer l’instruction pour l’instant suivante c’est-a`-dire de remplir la liste des instructions a` ex´ecuter avec les instructions de la liste des STOP. Pour cela, nous intervertissons simplement les r´ef´erences vers ces deux listes.

Table des matières

Introduction
1.1 L’approche synchrone
1.1.1 Formalismes orientés flots de données
1.1.2 Formalismes orientés contrôle d’exécutions
1.1.3 Formalismes graphiques
1.2 Outils de construction et simulation graphique
1.3 Objectifs et r´ealisation
1.4 Structure du document
I Moteur reactif
2 Modele reactif
2.1 Approche reactive
2.1.1 Definitions
2.1.2 Modele d’execution
2.2 API de Junior
2.2.1 Interfacage avec Java
2.2.2 Les instructions de base
2.2.3 Evenements et configurations evenementielles
2.2.4 Machine et environnement d’execution
2.2.5 Exemple d’utilisation de Junior
2.3 Mod`ele d’ex´ecution de Reflex
2.3.1 S´erialisation des objets de l’API
2.3.2 Disparition de la configuration Not
2.3.3 Pr´eemption r´eguli`ere
2.3.4 Control avec configuration ´ev´enementielle
2.3.5 Retrait de l’instruction Freezable
2.3.6 Retrait de l’instruction Link
2.3.7 Instruction IcobjThread
2.3.8 Machine r´eactive
2.3.9 Instruction Scanner
2.3.10 Instruction Run
2.4 Bilan
3 Semantique de Reflex
3.1 Regles de semantique
3.1.1 Notations
3.1.2 Statuts de terminaison
3.1.3 Environnement d’execution
3.2 Wrappers
3.3 Configurations ´ev´enementielles
3.4 Syntaxe abstraite
3.5 Instructions de base
3.5.1 Nothing
3.5.2 Stop
3.5.3 Actions atomiques
3.5.4 S´equence N-aire
3.5.5 Boucle infinie
3.5.6 Boucle finie
3.5.7 Contrˆole bool´een
3.6 Instructions ´ev´enementielles
3.6.1 G´en´eration d’´ev´enement
3.6.2 Attente d’´ev´enements
3.6.3 Contrˆole ´ev´enementiel
3.6.4 Condition ´ev´enementielle
3.6.5 Pr´eemption
3.6.6 ´Ev´enements locaux
3.7 Ordonnancement : Par N-aire
3.7.1 Fonctions auxiliaires
3.7.2 Les regles
3.8 Machine reactive
3.9 Ajout pour Icobjs
3.9.1 Preemption reguliere
3.9.2 Scanner
3.9.3 Run
3.10 Bilan
4 Implementations
4.1 Implementations existantes
4.1.1 Rewrite
4.1.2 Replace
4.1.3 Simple
4.1.4 Storm
4.1.5 Glouton
4.2 Implementation de Reflex
4.2.1 Instructions N-aire
4.2.2 Gestion des evenements
4.2.3 Machine r´eactive
4.3 Performances
4.4 Bilan
II Icobjs
5 Mod`ele des Icobjs
5.1 Mod`ele d’objets r´eactifs
5.2 Construction par Icobjs
5.2.1 Comportements ´el´ementaires
5.2.2 S´equence et composition parall`ele
5.2.3 Nommage
5.2.4 G´en´eration et attente d’´ev´enements
5.2.5 Pr´eemption
5.2.6 Contrˆole
5.2.7 Construction de boucle
5.2.8 Interruption d’une s´equence
5.2.9 Workspace
5.3 Environnement des Icobjs
5.3.1 Pr´esentation du framework
5.3.2 Inspection des champs
5.3.3 Inspection des comportements
5.4 Bilan
6 Impl´ementation des Icobjs
6.1 Structure d’un icobj
6.2 Ex´ecution des icobjs
6.3 Gestion des ´ev´enements clavier et souris
6.3.1 Les ´ev´enements de souris
6.3.2 Les ´ev´enements du clavier
6.3.3 Les comportements
6.4 Affichage des icobjs
6.5 Inspecteur des Icobjs
6.5.1 Introspection des champs d’un icobj
6.5.2 Introspection du comportement d’un icobj
6.6 Chargement et enregistrement dans un fichier
6.7 Cr´eer sa propre simulation
6.8 Bilan
7 Exp´erimentations
7.1 Projet PING
7.1.1 Architecture de la plate-forme
7.1.2 Mondes virtuels
7.1.3 Communication entre les objets
7.1.4 Coh´erence
7.1.5 M´ecanisme de dead-reckoning
7.1.6 Bilan
7.2 Simulation physique
7.2.1 Mod`ele des comportements physiques
7.2.2 Impl´ementation
7.2.3 Bilan
7.3 Simulation multi-horloges
7.3.1 Description
7.3.2 Impl´ementation
7.3.3 Bilan
8 Conclusions et perspectives
8.1 R´ealisations
8.2 Perspectives
Bibliographie