Rapport de stage
Contents
1. Supposons que les deux processus soient chacun arriv s sur leur commande alternative Les deux commandes vont donc tre valu es parall lement le premier processus va valuer chacune des gardes de l alternative puis les deux tant vrai il va effectu un choix al atoire entre l une ou l autre de m me le second processus va se retrouver devoir faire un choix entre l une ou l autre des gardes de son alternative 14 39 3 LE LANGAGE CSP 3 2 D tails sur les commandes Si les deux alternatives s lectionnent la m me communication aucun probl me n est soulev Par contre si chacune choisie une communication diff rente on assiste un cas d incoh rence entra nant n cessairement un interblocage Ainsi la communication entre commandes d entr e sortie gard es posant des probl mes HOARE a d cid de l emp cher en autorisant uniquement les commandes d entr e dans les gardes Notons que cette contrainte tr s restrictive fait l objet d une modification cf paragraphe 3 3 3 3 2 4 La commande r p titive La commande r p titive est compos e d une unique commande alternative dont l chec entra ne la fin de la r p tition On peut donc consid rer qu une r p titive ne peut que se terminer qu avec succes Syntaxiquement elle se pr sente sous la forme d une toile suivie d une alternative commande alternative Par exemple i 02. i lt 10 gt i i 1 Ici la commande r p titive se terminera lorsque i aura atteint la valeur 10 15 39 3 LE LANGAGE CSP 3 3 Extensions faites au langage 3 3 Extensions faites au langage Voici la liste des extensions faites CSP 1 la syntaxe des d clarations des variables et tableaux t explicit e 2 la possibilit de d clarer des processus en dehors d une commande parall le t rajout e 3 la d claration d un processus MAIN a t impos e afin d indiquer quel sera le premier processus ex cuter 4 la possibilit de d clarer des constantes aussi t rajout e 5 deux nouvelles commandes ont t d finies print et sleep 6 et enfin une modification notoire de la commande alternative a t faite Les points 1 2 et 4 sont principalement des apports syntaxiques et sont repris en annexe Le troisi me point ne n cessite pas d explication particuli re pour une clarification ventuelle se r f rer aux exemples fournis en annexe Les autres extensions sont d taill es dans la suite du rapport 3 3 1 La commande print Dans les exemples donn s dans l article original de CSP HOARE utilisait un processus console afin d afficher l cran les diff rents messages que pouvaient produire les processus Ainsi pour afficher le contenu d une variable message la commande pouvait ressembler ceci console message Le processus console tait don
3. les commandes simples commande nulle skip commande d affectation et commande d en tr e sortie les commandes structur es commande parall le commande r p titive et commande alterna tive Les commandes d entr e sortie parall le r p titive et alternative seront d taill es par la suite Les autres commandes ne n cessitant pas d explications particuli res elles sont simplement reprises en annexe Notons aussi que l chec d une commande entra ne l chec du processus ou de la commande struc tur e qui la contient Sauf dans le cas particulier d une r p titive dont l chec d une commande interne entra ne sa terminaison et non sa faillite cf partie 3 2 4 La commande r p titive Une notion de signal a aussi t introduite en CSP Un signal est en quelque sorte une variable complexe ou structur e compos d un constructeur un identifiant libre ainsi que d un ensemble de valeurs Les valeurs peuvent tre soit de type l mentaire entier cha ne de caract res etc soit Communicating Sequential Processes C A R HOARE 1978 www cs virginia edu evans crab hoare1978csp pdf 10 39 3 LE LANGAGE CSP 3 2 D tails sur les commandes d autres signaux Exemples p 3 5 le constructeur est p et contient les valeurs 3 et 5 p q 3 5 pO ici on dit que p est un signal pur puisqu il ne contient aucune valeur Notons aussi qu un signal pe
4. alternative les gardes des s lectives pouvant en effet contenir une commande d e s Ainsi cet outil devra fournir deux acc s concr tement deux m thodes un premier acc s pour la gestion d une commande d e s simple c est dire hors garde qui prendra donc en entr e un objet CommandeES et fournira en sortie vrai si la commande a r ussi ou faux si elle a chou gestionCommandeES cmd CommandeI0O retourne bool en un second acc s pour les commandes alternatives prenant en entr e une liste de gardes objet Garde et indiquant en sortie la garde s lectionn e ou null si aucune garde n est valide si toutes les gardes sont fausses gestionAlternative gardes Garde retourne Garde Cependant un tel sch ma impliquerait la construction de deux algorithmes Rappelons alors qu une garde est compos e d une expression bool enne et d une commande d e s l une ou l autre de ces parties pouvant tre omise Une simplification possible pourrait donc tre de consid rer une commande d e s comme une garde sans partie bool enne Le premier acc s deviendrait donc inutile et le contr leur serait simplifi une seule m thode traitant une liste de gardes cette liste ne conte nant qu un seul l ment dans le cas d une commande d e s simple Du point de vue du comportement du contr leur ceci ne poserait aucun probl me Dans le cas d une garde unique ne contenant qu une command
5. est d crite avec ANTLR par TLALL k Look Ahead Left to right with Leftmost derivations signifiant analyse ascendante en fonction des k prochaines lex mes 30 39 5 LE PROCESSUS DE COMPILATION 5 2 Utilisation de ANTLR commandeES commandeEntree gt commandeFntree commandeSortie gt commandeSortie La syntaxe a gt a indiquant que a doit tre v rifi avant d tre appliqu C est donc principalement pour cette raison que ANTLR a t pr f r e 4 CUP pour impl menter la grammaire de CSP 5 2 Utilisation de ANTLR Pour cr er un analyseur syntaxique ANTLR compile chaque r gle grammaticale sous la forme d une m thode La r gle d crite dans la section pr c dente sera par exemple compil e par la m thode suivante public void commandeES Ainsi la syntaxe CSP contenant une r gle programme racine de toute la grammaire la v rifica tion syntaxique d un programme CSP s effectuera en appelant la m thode programme de l analyseur cr par ANTLR Tout erreur dans la syntaxe tant alors indiqu e par la lev e d une exception Par ailleurs ANTLR apporte aussi la possibilit d int grer dans l analyseur qui va tre cr des instructions JAVA libres permettant la construction de toute une structure de classes en m me temps que se d roule l analyse syntaxique Pour illustrer ce propos l exemple d cris dans la section pr c dente pou
6. r aliser sera compos e de trois modules un module compilateur centre de l application charg de transformer un programme CSP en programme JAVA un module interface un module runtime englobant les outils n cessaire l ex cution du programme JAVA r sul tant de la compilation 9 39 3 LE LANGAGE CSP 3 Le langage CSP CSP a t mis au point par HOARE dans un article publi en 19782 Comme expliqu pr c dem ment c est un langage de programmation parall le qui int gre un m canisme de synchronisation bas sur le principe du rendez vous d taill plus loin au travers de la commande d entr e sortie Com binant ce m canisme une syntaxe simple et concise CSP permet alors l impl mentation rapide des paradigmes classiques de la concurrence tels que producteurs consommateurs ou lecteurs crivains Un exemple de programme CSP tel que le compilateur doit l accepter c est dire tenant compte des extensions d finies dans la partie 3 3 et d taill est disponible en annexe D autres exemples non comment s sont par ailleurs disponibles impl mentant des paradigmes classiques de lecteurs crivains avec priorit aux crivain producteurs consommateurs avec tampon etc 3 1 G n ralit s Un programme CSP se pr sente sous la forme d une suite de commandes et de d clarations de variable s par es par des points virgule HOARE distingue alors deux types de commandes
7. 1 1 Pr sentation de l institut La pr sentation suivante de VIRCCYN a t r cup r e depuis leur site internet L Institut de Recherche en Communications et Cybern tique de Nantes IRCCyN UMR CNRS 6597 est une unit mixte de recherche du Centre National de la Recherche Scientifique CNRS rattach e au D partement Sciences et Technologies de l Informa tion et de la Communication STIC dont les tutelles sont l cole Centrale de Nantes l Universit de Nantes et l cole des Mines de Nantes Il rel ve aussi des d partements Sciences Pour l Ing nieur SPI et Sciences De la Vie SDV Cet institut compte aujourd hui environ 175 personnes dont 78 chercheurs et enseignants chercheurs 70 doctorants et 19 ing nieurs techniciens et administratifs Il est aussi soutenu par les collectivit s locales et r gionales du fait de sa vocation f d rer les activit s nantaises de recherche relatives tude des m canismes de com munication et de contr le dans les machines les syst mes organisationnels et les tres vivants cybern tique La recherche VIRCCYN n est pas seulement sp culative pour la production de connais sances nouvelles mais elle est en grande partie de nature technologique en ce sens qu elle concerne le d veloppement d outils et de m thodologies capables d apporter des solu tions des probl mes concrets issus du tissus industriel ou socio conomique Les recherche
8. Ici pas de m thode get ou set mais une m thode copyFrom permettant de r cup rer les valeurs d un autre signal de m me constructeur et de les affecter aux valeurs de l objet courant Par exemple les instructions x p integer integer p 1 2 x p 3 5 seront compil es par Signal x new Signal p new CspData lt Integer gt 1 new CspData lt Integer gt 2 x copyFrom new Signal p new CspData lt Integer gt 3 new CspData lt Integer gt 5 M me si une telle compilation peut paraitre lourde elle n en reste pas moins puissante et permet entre autre des affectations du type p a b p b a En effet la m thode copyFrom utilise un tampon afin de palier aux probl mes qui peuvent tre pos s par de telles instructions 4 2 5 Gestion des communications le contr leur Le contr leur est l outil permettant de g rer les synchronisations telles que CSP les d finit en jouant le r le d interm diaire pour chaque communication Ainsi les commandes d entr e sortie ne s adresseront pas directement au processus avec lequel elle doivent communiquer mais au contr leur qui se chargera alors de v rifier les diff rentes contraintes impos es par CSP puis d effectuer la 22 39 4 IMPLEMENTATION DE CSP EN JAVA 4 2 Les outils cr s package csp_ runtime transmission De m me le contr leur est charg de choisir la s lective ex cuter dans le cas d une commande
9. taill plus loin Cependant seuls les s maphores ont t utilis s les autres outils n offrant que peu d int r t ici Les loquets permettent de bloquer un processus jusqu ce qu un certain nombre de t ches aient t effectu es Un tel m canisme n a pas vraiment d utilit ici Les barri res correspondent un rendez vous plusieurs threads En effet chaque thread a la possibilit de venir se bloquer sur une barri re jusqu ce que tous les processus attendus soient eux aussi venus se bloquer Tous sont alors lib r s Un tel outil aurait pu s av rer utile mais l utilisation des s maphores a t favoris e ces derniers fournissant une utilisation plus simple et moins propice aux erreurs Les changeurs sont tr s proches de la synchronisation CSP En effet cet outil permet deux processus de s changer des informations de m me type mettant en attente le premier processus arriv Cependant la commande alternative aurait t difficilement impl mentable cet outil n of frant que peu de souplesse d une part et ne correspondant pas tout fait la s mantique de CSP d autre part En effet la transmission d information est r alis e dans les deux sens tandis que CSP ne permet que des transmission unilat ral Les s maphores ont eux aussi t impl ment s dans ce nouveau package JAVA Rappelons qu un s maphore a comme principale utilit d assurer une forme d excl
10. RECS TN D partement Informatique Rapport de stage COMPILATEUR DE PROGRAMMES CSP EN JAVA Benjamin LE BOZEC 27 juin 2005 Encadrant M Olivier ROUX Responsable M S bastien FAUCOU Stage du 10 avril au 18 juin 2005 version 1 1 Suivi du document version 1 0 20 06 2005 Version initiale version 1 1 24 06 2005 Modifications orthographiques Je remercie particuli rement M Olivier ROUX pour m avoir accueilli pendant dir semaines Je remercie aussi M S bastien FAUCOU pour m avoir aid et conseill tout au long du stage R sum Ce rapport s inscrit dans le cadre d un stage de fin d ann e effectu l IRCCYN sous la tu telle de M Olivier ROUX Le th me du stage tait de r aliser un compilateur de programmes CSP Communicating Sequential Processes mis en place par C A R HOARE en 1978 en JAVA En d autres termes il fallait r aliser un outil capable de cr er un programme JAVA ayant le m me comportement qu un programme CSP donn Dans cet optique la premi re d marche fut d tudier le langage CSP afin d analyser ses contraintes et principes On retiendra tout particuli rement le m canisme de synchronisation complexe bas sur le principe du rendez vous Par ailleurs la d finition originale de CSP donn e par HOARE laissait quelques ambiguit s qu il a fallu clarifier notamment concernant la d claration des variables et tableaux A l initiative de M Olivier ROUX une
11. ROUX The theme was to set up a compiler of CSP programs Communicating Sequential Processes set up by C A R HOARE in 1978 into JAVA programs In other words the purpose was to develop a tool able to create a JAVA program having the same behavior as a given CSP program Accordingly the first step was to study CSP in order to analyze its constraints and principles We will particularly remember the complex synchronization mechanism based on the rendez vous principle In addition the original CSP definition given by HOARE involves some confusions which needed to be clarify specially about variables and arrays declarations With the initiative of Mr Olivier ROUX an important change of the alternative command was made Thereafter the training consisted in focusing on the JAVA language in order to study its tools and constraints The choice of JAVA 1 5 as a platform can be justified by the flexibility in imple mentation specially through the generics and the new concurrent API At the same time the theory of compilation was studied from the lexical analysis to the code generation At last a graphical user interface has been set up Its purposes was to easien the use of the compiler in one hand and to allow the user to follow and monitor the behavior of the program throughout its run It is important to note that developping such an interface is not easy specially in the matter of monitoring the run which means the set up of add
12. a commande fireDeath permettant au processus d indiquer la fin de son ex cution 4 2 2 Impl mentation des variables la classe CspData Comme cela va tre expliqu par la suite un contr leur sera charg de g rer les commandes d e s Par cons quent c est lui que revient la charge d effectuer la transmission et donc d affecter la valeur de l expression source la variable cible cf commande entr e sortie Pour que cette trans 20 39 4 IMPLEMENTATION DE CSP EN JAVA 4 2 Les outils cr s package csp_ runtime mission se fasse correctement il est donc n cessaire au processus mettant la commande d entr e de fournir une r f rence la variable cible En JAVA il n est pas possible de passer directement un pointeur vers une variable et il a donc fallu cr er une nouvelle classe englobant toutes variables c est la classe CspData Du point de vue structurel elle contient un param tre value contenant la valeur de la variable accessible au travers de m thodes get et set Une m thode matches a aussi t d clar e afin de v rifier si deux variables sont de m me type utile lors de la v rification des contraintes d tablisse ment de communication par le contr leur Il est aussi important de noter que la classe CspData est de type g n rique cette notion ayant t apport e avec JAVA 1 5 permettant une manipulation plus facile de la valeur de la variable Par exemple une variabl
13. axiques est explicit en annexe 1 5 1 commandeES commandeEntree commandeSortie commandeEntree nomProcessus indicage variableCible commandeSOrtie nomProcessus indicage expressionSource indicage indice indice indice variable nombre Pr cisons que ces r gles permettent l criture de commandes telles que lecteur 1 message ou ecrivain message etc On remarque ici que la diff rence entre une commande d entr e et une commande de sortie ne peut tre d tect e que lorsque l analyseur rencontre l un ou l autre des symboles ou Par exemple pour l entr e suivante extraite de la commande lecteur 1 message lecteur wey il n est pas possible un analyseur LALR 1 de d tecter s il s agit d une commande d entr e ou de sortie D ailleurs aucun analyseur LALR k ne peut la d tecter le nombre d indices peut varier de 0 linfini th oriquement videmment et par cons quent il n est pas possible de trouver un entier k fixe suffisamment grand pour lever l ambigu t ANTLR qui est de type LALL k avec k param trable propose quant lui des m canismes permettant de lever ce type d ambigiiit En effet il lui est possible de v rifier si une r gle est applicable avant de l appliquer c est ce que ANLTR appelle la pr diction syntaxique Par cons quent la r gle commandeES commandeEntree commandeSortie
14. c est la m thode wait qui est utilis e pour interrompre l ex cution Gr ce ce contr leur d ex cution quatre modes d ex cution sont possibles 1 le mode run il consiste laisser libre l ex cution de tous les processus configurant l objet Sync en cons quence et lib rant l aide de la m thode notifyA11 les ventuels processus ayant t interrompu auparavant 2 le mode pause il consiste interrompre tous les processus configurant l objet Sync en mode pause 35 39 6 L INTERFACE 6 2 Contr le du d roulement 3 le mode pas pas il a pour principe d obliger chaque processus n ex cuter qu une com mande la fois Pour ce faire l objet Sync est configur en mode pause les processus sont alors lib r es par notifyAll puis reviennent se bloquer sur le contr leur d ex cution 4 Enfin le mode temporiser il correspond un mode pas pas la diff rence que ce n est plus l utilisateur qui se charge de lib rer les processus mais un objet Tempo qui appelle la m thode notifyAll intervalle r gulier Pour finir pr cisons que l utilisateur a aussi la possibilit d arr ter l ex cution du programme l aide d un bouton Terminate Ce fonctionnement est possible gr ce l utilisation d un bool en mustStop pr sent dans tous les processus d rivant de la classe CspThread et qui est retourn chaque appel de la m thode debug permetta
15. c un processus toujours pr sent c est dire automatiquement lan cer a l ex cution de tout programme CSP et pouvant communiquer avec tous les processus sans avoir les citer explicitement dans une commande d entr e sortie comme l exige cependant CSP Pour palier aux probl mes que pouvait soulever l int gration d un tel processus la cr ation d une commande print a t pr f r e Cette commande permet chaque thread d afficher un message sur la sortie standard prenant en entr e n importe quelle expression print expression 16 39 3 LE LANGAGE CSP 3 3 Extensions faites au langage 3 3 2 La commande sleep Cette commande a simplement t rajout e afin de permettre l interruption momentan e d un processus Elle se pr sente sous la forme suivante sleep temps temps tant exprim en millisecondes L utilit d une telle commande sera par exemple de simuler un acc s long une ressource ou m me de permettre l impl mentation de processus horloge chien de garde etc Un exemple concret d utilisation est donn en annexe au travers du cas faisant intervenir un chien de garde annexe 1 4 4 3 3 3 Modification de la commande alternative Une modification assez importante de la commande alternative a t faite Comme expliqu pr c demment une commande alternative est compos e d une liste de gardes ces gardes pouvant contenir une commande d entr e mais pas d
16. d dest garde cmdES dest Garde otherGarde dest ctrl findMatches garde garde cmdES perform otherGarde cmdES dest ctrl waitingGardes otherGarde choosen true dest ctrl sem V Kh n H mutex V fsi Commentaires sur l algorithme Dans cet algorithme on remarque donc que c est la m thode filtreGardes qui se charge de v ri fier les quatre contraintes respecter pour l tablissement d une communication cf partie 3 3 3 puisque c est elle qui est charg e d valuer les gardes et donc les ventuelles commandes d entr e sortie Par ailleurs on peut remarquer la pr sence d un s maphore mutex permettant de ne traiter qu une demande de communication la fois 26 39 4 IMPLEMENTATION DE CSP EN JAVA 4 3 Exemple de compilation Pour conclure voici un chronogramme pouvant illustrer le fonctionnement de l tablissement d une communication entre deux processus proci et proc2 proc contr leur proc2 1 Demande de 2 Demande de 3 Communication communication communication de proct de proc Fic 1 Chronogramme d tablissement d une communication Les traits pleins corres pondent l ex cution d un processus On remarque donc que le contr leur stoppe l ex cution du premier processus demandant la communication puis la r tablit une fois que la communication a t effectu e 4 3 Exemple de compilation Un exemple d
17. de listeners a t impl ment Ainsi chaque fois qu un processus souhaite afficher un message les objets ici la fen tre d in terface tant venu se r f rencer sur sa m thode print sont avertis et re oivent le message afficher Le suivi de l ex cution de chaque commande est quant lui l g rement plus complexe fai sant intervenir le compilateur En effet c est ce dernier qui a la charge d ajouter avant chaque commande un appel la m thode debug Cette m thode impl ment e dans la classe CspThread permet au processus d indiquer la prochaine commande qu il va ex cuter Ainsi de m me qu avec la m thode print un m canisme de listeners permet l interface de d tecter chaque appel cette m thode r cup rant alors la position courante de l ex cution 6 2 Contr le du d roulement Il est assur au travers de la m thode debug En effet cette m thode est appel e avant chaque commande et est charg e de dispatcher cet appel vers tous les listeners associ s l objet Le prin cipe est donc d ajouter un listener ayant pour seule utilit de d vier l ex cution du processus vers un contr leur d ex cution ici impl ment par la classe Sync Pr cisons alors que cet objet Sync peut fonctionner sous deux modes un premier mode run laissant libre l ex cution de tous processus un second mode pause for ant tous les processus venir ce bloquer sur l objet Ici
18. e commande de sortie Cette contrainte d ordre syntaxique justifi e dans le paragraphe 3 2 3 a t lev e afin de permettre plus de souplesse dans le programme la place une condition suppl mentaire a t rajout e aux conditions d tablissement d une communication entre deux processus Maintenant pour qu une transmission soit possible entre deux commandes d e s il faut que les conditions suivantes soient remplies 1 l une soit une commande d entr e l autre une commande de sortie 2 les deux processus se nomment mutuellement 3 les typages de la variable cible et de l expression soient identiques 4 l une des deux commandes d entr e sortie doit tre hors garde Ainsi on vite bien les incoh rences pouvant r sulter d une communication entre deux gardes de deux commandes alternatives 17 39 4 IMPLEMENTATION DE CSP EN JAVA 4 Impl mentation de CSP en JAVA Dans cette partie vont tre pr sent s 1 Les diff rents outils fournis par JAVA et pouvant tre utilis s pour impl menter les m canismes de CSP 2 Les diff rents outils cr s tel que le contr leur 3 Un exemple de compilation 4 1 Les outils fournis par JAVA 4 1 1 L API de concurrence JAVA 1 5 a enrichi API classique d un nouveau package java util concurrent contenant de nombreux outils de synchronisation tels que les loquets les barri res les semaphores ou m me les changeurs chacun tant d
19. e compilation est fourni en annexe afin d expliciter au mieux la correspondance JAVA des commandes CSP 27 39 5 LE PROCESSUS DE COMPILATION 5 Le processus de compilation La compilation est un proc d bien connu en Informatique qui suit comme c est le cas ici le sch ma suivant Analyse lexicale Analyse syntaxique G n ration de code Compilation F1G 2 D roulement d une compilation 5 1 Analyse lexicale et analyse syntaxique L analyse lexicale consiste d couper une suite de caract res donn e en entr e comme par exemple un fichier en une suite de lex mes aussi appel s symboles d apr s des r gles de substi tutions bien pr cises souvent donn es sous la forme d expressions r guli res Exemple un nombre entier peut tre repr sent par la r gle nombre 0 9 0 9 L analyseur syntaxique prend quant lui la suite de lex mes g n r e par un analyseur lexical puis cherche quelles r gles grammaticales cette suite peut correspondre 28 39 5 LE PROCESSUS DE COMPILATION 5 1 Analyse lexicale et analyse syntaxique L exemple suivant explicite ce fonctionnement x integer analyse lexicale x integer analyse syntaxique D claration gue eu Variable Type X integer Fic 3 Exemple d analyse lexicale et syntaxique Afin d impl menter de tels analyseurs plusieurs outils existe
20. e d e s par exemple delegueur msg gt le contr leur doit ex cuter la commande si elle est valu e vrai ici si le processus delegueur est d j en attente il doit placer le processus en attente si elle est valu e neutre si delegueur n est pas encore pr t et enfin il doit indiquer que la commande a chou si elle est valu e faux si delegueur a d j fini son ex cution Dans le cas d une commande d e s hors garde le contr leur doit l ex cuter si elle est valu e vrai mettre en attente le processus si elle est valu e neutre ou indiquer que la commande a chou si elle est valu e faux Les deux comportements sont bien identiques et le contr leur pourra donc les g rer de la m me mani re 23 39 4 IMPLEMENTATION DE CSP EN JAVA 4 2 Les outils cr s package csp_ runtime Cependant il est important de souligner qu une telle assimilation permettra possible la commu nication de deux commandes d entr e sortie gard es la condition qu au moins une des deux soit l unique garde de l alternative ce qui ne respecterait plus la derni re condition d tablissement d une communication d crite dans le paragraphe 3 3 3 Rappelons alors que le probl me que posait la communication inter gardes r sultait principalement du fait que l une et l autre des commandes alternatives concern es contenaient plus d une s lective Dans le cas d une alt
21. e d clar e en CSP par x integer 0 sera d clar e en JAVA par CspData lt Integer gt x new CspData lt Integer gt 0 4 2 3 Impl mentation des tableaux classe CspArray En CSP les tableaux peuvent avoir plusieurs dimensions chacune ayant une borne inf rieure ainsi qu une borne sup rieure JAVA lui n a pas cette notion de bornes inf rieure et sup rieure Ainsi afin de simplifier la compilation une nouvelle classe la classe CspArray a t cr e Elle peut tre instanci e pour un type donn e utilisation des g n riques les dimensions pouvant tre born es la CSP Une m thode matches a l aussi t impl ment e afin de tester la correspondance de type entre deux tableaux Les instructions tab 1 10 integer 1 10 0 tab 1 5 21 39 4 IMPLEMENTATION DE CSP EN JAVA 4 2 Les outils cr s package csp_ runtime seront donc compil es par CspArray lt Integer gt tab new CspArray lt Integer gt 0 new Borne 1 10 tab set 1 5 Notons par ailleurs l utilisation de la classe Borne englobant les deux bornes d une dimension 4 2 4 Impl mentation des signaux classe Signal Comme expliqu dans la partie 3 1 un signal est caract ris par un constructeur ainsi qu un ensemble de valeurs Ici le constructeur sera impl ment par une cha ne de caract res les valeurs tant de type Valeur et pouvant donc tre des objets de type CspData CspArray ou Signal
22. ernative une s lective unique le probl me n appara t pas L assimilation peut donc tre valid e Voici donc l algorithme qu impl mente la m thode principale gestionGardes correspondant la m thode gestionAlternative cit e ci dessus Il prend en entr e le processus source metteur de la demande de communication une liste d objets Garde et fournit indirectement en sortie la garde s lectionn e en mettant son attribut choosen vrai Toutes les gardes fournies en entr e doivent donc avoir leur param tre choosen initialis faux Rappelons que les classes Garde CspThread ThreadCtrl et CommandeES utilis es dans l algo rithme sont d taill es en annexe section 2 24 39 4 IMPLEMENTATION DE CSP EN JAVA 4 2 Les outils cr s package csp_ runtime Semaphore mutex new Semaphore 1 m thode gestionGardes source CspThread gardes Garde d but mutex P trueGardes filtreGardes gardes VRAI si trueGardes taille 0 alors neutreGardes filtreGardes gardes NEUTRE si meutreGardes taille 0 alors mutex V sinon source ctrl waitingGardes neutreGardes mutex V source ctrl sem P fsi sinon Garde garde trueGardes random 1 trueGardes taille garde choosen true si garde cmdES null alors 25 39 4 IMPLEMENTATION DE CSP EN JAVA 4 2 Les outils cr s package csp_ runtime CspThrea
23. ette commande Pour expliciter son fonction nement partons du cas simple de deux processus producteur et consommateur le premier voulant transmettre une variable x au second Une telle communication s effectuera alors au travers des commandes suivantes consommateur x permettra au processus producteur d envoyer x au processus consommateur producteur x permettra au processus consommateur de recevoir x depuis le processus producteur Du point de vue de la syntaxe on remarque que le indique une commande de sortie tandis que le indique une commande d entr e Plus formellement une commande d entr e se pr sentera sous la forme processus_source variable_ cible et une commande de sortie sous la forme processus_cible expression_source De plus pour que la communication soit possible entre deux commandes d e s CSP impose que 1 l une soit une commande d entr e l autre une commande de sortie 2 les deux processus se nomment mutuellement 3 les typages de la variable cible et de l expression source soient identiques Dans ces conditions la transmission peut avoir lieu et le contenu de l expression source est copi vers la variable cible Si l une de ces conditions n est pas respect e les processus sont mis en attente entra nant par cons quent un interblocage Si l un des processus est mort alors toute commande d entr e sortie impliquant ce processus doit chou e Enfin le premie
24. ipulation et la visualisation de l ex cution du pro gramme CSP en temps r el pause temporiser terminate Affichage Threads en cours MAIN producteur producteur consommateur liste m Lay out console Console g n r Debug g n rale mb integer 0 message string E true gt message objet num nb print production i nb nb 1 0 TL 1 string tete queue integer message string l 4 message n G 1 NP tete 1 mod TL queue producteur i prod tab tete tete tete 1 mod TL i 1 NC tete queue consommateur i cons tab queue gt F1 console g n rale gt production 1 Fic 6 Fen tre d ex cution objet num 0 L utilisation de l une et l autre de ces parties a t explicit e dans un manuel d utilisateur fourni en annexe Cependant il est important d apporter quelques pr cisions sur la deuxi me partie le suivi et le contr le de l ex cution n tant pas simple impl menter 34 39 6 L INTERFACE 6 1 Suivi du d roulement 6 1 Suivi du d roulement Rappelons que la classe CspThread contient une m thode print cf annexe permettant chaque processus d afficher un message l cran Afin de capter les appels cette m thode tout au long de l ex cution du processus un m canisme
25. itional tools TABLE DES MATIERES TABLE DES MATIERES Table des mati res 1 Environnement 7 1 1 Pr sentation de l institut 7 1 2 D roulement durstaeey owing ack Ai Pe ER oa a GO es 8 2 Expression de la demande 9 3 Le langage CSP 10 Salt SGemeralites o arip Sade po te wong dist eR shee Hon eee PR ONCE IR ee 10 3 2 D tails sur les commandes 11 3 3 Extensions faites au langage oaoa aa 16 4 Impl mentation de CSP en JAVA 18 4 1 Les outils fournis par JAVA 18 4 2 Les outils cr s package csp_runtime 0 a 20 4 3 Exemple de compilation 27 5 Le processus de compilation 28 5 1 Analyse lexicale et analyse syntaxique 28 52 Utihsation de ANTER ES qh eed hie eo Moe ane Re RSR UNIS en 31 5 3 G n ration de Code es ut de dt Mn de eB ee Ne ee de de ut Ro 33 6 L interface 34 6 1 Suivi du d roulement 35 6 2 Contr le du d roulement 35 7 Bilan 37 7 1 D tails de la livraison 37 7 2 Comparaison travail attendu travail effectu 37 7 3 Planning pr visionnel planning r el 38 7 4 volutions possibles name ta 0X gad er wurde de Mile darts 39 6 39 1 ENVIRONNEMENT 1 Environnement
26. modification notoire de la commande alternative a de plus t apport e Par la suite le stage consist a se porter vers le langage JAVA pour en tudier les outils et les contraintes Le choix de JAVA 1 5 comme plate forme a par ailleurs permis une plus grande souplesse dans l impl mentation notamment avec le principe des g n riques ainsi qu au travers de la nouvelle API de concurrence Parall lement il a aussi t n cessaire de s int resser aux grands principes de la compilation depuis l analyse lexicale jusqu la g n ration de code Enfin une interface graphique a t r alis e Ses missions taient de faciliter l utilisation du com pilateur d une part et de permettre le suivi et le contr le de l ex cution du programme CSP d autre part Il est important de pr ciser que la mise en place d une telle interface n a pas t simple notam ment concernant le contr le de l ex cution qui a n cessit l impl mentation d outils suppl mentaires Ce stage a donc permis d aborder de nombreux domaines et fut particuli rement instructif tout particuli rement en ce qui concerne le domaine de la compilation qui n avait pas t abord durant ma formation IRCCYN Institut de Recherche en Communications et Cybern tique de Nantes URM CNRS 6597 Abstract This report falls under the scope of a training course executed in the IRCCYN under the super vision of Mr Olivier
27. ne la v rification du typage dans les op rations et les affectations La partie contr le de l ex cution de l interface pourrait elle aussi tre am lior e en apportant notamment la possibilit de visionner la valeur de chaque variable 39 39
28. nt ainsi de v rifier r guli rement son tat Tout processus a donc pour contrainte de se terminer d s que cette m thode retourne vrai 36 39 7 BILAN 7 Bilan 7 1 D tails de la livraison Voici donc concr tement ce qui a t fourni la fin du stage un compilateur de programmes CSP vers JAVA avec son interface un manuel d utilisateur explicitant le fonctionnement de cette interface le cahier des charges de l application ce rapport et ses annexes 7 2 Comparaison travail attendu travail effectu Globalement le cahier des charges a t rempli un compilateur de programmes CSP en JAVA a bien t r alis de m me qu un contr leur pour g rer les communications L interface a cependant t plus pouss e que pr vu le contr le de l ex cution n tant pas abord dans le cahier des charges Notons cependant que le compilateur ne g re pas d autres types que integer boolean et string le manque de temps n ayant pas permis l impl mentation de types suppl mentaires Par ailleurs le compilateur ne v rifie pas toutes les contraintes qu il devrait pour un programme CSP Par exemple si dans une op ration un bool en est additionn un entier le compilateur ne d tectera pas l erreur par contre l erreur sera bien videmment d tect e par le compilateur JAVA 37 39 7 BILAN 7 3 Planning pr visionnel planning r el 7 3 Planning pr visionnel
29. nt d j en JAVA JFlex cr des analyseurs lexicaux partir de r gles semblables des expressions r guli res CUP fonctionne avec JFlex et cr des analyseurs syntaxiques partir de r gles gramma ticales ANTLRS cr la fois des analyseurs lexicaux et syntaxiques 5 1 1 Comparaison JFLex CUP ANLTR Dans un premier temps l utilisation de JFLex coupl e avec CUP avait t pr f r e ces deux outils tant nettement plus simples utiliser que ANTLR Cependant des probl mes d ambiguit dans la syntaxe ont finalement forc l utilisation de cet outil difficile prendre en main mais tr s puissant En effet CUP est un analyseur de la famille LALR k plus pr cis ment un LALR 1 Il permet 3 JFlex developp par Elliot BERK http jflex de CUP developp par Scott E HUDSON http www cs princeton edu appel modern java CUP SANTLR http www antlr org SLALR k Look Ahead Left to right with Rightmost derivations signifiant analyse ascendante en fonction des k prochains lex mes 29 39 5 LE PROCESSUS DE COMPILATION 5 1 Analyse lexicale et analyse syntaxique donc la r alisation d analyseurs simples et rapides mais se retrouve tr s contraignant sur le type de syntaxe accept e Pour illustrer ceci partons des exemples de r gles suivants issus de la grammaire de CSP rap pelons que le formalisme utilis pour l expression des r gles synt
30. pas encore pr t faux si le processus nomm par la commande est mort i e a fini son ex cution Dans le cas d une garde contenant la fois une partie expression bool enne et une partie commande_entr e l expression bool enne est d abord valu e Si elle est faux la garde est valu e 13 39 3 LE LANGAGE CSP 3 2 D tails sur les commandes faux Si elle est vrai la commande d entr e est alors valu e donnant ainsi la valeur la garde Ainsi si une ou plusieurs commandes gard es sont vraies un choix ind terministe i e al a toire doit tre effectu pour n en s lectionner qu une Si aucune n est vraie mais que certaines sont neutres le processus se met en attente des commandes d entr es correspondantes Et si toutes les commandes gard es sont fausses la commande alternative choue Si une garde est s lectionn e la liste de commande correspondante doit alors tre ex cut e Il est aussi important de noter que la contrainte d ordre syntaxique limitant les commandes d e s dans les gardes aux simples commandes d entr e provient d un choix fait par HOARE dans le but d viter les incoh rences Pour illustrer ce propos partons de l exemple suivant qui suppose possible l utilisation de commande de sortie dans les gardes proci proc2 p gt proc2 q gt proc2 proci p gt proci q gt
31. planning r el Sur le diagramme ci dessous apparaissent planning pr visionnel en rouge et planning r el en orange Installation et prise en main Recherche des outils dis ponibles Compr hension langage CSP Impl mentation du contr leur Tests impl mentation de l analys eur Tests Impl mentation de l interface Tests Tests globaux Manuel d utilisateur Rapport Semaine du au 7 E 9 Tf avr 18 avr 25 avr 02 mai 09 mai 16 mai 23 mai 30 mai O6 juin 13 juin 16 avr 23 avr SO avr O7 mai T mai 21 mai 28 mai Od juin T1 juin 18 juin Fic 7 Comparaison planning pr visionnel planning r el On remarque donc de nombreuses diff rences notamment concernant les phases d analyse et de g n ration de code En effet la compilation reste un th me tr s peu abord durant la forma tion de DUT Informatique et c est un principe qui s est av r bien plus complexe qu il n y paraissait Le contr leur s est quant lui r v l plus simple le traitement des commandes une une permettant d viter de nombreux probl mes 38 39 7 BILAN 7 4 volutions possibles 7 4 Evolutions possibles Le compilateur fournit ne g rant pas d autres types que integer boolean et string une pre mi re volution serait d tendre sa port e des types comme float ou double Ensuite une autre volution serait d am liorer la d tection des erreurs du compilateur notam ment en ce qui concer
32. qu pr c demment chaque r gle syntaxique a t associ e une classe JAVA La g n ration de code a donc consist impl menter pour chacune de ces classes une m thode compile retournant le code JAVA associ la r gle CSP sous forme d une cha ne de caract res Par exemple la m thode compile de la classe Affectation pourrait tre impl ment e de la mani re suivante public String compile return variableCible compile expressionSource compile Par cons quent la g n ration de code li un programme CSP consiste appel la m thode compile de l objet Programme r sultat de l analyse syntaxique 33 39 6 L INTERFACE 6 L interface L interface doit permettre l utilisateur une maitrise facile du compilateur et du d roulement de l ex cution Ainsi L interface se compose de deux parties 1 une partie visant simplifier l utilisation du compilateur E compilateur CSP gt Java programme csp javac gt 1 5 package cible C Documents and Settings Administrateur BureauistageleclipseicspProjetv0 9991 test2 csp CAProgram Files Javaljdk1 5 0_02 bin javac exe outputDir Compiler Analyse syntaxique Compilation CSP gt JAVA Compilation JAVA icompilation OK Fic 5 Fen tre du compilateur 2 une partie runtime permettant la man
33. que le programme CSP source Le choix de JAVA comme langage destination peut tre justifi par la grande palette d outils qu il fournit d une part la derni re version de JAVA apporte en effet de nombreux m canismes de synchronisation et d autre part par le fait qu il soit compatible sur les diff rents syst mes existants Microsoft Windows Linux C est d ailleurs pour ce second atout que le compilateur sera lui m me impl ment en JAVA Dans un premier temps il convient donc de comprendre le langage CSP et d analyser ses contraintes Parall lement il est n cessaire de rechercher quels outils fournis par JAVA peuvent tre utilis s pour impl menter les m canismes de CSP Ce travail de recherche et d analyse devra donc aboutir l laboration d outils visant simplifier la compilation tel qu un contr leur pour g rer les communications inter processus Dans un second temps le travail se portera alors sur le processus de compilation c est dire sur la traduction propre des programmes CSP en programmes JAVA Par ailleurs une interface graphique t r alis e afin de faciliter l utilisation du compilateur Cet interface a aussi pour vocation de permettre l utilisateur de suivre l ex cution du programme Un manuel d utilisateur est fourni en annexe pour expliciter le fonctionnement de cette interface Architecture de l application On peut donc consid rer que l application
34. r processus demandant la com munication doit tre mis en attente jusqu a ce que le second le rejoigne On retrouve ici le principe du rendez vous Notons aussi le cas particulier d une synchronisation simple c est a dire sans transmission de valeur possible gr ce l utilisation d un signal pur 12 39 3 LE LANGAGE CSP 3 2 D tails sur les commandes Exemple producteur consommateur p I consommateur producteur p 3 2 3 La commande alternative Une commande alternative se pr sente sous la forme d un ensemble de s lective chacune tant compos e d une garde ainsi que d une liste de commandes Une garde est quant elle compos e d une partie expression bool enne et d une partie commande d entr e l une ou l autre pouvant tre omise Syntaxiquement une commande alternative se pr sente sous la forme suivante gardei gt liste de commandes 0 garde2 gt liste de commandes E Lors de l ex cution d une commande alternative chacune de ses gardes est test e afin de d terminer sa valeur selon une logique trivalu e c est dire qu une garde peut tre vrai fausse ou neutre Une expression bool enne peut videmment prendre les valeurs vrai ou faux Une commande d entr e prend la valeur vrai si la communication est possible imm diatement neutre si le processus nomm par la commande n est
35. rra tre transformer de la mani re suivante Attention Il est important ici de bien not que la classe CommandeES utilis e ici ne correspond en aucun cas la classe CommandeES du package csp_runtime commandeES returns CommandeES cmd commandeEntree gt cmd commandeEntree l commandeSortie gt cmd commandeSortie 31 39 5 LE PROCESSUS DE COMPILATION 5 2 Utilisation de ANTLR et sera compil par ANTLR de la mani re suivante public CommandeES commandeES CommandeES cmd cmd commandeEntree cmd commandeSortie return cmd Ici il a donc t d cid d utiliser au maximum les possibilit s fournies par ce compilateur d analyseur dans le but d obtenir en fin d analyse un unique objet Programme contenant de mani re hi rarchis e l ensemble du programme sous forme d objets JAVA comme l explicite le sch ma suivant Programme Liste de macros acro Macro ee commandes Commande Commande w affectation entr e sortie Fic 4 Hi rarchie d objets r sultant d une analyse syntaxique Par cons quent une classe JAVA a t cr e pour chaque r gle de la grammaire de CSP l ensemble de ces classes tant contenu dans le package compilateur cspLangage 32 39 5 LE PROCESSUS DE COMPILATION 5 3 G n ration de code 5 3 G n ration de code Comme ceci a t expli
36. s et les actions de valorisation qui y sont d velopp es couvrent un domaine scientifique tr s large englobant l automatique le traitement du signal des images et des signaux radar la robotique la productique la conception m canique assist e par ordinateur les syst mes temps r els la logistique et la recherche op rationnelle 7 39 1 ENVIRONNEMENT 1 2 D roulement du stage la prise en compte des facteurs humains psychologie cognitive La qualit des r seaux Ceci en fait un des principaux laboratoires nationaux dans cette th matique 1 2 D roulement du stage Le stage a t effectu dans l une des salles informatique de l IRCCYN Un ordinateur fut mis ma disposition ordinateur qui a par ailleurs n cessit l installation de la derni re version de JAVA 1 5 et du logiciel ECLIPSE 8 39 2 EXPRESSION DE LA DEMANDE 2 Expression de la demande et premi re approche du sujet CSP Communication Sequential Processes est un langage de programmation parall le ou concurrente Il repose sur quelques principes algorithmiques simples alternative et r p tition es sentiellement et propose un m canisme de synchronisation de processus fond sur le principe du rendez vous L objectif du travail est de mettre au point un compilateur qui transforme des programmes CSP en JAVA dans le but de d obtenir un programme JAVA ayant le m me comportement
37. usion mutuelle mais il peut aussi 18 39 4 IMPLEMENTATION DE CSP EN JAVA 4 1 Les outils fournis par JAVA permettre de bloquer un processus jusqu ce qu un autre d cide de le lib rer cas o le semaphore est initialis avec 0 jetons C est donc surtout cette deuxi me fonction qui nous int ressera ici Les verrous existaient d j avant la version 1 5 Ils correspondent un m canisme relativement complexe permettant en autre d assurer un processus la manipulation exclusive d un objet Ici les s maphores ont t pr f r s ce m canisme 4 1 2 La cr ation de processus en JAVA En JAVA tout processus doit h riter de l interface Runnable obligeant ainsi l impl mentation de la m thode run qui est ex cut e au lancement du processus La classe Thread permet alors la manipulation de ces processus se chargeant entre autre de les ex cuter Notons aussi la m thode statique sleep de la classe Thread qui pourra tre utilis e pour la compilation de la commande sleep 19 39 4 IMPLEMENTATION DE CSP EN JAVA 4 2 Les outils cr s package csp_ runtime 4 2 Les outils cr s package csp_ runtime Le package csp_ runtime contient un ensemble de classes et d interfaces visant simplifier l ex cution des programmes CSP On peut citer la classe CspThread qui correspond 4 la classe parente de tous les processus CSP la classe CspData qui est la classe parente de toutes les
38. ut tre affect une variable exemple x p 4 Enfin du point de vue de la port e des variables les variables d finies avant une commande structur e doivent tre visibles par les commandes qu elle contient 3 2 D tails sur les commandes 3 2 1 La commande parall le Elle permet la mise en concurrence de processus par la syntaxe suivante proci liste de commandes I proc2 liste de commandes Une telle commande ne se termine que lorsque tous les processus qu elle d finit sont termin s V chec d un seul entra nant l chec de la commande parall le Rappelons ici qu une variable d finie avant une commande structur e doit tre visible par les commandes qu elle contient Dans le cas d une commande parall le ceci implique n cessairement que tous les processus d finis devront avoir acc s aux variables d clar es avant la commande pa rall le On assiste donc ici un partage de ressources dont les contraintes soulev es acc s exclusive etc sont la charge du programmeur On note aussi la possibilit de d clarer plusieurs processus pour une m me liste de commandes comme le montre l exemple suivant proci i 1 10 liste de commandes Ici dix processus ayant la m me liste de commandes seront mis en concurrence 11 39 3 LE LANGAGE CSP 3 2 D tails sur les commandes 3 2 2 La commande d entr e sortie Les communications entre processus reposent sur c
39. variables la classe CspArray permettant de d finir des tableaux la classe Signal correspondant 4 la notion de signal CSP la classe Select permettant de simplifier les commandes alternatives la classe Garde simplifiant la manipulation des gardes des commandes alternatives la classe CommandeES correspondant une commande d entr e sortie CSP l interface ExprBool qui permet la d claration de la partie bool enne d une garde l interface Valeur qui est impl ment par toutes les classes stockant des donn es c est dire les classes CspData CspArray et Signal la classe Controleur venant g rer les communications inter processus et enfin la classe ThreadCtrl correspondant un vecteur d tat associ chaque processus et utilis exclusivement par le contr leur En annexe sont fournies des pr cisions sur chacune de ces classes et interfaces la mani re d une documentation JAVA 4 2 1 Impl mentation des processus classe CspThread Pour chaque processus d fini dans un programme CSP une nouvelle classe h ritant de CspThread devra tre cr e CspThread fournit par ailleurs quelques m thodes afin de simplifier la compilation La m thode start permettant de lancer le processus La m thode join permettant d attendre la fin de l ex cution d un processus Les m thodes input et output correspondant respectivement une commande d entr e et une commande de sortie enfin l
Download Pdf Manuals
Related Search