Home

Génération de code de systèmes distribués

1. brief De allocates a chunk in the pool param p The pool param el The contetns to be freed void free_pool pool p void el gt size defin alloc_imess 1 MESS define wait_alloc_imess 1 MESS defin free_imess m defin alloc_omess 1 MESS define wait alloc omess l MESS defin free omess m defin alloc site SITE ls wait alloc pool Il ll e J return sem trywait amp p gt size pool free p head el sem post amp p alloc pool amp IMESS_ POOL amp IMESS POOL amp IMESS POOL m free pool I amp OMESS POOL alloc pool wait alloc pool amp OMESS POOL free pool amp OMESS POOL m alloc pool amp SITE POOL KKKKkK K K K K Kk K K K Kk K K K Kk K K K Kk K K K Kk K K K Kk K K Kk Kk K K Kk Kk K K Kk Kk K K k Kk K K Kk Kk K K Kk K K Kk k K K Kk Kk K K Kk k K K Kk k K K Kk k Kk Kk Kk K DYNAMIC ALLOCATION RR KR KK K K K K K K K Kk K K K K K K K Kk K K K Kk K K Kk Kk K K Kk Kk K K Kk Kk K K Kk Kk K K Kk Kk K K Kk Kk K K Kk K K K Kk K K Kk k K K Kk k K K Kk k K K Kk k K Kk Kk K in in line SITE al loc_site ine MESS in in line void line void ndif return mal loc sizeof SITI Pl return mal al loc sizeof MESS DEFAUL loc_mes
2. Figure 2 29 Exemple de s quence dSL instruction d attente GLOBAL VAR I e ENR i BOOL END VAR SIT E sitel INPUT a 0 0 1 OUTPUT b t gt VELG E ND_SITE E SEQUENCE distri x INT y BOOL wait i OR y h x END SEQUENCE Figure 2 30 Exemple de s quence dSL deux param tres 33 10 11 Les v nements Un v nement est d fini sur une condition et une suite d instructions respectant la contrainte atomique Les diff rentes m thodes pour rel cher la contrainte atomique ont t d taill es dans 6 Code atomique et s quentiel La figure 2 31 pr sente un ensemble d v nements d finis de mani re correcte Les sites de distribution de chacun des v nements ont t pr cis s en commentaires CLASS CD Geh LNT END CLASS GLOBAL VAR a b INT cd CD END VAR SITE sitel INPUT a 0 0 1 OUTPUT b 1 1 1 END SITE SITE site2 INTERNAL cd c INTERNAL cd d END SITE ETHOD CD cEGALd self c self d END METHOD HEN a 0 THEN sitel LAUNCH bEGALa END WHEN I EN c 0 THEN site2 cEGALd appel synchrone sur son propre site END WHEN HEN a 0 THEN sitel LAUNCH cEGALd appel asynchrone
3. ENGTH DEFAULT HEADER SIZE switch BIT of site sem post amp sem ab write Message treated destroy it t M M M gt NEXT free imess t Loop on messages sem post amp sem ab write Loop while 1 brief Thread handling outgoing messages Ze static int thread AB_O SITE S unsigned char MSG while 1 msleep 250 134 sem_wait amp sem_ab write S S_ while S S FIRST if S gt LIST NULL _MSG S gt LIST gt MSG if MSG DEST MSG S LIST erase S else MSG HEAD MSG 0 set bit MSG get sb S user portHandler MSG DEFAULT H id_site EADER SIZ gt LENGTH DEFAU T HEAD gt RSBIT 1np integrity write _MSG S gt LIST gt LENGTH msleep 0 EXT sem post amp sem ab write return 0 Naddtogroup ab interface brief Initialises everyth param u portHandler The f received param id site The i param n sites The n param incoming The n param outgoing The n return 0 on success 1 ot warning When AB STATIC is ougoing are ignored x int init ab protocol void u portHandler unsigned char length if AB STATIC y ER SIZE ing needed for us unction that will b of reliable protocol is nt site umber participating
4. AND c_1 free TRUE take control of the moving car IF last in FALSE H EN LAUNCH tl 3 last in T ELSE LAUNCH t2_to last_in FA IF to RUE SE END END WHEN T 0 r E347 152
5. wait event amp getControl unsigned int cpid void wakeup pid t id pushStack pid t cpid current thread id id wait event amp getControl unsigned int cpid Figure 5 5 Fonctions C de mise en attente et de r veil de tache LegOS 2 La tache Input Process Output Nous avons vu dans 77 1 Introduction au langage SL que chacun des sites constituant le syst me devra ex cuter continuellement la boucle nput Process Output qui fera donc l objet d une t che par site cr e d s l initialisation du syst me La figure 5 6 reprend le code de la fonction contenant les instructions de la tache principale Cette fonction fait partie des m thodes pr d finies du fichier dsl vm h dont le code est repris en Annexe D int start while true sampleInputs handleWhens handleMsg writeOutputs return 0 Figure 5 6 Fonction de la tache de la machine virtuelle samplelnputs est la fonction charg e de la lecture des entr es du site handleWhens est la fonction charg e du traitement des WHEN distribu s sur le site handleMsg est la fonction charg e de la gestion des messages recus par le site Et finalement writeOutputs est la fonction charg e de la mise jour des dispositifs de sortie du syst me Le contenu des fonctions samplelnputs et writeOutputs est d taill dans le paragraphe 7 Les entr es sorties La fonction handleWhens est d
6. You should have received a copy of the GNU General Public License program if not write to the Free Software 59 Temple Place Suite 330 Boston MA 02111 1307 USA along with this Foundation Inc E mainpage Alternating Bit Protocol section contents Package Contents This package implements the Alternating in C with legOS BrickOS system calls htmlonly Bit Protocal AB Protocol For more information on the alternating bit protocol look lt a href http wombat doc ic ac uk foldoc foldoc cgi Alternatingtbit protocol gt her e lt A gt FOLDOC endhtmlonly communication primitives wi F x The AB protocol makes the communciations between Lego RCXs reliable The importance of a reliable protocol is undeniable since the standard th LegOS BrickOS based on LNP guarantee only the integrity of packets lt B gt not lt B gt their delivery This protocol implementation does not achive miracles two bricks that are definately out of range will never communicate unless using a nifty 124 0X 0 F 0X H H H F F H F 0o 0 F 0k 0X 0X 0 OX 0k OX 0X OX 0X 0X F 0X OX F FF OX FF FF Xo Xo FF FF F OF S ad hoc protocol The protocol will continue to try to send the message and can notify the sender when the message was received This package is multi threaded robust effici
7. 4 brief Gets the first free element and marks it as not free param head The pool s first element return the content pointed to by the first free element NULL if none warning disables IRQs to make concurrent access safe Linear in the size of the pool yf void pool get first pool el head ENTER CRITICAL for head head head gt next if head gt free head gt free FALSE break EXIT CRITICAL return head head gt cont NULL SC brief Marks an element as free in a pool param head The pool s first element param el The chunk of allocated memory warning disables IRQs to make concurrent access safe Linear in the size of the pool void pool_free pool_el head void el ENTER CRITICAL for head head head next if head gt cont el head gt free TRUE break EXIT CRITICAL pel brief Allocates a chunk from the pool and waits until an element is freed in case no elements are free param p The pool return A pointer to the first free element void wait alloc pool pool p sem wait amp p size return pool get first p head Pes brief Allocates a chunk from the pool param p The pool Nreturn A pointer to the first free element NULL if none where free 130 VO qd alloc pool pool p pool get first p gt head NULL
8. c Les instructions d it ration La forme g n rale d une instruction d it ration est WHILE condition DO liste instructions END WHILE 21 La construction WHILE permet d ex cuter une suite d instructions tant qu une condition est vraie Lorsque le contr le arrive sur une instruction WHILE la condition est valu e Si celle ci est fausse l instruction suivant le END WHILE est ex cut e Si celle ci est vraie la liste d instructions est ex cut e et la condition est r valu e d Les instructions d attente L instruction WAIT permet de sp cifier un arr t dans l ex cution d une s quence Cet arr t est d fini soit sur un intervalle de temps soit sur une condition Dans le premier cas la forme g n rale est WAIT constante ou constante est le temps en milisecondes pendant lequel l ex cution de la s quence sera retard e Dans le second cas la forme g n rale est a WAIT condition ou condition est une expression logique L ex cution de la s quence est suspendue juqu a ce que la condition soit vraie e Les instructions de lancement Les instructions de lancement sont d finies au moyen des op rateurs lt et LAUNCH Les formes g n rales d une instruction de lancement d une m thode sont instance classe id m thode param tres 3 LAUNCH instance classe lt id m thode param tres o
9. brief Use this function to asynchronously send a message The message is added to the list and will be sent as soon as possible The function returns immediately param message The message to send param length The length of the message param destination The destination for the message return A pointer to the MESS structure if successfully added to the list ULL otherwise N MESS ab_awrite const unsigned char message unsigned char length unsigned char destination brief Use this function to synchronously send a message The message is added to the list and will be sent as soon as possible The function returns when an acknowledgment is received for the message param message The message to send param length The length of the message param destination The destination for the message return A pointer to the MESS structure if success NULL otherwise MESS ab_swrite const unsigned char message unsigned char length unsigned char destination brief Initialises everything needed for use of reliable protocol param u portHandler The function that will be called when a message is received param id site The id of the current site param n sites The number participating distant sites Nparam incoming The number of simultaneously incoming messages Nparam outgoing The number of simultaneously outgoing messages return 0 on success 1 otherwi
10. Figure 5 18 Traduction d une instruction d it ration dans une s quence 13 Les v nements Soit l v nement suivant WHEN condition THEN liste instructions END WHEN liste instructions doit tre ex cut chaque fois que condition passe de faux vrai Une variable 69 globale bool enne est cr e pour chaque v nement d un site et contient l ancienne valeur de la condition de l v nement cf 6 Les variables Les instructions de traitement d un v nement sont isol es dans une fonction void graph_id Cette mani re de proc der est conserv e pour des raisons historiques Elle provient du fait que le parser cr e un bloc de base d identificateur id qui contient le traitement de l v nement Le code de l inspection de la condition d un v nement est repris dans la figure 5 19 o id v nement est l identificateur de l v nement et id traitement est l identificateur du bloc de base des instructions de l v nement IF NOT old condition id v nement AND condition old condition id v nement condition graph id else old condition id v nement condition Figure 5 19 Code d inspection d une codition La condition d un v nement doit tre inspect e chaque fois qu une des variables apparaissant dans l expression de sa condition est modifi e Lorsqu une variable apparaissant dans le code d au moins une condition d v nement est assign
11. X l ensemble des variables tild es corespondant X X x x eX De plus pour d finir la s mantique de dSL les expressions suivantes sont ajout es pour d crire des traitements internes INPUT id repr sente la lecture de la variable d entr e id 35 OUTPUT id repr sente l criture de la variable de sortie id BCAST id repr sente l envoi de la variable id tous les sites d ex cution MSG repr sente le traitement des messages stock s dans une file FIFO c est dire First In First Out 11 2 Distribution maximale dSL permet de mod liser des syst mes distribu s La distribution d un programme dSL correct est la partition de l ensemble des variables du programme respectant les contraintes atomiques impos es par les WHEN Notons que si deux variables apparaissent non tild es dans un WHEN alors elles doivent tre n cessairement distribu es sur le m me site Pour rappel les m thodes sur lesquelles portent aussi la contrainte atomique sont suppos es inline Definition 1 Distribution d un programme dSL correct La distribution d un programme dSL P est un partitionnement D Vi V2 V de l ensemble Var P et est correct si et seulement si V w e When P Vvi v e Var w 3V e D vv C Vi L ensemble de toutes les distributions correctes d un programme P est not e Dp Le comportement d un programme dSL est d fini par la distribution de ses variables et de son code La contrainte
12. kind localizable Ihside NUMBER NUMBER NUMBER ID localizable lhside ID localizable_lhside constant P localizable_lhside INTERNAL INPUT OUTPUT WHEN rhside THEN local variables instruction list END WHEN WHEN IN ID rhside THEN local variables instruction list END WHEN 107 method sequence parameter_declaration_list type instruction list instruction assign wait else while Jhside rhside constant METHOD ID ID parameter declaration list local vanables instruction list END METHOD SEQUENCE ID parameter declaration list local variables instruction list END SEQUENCE ID C parameter declaration list local variables instruction list END SEQUENCE variable declaration parameter declaration list LONG INT BOOL ID ARRAY NUMBER NUMBER TP OF type instruction assign wait if while call lhside rhside WAIT rhside TF rhside THEN instruction list else ELSE instruction list END IF WHILE rm side DO instruction list END WHILE ID lhside ID Ihside f rhside J lhside constant C rhside rhside OR rhside rhside AND thside rhside lt rhside rhside gt rhside rhside lt rhside rhside gt rhside
13. none id transmitted i va arg ap int ADD INT TO CHAR p i param send message ln site va end ap void SEND ID WARN int site int id int val char message 5 p message ptt 3 ADD INT TO CHAR p id ADD INT TO CHAR p val send message 5 site void HOP int site int sequence int id int n para const unsigned char ln n para 2 6 char message ln p message unsigned char i int arg 121 va list ap va start ap n para p 1 ADD INT TO CHAR p sequence ADD INT TO_CHAR p id p n para for i 0 i n para 2 i For each parameters id val arg va_arg ap int ADD INT TO CHAR p arg send message ln site va end ap define SELF HOP sequence id HOP ID SITE sequence id 0 void handleMsg int nbVal i nMax id val seq unsigned char ptr type pid t seq id Ka sem getvalue amp sem SIZE BUF amp nMax while sem trywait amp sem SIZE BUF type ptr dsl vm buf ST BUF ptr if type 1 launch sequence O amp amp nMax READ INT FROM CHAR seq ptr READ INT FROM CHAR dsl vm id ptr if dsl vm args char malloc ptr 2 1 error ERR OUT OF MEMORY halt else dsl vm args ptr pushStack pid t cpid seq id pid t getID seq if seq id
14. 20 ND IF END METHOD METHOD elevator down IF self touch down 0 THEN self state FALSE self rotor lt stop self motor 2 ND IF END METHOD METHOD elevator stop self motor 0 self state TRUE END METHOD self position TRUE self stop END WHEN WHEN IN moving cart self touch one 0 THEN WHEN IN moving cart self touch two 0 THEN WHEN IN elevator self touch up 0 THEN WHEN IN elevator self position self stop END WHEN self touch down 0 THEN FALSE KHK KKK KK Kk K Kk K Kk Kk k K Kk K Kk Kk Kk k Kk kk KKK KKK xk SHQUENCES k k k k KK KkKKk K Kk kK K K Kk K k Kk K K k k K Kk k k Kk k Kk KK ini tialization SEQUENCE MAIN last in FALSI Kal c l go in on c l free TRU t 3 free TRUE O Ed pd D 148 a l free TRUE c 2 go in on c 2 free TRU a l down last out FALSI t l motor 20 t 2 motor 20 O Di A D C Gl S END SEQUENCE A Garry EQUENCE t4 to t5 get the moving cart 2 c 2 go in one brick from t 4 to t 5 in position 1 wait c 2 state TRUE and c 2 position TRUE launch the two conveyer belts c 2 rotor go LAUNCH t 4
15. M thode incorrecte M thode correcte METHOD cd assignCtoG METHOD cd assignCtoG self c g c sitel g site2 self c g END METHOD END METHOD Figure 2 27 Exemple de m thode incorrecte et de sa correction 10 10 Les s quences et les instructions de lancement de s quence Une s quence est une suite d instructions identifi e par un identificateur et des param tres et ne respectant pas n cessairement la contrainte atomique cf 6 Code atomique et s quentiel La figure 32 2 29 reprend un exemple de s quence correcte La s quence est constitu e de diff rents blocs qui seront ex cut s sur les sites sp cifi s en commentaires L instruction permettant d ex cuter de mani re asynchrone cette s quence est LAUNCH distri cf 9 10 e Les instructions de lancement La s quence de la figure 2 30 prend deux param tres Elle est distribu e sur le site 1 et utilise une GLOBAL VAR a b c d e f INT END VAR SITE sitel INPUT a 0 0 1 OUTPUT b zs 1 1 1 y END SITE SITE site2 INTERNAL cC INTERNAL d END SITE SITE site3 INTERNAL e INTERNAL f END SITE SEQUENCE distri LOCAL VAR Le ENT END_VAR IF a gt O THEN b 1 ELSE b 0 END IF sitel l c c d d 1 site2 b a b l sitel e f site3 1 a b 1 sitel END SEQUENCE
16. Message HOP 1 SITE ID_SEQUENCE ID_PARTIE NB_PAR ID VALEUR i lt 8 1 gt lt 1 81 gt lt 16 C gt lt 16 gt lt 8 gt 4 16 I gt lt 16 Message LAUNCH 1 SITE ID_METHODE d 8 5 T8 rL lt 16 gt Message TILD 1 SITE ID VARIABLE VALEUR lt 8 8 HH lt 16 lt j 16 L gt 137 Annexe G Principe de construction des tapis roulants en Lego Mindstorms Etape 1 Etape 2 138 Etape 3 Etape 4 139 Etape 5 Etape 6 140 Annexe H Principe de construction des chariots mobiles en Lego Mindstorms Etape 1 Etape 2 141 Etape 3 Etape 4 142 Annexe I Principe de construction des ascenceurs en Lego Mindstorms 143 Annexe J Principe de construction de la cage d ascenceur en Lego Mindstorms Etape 1 Etape 2 144 Etape 3 Etape 4 145 Annexe K Code dSL de la chaine de montage d kk kk fine TRESHOLD 39 treshold value of light sensors kkk k k k k k k k k k k k k k k k k x x CLASSES KkKKk KKK K K Kk Kk k K K k k K Kk k Kk KK CLASS conveyor belt motor INT light LONG light sensor free BOOL state END_CLASS CLASS moving_cart motor INT touch one INT touch sensor position 1 touch two INT
17. Processing expr Expr j i e si s M j M U wait expr SH Since process i can t evaluate the expression the sequence is sent over to the process that can evaluate it Launch a 2 Z lt Launch id S2 s gt lt Sa 8 gt if s y Processing Msg e s Fis gt Fis C id Let j be the process that can execute the instructions associated to id Define id as the function that maps an id to the statement list associated to that id End Of Process lt e lll Ells gt HUT e Hais if A s E v Processing sai s y Msg End Of Process o 76 ls lt gt EI if Ai pAs E pi Processing e sl ale Output End Of Process A lt llles gt l S lees gt if3S e A s E pi Processing es s A e A S 3 4 Output Output e Ier es TO gE pua gt ifs E pi Output sai s y Input After performing the output pass to the input phase e f OVar T L z V 9 4 This function specifies the new values for the output variables 114 Annexe C Manuel d utilisation LegOS D 1 Capteur de lumi re LIGHT X variable contenant la valeur lue par le capteur de lumi re situ en position X gal 1 2 ou 3 ds passive SENSOR X fonction de mise en mode passif du capteur situ en position X 1 2 ou 3 ds active SENSOR X fonction de mise en mode actif du capteur situ en position X 1 2 ou 3 D 2 Capteur de toucher TOUCH X
18. r agir en temps r el des v nements est utile pour mod liser des dispositifs physiques qui r pondent des requ tes par des actions appropri es La mod lisation de ces syst mes est un domaine aux applications vastes Ce type de syst mes peut tre utilis pour mod liser le comportement d un tre artificiel par exemple mais aussi de bons nombres de dispositifs de contrdle d quipements domestiques ou industriels tels qu un chauffage central ou un syst me anti incendie Lorsque de la fum e est d tect e par un des capteurs du syst me ce dernier r agit en cons quence par exemple en d clenchant une alarme Il y a diff rents aspects dans la mod lisation de ce type de syst mes Non seulement parce qu ils doivent tre con us de mani re a r agir correctement et instantan ment aux v nements mais aussi parce que souvent il s agit de syst mes distribu s Un syst me distribu est un syst me constitu d un ensemble de composants ind pendants et distants reli s entre eux par un r seau Diff rents probl mes se posent alors D une part le bon fonctionnement du syst me passe par la gestion des communications entre les stations composant le syst me D autre part il faut r soudre des probl mes li s a la distribution non seulement en ce qui concerne les donn es mais aussi le traitement des v nements Deux approches peuvent tre utilis es pour concevoir des syst mes r actifs l approche synchrone
19. 1 MSG 2 OLDE ES E Pen ROK MSG 2 _ bit 0 TEMPO 1 MSG 2 SES Bs TEMPO 1JACK 2 11MSG 2 bit 0 1JACK 2 0 MSG 3 0 MSG 3 OJACK 3 aN aL cca MM bit 1 Figure 5 38 Exemple de messages chang s avec un protocole ab MSG 3 bit 1 Une station sera amen a envoyer et a recevoir des messages Il faut donc voir les communications entre deux stations comme divis es en deux canaux Un canal d envoi et un canal de r ception De m me il faut que chaque station retienne un bit d envoi et de r ception pour chacune des stations avec laquelle elle communique La figure 5 39 reprend le pseudo code du protocole o message b d signe la r ception d un message contenant le bit b message b correspond a l envoi de message avec le bit b maj 80 TEMPO signifie que le temporisateur est remis a z ro et tempo indique que le temps d attente d un acquittement est d pass De chaque c t le bit est mis z ro d s l intialisation Lorsqu un message est re u par une station celle ci compare le bit de l en t te du message avec le bit de r ception correspondant la source du message Si ceux ci coincident le message est transmis au programme utilisateur Quoiqu il en soit il faut acquitter le message Du c t de la station mettrice lorsque le programme utilisateur lui donne un message envoyer elle ajoute l en t te du message contenan
20. 2 OUTPUT ab b 1 0 1 END SIT Figure 2 14 Exemple de d finition de site avec une classe Lr 10 5 Les instructions d assignations La figure 2 18 reprend un ensemble de diff rentes instructions d assignation d une variable correctes Rappelons que la variable de destination doit tre une variable interne de sortie ou locale et qu il n y a pas de conversion automatique en dSL Les types de chacune des op randes de l expression de droite doivent correspondre avec si besoin est le recours aux primitives de conversion cf 9 3 Les types de base des variables En ce qui concerne les vecteurs l indice sp cifi entre et doit tre compris entre les bornes inf rieure et sup rieure de sa d claration entier 0 entier 1 2 3 MOD 10 ntier entier 1 entier LONG TO INT long BOOL TO INT booleen booleen TRUE booleen LONG TO BOOL long OR INT TO BOOL entier vecteur 1 10 vecteur 3 vecteur 2 vecteur 1 Figure 2 18 Exemples d assignation dSL Lorsqu une variable d une classe est assign e il est n cessaire de pr ciser l instance de la classe sauf en ce qui concerne les instructions de code des m thodes de la classe cf 9 11 Les m thodes La figure 2 19 reprend un exemple de d claration d une classe et d assignations de ses valeurs 27 CLASS AB a b INT c BOOL END CLASS
21. SITE sitel 1 INTERNAL _ab a OUTPUT ab b 1 0 1 END SITE _ab a 10 _ab b abia ab b _ab c INT TO BOOL ab b Figure 2 19 Exemple d assignations sur une classe 10 6 Les instructions conditionnelles La figure 2 20 montre diff rents exemples d instructions conditionnelles La premi re d finit que si entier est sup rieur 10 booleen est mis TRUE La deuxi me ajoute le fait que si entier est inf rieure ou gal 10 alors booleen est mis FALSE La troisi me montre un exemple d instructions conditionnelles imbriqu es Si la condition est de valeur inconnue l instruction conditionelle n a pas d effet GLOBAL VAR entier INT booleen BOOL END VAR IF entier 10 THEN booleen TRUE END IF IF entier 10 THEN booleen TRUE ELSE booleen FALSE END IF IF entier 10 THEN IF booleen FALSE THEN booleen TRUE END IF ELSE a IF booleen TRUE THEN booleen FALSE END IF END IF Figure 2 20 Exemple d instructions conditionnelles dSL 28 10 7 Les instructions d it ration Une instruction d it ration est d finie sur une expression bool enne Dans la figure 2 21 le WHILE porte sur booleen L ex cution de ce WHILE aura pour effet d augmenter la valeur d entier jusqu ce que celui ci soit plus grand que 10 Remarquons qu une
22. entier gt 10 booleen TRUE DE Figure 5 27 Exemple d instructions conditionnelles 14 7 Les m thodes et les instructions de lancement Nous allons reprendre ici les deux m thodes de la figure 2 23 afin d illustrer la g n ration de code pour les m thodes Les identificateurs des m thodes sont par exemple 4 pour acc l rer ajout et 5 pour freiner Deux fonctions vont donc tre cr es l une avec param tre l autre sans La figure 5 28 pr sente le code g n r pour ces deux fonctions La figure 5 29 montre le code g n r pour la fonction handleExec args La fonction READ INT FROM CHAR int unsigned char est une macro d finie dans dsl vm h void graph 4 unsigned char args acc l rer int ajout READ INT FROM CHAR ajout args vl vitesse vl vitesse ajout void graph 5 freiner vl vitesse 0 Figure 5 28 Exemple de d clarations de m thodes g n r es 73 void handleExec int id unsigned char args switch id case 4 if args graph 4 args break case 5 graph 5 break case default error ERR UNKNOWN ID halt Figure 5 29 Exemple de fonction handleExec La figure 5 30 reprend la g n ration de code des appels dSL aux m thodes pr sent es ci dessus de la figure 2 24 Les m thodes sont distribu es sur le site d identificateur 1 La premi re instruction appelle freiner asynchr
23. go brick on conveyer bel t of moving cart wait c 2 rotor light TRESHOLD LAUNCH t 4 stop c 2 rotor stop wait the next conv b wait t 5 light TRESHOL launch the two convey t 5 go LAUNCH c 2 rotor go brick on conveyer bel wait t_5 light lt TRESHOLD t 5 stop c 2 rotor stop free the moving cart c 2 free TRUE END SEQUENCE S elt to be clear D er belts 223998 carry brick from t 4 to t 6 EQUENCE t4 to t6 get the moving cart in position 1 c 2 go in one wait c 2 state TRUE AND c 2 position TRU Lr launch the two conveyer belts c 2 rotor go LAUNCH t 4 go brick on conveyer bel t of moving cart wait c 2 rotor light TR t 4 stop c 2 rotor stop ESHOLD get the moving cart in position 2 c 2 go in two wait c 2 state TRUE AND c 2 position FALSE wait the next conv belt to be clear wait t 6 light TRESHOLD launch the two conveyer belts t_6 lt go 149 LAUNCH c_2 rotor lt go brick on conveyer belt 6 wait t_6 light lt TRESHOLD t 6 stop c 2 rotor stop bring back the moving cart 2 in position 1 LAUNCH c 2 go in one free the moving cart c 2 free TRUE END SEQUENCE S
24. variable contenant l tat du capteur de toucher en position X 1 2 ou 3 Renvoie 1 si le bouton est enfonc 0 sinon D 3 Bouton PRESSED button state NAME macro permettant de tester si le bouton NAME BUTTON RUN ou BUTTON VIEWED est enfonc RELEASED button state NAME macro permettant de tester si le bouton NAME BUTTON RUN ou BUTTON VIEWED est relach D 4 Moteur motor X dir enum motor dir fonction permettant de mettre jour la direction d un moteur situ en position X A B ou C motor dir peut prendre les valeurs fwd avant rev arri re off arr t ou brake roues bloqu es motor X speed int motor speed fonction permettant de mettre jour la vitesse d un moteur 115 situ en position X A B ou C motor_speed doit tre compris entre MIN SPEED 0 et MAX SPEED 255 D 5 cran LCD cputw int i fonction permettant d afficher l entier i sur l cran cputs char s fonction permettant d afficher le string s de longueur maximale de 5 caract res sur l cran lcd clear fonction permettant d effacer l cran D 6 Multithreading execi amp function int argc char argv int prior DEFAULT STACK SIZE fonction permettant de lancer une tache ex cutant les instructions contenue dans function Les param tres argc et argv contiennent respectivement le nombre et les param tres de la tache La priorit prior est comprise entre PRIO LOWEST 0 et PRIO HIGHEST 20 La fon
25. A ceux l s ajoutent d autres op rateurs plus sp cifiques tels que l op rateur tilde par exemple Il y a deux s parateurs en dSL qui sont les s parateurs d instructions et de commentaires a Op rateur d assignation L op rateur d assignation est un op rateur binaire qui remplace la valeur de la variable identifi e par son membre de gauche par la valeur de l expression de son membre de droite cf 8 10 a Les instructions d assignation b Op rateurs arithm tiques La figure 2 6 reprend les diff rents op rateurs arithm tiques de dSL Ces op rateurs se comportent de la m me mani re que dans les langages de programmation classiques Les priorit s de ces op rateurs sont celles repr sent es dans la figure 2 7 Op rateurs Actions Soustraction et inversion de signe F Addition Multiplication Division MOD Modulo Figure 2 6 Op rateurs arithm tiques dSL 18 Plus haute priorit inversion de signe ey Plus basse priorit M OD Figure 2 7 Priorit s des op rateurs arithm tiques dSL c Op rateurs relationnels Les op rateurs relationnels sp cifient les relations que les variables peuvent avoir entre elles Ils sont repris la figure 2 8 et sont similaires aux op rateurs relationnels traditionnels La forme g n rale de l usage d un op rateur relationnel est expression op rateur_relationnel expression Op rat
26. LAUNCH ID COLOR 2 20 0 void handleWhens BOOL cond result cond result a gt 0 if old condition 3 amp amp cond result old condition 3 cond result graph 110 else old condition 3 cond result cond result a 0 if old condition 3 amp amp cond result old condition 3 cond result graph 130 else old condition 3 cond result cond result a 0 if old condition 3 amp amp cond result old condition 3 cond result graph 15 else old condition 3 cond result lt Figure 5 36 Exemple de g n ration de code pour des v nements l re partie 78 void graph 20 cEGALd cdc cdd void graph 21 graph 20 void graph 221 graph 20 void handleWhens BOOL cond result cond result c 0 if lold condition 3 amp amp cond result old condition 3 cond result graph 21 else old condition 3 cond result cond result a 0 if old condition 3 amp amp cond result old condition 3 cond result graph 22 else old condition 3 cond result j Figure 5 37 Exemple de g n ration de code pour des v nements 2 me partie 15 Le protocole de communication La mise en ceuvre de syst mes distribu s n cessite un protocole fiable de communication Il est impensable en effet qu un message de saut dans une s quence soit perdu N oublions
27. MESS i site gt LIST if m if i else while i gt NI site gt LIST m EXT i i 2NI EXT i gt NEXT m 132 brief Searches for a site with a given id and creates one if not found param id_site The id to look for return The site with the given id NULL if not found and no more available memory WE static SITE search and add unsigned char id site SITE i for i S FIRST i i i gt NEXT if i gt ID SITE id site break L i1 i S FIRST S FIRST new site id site if S FIRST S_FIRST gt NEXT i S FIRST return i brief This is the ISR for the infrared Incoming messages are put into the linked list pointed to by M FIRST and will be treated by one of the protocol s threads A static void AB portHandler const unsigned char message unsigned char length MESS curr EFAULT HEADER SIZE T message id site r if length gt D if MSG DES ywait amp sem ab portHandler 0 list not in use in thread AB new_msg message message DEFAULT HEA length DEFAULT HEAD curr gt NEXT M FIRST if sem if cu U ER SIZE R SIZE 0 INCOMING NULL I M FIRST Curr sem post amp sem_ todo sem post amp sem ab portHandler brief Thread handling incoming messages static in
28. chaque W w e When P Var w c V Dans la suite nous appelerons chaque V W un contexte d ex cution local et nous le d noterons par E Notons que puisque D est une distribution de P nous avons Lie Wi When P et Vij e 1 n C gt W Wi 9 Il est aussi n cessaire d introduire des fonctions auxiliaires suivantes Les deux premi res fonctions qui suivent construisent des listes d instructions correspondant respectivement la lecture des entr es et l criture des sorties des variables d un ensemble V donn D finition 6 Lecture des entr es Ecriture des sorties Etant donn un ensemble de variables V nous d finirons Sample V lt v respectivement Write V v comme une liste d instructions r alisant la lecture des variables d entr e respectivement l criture des variables de sortie de V dans l ordre sp cifi par lt y comme suit Sample V lt v INPUT vi INPUT v2 INPUT vx Write V v OUTPUT vi OUTPUT vi OUTPUT vx Il avec Vi e 1 k 1 vi lt v vio et L iens Vi V 37 La d finition suivante construit une liste d instructions correspondant a un traitement des WHENs d un ensemble W D finition 7 Traitement des WHENs Etant donn un ensemble de WHENs W nous d finirons Treat W w comme une liste d instructions r alisant le traitement de tous les WHENSs de W selon l ordre d fini par lt w comme suit Treat W lt w 1 2 Ow av
29. e tapis roulants Figure 6 1 Sch ma de la chaine de montage vue de profil 86 NIVEAU INFERIEUR 1 ASCENCEUR NIVEAU SUPERIEUR entr e sortie mobile mobile I I tapis roulant tapis roulant 1 L tapis roulants Figure 6 2 Sch ma de la chaine de montage vue de haut 2 Les difficult s 2 1 Lancement et arr t des tapis La gestion de plusieurs tapis roulants cons cutifs n cessite une attention particuli re En effet le lancement et l arr t des tapis doivent tre effectu s avec pr caution En r gle g n rale en aucun cas un tapis ne peut tre en marche alors que le suivant est l arr t Dans ce cas un colis pourrait alors se retrouver coinc et abim Les tapis pourraient aussi tre endommag s Pour ces raisons de s curit et de s ret l ordre de mise en route et d arr t des tapis doit tre d fini pr cis ment La mise en route se fait du dernier tapis au premier et invers ment en ce qui concerne l arr t Toute op ration o l ordre est important n cessite l emploi d une s quence 2 2 Exclusion mutuelle des tapis d entr e La notion d exclusion mutuelle entre deux op rations d signe le fait que l une emp che l autre En d autres termes les deux op rations ne peuvent tre effectu es en m me temps L exclusion mutuelle r sulte souvent de l utilisation d une ressource commune Il en est question pour les deux tapis d ent
30. e 14 2 Les variables La figure 5 21 reprend un exemple de d claration de variables globales distribu es sur deux sites Elles sont g n r es partir du code dSL de la figure 2 13 Les variables distribu es sur le site 1 auront leur d claration dans le fichier vm 1 h g n r par le compilateur idem pour le site 2 vm lh short entreel unsigned char sortiel time t internel vm 2h short entree2 unsigned char sortie2 Figure 5 21 Exemples de d claration de variables globales La figure 5 22 reprend un exemple de d claration de variables de classe correspondant la figure 2 12 int vl vitesse bool vl marche int v2 vitesse bool v2 marche Figure 5 22 Exemple de d claration de variables globales g n r es 71 14 3 Les entr es sorties La figure 5 23 reprend un exemple de d claration de variables dSL correspondant a tous les types de dispositifs disponibles La figure 5 24 pr sente le contenu des fonctions samplelnputs et writeOutputs g n r es INPUT lumi re 0 0 0 position 1 INPUT toucher 0 1 0 position 2 INPUT rotation 0 2 0 position 3 OUTPUT moteur 1 1 1 X position B OUTPUT lcd 1 0 0 Figure 5 23 Exemple de d claration d entr es sorties dSL void sampleInputs lumi re sample 1 toucher sample 2 rotation sample 3 void writeOutputs cputw lcd if moteur 0 motor
31. e 1 soit on inspecte uniquement les conditions des v nements dans lesquelles la variable appara t Lors de la compilation il faut conserver pour toute variable globale les identificateurs des blocs de base d inspection des conditions d v nement dans lesquels la variable appara t Cette solution est donc plus complexe g n re plus de code mais est plus efficace en temps d ex cution 2 soit on inspecte syst matiquement les conditions de tous les v nements du site Ce qui simplifie la gestion des v nements g n re moins de code mais est moins efficace puisque certaines des conditions inspect es pourront ne pas avoir chang de valeur La deuxi me option a t retenue vu le peu de place m moire disponible sur les Lego Mindstorms Chaque assignation sur une variable d une condition d venement est suivie d un appel handleWhens la fonction contenant le code de l inspection de toutes les conditions des v nements du site La gestion des v nements implique donc la g n ration de code par le compilateur 1 d une fonction de traitement pour chaque v nement du site 2 et de la fonction handleWhens chaque fois qu une variable sur laquelle porte au moins un v nement est assign e handleWhens est ex cut e cf 6 Les variables De plus elle est ex cut e apr s chaque cycle de sampling des entr es cf 4 La machine virtuelle 14 Exemples de g n ration de code Ce paragraphe pr sente une
32. e sur plusieurs sites Le probl me de la localisation des variables est de permettre aux sites d acc der la valeur d une variable dont il a besoin 2 Le probl me de localisation des instructions du code il consiste prendre en compte la nature distribu e du syst me et permettre l ex cution de son code Les instructions peuvent par exemple tre assign e un site 4 1 Localisation des variables Le probl me de localisation des variables peut tre r solu en utilisant un syst me m moire partag e distribu e distributed shared memory DSM NL91 ow l espace d adressage est r parti sur les diff rents sites et la gestion de la m moire memory fault est dynamique Lorsqu une instruction r f rence une adresse m moire qui n est pas pr sente dans la m moire locale du site une demande de transfert de valeur est broadcast e c est dire envoy e tous les sites Le propri taire de la variable demand e lui envoie sa valeur M me si cette solution offre un environnement distribu transparent elle souffre de plusieurs d savantages La gestion d un tel syst me est difficile et son efficacit n est pas garantie Pour des raisons d efficacit certaines donn es sont dupliqu es Le d savantage principal est que le temps d attente d une donn e c est dire le temps coul entre l instant de la demande de la donn e et celui de la r ponse n est pas pr visible Des probl mes de consistance des donn es appar
33. endormie waiting for CPU en attente du processeur La figure 5 4 pr cise la m thode qui permet de mettre en attente une t che sur un v nement wake_up t id param tres code return expression bool enne Figure 5 3 Syntaxe d un v nement LegOS wait event wake up t wakeup wakeup t wakeup t data Figure 5 4 Syntaxe de m thode de mise en attente d une tache LegOS Nous avons donc d fini l venement LegOS getControl pid t id qui teste si le jeton est gal id l identificateur de t che fourni en param tre D s lors lorsque une t che veut donner le contr le une tache de s quence elle stocke son pid sur le stack de contr le elle met jour le jeton et elle se met en attente grace l instruction wait event amp getControl myPid o myPid est son propre pid Une tache de s quence dont l ex cution est termin e fin de la s quence ou migration passe obligatoirement le contr le la tache qui le lui a donn Elle met jour le jeton avec le sommet du stack de contr le et se met en attente de la m me mani re En pratique la mise en attente et le r veil des taches de s quence se fait via deux fonctions respectivement startwait et wakeup pid t id o id est l identificateur de la tache r veiller pr sent es dans la figure 5 5 et d finies dans le fichier dsl vm h 56 void startwait if StackIsEmpty current thread id popStack
34. fine DEBUG AB debug instr debug instr Fels define DEBUG AB debug instr ndif define TRUE 1 define FALSE 0 define INCOMING 0 define OUTGOING 1 define ERR AB WRITE 10 define DEFAULT HEADER SIZE 3 define MSG HEAD msg msg 0 define MSG SOURCE msg msg 1 define MSG DEST msg msg 2 include 1np sys irq h define ENTER CRITICAL disable irqs define EXIT CRITICAL enable irqs if AB STATIC Preallocated memory for incoming messages pool IMESS POOL 128 Preallocated memory for outgoing messages pool OMESS POOL Preallocated memory for sites pool SITE POOL ndif Semaphores for mutual exclusion and producer consumer sem t sem ab write sem ab portHandler sem todo list of current messages to re send SITE S FIRST list of ceived messages MESS M FIRST Current site s id unsigned char id site Pointer to the user s porthandler for incoming messages dispatched to the user void user portHandler const unsigned char buf unsigned char len Message 0 1 2 3 payload N MSG HEAD MSG SOURCE MSG DEST MSG HEAD 76543210 8 bits HOB LOB 0 bit for abp 1 is ack gt HEAD 0 message with bit 0 1 message with bit 1 2 ack with bit 0 3 ack with bi
35. le distributeur sera charg de r partir les variables et les instructions sur les diff rents sites composant le syst me cf Chapitre II Le langage dSL Pour chaque site le compilateur est charg de cr er deux fichiers c et h qui constitueront le programme utilisateur qui sera charg sur chacune des briques Les programmes utilisateur sont compil s dans un format relocatable avec l extension lx Ils sont ensuite charg s dans la brique gr ce la fonction dll qui les transf re par l interm diaire des ports infra rouges du PC et des briques 4 program c compilateur mE program dSL compilateur Dios h cio program lx dll wo firmdl3 legos srec Figure 3 5 La compilation vers LegOS En ce qui concerne le noyau la directory de boot contient deux fichiers LegOS srec image du noyau et LegOS lds script du linker g n r lors de la compilation Le syst me d exploitation doit tre charg sur chaque brique avant d y transf rer le programme utilisateur Ceci s effectue grace firmdl3 Plus d informations sur le noyau LegOS peuvent tre trouv e dans Nie00 La figure 3 6 reprend l architecture d une brique RCX apr s chargement du syst me d exploitation et du ou des programmes utilisateur Un programme utilisateur utilise les primitives du syst me d exploitation qui utilise la couche syst me interruptions et de la couche hardware
36. nous tudierons le design d un contr leur d une chaine de montage afin d illustrer les concepts de dSL et d valuer ce langage Ensuite nous parcourrons les principaux probl mes pos s par la gestion de ce syst me De plus nous d taillerons quelques aspects li s a sa mod lisation en Lego Mindstorms pour terminer par son impl mentation dSL et son valuation 1 La description du syst me Le syst me consiste en un contr leur d une chaine de montage Celle ci est compos e de plusieurs tapis roulants et d un ascenceur Le principe de cette application est de faire d filer des colis du d but la fin des tapis roulants Ces colis sont remplis au fur et mesure de leur parcours A chaque tape de construction le colis est arr t et transform Par exemple il peut s agir de boites en carton remplies suivant une commande A chaque arr t un certain nombre de livres est ajout dans la caisse En d but de chaine les colis peuvent arriver sur deux tapis De mani re similaire deux tapis de sortie correspondant deux types de colis diff rents ont t dispos s la fin de la chaine De plus un ascenceur est introduit au milieu de celle ci pour transmettre les colis du tapis de niveau inf rieur la suite de la chaine Les figures 6 1 et 6 2 repr sentent un sch ma de la chaine de montage vu respectivement de profil et de haut NIVEAU INFERIEUR NIVEAU SUPERIEUR tapis roulant mobile 3 tapis roulant mobile entr
37. rique est donc d fini par trois num ros un num ro de rack un num ro de carte et un num ro de slot Le langage de programmation du superviseur est SL Il permet de mettre en oeuvre la gestion des diff rents CPs composant le syst me SL est dit event driven Son concept principal est la notion d v nement qui est d finie par une condition et un traitement ex cuter A chaque fois que la condition devient vraie le traitement est ex cut SL offre la possibilit de d finir diff rents types de donn es des m thodes et des v nements En outre d autres constructions communes la plupart des langages de programmation telles que les boucles FOR et WHILE sont galement disponibles Beaucoup de fonctionnalit s de SL sont reprises dans dSL qui sera d crit plus loin 2 Inconv nients de SL et motivations de dSL L utilisation du langage SL comporte un certain nombre d inconv nients Tout d abord deux langages diff rents doivent tre utilis s SL et le langage des CPs Ensuite la distribution du code n est pas automatique Les communications d un CP vers le superviseur doivent tre sp cifi es la main en langage PIP De plus c est le programmeur qui doit pr voir les transferts de valeur du superviseur vers les CPs Enfin il est difficile d avoir une vision centralis e du syst me Le syst me consiste en un certain nombre de contr leurs programmables ind pendants tous connect s au superviseur Afin de pallier c
38. te du message Le bit d envoi est recopi les identificateurs de source et de destination sont invers s et le bit d acquittement est mis 1 B 1 SOURCE DESTINATION Figure 5 45 Format d un acquittement ab Si le bit du message est identique au bit de r ception correspondant au site source le message est lib r de son en t te et transmis au portHandler de l utilisateur comme pr sent la figure 5 46 Sinon le message est oubli PROG UTILISATEUR RECEPTEUR fa PROG UTILISATEUR EMETTEUR Figure 5 46 Parcours d un message envoy Si le message re u est un acquittement la t che parcourt la liste des sites la recherche de l l ment correspondant au site source et compare le bit du message avec le bit d envoi S ils ne coincident pas le premier message de la liste des messages du site est envoy Sinon cela signifie que le message envoy a bien t recu et que celui ci peut tre retir de la liste des messages a envoyer 84 Le deuxi me r le de thread ab est de parcourir la liste des sites et d envoyer tous les premiers messages de chaque liste de messages La gestion des temporisateurs a t quelque peu simplifi e En effet tester l intervalle de temps coul depuis l envoi d un message et d terminer une valeur correcte pour le temporisateur nous a sembl trop sp cifique Nous nous sommes donc simplement assur qu un certain temp
39. Ces deux syst mes d exploitation imposent chacun un langage particulier l un inspir de Java et l autre du langage C 4 Les communications infrarouges En vue de choisir un de ces syst mes d exploitation et donc le langage destination de la compilation il ne faut pas oublier qu il sera n cessaire de g rer les communications inter brique Qui plus est de la mani re la plus efficace et fiable possible D s lors il est primordial d examiner les diff rents protocoles de communications existants Le protocole de transport de donn es doit satisfaire certaines conditions 1 unidirectionnel Les donn es seront envoy es d une RCX vers une autre sans aucune r ponse n cessaire Par l nous voulons dire qu il n y aura pas de dialogue entre deux RCX mais pas forc ment que plusieurs messages ne seront pas chang s En d autres termes quand un site envoie un message typiquement un transfert de valeur ou un ordre d ex cution il n attend jamais une r ponse de son destinataire Mais en pratique le protocole de communication pourra imposer l change de plusieurs messages d acquittement ou de retransmission 2 correction des donn es les donn es doivent avant tout tre correctes En effet il s agit le plus souvent de transferts de valeur de variables 3 fiabilit les programmes qui sont impl ment s requi rent une tr s grande fiabilit En plus de satisfaire la fiabilit dans le cas de briques statiques il faudra a
40. Language Dans Another Look at Real Time Programming Proc of the IEEE vol 79 pp 1293 1304 1991 P Caspi D Pilaud N Halbwachs et J A Plaice Lustre a declarative language for programming synchronous systems Dans ACM Symp on Principles of Programming Languages POPL Munich 1987 Bram De Wachter Code distribution in the dSL environment for the synthesis of industrial process control Bruxelles 2002 Bram De Wachter Thierry Massart C dric Meuter dSL An environment with automatic code distribution for industrial control systems Bruxelles 2003 102 DMM03 2 Bram De Wachter Alexandre Genon Thierry Massart et C dric Meuter dSL to design distributed industrial control systems and verify them with Spin Bruxelles 2003 DMM04 Bram De Wachter Thierry Massart et C dric Meuter dSL An environnement with automatic code distribution for industrial control systems Technical Report 512 Bruxelles 2004 HIT Hitachi Single chip microcomputer H8 3297 Series Hardware Manual LFS02 D Laverde G Ferrari et J Stuber Programming Lego Mindstorms with Java Ed Syngress 2002 Nie00 S Nielsson Introduction to the LegOS kernel Sept 2000 NL91 B Nizeberg et V Lo Distributed shared memory A survey of issues and algorithms IEEE Computer vol 24 no 8 pp 52 60 Aug 1991 TV02 A S Tanenbaum et M Van Steen Distributed Systems principles and paradigms Ed Prentice Hall 2002 103 Chapit
41. S quence Il n y a pas de type associ une s quence juste ses ventuels param tres 2 2 Le distributeur Comme son nom l indique sa tache essentielle est de distribuer statiquement les instructions sur les diff rents sites Pour cela il va utiliser les r sultats de l analyse du code Une technique de distribution consiste colorier le graphe de contr le de flot des instructions Une solution optimale de coloriage d un graphe de flot bas e sur une fonction de co t est pr sent e dans Dew02 Le co t est d termin gr ce une grammaire attribu e qui calcule le nombre moyen de migrations qui se produiront lors de l ex cution Cette technique minimise cette fonction en assignant chaque instruction une couleur c est dire un site De plus elle respecte le coloriage initial d fini sur base de la distribution des variables sp cifi e dans le programme dSL et de la contrainte atomique cf 11 6 Code atomique et s quentiel Cette technique de coloriage est optimale mais requiert la r solution d un probl me NP complet Une technique de r duction du graphe de flot et l utilisation d une heuristique locale permettent d obtenir en un temps raisonnable une solution acceptable En fonction de la distribution le distributeur r alise aussi l analyse des variables actives Pour un bloc de base donn une variable du bloc est dite active si elle est utilis e par une instruction d un bloc situ plus loin dans le chemin d ex
42. Version author Bram De Wachter lt B gt bdewacht lt B gt lt I gt a t lt I gt lt B gt ulb lt B gt I d o t I lt B gt ac lt B gt I d o t I lt B gt be lt B gt author Nicolas Devos date April 2004 version 1 0 Alternating Bit Protocol ny La Dei use init AB protocol portHandler to initialize the protocol use AB write message length to send a message ifndef AB H define AB H include lnp lnp h include lt unistd h gt include lt stdlib h gt include lt string h gt include semaphore h defgroup ab interface Ab protocol interface 125 brief These functions should be called to get the AB protocol up and running Ki Set to 1 to get some debugging on LCD define DEBUG 0 brief Set to 1 if pools are to be used instead of malloc Setting to 0 may cause problems if more memory is asked than available s7 defin AB_STATIC 0 defgroup ab internals Ab protocol internals Internal function for the AB protocol brief Structure used to store incoming and outgoing messages 7 typedef struct mess The pointer to the actual message contents unsigned char MSG The message length limited to 255 characters unsigned char LENGTH For use with synchron
43. a partir du langage de programmation dSL d un g n rateur de code pour des syst mes de contr le distribu s Pour r aliser nos objectifs nous avons recouru l utilisation des Lego Mindstorms comme laboratoire d exp rimentation Pour cela nous avons r cup r et adapt un compilateur existant Nous avons finalement labor une tude de cas afin d valuer de mani re pragmatique le langage dSL et notre compilateur 2 Les syt mes r actifs Un syst me est une combinaison de parties qui se coordonnent pour former un ensemble Il peut tre vu comme une r union de composants en interaction syst me solaire syst me nerveux etc Chaque composant a une responsabilit une fonctionnalit Un syst me est un ensemble d entit s telles qu on ne peut d finir la fonctionnalit de l une ind pendamment de celles des autres L environnement d un syst me est le milieu dans lequel celui ci volue Un syst me r actif est un syst me en interaction permanente avec son environnement Il r agit aux v nements qui se produisent dans cet environnement en r alisant des actions qui influencent ventuellement cet environnement En d autres mots il r pond aux stimuli de son environnement Une repr sentation d un tel syst me est donn e dans la figure 1 1 di Systeme r actif Ev nement Actions Figure 1 1 Le syst me r actif et son environnement La propri t de r activit c est dire la capacit
44. acc s aux entr es et sorties 47 Programme Couche syst me j Couche hardware Figure 3 6 L architecture d une brique RCX sous LegOS La conception de programmes destin s aux briques Lego n est pas sans danger Une erreur de manipulation de donn es par exemple crire une valeur dans un mauvais emplacement en m moire peut crasher l application et rendre la brique RCX inactive Pas de panique Il suffit d enlever les batteries de la RCX et de recharger le syst me d exploitation et l application pr alablement corrig e Signalons qu un petit manuel d utilisation de LegOS a t ajout l Annexe C 48 Chapitre IV Compilation et distribution Dans ce chapitre nous commencerons par introduire les diff rentes tapes de la compilation Ensuite nous d taillerons la structure du compilateur et les r les de chacun de ces constituants notamment ceux du distributeur 1 Le chemin de compilation La figure 4 1 reprend l ensemble des tapes que le programme du syst me va traverser Comme nous l avons dit pr c demment le code est g n r par le compilateur en langage C Il sera ensuite compil par un compilateur crois gcc vers le format LegOS plus pr cis ment vers un format relocatable Jh Les fichiers Ix sont finalement charg s sur les briques RCX cf 777 6 La compilation vers LegOS La version LegOS que nous avons utilis e 0 2 6 et le cross compiler sont disponibles sur le net
45. ce choix de langage est inappropri Il apparait clairement que nous avons in vitablement int r t trouver un syst me d exploitation alternatif qui ne nous impose pas ce type de contraintes LegOS BGT00 LegOS d velopp par Markus Noga a t le premier syst me d exploitation alternatif a destination du RCX LegOS est tr s complet il est multitache dispose d un allocateur dynamique de m moire permet le chargement dynamique de programmes grace a l interface infrarouge et g re l ensemble des p riph riques disponibles pour la RCX LegOS est un syst me d exploitation qui fournit des librairies permettant de remplacer le firmware de la brique par un OS plus puissant Le code r dig en C C est compil en un code binaire plus compacte que ceux obtenus avec LejOS Toutefois m me si LegOS offre un m canisme de configuration statique c est un noyau monolithique difficilement modifiable et peu volutif BrickOS C est le successeur de LegOS Il fournit un environnement de d veloppement pour les RCX bas sur les outils gcc et g ainsi que les outils n cessaires pour t l charger les programmes Con u l origine pour Linux il est galement utilisable sous Windows LejOS LFS02 Une alternative au firmware serait de remplacer celui ci par une Machine Virtuel Java JVM A l instar de LegOS cette solution offre de nombreux avantages par rapport Not Quit C nombre de variables illimit utilisation de
46. concret de syst me de contr le distribu savoir une cha ne de montage tant du point de vue de l impl mentation dSL que de la construction Lego Mindstorms Cette tude de cas nous a permis d une part d valuer le travail effectu sur le compilateur et d autre part de valider l approche dSL de mani re pragmatique Les r sultats de cette valuation sont une r duction de l effort de programmation du concepteur du syst me tant du point de vue de la conception que de la taille du code produire Ces facilit s sont issues du fait que dSL permet de ne pas devoir g rer explicitement les aspects de communication entre les sites et de se concentrer sur les fonctionnalit s du syst me Il offre en outre une vision centralis e du syst me Le compilateur que nous avons cr permet de simplifier la programmation des Lego Mindstorms en utilisant le langage dSL pour mod liser des syst mes distribu s sur plusieurs briques RCX Il permet en outre de recourir aux Lego Mindstorms afin de tester des impl mentations dSL de syst mes r actifs distribu s Il serait d ailleurs int ressant que le compilateur soit mis disposition sur Internet 100 2 Travaux futurs Puisque les syst mes impl ment s sont critiques la sp cification et la v rification des programmes dSL doit tre tudi e Cela peut tre r alis par l utilisation de Spin comme introduit dans DMM03 2 Une autre n cessit est de prouver qu une distribution est cor
47. current thread id seq id wait event amp getControl unsigned int cpid else error ERR UNKNOWN SEQ ID else READ INT FROM CHAR id ptr if type 2 launch method handleExec id ptr else if type 3 tild READ INT FROM CHAR val ptr handleWarn id val else error ERR UNKNOWN MSG ID ST BUF ST BUF 1 SIZE MAX free type void init POS BUF 0 ST BUF 0 POS STACK 0 SIZE STACK 0 ST STACK 0 dsl vm id 0 transmitted 122 current thread id 0 sem init amp sem SIZE BUF 1 0 if i wakeup t button press wakeup wakeup t data return PRESSED dbutton data ndif 123 Annexe E Code du protocole de communication ab h Implementation of the alternating bit protocol on top of LNP for LegOS BrickOS Copyright C 2004 Bram De Wachter This program is modify it under as published by of the License This program is but WITHOUT ANY MERCHANTABILITY G NU General Public Lice free software you can redistribute it and or the terms of the GNU General Public License the Free Software Foundation either version 2 or at your option any later version distributed in the hope that it will be useful WARRANTY without even the implied warranty of or FITNESS FOR A PARTICU LAR PURPOSE See the nse for more details
48. cution sans que celle ci soit red finie sur ce chemin L analyse des variables actives n cessite de d terminer quatre ensembles pour chaque bloc de base B savoir 1 Def B l ensemble des variables qui re oivent une valeur dans B avant d tre utilis e dans B 2 Use B les variables qui peuvent tre utilis es dans B avant toute red finition 3 In B l ensemble des variables actives l entr e du bloc 4 Out B l ensemble des variables actives la sortie du bloc Pour chaque bloc B Def B et Use B peuvent tre d termin s directement sur base du contenu du bloc In B et Out B sont calcul s suivant les formules de la figure 4 4 en r alisant une analyse en arri re sur le graphe de flot des donn es du programme cf ASU00 in B use B out B def B out B in s s successeur de B Figure 4 4 Formules de In B et Out B 52 Sur base du coloriage et de l analyse des variables actives le distributeur va ins rer des points de migration dans le code et plus particuli rement a l int rieur des s quences Un point de migration entre deux instructions cons cutives d une m me s quence est n cessaire lorsque les instructions sont localis es sur des sites diff rents L analyse des variables actives permet de d terminer le sous ensemble des variables du contexte local qui doivent tre transmises c est a dire les variables dont la valeur est utilis e plus loin par une instruction
49. d finition quivalente mais plus courte du WHILE est WHILE entier lt 10 DO entier entier 1 END WHILE Bien entendu les instructions d it rations peuvent tre imbriqu es de la m me mani re que les instructions conditionnelles Si la condition a la valeur inconnue l instruction d it ration n a aucun effet GLOBAL VAR entier INT booleen BOOL END VAR IF entier 10 THEN booleen TRUE ELSE booleen FALSE END IF WHILE booleen DO ntier entiertl IF entier 10 THEN booleen TRUE END I END WHILE Figure 2 21 Exemple d instructions d it ration dSL 10 8 Les instructions d attente Les instructions d attente peuvent porter soit sur un intervalle de temps entier d fini par une expression arithm tique enti re soit sur une condition d finie par une expression bool enne La figure 2 22 pr sente diff rents exemples d instructions d attente correctes WAIT 10 WAIT entierl WAIT entierl entier2 WAIT booleen WAIT entierl entier2 Figure 2 22 Exemple d instructions d attente 10 9 Les m thodes et les instructions de lancement de m thode Les m thodes sont d finies par rapport une classe Elles s ex cutent toujours sur une instance de la classe Les variables de l instance sont acc d es au moyen du mot self La figure 2 23 pr sente deux
50. dSL P et une distribution D V Va de P la s mantique distribu e de P not e P p peut tre d finie par un syst me transitions tiquet es 95 Gp V P x 5 x T L 9 o Gp M1 Vi 81 Ov Vn Bn avec V i e Ln Wi E x L Yz V U Var P U OldCond W i gt est telle que G a G gt si et seulement si E 5 G G peut tre d riv de toute r gle op rationnelle structurelle donn e pr c demment G est l tat initial du syst me c est dire l tat dans lequel se trouve le syst me lorsque celui ci est lanc Tous les espaces de travail et les canaux de communication sont vides 40 Chapitre ITI Les Lego Mindtsorms Dans ce chapitre nous introduirons les Lego Mindstorms et d crirons l environnement d ex cution Ensuite apr s avoir d taill les diff rents langages de programmation possibles nous nous pencherons sur le choix d un de ces langages en fonction entre autres des communications infrarouges Nous d taillerons pour finir quelles sont les tapes de la compilation vers les Lego Mindstorms 1 Introduction aux Lego Mindstorms Les Lego Mindstorms Bau00 BGT00 sont d riv s de recherches sur la robotique et sur son potentiel vis vis de l ducation la science et l ing nierie C est un projet du Massachusetts Institute of Technology la brique programmable MIT PB qui est l origine de l l ment central des L
51. effet toutes les caract ristiques requises savoir la possibilit d avoir plusieurs unit s distinctes capables d ex cuter un certain nombre d instructions d interagir avec son environnement par l interm diaire des entr es et sorties ainsi que de communiquer avec les autres unit s par l interm diaire de leur port infrarouge 2 D finition de l environnement Lego Mindstorms En vue de concevoir des applications distribu es sur diff rentes briques Lego Mindstorms il est important de d tailler quelque peu les caract ristiques des composants principaux de celles ci En effet la compr hension de l architecture et du fonctionnement des RCX permet d obtenir plus de fonctionnalit et de s ret pour les syst mes cr s 42 La brique RCX utilise le microcontr leur Hitachi H8 3292 HIT analogique 8 bits tendu avec 32kb de RAM externe II supporte un espace d adressage de 16 bits et poss de 16 registres de 8 bits ROH ROL R7H R7L Il y a deux registres de contr le le program counter PC 16 bits et les registres de code des conditions CCR 8 bits Le registre R7 est utilis comme registre de stack pointer et renvoie vers le sommet du stack Toutes les op rations sur le stack y acc dent en utilisant des mots de 2 bytes Le CPU dispose de 16 kb de m moire ROM contenant des softwares fournis par le fabriquant La ROM contient un driver qui est lanc d s l allumage de la brique et un ensemble de routines de bas ni
52. en cas d erreur c est a dire en cas d identificateur de bloc erron et case HOP WAIT ID Ce dernier correspond dispatch c est dire l tat d attente d une s quence Il contient 1 l appel de startwait qui met la 67 t che courante en attente de l v nement de reprise du contr le 2 l identification de la partie de s quence ex cuter 3 les instructions d extraction des variables actives ou des param tres lorsqu il s agit de la premi re partie de la s quence L identificateur du bloc a ex cuter et les param tres sont transmis de handleMsg a la t che par l interm diaire de deux variables globales respectivement del vm id et dsl vm args Apr s le traitement du message et la mise jour de ces variables handleMsg r veille la t che de s quence Pour r veiller une tache la fonction handleMsg a besoin de connaitre son identificateur L identificateur est attribu lorsque la tache est cr e en d but d ex cution Pour cela nous avons cr une variable globale pid t thread d par s quence qui stocke l identificateur de la t che de s quence d identificateur id La fonction get D est g n r e la compilation telle que sur base de l identificateur de la s quence elle renvoie l identificateur de la tache correspondante La figure 5 16 pr sente la structure de la fonction get D pid t getID int id switch id case id x return thread id x case default error ERR UNKNO
53. est vide un nouveau cycle Input Process Output est ex cut Cette r gle d finit le comportement cyclique de chaque processus D but Cycle ED i F e vi i gt Sample Var P n Vi lt v Treat W lt w MSG Write Var P N Vi lt v vi di La deuxi me r gle d finit la lecture d une entr e La valuation doit tre mise jour et des messages de transfert de valeur pourront tre n cessaires La transition est labellis e par la variable d entr e lue et sa valeur Input Eb H INPUT x wi vi i ae BCAST x w 4 x a i Va T 1 Les deux prochaines r gles d crivent le traitement des messages de transfert de valeur Les messages sont lus du canal de r ception et la valuation locale est mise a jour D s lors il est n cessaire d examiner les WHENS portant sur la variable mise jour puisque leurs conditions peut avoir chang de valeur Les et repr sentent le contenu du canal de communication respectivement avant et apr s la transition Un message est caract ris par un tuple x v s o x est la variable mise jour v sa nouvelle valeur et s le processus d origine du message Traitement des messages ED F MSG w vi i gt Treat W lt w MSG o vi T gt vx di i 1 V1 81 Zk 1 Vk 1 Sk 1 Tk Vk Sk 9 1 01 531 zk 1 Vk 1 Sk 1 9 Vl 1 k E 1 81 Sk 39 Fin du traitement des messages ED F MS
54. exclusion mutuelle par l usage de s maphore Mais puisque le portHandler ne peut tre mis en attente c est sem trywait sem ab write qui est utilis e car elle est non bloquante Si la structure est utilis e par une autre t che le portHandler ne peut pas stocker le message recu dans la structure Il serait possible d oublier le message puisque celui ci sera renvoy quelques instants plus tard Cependant nous avons imagin utiliser une structure temporaire dans laquelle sont stock s les messages qui n ont p tre ajout s la liste des messages re us Si la structure des messages re us est utilis e le portHandler stocke le message dans la liste temporaire Sinon il recopie le contenu de la structure temporaire dans la liste des messages recus et ajoute le message recu en fin de liste 83 HEAD END ess ess MSG LENGTH NEXT MSG LENGTH NEXT Figure 5 44 Repr sentation de la structure des messages re us Pour traiter les listes de messages re us et de messages envoyer une t che appel e thread ab est cr e La gestion des messages re us se fait de la mani re suivante La t che consulte l en t te du message pour d terminer le type acquittement ou non le bit et la source Si le message n est pas un acquittement un acquittement est transmis la station d envoi La figure 5 45 pr sente le format d un acquittement qui d coule de l en t
55. la fonction handleExec int id char args Le code d handleExec savoir les appels aux m thodes du site selon l identificateur transmis est g n r par le compilateur dans le fichier c du site La mani re dont les param tres sont transmis la m thode est d taill e dans le paragraphe 10 Les m thodes 2 Dans le cas d une demande d ex cution d une partie de s quence la tache de la s quence doit tre r veill e La t che courante c est dire la t che Jnput Process Output est endormie dans l attente de la fin de l ex cution de la partie de s quence ex cuter La mani re dont les s quences sont g r es et dont les param tres sont transmis la s quence est d taill e dans le paragraphe 12 Les s quences 3 Dans le cas d un transfert de valeur d une variable tild e l identificateur et la valeur de la variable sont transmis la fonction handleWarn int id int val dont le code est g n r par le compilateur tel qu en fonction de l identificateur la variable correspondante est assign e la valeur transmise cf 10 La gestion des tildes 4 Les identificateurs Le nom des variables dans le programme source dSL est conserv dans le programme cible sauf en ce qui concerne les classes En fait il n y a pas de classe g n r e par le compilateur Ce dernier combine le nom de l instance de la classe avec le nom des diff rentes variables pour cr er un nom de variable unique Par exemple imaginons une class
56. le En plus de ses nouvelles primitives il faudrait modifier le comportement du syst me d exploitation en supprimant le caract re multitache pr emptif du noyau c est dire tout ce qui concerne les interruptions de l horloge etc Apr s compilation du noyau nous obtiendrions un nouveau noyau modifi que nous devrions utiliser pour ex cuter nos applications Cela diminuerait la portabilit des applications g n r es par notre compilateur puisqu il serait imp ratif d utiliser le noyau modifi pour ex cuter les applications Modifier le noyau n est donc pas une bonne id e Il est pr f rable de laisser le noyau tel quel et d utiliser ses primitives pour simuler le scheduling 55 d aite 7 TT utili gt ui Une solution pourrait tre alors de jongler avec les sections critiques en utilisant les s maphores qui permettent de mettre en attente ou de r veiller une t che Cependant rendre le contr le la t che qui nous a rendu la main s av re tr s complexe avec le seul usage des s maphores Pour qu une t che rende le contr le la t che qui l a lanc e nous avons pens un stack de pid de contr le sur lequel la t che qui compte donner le contr le une autre stocke son pid pour un retour de contr le ult rieur Ensuite elle passe le contr le la t che lancer et se met en attente Lorsque la t che en cours d ex cution va vouloir rendre le contr le elle consultera le pid au sommet du stack de contr le pou
57. n cessaire de g n rer le code de transfert de valeur cf 10 La gestion des variables tild es En ce qui concerne les variables de sortie la gestion est un peu plus complexe Pour rappel deux types de dispositifs de sortie peuvent tre utilis s l cran LCD et le moteur Pour le premier la fonction de mise jour de la sortie est cputw valeur o valeur est la valeur de la variable associ e l cran Pour le second la mise jour se fait gr ce deux fonctions motor x speed vitesse pour la vitesse et motor x dir direction pour la direction o x est la position du moteur a b ou c Pour tre clair imaginons un moteur en position A sa mise jour se fait gr ce au fonction motor a speed vifesse et motor a dir direction La figure 5 12 reprend les diff rents param tres de direction permis en LegOS La direction est d termin e suivant le signe de la variable de sortie Si celui ci est positif la direction est 1 s il est n gatif la direction est 2 s il est nul la direction est 3 La vitesse sera la valeur absolue de la variable de sortie 61 Param tre Direction 1 Marche avant 2 Marche arri re 3 Off moteur en roue libre Figure 5 12 Correspondance des directions des moteurs legOS 8 Les op rateurs L op rateur d assignation est traduit par l op rateur C d assignation L op rateur MOD est traduit par l op rateur modulo C Les
58. pas l enti ret des possibilit s de LegOS Par exemple aucune instruction de production de son n est disponible en dSL Cela dit au vu de la bonne lisibilit du code produit par le compilateur il est ais pour le programmeur de retoucher le code C en y ajoutant des instructions plus sp cifiques dSL est aussi limit par rapport l utilisation de structure de donn e particuli re string pointeur etc 99 Chapitre VII Conclusions 1 R sum Dans ce texte nous avons d fini de la mani re la plus complete possible le langage dSL un langage de design de syst mes de contr le distribu Nous avons extrait les principaux avantages de dSL par rapport son anc tre SL et a d autres approches comme les langages synchrones Une pr sentation de la syntaxe et de la s mantique de dSL a t faite Nous avons par la suite pr sent les Lego Mindstorms qui ont t utilis s comme laboratoire d exp rimentation du langage et nous avons motiv le choix de LegOS parmi les syst mes d exploitation disponibles Ensuite nous avons tudi la g n ration de code de dSL vers LegOS et nous l avons illustr e par une s rie d exemples Nous avons r alis un compilateur qui g n re automatiquement le code de tous les sites du syst me Nous avons galement pr sent le mode de fonctionnement et l impl mentation du protocole de communication fiable que nous avons impl ment Pour finir nous avons mis en ceuvre un exemple
59. pendant l ex cution Lorsqu une t che en cours d ex cution doit tre transf r e sur un autre site par exemple moins charg son ex cution est arr t e et son contexte c est dire ses variables locales et le program counter est transf r sur l autre site o il est restaur et o l ex cution de la t che se poursuit En ce qui concerne le code des t ches il est soit pr sent sur tous les sites soit transf r de site en site avec son contexte Ce type de solution pose videmment plusieurs probl mes notamment de performance et de surcharge des communications Transf rer tout un contexte co te en temps et en ressource r seau Des am liorations de performances sont possibles en particulier lorsque qu un processus est migr d une station lourdement charg e vers une station l g rement charg e ou plus puissante Il existe un certain nombre d algorithmes pour r partir la charge d un syst me distribu load balancing Mais en pratique la distribution est d termin e de mani re limiter les communications En plus les syst mes utilisant la migration de taches sont relativement difficiles g rer Pour ces raisons la distribution du code se fait galement de mani re statique dans l environnement dSL Une t che pourra tre divis e en diff rentes parties successives qui seront r parties uniquement sur diff rents sites en fonction de la r partition des variables globales et de la capacit des sites Lorsque
60. port Inp integrity set handler int port portHandler function fonction permettant de sp cifier un gestionnaire du port port Lorsqu un aquet est re u le syst me d exploitation appelle 116 portHandler function pour le traiter Les paquets sont transmis de mani re broadcast e Inp integrity write unsigned char data unsigned char length int port fonction permettant d envoyer de mani re broadcast e le message data de longueur ength par l interm diairie du port port 117 Annexe D Code du fichier dsl vm h include lt string h gt include lt stdlib h gt include lt stdarg h gt INCLUDE de LEGOS include lt dbutton h gt include lt dsensor h gt include lt dmotor h gt i L qe include lt lnp inp h gt include dsound h include lt sys tm h gt include conio h include lt unistd h gt include semaphore h include 1np sys irq h define EC disable irqs define XC enable irqs define ABS a a 0 a define halt while 1 define HOP WAIT ID 65200 define ERR UNKNOWN WARN ID 1 defin ERR UNKNOWN EXEC ID 2 defin ERR UNKNOWN HOP ID 3 de
61. pour transf rer la brique sur un des tapis de sortie La variable last out est utilis e pour stocker la derni re d cision prise par rapport au tapis de sortie 97 carry brick from t_3 to t_4 SEQUENCE t3 to t4 wait the elevator to be in position down wait a l position FALSE AND a_1 state TRUE DH Launch the two conveyer belts a l rotor go t_3 lt go brick on conveyer belt of elevator wait a l rotor light TRESHOLD a l rotor stop t 3 stop fr the conveyer belt 3 t 3 free TRUE get the elevator in position up a_l lt up wait a l state TRUE AND a_1 position TRU C launch the two conveyer belts t_4 lt go a_l rotor lt go wait t_4 light lt TRESHOLD t 4 stop a l rotor stop bring back the elevator in position down LAUNCH a 1 down asynchron call wait the moving cart to be free wait c 2 free TRUE c 2 free FALSE launch the next sequence IF last ou TRUE THEN last out FALSE LAUNCH t4 to t5 ELSE v aN last out TRUE LAUNCH t4 to t END IF free the elevator a l free TRUE END SEQUENCE Figure 6 12 Code de la s quence t3 to t4 Bien entendu une s quence d initialisation est d finie Elle intialise toutes les variables utilis es dans le code et notamment l
62. programme sauf vis vis du respect de la contrainte atomique Les changements dans les primitives d acc s seront g n r es automatiquement par le compilateur Deuxi mement c est un langage extr mement simple avec une distribution de code transparente Il ne n cessite pas le recours des sch mas de synchronisation De plus un seul langage est utiliser pour programmer l enti ret du syst me Il offre en outre la possibilit de v rifier les syst mes cr s Cet aspect est tr s important parce que les systemes mod lis s sont souvent critiques c est dire des syst mes dont les pannes peuvent avoir des effets catastrophiques Leurs d faillances sont susceptibles d entrainer directement ou indirectement la perte de vies humaines ou du moins des risques majeurs pour le public ou des co ts importants Il s agit par exemple de syst mes de contr le de s curit de surveillance etc Ils peuvent d s lors tre soumis des r glements de certification A titre d exemple signalons qu il existe pour les syst mes de pilotage automatique des avions de transport un r glement de certification am ricain FAR25 et son quivalent europ en JAR25 Notons titre d information qu un nouveau type de CPs est en cours de d veloppement pour dSL le PIP 5000 Il s agit d un automate fonctionnant sous pC linux avec un processeur Motorola ColdFire avec 8Mb de RAM 14 8 Inconv nients de dSL L inconv nient majeur de dS
63. que l ex cution d une s quence est n cessaire Nous avons donc d fini un certain nombre de s quences qui prendront en charge le traitement des briques Puisqu une seule instance de s quence ne peut tre ex cut e tout instant nous avons veill d couper le traitement d une brique de l entr e la sortie en le plus grand nombre de s quences possibles et ainsi en limiter la taille La taille minimale d une s quence correspond la prise en charge d une brique sur une section o il ne peut y avoir qu une seule brique en cours de traitement Par exemple le chariot mobile ou l ascenceur Les s quences sont donc d finies par rapport la d coupe qui peut tre faite de la topologie de la chaine La s quence t1 to t3 prend en charge la brique du tapis 1 au tapis 3 en passant par le chariot mobile Idem pour t2 to t3 0 t3 to t4 fait passer la brique du tapis 3 au tapis 4 en tranversant l ascenceur t4 to t5 et t4 to t6 se chargent d amener une brique du tapis 4 vers les tapis 5 ou 6 Les deux premi res s quences sont mutuellement exclusives Elles utilisent en effet la m me ressource Nous avons donc d fini un jeton correspondant l acc s au premier chariot mobile Ce jeton est une variable bool enne free mise vrai lorsque la ressource chariot mobile est disponible et mise faux lorsque la ressource est utilis e La modification du jeton doit se faire en tout d but et en toute fin de l ex cution des s quenc
64. quence 2 I EN d claration des v nements WHEN ventuels END WHEN fin de la derni re d claration d v nement VHEN IN d claration des v nements WHEN IN ventuels END WHEN fin de la derni re d claration d v nement 7 Figure 2 10 Squelette d un programme dSL 10 3 Les variables globales La figure 2 11 pr sente un extrait de programme dSL contenant la d claration de quelques variables globales chacune de diff rents types Les deux premi res sont de type entier la troisi me de type bool en la quatri me est un entier long et les derni res sont des vecteurs d entiers et de bool ens La d claration des variables globales est plac e en d but de programme cf 9 2 La structure du programme GLOBAL VAR ntierl ntier2 INT booleen BOOL long LONG vecteur entier ARRAY 0 10 of INT vecteur booleen ARRAY 2 5 of BOOL END VAR Figure 2 11 Exemple de d claration de variables globales Le dernier type de variables qui peut tre utilis est la classe La figure 2 12 pr sente la d claration d une classe voiture contenant deux variables l une enti re et l autre bool enne correspondant respectivement la vitesse et l tat du v hicule La d claration des classes doit se trouver avant celle des variables globales cf 9 2 La structure du programmoe Dans la figure 2 12 deu
65. s rie d exemples de code g n r pour l ensemble des constructions dSL La structure de celui ci est calqu e sur le paragraphe 77 9 Exemples La grande majorit des exemples sont d ailleurs tir s de ce paragraphe Cela dit quelques exemples suppl mentaires plus repr sentatifs ont t ajout s 70 14 1 Les taches Pour illustrer la cr ation de taches nous allons pr senter un exemple de fonction d initialisation g n r e par le compilateur repris dans la figure 5 20 Elle correspond a un site sur lequel ont t distribu es deux s quences d identificateur respectif 2 et 3 Trois t ches sont donc cr es threadStart correspond la t che nput Process Output laquelle est assign e une priorit de 8 thread 2 et thread 3 sont les identificateurs des t ches des s quences de priorit 9 graph 2 et graph 3 contiennent les instructions des s quences Nous pouvons remarquer que les taches de s quence sont initialis es et mises en attente d un message avant que la t che Jnput Process Output ne recoive le contr le de l OS int main init init AB protocol portHandler threadStart execi amp start 0 0 PRIO NORMAL 2 DEFAULT STACK SIZI thread 2 execi amp graph 2 0 0 PRIO NORMAL 1 DEFAULT STACK SIZE 2 thread 3 execi amp graph 3 0 0 PRIO NORMAL 1 DEFAULT STACK SIZE 2 return 0 E 2 Figure 5 20 Exemple de fonction d initialisation g n r
66. site en site Par exemple la s quence pr sent e dans la figure 5 2 doit suspendre son ex cution sur le site 1 en attendant de reprendre le contr le apr s que les instructions de la deuxi me partie de la s quence distribu e sur le site 2 aient t ex cut es Chaque s quence est traduite par une tache dont l ex cution sera suspendue aux points de migration en attendant d tre r veill e pour continuer son ex cution Remarquons qu il n y a pas de concurrence dans l ex cution des taches pour un site donn Ce qui signifie qu il faut veiller n avoir tout moment qu une et une seule tache active site 1 site 2 l re partie de s quence 2 me partie de s quence 3 me partie de s quence Figure 5 2 Exemple de s quence distribu e Nous devons donc pouvoir 1 suspendre l ex cution d une tache en cours et 2 passer le contr le une autre t che en particulier De plus lorsque l ex cution d une t che assign e une s quence s arr te la tache doit rendre le contr le la tache qui lui a donn la main Afin d impl menter un tel comportement trois solutions auraient t envisageables La premi re consiste modifier le scheduling du syst me d exploitation par l ajout de nouvelles primitives tels que start until suspend et suspend qui permettraient de suspendre l ex cution d une t che en restaurant la tache qui lui a donn le contr
67. situ e sur un autre site avant laquelle les variables ne sont pas assign es Pour rappel les v nements et les m thodes sont tenus de respecter la contrainte atomique C est pourquoi les points de migration ne sont introduits qu au sein des s quences 2 3 Le backend Il est charg de g n rer le code cible du programme sur base des analyses r alis es par les deux autres parties du compilateur Pour chaque site du syst me il va donc cr er deux fichiers c et h qui contiendront le code des composants du syst me Ce code doit tre correct et efficace Nous avons veill galement ce que le code g n r soit de bonne qualit c est dire structur lisible et ais ment compr hensible pour le programmeur avec par exemple l ajout de commentaires d explication La g n ration automatique du code est l objet du chapitre suivant 53 Chapitre V G n ration automatique de code LegOS pour Lego Mindstorms Dans ce chapitre nous pr senterons l apport que nous avons fait au compilateur existant tant dans la r flexion que dans l impl mentation Nous tudierons la mani re dont le code C est g n r par le compilateur et nous nous efforcerons de d crire les principaux m canismes employ s pour mettre en ceuvre les constructions dSL en langage C Nous illustrerons galement la g n ration de code par une s rie d exemples Pour finir nous pr senterons galement le protocole de communication fiable que nous avons im
68. startwait nextBasicBlock dsl vm id break case default error ERR UNKNOWN HOP ID halt case 13 g c c d d 1 HOP 1 6 14 1 23 1 nextBasicBlock HOP WAIT ID break Figure 5 33 Exemple de code g n r pour une s quence distribu e 2 me partie void graph 6 distri int 1 int nextBasicBlock HOP WAIT ID while true switch nextBasicBlock case HOP WAIT ID startwait nextBasicBlock dsl vm id break case default error ERR UNKNOWN HOP ID halt case 15 e f HOP 1 6 16 0 nextBasicBlock HOP WAIT ID break Figure 5 34 Exemple de code g n r pour une s quence distribu e 3 me partie La s quence pr sent e ci dessus ne prend pas de param tre La s quence de la figure 2 30 prend deux param tres x et y Le code g n r pour cette s quence est repris dans la figure 5 35 Nous profiterons aussi de l occasion pour illustrer la g n ration de code associ e une instruction d attente dSL Supposons que le compilateur doit g n rer du code pour l instruction i TRUE Cette assignation n cessite de tester l tat de la s quence 6 Si celle ci est en train d attendre il faut lui passer le contr le 76 void graph 7 int x bool y int nbVal int nextBasicBlock while true switch nextBasicl distri HOP WAI
69. stop wait the next conv belt to be free wait t 3 free TRUE t 3 free FALSE launch the two conveyer belts t 3 go c l rotor go brick on conveyer belt 3 wait t 3 light TRESHOLD t 3 stop c l rotor stop wait the elevator to be free wait a l free TRUE a l free FALSE launch the next sequence LAUNCH t3 to t4 free the moving cart c l free TRUE END SEQUENCE carry brick from t 2 tot 3 SEQUENCE t2 to t3 get the moving cart in position 2 c l1 go in two wait c l state TRUE AND c_1 position FALSE launch the two conveyer belts c l rotor go LAUNCH t 2 go brick on conveyer belt of moving cart wait c l rotor light TRESHOLD get the moving cart in position 1 LAUNCH c 1 lt go in one wait c l state TRUE AND c_1 position TRU Lr wait the next conv belt to be free wait t 3 free TRUE t 3 free FALSE launch the two conveyer belts t 3 go LAUNCH c 1l rotor go brick on conveyer belt 3 wait t_3 light lt TRESHOLD t 3 stop 151 c l rotor stop wait the elevator to be free wait a l free TRU a l free FALSE E P H launch th LAUNCH t3 to t4 free er tee TRUE END S QUENCE next seq
70. strings etc LejOS reprend une partie du code de LegOS en essayant de le modulariser De plus LejOS int gre une micro machine virtuelle Java et permet le chargement dynamique de classes Java travers l interface infrarouge du RCX Il devient donc possible de programmer les Lego Mindstorms directement en Java Toutefois le noyau r sultant est relativement lourd L espace n cessaire pour la JVM repr sente 9 des 32 Kb disponibles sur la RCX D s lors cette solution semble tre co teuse Pbforth BGT00 A ne pas mettre entre toutes les mains Pbforth n est pas un langage de d butant C est la version RCX du langage Forth Il est bas su une machine pile Son avantage est que l interpr teur est dans la m moire de la brique Ainsi il est possible de t l charger des programmes partir de n importe quelle machine capable d acc der au port USB en mode ASCII 44 En fait Pbforth a trois caract ristiques principales Finteractivit les syst mes interactifs sont des syst mes recevant des commandes de l utilisateur et r pondant directement celle ci interpr tation c est dire le fait que Pbforth soit un langage interpr t ce qui implique une certaine lenteur l ex cution extensibilit l interpr teur peut tre tendu de nouveaux mots pour modifier la mani re de g rer les donn es D ors et d j nous pouvons sortir deux syst mes d exploitation du lot LejOS et LegOS ou brickOS
71. sur d autres supports utilisant une machine virtuelle Java JVM Mais la place m moire disponible pour les programmes utilisateurs et les ressources utilis es par le syst me d exploitation sont malheureusement limit es D autre part LegOS est un choix de syst me d exploitation int ressant dans le probl me qui nous concerne savoir la g n ration de code de syst mes distribu s Il fournit un OS puissant alternatif au firmware standard d avantage de place en m moire disponible un protocole de communication un ensemble de librairies la possibilit de faire du multitache sans pr emption une gestion dynamique de la m moire 46 LegOS a donc t choisi comme langage cible de la g n ration de code En ce qui concerne les communications le protocole LNP originellement d velopp pour LegOS fonctionne tr s bien pour les transferts de donn es et offre de bons r sultats dans un environnement suffisamment favorable Cela dit nous serons amen a envisager l utilisation d un protocole fiable de communication utilisant la couche LNP pour l envoi des messages et assurant la fiabilit des communications 6 La compilation vers LegOS Le compilateur sera donc charg de cr er un programme interm diaire en C qui sera ensuite compil pour LegOS par un compilateur existant appel cross compiler ou compilateur crois Le parcours d un programme dSL est repris par la figure 3 5 Une partie du compilateur
72. te Le code de la classe est repris la figure 6 7 L utilit de la variable ree sera expliqu e dans le paragraphe suivant 4 4 Les liens entre les l ments de la chaine Le syst me impl ment est un syst me r actif Il r agit un certain nombre d v nements Ces v nements sont li s aux capteurs de lumi re qui d tectent la pr sence d une brique sur un tapis roulant 95 Avant de commencer les d tailler nous allons voquer un probl me auquel nous avons d faire face dans l impl mentation Les capteurs de lumi re manifestent une tr s grande sensibilit aux variations de luminosit La valeur seuil c est dire la valeur relev e par le capteur sous laquelle on peut tre s r qu une brique est en face du capteur est tr s difficile d terminer de mani re pr cise Elle peut varier en fonction de l inclinaison des tapis par rapport la lumi re ou m me d un instant de la journ e un autre Nous avons tent de cr er des conditions optimales afin que l environnement n influence pas le comportement du syst me Pour cela nous avons construit des ponts recouvrants les tapis roulants Ces ponts sont construits en briques blanches Nous utilisons alors des colis de couleur noire pour maximiser la diff rence de relev Le seuil a ensuite t d fini la valeur 39 de mani re empirique Remarquons l usage d un define TRESHOLD valeur qui permet de sp cifier la valeur du seuil en d but de code P
73. tous les composants du syst me voluent simultan ment et effectuent les m mes actions par exemple la lecture des entr es ou la mise a jour des p riph riques de sortie en m me temps l approche asynchrone chaque composant du syst me volue de mani re autonome ind pendemment des autres De nombreux langages synchrones comme Esterel Ber98 BD91 Lustre CPHP87 et Signal BGL91 permettent de sp cifier le comportement de tels syst mes de mani re abstraite et rendent possible leur validation formelle cruciale dans le cas de syst mes critiques En pratique la synchronisation s effectue par la mise en uvre d un site maitre qui met a tous les sites l ordre d effectuer une action particuli re et attend que tous les sites aient termin cette action pour passer a la suivante Faire voluer de mani re synchrone tous les sites peut s av rer totalement inefficace De plus nous ne pouvons imaginer un tel syst me pour une raison de s ret Si un des sites venait pour une raison quelconque se bloquer ou tre coup des autres tout le syst me serait bloqu C est pourquoi l hypoth se de synchroniser les sites a t rejet e 3 Structure du m moire Dans le chapitre II le langage dSL est pr sent de mani re compl te ainsi que les probl mes li s la distribution de code des syst mes distribu s Le chapitre III contient une br ve introduction la technologie Lego Mindstorms et son environnement E
74. transitions tiquet es 36 Pour rappel un syst me transitions est d fini par un ensemble d tats et par une relation de transition entre ces tats Les syst mes transitions tiquet es sont des syst mes transitions o celles ci sont accompagn es d un symbole appel tiquette Definition 4 Syst me transitions tiquet es Un syst me a transitions tiquet es L est un tuple Q q X gt avec Q un ensemble d tats q e Q l tat initial Z l ensemble des symboles du langage appel alphabet avec t X t est une action interne gt c Qx Z U t x Q est la relation de transition tant donn s deux tats q q Q pour tout symbole a U t nous notons q gt q si q a q et pour tout w a az dn E U x q gt q s il existe une s quence de transitions qo qi Qn1 gt qn avec q Go et q qn tant donn un programme dSL P correct et une distribution D Dp nous pouvons d finir l environnement distribu dans lequel P sera ex cut En effet en vertu des contraintes atomiques le partitionnement des variables du programme P donn e par D impose une r partition de l ensemble des WHEN de P D finition 5 Contexte d ex cution distribu Etant donn s un programme dSL P et une distribution D V V2 Va Dp le contexte d ex cution distribu de P est d fini comme suit E 57 V Wp V2 W2 Va Wn o
75. 1 free TRUE THEN Cc l free FALSE take control of the moving cart IF last in FALSE THEN LAUNCH tl to t3 last in TRUE ELSE LAUNCH t2 to t3 last in FALSE ENDIF END WHEN Figure 6 9 Code des v nements de lancement des s quences t1 to t3 ett2 to t3 95 En tant que tapis d entr e les tapis 1 et 2 doivent tourner tant qu il n y a pas de brique en face de leur capteur Les v nements de la figure 6 10 assurent cela WHEN ask_on FALSE THEN t_1 lt g0 END WHEN WHEN ask two FALSE THEN t_2 lt go END WHEN Figure 6 10 Code des v nements de mise en route des tapis d entr e Apr s avoir d fini les v nements il est n cessaire de d tailler les s quences Lorsqu une brique est en face d un des deux capteurs des tapis d entr e il faut amener le chariot mobile en face du tapis d entr e lancer les tapis jusqu a ce que le colis soit sur le chariot mobile amener le chariot mobile face au tapis interm diaire lancer les tapis jusqu a ce que la brique soit sur le tapis interm diaire lancer la s quence suivante a condition que l ascenceur soit libre Ur ka bit Tout ce traitement ne peut tre fait de mani re naturelle efficace et s re que sous forme d une s quence d taill e dans la figure 6 11 De plus une s quence permet d utiliser des instruction
76. 3 Les v nements 19 f Op rateurs de lancement LAUNCH et lt Ces op rateurs permettent de lancer l ex cution asynchrone d une s quence ou d une m thode d une classe sur une instance de cette classe dans une instruction de lancement cf 6 70 e Les instructions de lancement L op rateur permet de sp cifier sur quelle instance de la classe la m thode est ex cut e g Op rateur L op rateur tilde permet de r f rencer une variable dite tild e c est dire la copie locale d une variable cf Code atomique et s quentiel Il s agit d un op rateur unaire La forme g n rale est id variable Aucune assignation ne peut tre effectu e sur une variable tild e Aucune r f rence une variable tild e ne peut tre faite dans le corps d un WHEN seulement dans sa condition h S parateur Ce s parateur permet de d finir la fin d une instruction Il est n cessaire pour tous les types d instructions i S parateurs a et Ces s parateurs permettent d introduire des commentaires dans un programme c est dire une suite de caract res qui ne sera pas prise en compte lors de la compilation Ils sont utiles lorsque le programmeur veut commenter son code et n ont aucun effet sur l ex cution du programme car ils sont ignor s par le compilateur Les commentaires peuvent tre plac s partout sauf au milieu d un mot cl ou d un identificateur Ils n
77. 70 La gestion des variables tild es ces d clarations globales viennent s ajouter la d claration des anciennes valeurs des conditions des v nements cf 3 Les v nements En effet un v nement se produit lorsque sa condition passe de vrai faux Il faut par cons quent conserver l ancienne valeur de la condition de chaque v nement De plus il sera g n r les d clarations de variables bool ennes d tat des s quences indiquant si la t che est en attente ou non et dont la formulation et l utilit seront expliqu es plus loin cf 9 4 Les instructions d attente En r sum pour un site donn l ensemble des variables globales d finies est les variables globales qui lui sont distribu es les variables tild es utilis es sur le site les anciennes conditions des v nements etles variables bool ennes des tats des s quences Les d clarations de ces variables sont g n r es dans le fichier h des sites En ce qui concerne les variables locales une m thode ou une s quence leur d claration sera situ e dans le scope de la fonction g n r e correspondante cf 71 Les m thodes et 12 Les s quences 60 7 Les entr es sorties Avant de d tailler la mani re dont les dispositifs d entr e et de sortie sont acc d s nous devons pr ciser la correspondance entre les param tres dSL d une variable globale d entr e ou de sortie cf II 8 7 Les sites et les entr es sorties e
78. Ainsi il n y a que deux positions possibles soit en position 1 c est dire dans l axe du premier tapis d entr e et du tapis principal soit en position 2 c est dire perpendiculairement l axe du tapis principal face au deuxi me tapis d entr e Pour finir l ascenceur est l l ment le plus complexe de la chaine Le principe de sa construction est repris l Annexe I Il consiste en une plate forme sur laquelle deux moteurs actionnent deux axes termin s par deux engrenages chacun Ces engrenages sont les points d appui de la plate forme et permettent de faire monter et descendre l ascenceur Le principe de construction de la cage d ascenceur est pr cis en Annexe J Deux capteurs de toucher permettent de savoir lorsque l ascenceur est arriv en haut ou en bas Bien entendu pour assurer la continuit du tapis un tapis roulant est dispos sur la plate forme de l ascenceur Avant de passer l impl mentation dSL de la chaine de montage nous allons d terminer le nombre de briques Lego Mindstorms n cessaires La figure 6 3 r capitule les dispositifs d entr e sortie Lego Mindstroms n cessaires pour la r alisation des diff rents l ments constituant le syst me Chaque tapis roulant n cessite une sortie le moteur et une entr e le capteur de lumi re Les chariots mobiles n cessitent chacun une sortie le moteur du chariot et deux entr es suppl mentaires les capteurs de toucher En ce qui concerne l ascenceur il req
79. E est fausse le contr le sort de la construction WHILE et passe a l instruction suivante 7 WHILE IF Ma c Figure 4 2 Exemple de graphe de contr le de flot d un if imbriqu dans un while Ces blocs de base vides sont enlev s par un algorithme d optimisation pendant la compilation cf Dew02 La figure 4 3 pr sente le graphe de contr le de flot de la figure 4 2 apr s optimisation gt WHILE IF Figure 4 3 Graphe de contr le de flot de la figure 4 2 apr s optimisation 51 En plus de la conception du graphe de contr le de flot le frontend associe chaque variable m thode ou s quence un certain nombre d informations n cessaires tels qu un identificateur unique entier de 16 bits le type ou les param tres ventuels 1 Variable le type est celui de sa d claration dans le programme dSL A chaque utilisation de la variable dans une instruction la correspondance de type est v rifi e Les param tres sont n cessaires en cas de variable d entr e ou de sortie II s agit de sa sorte entr e ou sortie et des trois nombres qui identifient le type et l emplacement du dispositif cf 1 9 7 Les sites et les entr es sorties 2 M thode Les m thodes n ont pas de valeur de retour Il n y a donc pas de type associ une m thode juste ses ventuels param tres 3
80. G w vi i gt wi Vi i La r gle suivante correspond au traitement d une assignation La valuation est mise jour et si la variable apparait tild e sur un autre site sa nouvelle valeur doit tre transf r e De plus les WHENs qui porte sur cette variable doivent tre examin s Assignation Ps en y syn J BCAST x Treat Wij2 lt w wi vile vi e i _ if x Var P ED H wi vi i wi vile vi e i if z OldCond P o Wijs w Wi x Var Cond w La r gle suivante correspond au traitement d une instruction IF Si la condition est valu e vrai T le code de la partie THEN est ins r l espace de travail Sinon 1 c est la partie d instructions li e au ELSE qui est ins r e Celle ci est vide dans le cas d un IF sans code de ELSE If wr wi vi Qi if vile Py ea 37 hie E Ep IF e THEN wy ELSE w ENDIF wi Vi di outs ee E ee T L La derni re r gle locale correspond l criture d une variable de sortie Une transition tiquet e par la variable de sortie et sa valeur est prise Output lv v ED H DUTPUT x wi vi Qi wi Vi Qi Suivant ces r gles s mantiques tant donn un programme dSL et sa distribution il est possible de d finir une syst me transitions tiquet es d crivant le comportement du programme D finition 9 S mantique distribu e d un programme dSL Etant donn un programme correct
81. L est qu il n est pas proprement parl modulaire a cause de la contrainte atomique Une application distribuable peut ne plus l tre par le simple changement de site d une variable Par exemple prenons une m thode d finie sur une classe Si toutes les variables de la classe utilis es dans la m thode sont distribu es sur le m me site la contrainte atomique est respect e Un grand nombre d instances de la classe peut donc tre d fini tant que leurs variables sont distribu es sur le m me site Si maintenant on d finit une instance de la classe o une des variables apparaissant dans le code de la m thode est distribu e sur un site diff rent des autres variables de l instance l application n est plus distribuable et le code doit tre chang Cet inconv nient a aussi des impacts sur la compilation En effet il n est pas possible de faire une compilation s par e de librairies Et cela parce que le code g n r est d pendant de la localisation et que la localisation est d pendante des objets instanci s dans le programme Imaginons une m thode d finie sur une classe dans une librairie Si une instance de la classe est ajout e dans le programme et que cette instance est distribu e de mani re diff rente des autres instances d j d finies la librairie doit tre recompil e Ceci n est pas le cas pour des langages tels que C ou Java 9 La syntaxe de dSL Le concept principal de dSL est la notion d v nement En r acti
82. T ID Block startwai case HOP WAIT ID nextBasicB lock dsl vm id break case default error ER halt case 18 _ is_wai _ is_wai h x case 25 case default while 1 nbVal READ INT FROM CHAR dsl vm args while nbVal switch READ INT FROM CHAR dsl vm args case 24 x READ INT FROM CHAR dsl vm args break y READ BOOL FROM CHAR dsl vm args break error ERR UNKNOWN PARAM ID halt R UNKNOWN HOP ID ting6 TRUE i OR y twait ting6 FALSE break i TRUE i if is waiting6 wakeup nextBasicBlock HOP WAIT ID thread 6 Figure 5 35 Exemple de code g n r pour une s quence deux param tres et avec une instruction d attente 14 10 Les v nements La figure 5 36 pr sente l extrait du fichier vm 1 c correspondant la s rie d v nements de la figure 2 31 La figure 5 37 reprend le code de vm 2 c 77 void graph 10 bEGALa int nextBasicBlock HOP WAIT ID while true switch nextBasicBlock case HOP WAIT ID startwait nextBasicBlock dsl vm id break case default error ERR UNKNOWN HOP ID halt case 19 b a nextBasicBlock HOP WAIT ID break void graph 11 b 1 void graph 13 HOP 1 9 19 0 void graph 15
83. THEN self state FALSE self rotor lt stop self motor 20 END IF END METHOD ETHOD elevator down IF touch down lt 0 THEN self state FALSE self rotor stop self motor 2 END IF END METHOD ETHOD elevator stop self motor 0 self state TRUE END METHOD WHEN IN elevator touch up gt 0 THEN self position TRUE self lt stop END WHEN WHEN IN elevator touch down gt 0 THEN self position FALSE self lt stop D WHEN tj z Figure 6 6 Code dSL de la classe elevator Un ascenceur est constitu d un moteur de deux capteurs situ s en haut et en bas de la cage et d un tapis roulant Les m thodes de base consistent monter descendre et arr ter l ascenceur Les r gles de base sont que lorsque l ascenceur arrive en haut ou en bas les moteurs s arr tent Nous avons ajout deux variables internes l ascenceur repr sentant son tat et sa position L ascenceur est en position bas si position est gal FALSE et si l tat est gal TRUE L ascenceur est en position haut si position est gal TRUE et si l tat est gal TRUE Lorsque l tat est gal FALSE l ascenceur est en mouvement Lorsque l ascenceur est en mouvement il n est pas permis que le tapis soit en mouvement La figure 6 6 pr sente le code de la classe elevator La variable free
84. UNIVERSITE LIBRE DE BRUXELLES Facult des Sciences D partement d Informatique G n ration de code de syst mes distribu s DEVOS Nicolas M moire pr sent en vue de l obtention de la licence en informatique Sous la direction de M Thierry MASSART Ann e acad mique 2003 2004 Nous tenons a remercier notre promoteur Thierry Massart les assistants C dric Meuter Alexandre Genon et tout particuli rement Bram de Wachter sans qui ce travail n aurait pas t possible Ainsi que tous ceux ayant contribu a l laboration de ce m moire Table des mati res Chapitre I Introduction Lx Buts et approch SUITE S RS RE aedi D Re anale uns 6 2 LES SYST MES TAGS seras is Ur reise en ed Hugh Da Nd Var A Abi US ME eet te EEA 6 9 Str ct re du M MON essa eae ere e e io qu di ym e Re IR cU HOY QU M E cue 7 Chapitre II Le langage dSL T Titroduction au ENT EE 8 2 Inconv nients de SL et motivations de AS shot insiste 9 3o C LEE 10 4 Le probleme de la distribution du Code iar a n ao a Ho i ese ele nc va aha Dena 11 5e EVEN driven pra Lace opis pe cpu A ee D ea acca al TO Pet 12 6 Code atomique et s quentielle A e adu 13 75 Avant s s EE 14 ix Inco nventents de dSE outs cnt ib tus Eeer ne a ac Ee uM datas Le LM d 15 SV n xe EE 15 10 EXGIDISS nn a A nent dt eratac ton E aei Dus 24 Il Ea s mantique de E EE 35 Chapitre III Les Lego Mindstorms 1 Introduction aux Lego Mindstort s erret ete tete tiir Ere nec e eer
85. WN ID 3 Figure 5 16 Structure de la fonction getID Lorsqu un message de saut est re u la t che correspondante est r veill e Le current thread id est assign celui de la s quence et l identificateur du case ex cuter extrait du message est plac dans la variable globale 4s1 vm id La s quence se r veille dans le case HOP WAIT ID et consulte dsl vm id pour savoir quel est l identificateur du bloc ex cuter ainsi que dsl vm args pour r cup rer les variables transmises en param tre Le lancement d une s quence dans le code dSL est traduit par l instruction HOP site id s quence id partie param tres ou id partie est l identificateur de la premi re partie de la s quence identifi e par id s quence site est le site de distribution de cette partie et param tres sont les param tres ventuels de la s quence Lorsqu il s agit de traduire un point de migration c est dire lorsque l on se trouve l int rieur d une s quence et qu il faut ordonner l ex cution de la partie de s quence suivante situ e sur un autre site le compilateur g n re galement un appel la fonction HOP site id s quence id partie param tres o param tres correspond aux variables actives transmettre la partie de s quence suivante ainsi que la mise jour du prochain case ex cuter savoir le HOP WAIT ID puisque la tache doit tre mise en attente Lorsque la s quence contient des inst
86. a description du Systeme a oca eee rebar stages Dates P HL aad MURS tas a Data ant atlas PANNE EE 3 Mod lisation Lego Mindstorms du syst me ccccesccessceseeeeseeceseceseeeeeeeeseecaecneeseeeensaes 4 Impl mentation dSL du syst me us idi eie eterne ra ERES bI ER RO o Dae v Ann au 5 o EESTI Oen edu fe cr tt Le a cp A os Fe oka dl See basins frd wile Ve Chapitre VII Conclusions Re 2 Travaux E EE blue 102 Index Eer HEET 104 Annexes Ac Grammaire AS initie andr RENE AMARE MER aA en eU 107 B Syntaxe dS Ere Stacy nay nn than cepi A UA EATEN rA tette A ATL D cM Creo ue 110 C Manuel d utilisation LegOS uiis adeat etit aad ped diede dat Ne ue 115 D Code du fichier dsi vm EE 118 E Code du protocole de communication ab c ahh 124 F Format des 3 types de messages chang s cccsccsessestsecssscesscseccesscecsasceseesencesneees 137 G Principe de construction des tapis roulants en Lego Mindstorms 138 H Principe de construction des chariots mobiles en Lego Mindstorms 141 I Principe de construction des ascenceurs en Lego Mindstorms suus 143 J Principe de construction de la cage d ascenceur en Lego Mindstorms 144 K Code dSL de la cha ne de montage uisi tees tre iab deed Va tea Po diese sieste A Eae es 146 Chapitre I Introduction 1 Buts et approche suivie Les objectifs de ce travail sont l tude et la r alisation
87. aissent alors En effet pendant le transfert d une donn e il faut emp cher que la donn e soit modifi e sur le site d origine D s lors pour conserver les ex cutions 11 correctes le syst me doit introduire des blocages temporaires de l ex cution Il en r sulte donc des temps d ex cution al atoires En outre le nombre de messages inter sites pourra tre important De plus la r cup ration des erreurs et la v rification du code pourront s av rer d licates C est pour cela qu une distribution statique a t choisie en dSL Les variables globales sont r parties statiquement sur les diff rents sites Ce qui permet de pr voir la compilation les communications inter sites qui seront n cessaires au bon fonctionnement du syst me Une variable ne peut tre distribu e que sur un site et toutes les assignations de cette variable ne pourront tre effectu es que sur ce site La distribution statique repose sur le fait que plut t que de demander la valeur d une variable pendant l ex cution on va s assurer que la valeur soit disponible et pertinente tout moment de l ex cution 4 2 Localisation des instructions de code Apr s avoir attribu statiquement les variables des sites il faut r soudre le probl me d ex cution des instructions Une solution est la migration de t ches ou thread migration La d termination de l endroit o s ex cute une instruction donn e peut se faire de mani re dynamique c est dire
88. ait event amp getControl unsigned int cpid void portHandler const unsigned char message unsigned char length int SIZE BUF unsigned char ptr sem getvalue amp sem SIZE BUF amp SIZE BUF if SIZE BUF gt SIZE MAX i error ERR BUFFER OVERLOAD else if ptr char malloc length error ERR BUFFER OVERLOAD2 else memcpy ptr message length dsl vm buf POS BUF ptr POS BUF POS BUF 1 SIZE MAX 120 sem post amp sem_ SIZE BUF void systime setup handler const unsigned char message unsigned char length time t time CHAR TO INT time message sys time time time setup true void systime_send char message 2 time t time sys time INT TO CHAR message time lnp integrity write message 2 void systime setup int temp 0 time setup false lnp integrity set handler systime setup handler while time setup temp cputw temp void send unsigned char message unsigned char length unsigned destination if ab awrite message length destination error ERR WRITE FAIL void LAUNCH ID COLOR int site int id int param const unsigned char ln 3 2 param char message ln p message va list ap int i va start ap param 4 ptr 2 ADD_INT_TO_CHAR p id while param
89. aram tre un pointeur de caract re args Il contient les param tres de la m thode savoir les valeurs de ceux ci dans l ordre de leur d finition Les identificateurs des param tres ne sont pas n cessaires Donc pour toute d finition dSL d une m thode distribu e sur un site METHOD classe id m thode param tres liste instructions END METHOD le compilateur va cr er une fonction void graph_id param liste instructions C o id est l identificateur de la m thode au sein du compilateur param l ventuelle liste de param tres e si param tres est e unsigned char args sinon et liste instructions C est la liste des instructions C de la m thode Les instructions sont ventuellement pr c d es de la d claration des variables locales ainsi que de la d claration des param tres et des instructions d extraction des param tres si param tres n est pas vide Une instruction d appel synchrone d une m thode sans param tre est traduite par un appel direct la fonction correspondante d identificateur id graph d Si la m thode prend des param tres les valeurs des param tres sont stock s dans un vecteur de caract re transmis en param tre la m thode Dans le cas d un appel asynchrone une m thode un message de demande d ex cution de m thode est envoy Une instruction d appel asynchrone est traduite par LAUNCH ID COLOR int site int id int
90. ation avec notamment les routines d interruption et 3 l envoi des messages Les structures de contr le d taill es plus haut sont donc des ressources partag es entre ces taches Il faut donc mettre en ceuvre une section critique Le m canisme de s maphores assure l exclusion mutuelle entre des taches Le s maphore sem ab write est initialis avec une valeur de 1 Au d but de la fonction d envoi un sem wait sem ab write permet d attendre que l ex cution des autres instances de ab write soient termin es Un sem post sem ab write en fin de fonction permet de lib rer le s maphore pour qu une autre instance de la fonction puisse s ex cuter UTILISATEUR Figure 5 43 Chemin parcouru par un message envoy Lors de la r ception d un message sur le port infrarouge le syst me d exploitation donne le contr le au portHandler et lui transmet le message recu Les messages envoy s sont tous broadcast s La premi re mission du portHandler est donc de trier les messages pour ne conserver que ceux destin s au site sur lequel il se trouve Le portHandler constitue une routine d interruption il ne peut donc tre mis en attente Cela implique qu il ne peut pas envoyer lui m me l acquittement d un message recu Les messages recus sont donc stock s dans une liste en attendant d tre trait La structure de la lise des messages recus est reprise la figure 5 44 Puisqu il acc de une structure de donn es il faut assurer l
91. atomique impose que certaines variables et instructions soient distribu es sur un site pr cis cf 6 Code atomique et s quentiel En ce qui concerne les autres elles peuvent tre r parties sur un des sites composant le syst me Nous allons introduire ici la notion de distribution maximale qui repr sente la configuration la plus lib rale possible pour un programme dSL donn Il a t prouv dans DMM04 que la distribution maximale contient toutes les traces de n importe quelle distribution D de 2 D s lors v rifier la s curit d un syst me sur cette distribution impliquera la s curit pour tout autre distribution Pour d finir la notion de distribution maximale il faut pouvoir comparer deux distributions Nous introduisons donc un ordre partiel sur les distributions c est dire une hi rarchie Definition 2 Hi rarchie de distribution Soit D V Vz V et D V V V deux distributions d un programme dSL P La distribution D est un raffinement de la distribution D not D xD si VV e D AV e D Vii Vi Definition 3 Distribution maximale d un programme dSL correct La distribution maximale d un programme dSL correct P est la distribution Dmax tel que D Dmax Dmax lt D 11 3 D finitions pr liminaires Avant de d finir la s mantique op rationnelle structurelle de dSL il faut introduire certaines d finitions pr liminaires La s mantique sera d finie en termes de syst mes
92. aux d un programme dSL P tant donn e une distribution D est not G E Maintenant il est possible de d crire les r gles de s mantique qui d finiront la relation de transition des syst mes transitions labellis es La premi re r gle correspond la s mantique d interleaving Par exemple si dans un tat local une transition peut tre faite alors partir de n importe quel tat global contenant cet tat local la m me transition peut tre prise en ne modifiant que l tat local 38 Interleaving EP wi Vi Pi wi vi i Eb H wi v1 1 e wi Vi Di wn Vn d n Jl 2 w1 vi 1 I wi vi di wey Wn Un n Va Tr UX La deuxi me r gle de s mantique est celle du broadcast Lorsqu une variable tild e change de valeur le site doit transf rer ce changement de valeur tous les autres sites et sp cialement aux sites poss dant une copie locale de cette variable Il s agit d une t transition Tous les tats locaux des sites concern s seront mis jour avec le nouveau message Broadcast ED w1 11 1 BCAST x wi vi i sa Wa rs Qn 2 Loan v1 64 s Wi Vi di 5 Wn Vn Qn o Vj 1 n d di x vi i A l inverse des deux premi res r gles qui taient des r gles globales les r gles suivantes sont des r gles locales La premi re de ces r gles correspond au commencement d un nouveau cycle Lorsqu un espace de travail
93. b dir 2 else if moteur gt 0 motor b dir 1 else motor b dir 3 motor b speed ABS moteur Figure 5 24 Exemple de mise a jour des dispositifs 14 4 Les instructions d assignation La figure 5 25 reprend des exemples d instructions d assignation correspondant a l exemple de la figure 2 18 entier 0 entier 1 2 3 10 ntier entier 1 entier LONG TO INT long BOOL TO INT booleen booleen TRUE booleen LONG TO BOOL long OR INT TO BOOL entier Figure 5 25 Exemples d instructions d assignation g n r es 14 5 Les instructions conditionnelles La g n ration de code pour les instructions conditionnelles dSL de la figure 2 20 est reprise la figure 5 26 Ces instructions sont trait es comme situ es en dehors d une s quence 72 if entier gt 10 booleen TRUE if entier gt 10 booleen TRUE else booleen FALSE if entier gt 10 if booleen FALSE booleen TRUE else if booleen TRUE booleen FALSE Figure 5 26 Exemple d instructions conditionnelles g n r es 14 6 Les instructions d it ration Le code g n r de l instruction d it ration dSL de la figure 2 21 est repris a la figure 5 27 Cette instruction est consid r e comme d finie en dehors d une s quence while booleen ntier entiertl if
94. carry brick from t 3 to t 4 EQUENCE t3 to t4 wait the elevator to be in position down a l down wait a l position FALSE AND a l state TRUE launch the two conveyer belts a l rotor go t_3 lt go brick on conveyer belt of elevator wait a l rotor light TRESHOLD a l rotor stop t_3 lt stop SES the conveyer belt 3 t 3 free TRUE get the elevator in position up a 1 upO wait a l state TRUE AND a 1l position TRU Lj launch the two conveyer belts t 4 go a l rotor go wait t_4 light lt TRESHOLD t 4 stop a l rotor stop bring back the elevator in position down LAUNCH a 1 down wait the moving cart 2 to be free wait c 2 free TRUE c 2 free FALSE launch the next sequence IF last out TRU THEN last out FALSE LAUNCH t4 to t5 ELSE xy last out TRUE LAUNCH t4 to t6 END IF Cn EH Ez free the elevator a l free TRUE END SEQUENCE carry brick from t 1 to t 3 150 SEQUENCE tl to t3 get the moving cart in position 1 c l1 go in one wait c l state TRUE and c_1 position TRU Gl launch the two conveyer belts c l rotor go LAUNCH t 1 go brick on conveyer belt of moving cart wait c l rotor light TRESHOLD c l rotor
95. contr leurs programmables CPs ou programmable logic controllers un superviseur qui ensemble constituent le syst me et l environnement L environnement et le syst me interagissent l un avec l autre au moyen des dispositifs d entr e et de sortie des CPs A vise 10 Syst me Lo interface an gt interface F CP CP Environnement Figure 2 1 Architecture d un syst me SL Le superviseur est une unit ind pendante poss dant deux interfaces Une vers les diff rents CPs l autre vers l op rateur Il effectue le lien entre les diff rents CPs et l op rateur Les CPs galement appel s automates en raison de leur simplicit voluent dans un environnement local et interagissent avec lui par l interm diaire de leurs senseurs et actionneurs L tat de l environnement local d un CP correspond aux valeurs de ses entr es de ses sorties et de ses variables internes Les CPs ne communiquent qu avec le superviseur auquel ils transf rent notamment les valeurs des variables correspondant aux dispositifs d entr e et de sortie situ s sur chacun d eux C est le superviseur qui est charg de g rer le syst me en faisant le lien entre les diff rents contr leurs Il leur transmet les valeurs des variables n cessaires et d finit leur comportement Typiquement le superviseur va mettre jour certains flags sur les CP
96. correspondent aux bornes sup rieures et inf rieures des index du vecteur et type le type des l ments du vecteur Il est aussi possible de d finir des classes gr ce la syntaxe suivante CLASS id liste d clarations END CLASS ou id est l identificateur de la classe et iste d clarations l ensemble des d clarations des variables de la classe cf 9 6 Les variables 9 5 La valeur UNKNOWN Toute variable peut prendre la valeur UNKNOWN c est dire inconnue dans le cas par exemple d une mauvaise op ration ou d un probl me de r seau L valuation de n importe quelle expression dont un des membres est la valeur UNKNOWN donne la valeur UNKNOWN 16 Il est possible de tester si une variable ou une expression est de valeur inconnue grace a la fonction IS UNKNOWN qui doit tre utilis e de la mani re suivante IS UNKNOWN expression 9 6 Les variables Une variable est un espace m moire nomm qui peut tre utilis pour contenir une valeur qui peut tre modifi e pendant l ex cution du programme Toute variable doit tre d clar e avant d tre utilis e La forme g n rale d une d claration d une variable est id type ou id est l identificateur de la variable et type son type Remarquons que diff rentes variables d un m me type peuvent tre d finies ensemble gr ce la syntaxe suivante o id et id2 sont les deux variables de m me type id
97. ction renvoie l identificateur de la tache pid kill int pid fonction qui permet de tache la ta che identifi e par pid sleep int s fonction permettant de mettre en attente une tache pendant s secondes msleep int m fonction permettant de mettre en attente une tache pendant m millisecondes wait event amp f unction wakeup t data fonction permettant de suspendre une t che en attendant que function renvoie une valeur non nulle data permet de passer des param tres la fonction D 7 Lego Network Protocol Inp init int cp host int tcp port int Inp adress int Inp mask int flags fonction permettant d initialiser le protocole Pour chaque param tre 0 est la valeur par d faut tcp host et tcp port sont utiliser dans un programme qui s ex cutera sur un terminal pour se connecter au LNP daemon Inpd Inp adress et Inp mask permettent de sp cifier l adresse LNP du programme Flags permet de modifier le comportement de Inpd Inp adressing set handler int port portHandler function fonction permettant de sp cifier un gestionnaire du port port Lorsqu un aquet est re u le syst me d exploitation appelle portHandler function pour le traiter Les paquets sont transmis de mani re adress e Inp adressing write unsigned char data unsigned char length int dest addr int port fonction permettant d envoyer de mani re adress e le message data de longueur length l adresse dest addr par l interm diairie du port
98. dent aux instructions IF Les instructions d it ration sont d termin es par WHILE Les instructions d attente sont les instructions WAIT Celles de lancement les instructions LAUNCH En dSL toute instruction se termine par un a Les instructions d assignation La forme g n rale d une assignation est nom variable expression ou le membre de droite peut tre une simple constante ou une expression plus complexe La cible c est dire la partie gauche de l assignation doit tre l identificateur d une variable mais pas d un v nement d une m thode d une s quence ou une constante dSL ne permet pas les assignations multiples Une instruction d assignation ne porte que sur une variable qui doit tre d finie dans le scope de l instruction Cette variable doit tre de type interne ou de sortie cf 9 7 Les sites b Les instructions conditionnelles La forme g n rale d une instruction conditionnelle est IF condition THEN liste instructions 1 ELSE liste instructions 2 END IF ou condition est une expression logique et iste instructions 1 et liste instructions 2 sont des blocs d instructions qui sont ex cut s si la condition est respectivement vraie ou fausse lors de l ex cution de l instruction Il est possible de ne pas sp cifier de traitement dans le cas o la condition est fausse grace la forme g n rale suivante IF expression THEN liste instructions END IF
99. distan umber of simul umber of simul d of the curre taneously ou herwise memory allocation not used the parameters const unsig unsigned char id site unsigned c unsigned char incoming unsigned cha called when a messag sites taneously incoming messages tgoing messages problems n sites incoming and r outgoing ned char message har n sites if init pool amp IMESS POOL incoming sizeof MESS DEFAULT HEADER SIZE 255 init pool amp OMESS POOL outgoing sizeof MESS DEFAULT HEADER SIZE 255 init pool amp SITE POOL n sites sizeof SITE return 1 E 7 ndif S FIRST NULL M FIRST NULL id site id site sem init amp sem ab por sem init amp sem ab wri sem init amp sem todo 1 0 user portHandler u portHa ndler A lnp integrity set ha execi amp thread AB I execi amp thread AB O return 0 0 0 PRIO NORMA 0 0 PRIO NORMA tHandler 1 1 te 1 1 ndler B portHandler EFAU EFAU t m 4 ES T STACK SIZI T STACK SIZI 135 brief Use this function to asynchronously send a message The message is added to the list and will be sent as soon as possible The function returns f M immediately param message The message to send param length The length of the mes
100. e ABC avec deux variables x et y et une instance A de cette classe Les variables g n r es seront A_x et A y 59 En ce qui concerne les m thodes et les s quences l identificateur dans le programme cible LegOS est d fini selon la forme graph id o id est l identificateur qui a t attribu par le parser la m thode ou la s quence Cette d nomination fait r f rence au graphe de contr le de flot et est conserv e pour des raisons historiques 5 Les types des variables La figure 5 10 reprend les correspondances entre les types dSL et les types C Par exemple pour toute d claration de variable dSL de type BOOL une variable de type unsigned char sera g n r e dSL C INT short BOOL unsigned char LONG time t Figure 5 10 Correspondance entre les types dSL et C 6 Les variables Il existe deux types de variables les variables globales et les variables locales Nous avons vu que les variables globales d un programme dSL sont distribu es statiquement sur un des sites du syst me cf 77 4 1 Localisation des variables Pour chacune de ces variables sa d claration est g n r e globalement sur le site sur lequel elle est distribu e En ce qui concerne les variables globales tild es leur d claration se retrouve galement sur les sites o la variable est utilis e de mani re tild e Remarquons qu elles poss dent le m me identificateur sur ces diff rents sites cf
101. e peuvent tre imbriqu s 9 9 Les expressions Une expression valide dSL est une combinaison correcte d op rateurs hormis les op rateurs d assignation et de lancement de constantes et de variables La notion de combinaison correcte est d finie par la syntaxe compl te de dSL reprise en Annexe A L valuation d une expression se fera suivant les diff rentes priorit s des l ments la composant Une expression peut tre logique ou arithm tique suivant le type de ses variables et de ses op rateurs Une expression logique est une combinaison correcte d op rateurs de constantes et de variables logiques telle que par exemple booleen OR FALSE Une expression arithm tique est une combinaison d op rateurs de constantes et de variables arithm tiques telle que 5 2 3 L ordre d valuation des l ments d une expression n est pas sp cifi Le programmeur veillera donc ne pas se baser sur l ordre dans lequel les sous expressions sont valu es En l occurence l usage des parenth ses permet de d finir de mani re pr cise l ordre d valuation des sous expressions 20 9 10 Les instructions Selon la d finition courante une instruction est la plus petite partie d un programme qui peut tre ex cut e En dSL il est possible de diff rencier diff rents types d instructions d assignation conditionnelle d it ration d attente et de lancement Les instructions conditionnelles correspon
102. e valeur 30 METHOD bidon switch a INT b INT LOCAL VAR temp INT END VAR temp aj a b b temp END METHOD Figure 2 25 Exemple de m thode deux param tres avec variables locales Il est important de ne pas oublier que le code d une m thode est atomique Il doit donc tre distribuable sur un seul site La figure 2 26 montre un extrait de programme contenant diff rents exemples de m thodes correctes La figure 2 27 pr sente un exemple de m thode qui ne respecte pas la contrainte atomique et son quivalent qui la respecte 31 CLASS ab a b INT END CLASS CLASS cd c d INT END CLASS GLOBAL VAR A B ab Aet B sont des instances de la classe ab DC e e f g INT END VAR SITE sitel INPUT A a 0 0 1 OUTPUT Acb 1 0 1 INPUT INPUT END_SITE con Rem SITE site2 INPUT B a 0 0 1 OUTPUT B b 1 0 1 ND SITE tj METHOD ab assignA entier INT self a entier END METHOD METHOD ab switch LOCAL VAR temp INT END VAR temp self a self a self b self b re temp END METHOD METHOD cd assignCD entierC INT entierD INT self c entierC self d entierD END METHOD METHOD cd assignCtoF self c f END METHOD Figure 2 26 Programme dSL avec exemples de m thodes
103. e valeur d une variable tild e un appel handleWarn int id int val est ex cut dans handleMsg o id est l identificateur de la variable et val sa valeur Le code de cette fonction est d fini la compilation Il est g n r dans le fichier c du site sous la forme d un switch sur l identificateur de la variable Pour chacune des variables tild es utilis es sur le site un case est g n r selon le format case id variable nom variable val ou id variable est l identificateur de la variable nom variable son nom dans le programme dSL 64 Lorsque le type de la variable est bool en une conversion est effectu e en ajoutant bool avant val Remarquons que nous avons d faire face un petit probl me d efficacit Imaginons une variable d input tild e A chaque fois que la boucle nput Process Output va tre effectu e un ou plusieurs messages seront envoy s en fonction du nombre de sites sur lesquels la variable est utilis e Nous avons donc pris la pr caution de d clarer localement samplelnputs une variable contenant l ancienne valeur de la variable d entr e tild e c est dire la valeur de la variable avant d avoir lu le p riph rique d entr e Le message de transfert de valeur n est envoy uniquement s il y a un changement de valeur de l entr e 11 Les m thodes Pour toute m thode une fonction sera g n r e Si la m thode a des param tres la fonction prend en p
104. ec Vi e 1 W 1 o lt w i et U ien 09 W 11 5 La s mantique op rationnelle structurelle De mani re informelle le comportement d un programme dSL peut tre vu comme la composition parall le de n processus un pour chaque site communiquant avec l environnement Chaque processus g re un ensemble de variables V et communique avec les autres processus par des canaux FIFO c est dire First In First Out pour signaler entre autre la valeur d une variable tild e En r alit chaque S est la boucle infinie Input Process Ouput d taill e pr c demment avec Input correspond Sample Vi lt v Output Write V lt y et Process correspondant au traitement des messages et des WHENSs Nous commencerons par d finir l tat global d un programme dSL D finition 8 Etat global d un programme dSL correct Etant donn e une distribution D Vi V2 V d un programme dSL P l tat global de P peut tre d fini comme suit G 1 Vi 81 Ov Vn Gn avec V i e 1 n Vi 9 l tat local du processus i o est l espace de travail c est dire les s quences d instructions restant ex cuter v est une fonction de valuation renvoyant vrai ou faux et d finie sur les variables globales du processus i les copies locales des variables tild es et les variables contenant les anciennes valeurs des conditions des WHENS giest le canal FIFO de communication L ensemble des tats glob
105. ego Mindstorms la brique RCX Robot Control Explorer repr sent e la figure 3 1 Figure 3 1 La brique RCX Une brique RCX est un petit syst me informatique complet avec un CPU un affichage de la m moire et des p riph riques En effet elle comporte un microcontr leur Hitachi ainsi que trois entr es identifi es par les chiffres 1 2 et 3 trois sorties identifi es par les lettres A B et C et un cran LCD Quatre composants principaux peuvent tre utilis s des moteurs dont le sens et la vitesse de rotation peuvent tre param tr s et des capteurs de toucher de lumi re et de rotation Ceux ci sont d taill s la figure 3 2 Les Lego Mindstorms offrent d autres possibilit s plus ludiques telles que l utilisation de petites lumi res ou la production de sons 4 port infrarouge entr es capteur de lumi re v capteur de toucher capteur de toucher cran LCD Figure 3 2 La brique RCX et ses accessoires Les briques sont munies d un port de communication infrarouge Par l interm diaire de ce port chaque brique RCX peut non seulement recevoir un programme effectuer mais aussi communiquer avec un ordinateur comme illustr la figure 3 3 ou avec d autres briques Figure 3 3 Communication RCX PC Les Lego Mindstorms peuvent tre d s lors utilis s comme laboratoire pour la conception et la v rification d applications distribu es Elles offrent en
106. enant uniquement les caract res a b c d A C D 1 2 3 et 4 Identificateurs corrects Identificateurs incorrects abcd AbcD 1234 _abcd _AbCd labcd alb2c3d4 _ 1234 bcd _abl2cd34 abc_d Figure 2 9 Exemples d identificateurs corrects dSL 10 2 La structure d un programme Un programme dSL doit respecter un certain nombre de contraintes quant l ordre de d claration de ses l ments classes variables sites m thodes s quences v nements cf 9 2 La structure du programme La figure 2 10 reprend le squelette g n ral d un programme dSL correct Pour de plus amples pr cisions le programme dSL de l tude de cas peut tre consult en Annexe K Remarquons que l ordre des v nements m thodes et s quences peut tre diff rent 24 CLASS d claration des classes ventuelles END CLASS fin de la derni re d claration de classe GLOBAL VAR d claration des variables globales ND VAR fin de la d claration des variables globales E m SITE d claration des sites Er ND SITE fin de la derni re d claration de site METHOD d claration des m thodes ventuelles END METHOD fin de la derni re d claration de m thode SEQUENCE d claration des s quences END SEQUENCE fin de la derni re d claration de s
107. endrons plus loin sur ce point lorsque nous parlerons du traitement des messages La fonction de cr ation et d envoi de ce type de message est d taill e la figure 5 8 o site id et s quence sont respectivement les identificateurs du site de la partie de s quence et de la s quence Ensuite viennent les param tres pass s sous forme d une va list void HOP int site int s quence int id int n para Figure 5 8 Fonction d envoi d une demande d ex cution d une partie de s quence Dans le cas d un transfert de valeur de variable tild e le message doit contenir l identificateur de la variable et sa nouvelle valeur L identificateur est n cessaire aussi car il peut y avoir plusieurs variables tild es utilis es sur un site La fonction de cr ation et d envoi du message est reprise la figure 5 9 o id et val sont respectivement l identificateur et la valeur de la variable et site le site de destination du message void SEND ID WARN int site int id int val Figure 5 9 Fonction d envoi d un transfert de valeur d une variable tild e 3 3 Le traitement des messages Les messages recus par un site sont stock s dans l attente de leur traitement effectu par handleMsg cf 2 La t che Input Process Output Celui ci est diff rent selon le type de messages 1 Dans le cas d une demande d ex cution d une m thode l identificateur de la m thode et les param tres ventuels sont transmis
108. ent and small in that order section interface The AB Protocols interface 8 Three functions control the AB Protocol The init ab protocol which inits all data structures 2 ab swrite For synchronous message sending the send function returns when the messag is delivered and 3 ab awrite for asynchronous message sending the send Function returns immediately Look at the ab protocol interface module documentation for more details We used this implementation in highly asynchronous and multithreaded environment and took special care to avoid race conditions this implementation should therefore be sufficiently robust to survive the more demanding developer Nsection license License This software is released under the Gnu Public License GPL Feel free section Compiling To compile the library you must have legOS BrickOS 0 2 6 probably works with other versions too and the h8300 cross compiler which is also needed to use legOS BrickOS installed Next change LEGOS ROOT in the Makefile in src lib so it points to your legOS installation directory Launch lt b gt Make lt b gt to create the lt b gt ablib a lt b gt library Any legos program should then lt b gt include ab h lt b gt located in src include and the lt b gt ablib a lt b gt file must be linked with the program Look at the example program section contacts Contacts
109. es chariots mobiles Pour chaque l ment on peut d finir une classe contenant les m thodes de manipulation et les r gles de base respecter Ensuite nous tudierons les liens tablis entre ces diff rents l ments c est dire les messages chang s entre les sites pour assurer le bon fonctionnement du syst me Pour finir nous d taillerons la distribution des variables globales sur les cing sites constituant le syst me cf 3 Mod lisation Lego Mindstorms du syst me 4 1 Les tapis CLASS conveyor belt motor INT light INT free BOOL END CLASS METHOD conveyor belt go self motor 20 END METHOD METHOD conveyor belt stop self motor 0 END METHOD Figure 6 5 Code dSL de la classe conveyor belt Le code de base de la classe conveyor belt est repris dans la figure 6 5 Chaque tapis est constitu d un moteur et d un capteur de lumi re Les m thodes de manipulation sont la mise en route et l arr t du tapis La vitesse des moteurs a t d finie de mani re empirique La variable free est utilis e pour indiquer si une brique est sur le tapis ou non 91 4 2 L ascenceur CLASS elevator motor INT touch up INT touch down INT rotor conveyor belt state BOOL TRUE running FALSE stopped position BOOL TRUE up FALSE down free BOOL ND CLASS tj ETHOD elevator up IF touch up 0
110. es inconv nients des solutions classiques CORBA TAN02 DCOM TAN02 etc pourraient tre utilis es afin de faciliter le travail du designer Dans ce cas l organisation du syst me est bas e sur le paradigme d objet Chaque l ment du syst me est un objet poss dant une interface Dans ces syst mes dits orient s objet distribu distributed object oriented systems des services et des ressources sont disponibles aux clients sous la forme d objet Ces solutions se chargent des aspects de communication au travers des interfaces des objets et permettent au programmeur de se concentrer sur les fonctionnalit s du syst me De plus l approche objet distribu offre des facilit s dans la conception et la visualistion du syst me en permettant de repr senter celui ci sous forme d interactions d objets Cependant ces solutions sont relativement lourdes De plus il n existe pas de s mantique formelle concernant les communications Le comportement exact du syst me n est pas pr visible Ce qui n est pas envisageable pour un contr leur de syst me critique et qui ne permet pas leur v rification C est pour ces raisons que le langage dSL a t cr Il reprend la plupart des fonctionnalit s de SL mais rem die ses inconv nients en offrant une s mantique formelle une vision centralis e du syst me et une distribution de code transparente et automatique Dans la suite nous donnerons une description compl te du langage dSL concepts
111. es t1 to t3 et t2 to t3 Elle lance aussi la s quence suivante c est dire la s quence t3 to t4 Nous avons aussi d fini deux variables ask one et ask two qui indiquent si une brique est en attente sur le tapis 1 ou sur le tapis 2 Les conditions des v nements sont donc d finies sur ces variables Les variables ask one etask two sont mises jour gr ce aux v nements de la figure 6 8 qui permettent galement d arr ter les tapis lorsqu une brique se pr sente face aux capteurs 94 HEN t 2 1ight lt TRESHOLD AND ask two FALSE THEN t 2 stop ask two TRU END WHEN GI THEN I HEN t 2 1ight gt TRESHOLD AND ask two TRUE ask two FALSE END WHEN LH HEN t l light lt TRESHOLD AND ask one FALSE THEN t 1 stop ask one TRU END WHEN LH WHEN t l light gt TRESHOLD AND ask one TRUE THEN ask one FALSE END WHEN Figure 6 8 Code des v nements d arr t des tapis d entr e et de mise jour des variables ask one etask two L utilit des variables ask one et ask two r side dans l observation suivante S mantiquement lorsqu une variable est modifi e il faut valuer les conditions des v nements utilisant cette variable Nous avons vu que les valeurs relev es par les capteurs de lumi re sont tr s variables Les variables as
112. es variables ree Le code de tout le syst me est reprise en Annexe K 5 valuation L usage de dSL pour impl menter un syst me LegOS contribue r duire de mani re vidente le travail du programmeur tant du point de vue de la conception que de la taille du code g n rer et en particulier si on consid re des syst mes distribu s sur plusieurs briques RCX 98 Le langage dSL est un langage sp cifique pour la mod lisation des syst mes r actifs Il s av re id al pour impl menter des syst mes LegOS qui peuvent toujours tre vus comme des syst mes r actifs En effet un programme LegOS r agit a des stimuli tels que la pression d un bouton ou le changement de luminosit devant un capteur de lumi re Dans le paragraphe 4 nous avons pu voir la simplicit avec laquelle les l ments de la chaine ont pu tre impl ment s en dSL D autre part dSL offre une vision centralis e du syst me Le compilateur g n re automatiquement tout ce qui concerne la distribution du syst me tant du point de vue des messages chang s que des traitements distribu s Si nous voulions impl menter un syst me distribu en C pour LegOS il serait n cessaire de pr voir toute une s rie de choses telles que la syntaxe des messages chang s et les fonctions de conception d envoi de r ception et de traitement des messages De plus afin de garantir un comportement distribu correct le programmeur devrait g n rer lui m me toutes les c
113. essaire de transmettre une partie du contexte local 3 Variables tild es Lorsqu une variable tild e est assign e sa nouvelle valeur doit tre transmise tous les sites sur lesquels elle est utilis e Il existe donc trois types de messages 1 Les messages de demande d ex cution d une m thode 2 Les messages de demande d ex cution d une partie de s quence le lancement d une s quence est consid r comme la demande d ex cution de la premi re partie de la s quence 3 Les messages de transfert de valeur d une variable tild e Remarquons que selon le type de syst me consid r il pourrait tre n cessaire d effectuer une synchronisation d horloge entre certains ou tous les sites composant le syst me Une synchronisation implique un certain nombre de messages chang s entre ces sites Nous ne consid rerons pas ces messages 3 2 Les fonctions de conception des messages chaque type de message est associ e une fonction pr d finie de conception et d envoi du message Ces fonctions sont d finies dans la librairie dsl vm h cf Annexe D chaque fois qu un message est n cessaire une instruction d appel la fonction correspondante est g n r e dans le code du programme cible Selon le type du message celui ci contiendra diff rents param tres Les formats de chacun des messages sont repris en Annexe F Dans le cas d une demande d ex cution d une m thode le message devra contenir l identificateur de
114. et sorties Les d finitions des m thodes Les d finitions des s quences Les d finitions des v nements Une initialisation ventuelle OB WN H 15 9 3 Les types de base des variables Il existe trois types de bases en dSL Les entiers correspondant au mot syntaxique INT La valeur maximale d un entier ne peut pas exc der 21 1 Les bool ens correspondant au mot syntaxique BOOL de valeur FALSE 0 ou TRUE 1 Les entiers de type long correspondant au mot syntaxique LONG La valeur maximale d un entier de type long est 2 1 Ils peuvent tre par exemple utilis s pour les temps Aucun m canisme de conversion automatique n est disponible en dSL En d autres termes pour effectuer par exemple une assignation avec deux variables de type diff rents il est n cessaire d utiliser des primitives de conversion du style x LONG TO INT y qui convertit l entier de type long y en entier Ces primitives sont reprises dans la figure 2 5 Primitives Type du param tre Type du r sultat LONG TO INT long entier LONG TO BOOL long bool en BOOL TO LONG bool en long BOOL TO INT bool en entier INT TO LONG entier long INT TO BOOL entier bool en Figure 2 5 Ensemble des primitives de conversion 9 4 Les types tendus Il est possible de d finir des vecteurs au moyen de la syntaxe suivante ARRAY nombre 1 nombre 2 OF type ou nombre 1 et nombre 2
115. eurs Actions gt Plus grand que gt Plus grand ou gal lt Plus petit que lt Plus petit ou gal Egal a lt gt Pas gal Figure 2 8 Op rateurs relationnels dSL d Op rateurs logiques Les op rateurs logiques sp cifient la mani re dont les relations entre les variables peuvent tre associ es Les deux op rateurs principaux disposition en dSL sont le AND et logique et le OR ou logique dSL fournit aussi l op rateur NOT qui inverse la valeur d une expression logique Il n y a pas de OR exclusif traditionnellement XOR mais celui ci peut tre valu par une combinaison des trois op rateurs relationnels existants selon la forme suivante operateur 1 OR operateur 2 AND NOT operateur 1 AND operateur 2 Les priorit s des op rateurs logiques et relationnels sont reprises dans la figure 2 9 Plus haute priorit NOT gt gt lt lt AND Plus basse priorit OR Figure 2 9 Priorit s des op rateurs logiques et relationnels dSL e Op rateur L op rateur point est utilis pour r f rencer un l ment individuel d une structure de classe Il s utilise l int rieur d une structure c est dire dans une m thode de la classe ou un WHEN IN pour r f rencer un objet interne la classe savoir une de ses variables L usage de self permet de r f rencer l instance courante de la classe cf 8 71 Les m thodes et 8 1
116. exemples de m thode d une classe voiture 29 CLASS voiture END CLASS GLOBAL_VAR vl voiture ND_VAR E METHOD voiture self vitesse END METHOD METHOD voiture self vitesse END METHOD vitesse INT marche BOOL accelerer ajout INT self vitesse ajout freiner 0 Figure 2 23 Exemple de d claration de classe La figure 2 24 pr sente diff rents exemples d appels de ces m thodes cf 9 70 e Les instructions de lancement Le premier met v1 vitesse 0 Le deuxi me lui ajoute 2 Les deux derniers montrent comment il est possible d utiliser des variables dans les param tres d un appel une m thode Le troisi me exemple pr sente un appel de fonction synchrone plus sera mis 0 une fois que la m thode sera termin e Par contre le quatri me exemple pr sente un appel asynchrone L ex cution va se poursuivre sans attendre la fin de la m thode pilus INT Tus 2 25 plus Sec 0 LAUNCH vi freiner LAUNCH vl lt accelerer 2 p vl lt accelerer plus plus 0 plus 2 LAUNCH vl lt accelerer plus Figure 2 24 Exemples d appels de m thodes Il est possible de d finir un ensemble de variables locales une m thode La figure 2 25 pr sente un exemple de m thodes deux param tres qui d finit localement une variable temporaire Remarquons qu il n y a pas de retour d
117. fine ERR BUFFER EMPTY 4 define ERR BUFFER OVERLOAD 5 defin ERR OUT OF MEMORY 6 defin ERR STACK EMPTY 7 defin ERR UNKNOWN SEO ID 8 defin ERR WRITE FAIL 9 define ERR UNKNOWN MSG ID 10 define ERR BUFFER OVERLOAD2 11 define DS ALL ACTIVE sensors activation define tru T define false 0 define BOOL unsigned char define INT short define DINT short define ULINT time t defin SIZE MAX 8 define ab write ab awrite 118 define init AB protocol a init ab protocol portHandler ID SITE 4 4 4 define INT TO CHAR s i s char amp i s 1 char amp i 1 define CHAR TO INT i s char amp i s char amp 1 1 s 1 define ADD INT TO CHAR s i s char amp i s char amp 1 1 define READ INT FROM CHAR i s char amp i s char amp 1 1 s define READ DINT FROM CHAR i s READ INT FROM CHAR i s define READ ULINT FROM CHAR i s READ INT FROM CHAR i s define READ BOOL FROM CHAR i s READ INT FROM CHAR i s bool 1 or O pid t getID int s char dsl vm buf SIZE MAX pid t dsl vm stack SIZE MAX Gl int POS BUF 0 ST BUF 0 int POS STACK SIZE STACK ST STACK int dsl vm id char dsl vm args time t builtin cms BOOL time setup unsigned int id send message 0 sem t sem port handler sem SIZE BUF pid t cu
118. g Y emr T A expr Ezpri If A m e if expr then S end if S2 s gt lt Sa s gt if s y Processing Msg V i ezpr L A expr Ezpri If lt if expr then S end if S s gt 7 lt if s y Processing expr Expr j i e 5 s M j M U if expr then S end if SH Since process i can t evaluate the expression the sequence is sent over to the process that can evaluate it i fn esr While lt while expr do S end while s gt T if s y Processing Msg expr Expri SSeS lt if expr then S while expr do S end while S2 s gt While lt while expr do S end while S2 s gt lt e s gt if s y Processing expr Expr j i e s s M 4 M U while expr do S end while S2 Since process i can t evaluate the expression the sequence is sent over to the process that can evaluate it Wait lt wait expr Sall gt gt 35 gt 4 lt gt gt S2 s gt if s y Processing V i ezpr T A expr Ezpr Wait T lt wait expr 2 s l 8 gt if s i Processing V i ezpr L expr Ezpr e s s S S U wait expr S2 113 Wait i q a urr lt wait expr S2 gt gt 38 gt lt l E gt gt gt 38 gt if s y
119. globales est la liste des variables assign es ce site Pour chaque variable globale du site il faut d finir sa sorte et ses param tres Les variables globales peuvent tre de trois sortes interne au programme li e a une entr e INPUT ou li e a une sortie OUTPUT Les param tres d une variable globale d entr e ou de sortie consistent en trois nombres entiers rack card slot permettant de sp cifier le type particulier de senseur d entr e ou de sortie auquel correspond la variable et l emplacement du dispositif Le nombre et les intitul s des param tres sont issus des possibilit s offertes par les CP pour les dispositifs d entr e sortie cf 7 Introduction au langage SL et ont t conserv s tels quels La d claration d une variable globale d entr e ou de sortie identifi e par id variable est donc d finie comme suit sorte id variable NOMBRE NOMBRE NOMBRE Les variables internes d un programme ne n cessitent pas de sp cifier leur site de distribution Celle ci est d termin e par le distributeur en fonction de la localisation des instructions Il va de soit que les variables d entr e ne pourront en aucun cas tre assign es En d autres termes elles ne seront jamais le membre de gauche d une assignation 9 8 Les op rateurs et les s parateurs I existe diff rents types d op rateurs en dSL les op rateurs d assignation arithm tiques relationnels et logiques
120. http legos souceforge net Trois fichiers de librairies de m thodes pr d finies seront attach s au code g n r Il s agit du fichier des m thodes n cessaires pour la mise en ceuvre des syst mes g n r s dsl vm h et des fichiers du protocole de communication fiable ab c et ab h Le code de ces librairies est disponible respectivement en Annexes D et E Remarquons que le compilateur g n rera deux fichiers c et h par site contenant entre autres l ensemble des d clarations des variables et des instructions assign es statiquement ce site 49 el Figure 4 1 Chemin de compilation 2 La structure du compilateur Un compilateur est un programme charg de traduire un programme source en un programme cible quivalent Dans le cas pr sent le langage d origine est dSL le langage cible est C Le compilateur est constitu de trois parties la partie frontale ou frontend le distributeur et la partie finale ou backend Le frontend r alise tout ce qui est analyse du code du programme source le distributeur distribue celui ci sur les diff rents sites et le backend g n re le code cible des sites 2 1 Le frontend L analyse d un programme consiste identifier tous ses constituants lexicaux mots cl s op rateurs nombres identificateurs de variable de m thode etc et en cr er une repr sentation interm diaire sous forme de blocs de base et de graphe de flot de contr le Un bloc de base est u
121. indique si l ascenceur est en cours d utilisation ou non 92 4 3 Les chariots mobiles CLASS moving cart motor INT touch one INT touch two INT position BOOL TRUE one FALSE two state BOOL TRUE running FALSE stopped free BOOL ND CLASS tj ETHOD moving cart go in one IF self touch one 0 THEN self state FALSE self rotor stop self motor 30 END IF END METHOD ETHOD moving cart go in two IF self touch two 0 THEN self state FALSE self rotor motor 0 self motor 30 END IF END METHOD ETHOD moving cart stop self motor 0 self state TRUE END METHOD HEN IN moving cart self touch one gt 0 THEN self position TRUE self stop END WHEN WHEN IN moving cart self touch two 0 THEN self position FALSE self stop END WHEN Figure 6 7 Code dSL de la classe moving cart Chaque chariot mobile est compos d un moteur de deux capteurs un pour chaque position du chariot et d un tapis roulant Un chariot poss de aussi deux variables indiquant son tat et sa position Les m thodes de base consistent amener le chariot en position 1 go in one ou 2 go in two ou l arr ter Les r gles de base sont que lorsque le chariot arrive dans une position ou dans l autre il s arr
122. ines de caract res En ce qui concerne la m moire d une t che nous utiliserons la moiti de la variable legOS DEFAULT STACK SIZE qui quivaut 512 bytes La figure 5 1 reprend la m thode qui permet de cr er une tache Cette m thode renvoie le pid de la tache cr e c est dire son identificateur au sein du syst me d exploitation Il s agit en r alit du pointeur vers le stack de la tache Pour toutes les taches cr es cet identificateur sera conserv dans une variable particuli re Nous verrons pourquoi au paragraphe 3 3 le traitement des messages pid t execi fonction argc argv priorit taille du stack Figure 5 1 Fonction de cr ation d une tache LegOS 54 Nous avons pr c demment intoduit le concept d automate et plus pr cis ment la boucle nput Process Output cf 11 1 Introduction au langage SL Cette boucle doit tre ex cut e en permanence par chaque site Elle fera donc l objet d une tache permanente sur chaque site La partie Process concerne la gestion des v nements et des messages Lors du traitement des messages elle sera parfois amen e suspendre son ex cution pour ex cuter des m thodes ou des s quences distribu es sur son site Les s quences seront traduites par des taches suppl mentaires puisqu il faut conserver son contexte local En effet lorsqu une s quence dont les instructions sont distribu es sur plusieurs sites est ex cut e le contr le va devoir migrer de
123. k one et ask two permettent donc de limiter le nombre de conditions valu es aux quatre v nements mentionn s dans la figure 6 8 Les conditions des v nements de lancement des s quences sont donc d finies sur les valeurs ask one et ask two mais aussi Sur c 1 free l tat du chariot mobile Lorsqu une brique est pr sente sur un tapis d entr e et que le chariot est disponible la s quence de traitement correspondante est lanc e Pendant l ex cution de la s quence les briques arrivant sur les tapis d entr e sont mises en attente Il est donc possible qu une brique se trouve sur chacun des tapis lors de la lib ration du chariot Il a donc fallu pr voir un m canisme de d cision de la brique traiter dans ce cas Pour cela nous avons utilis une variable 1ast in qui stocke la derni re d cision prise La brique trait e est celle situ e sur le tapis qui n avait pas t trait pr c demment Nous obtenons donc les trois v nements de la figure 6 9 WHEN ask one TRUE AND ask two FALSE AND c_1 free TRUE THEN c l free FALSE take control of the moving cart LAUNCH t1 to t3 last in TRUE END WHEN WHEN ask one FALSE AND ask two TRUE AND c_1 free TRUE THEN c l free FALSE take control of the moving cart LAUNCH t2 to t3 last in FALSE END WHEN T WHEN ask one TRUE AND ask two TRUE AND c_
124. l id2 type Une variable peut tre globale au programme elle pourra tre utilis e n importe o dans le programme ou locale un certain v nement m thode ou s quence elle ne pourra tre utilis e qu l int rieur du code de l v nement de la m thode ou de la s quence L endroit de la d claration d une variable d finit sa visibilit Les variables globales sont d finies au d but du programme cf 9 2 La structure du programme Les d clarations de celles ci sont d finies grace la syntaxe GLOBAL VAR liste d clarations END VAR o iste d clarations est une suite de d claration de variables Les variables locales sont d finies au d but du code d un v nement d une m thode ou d une s quence au moyen de la syntaxe suivante LOCAL VAR liste d clarations END VAR Il n est pas possible de d finir des variables ailleurs qu en d but de programme d v nement de m thode ou de s quence 9 7 Les sites et les entr es sorties Un programme dSL contient la d finition des sites sur lesquels il sera distribu Leur nombre ainsi que la distribution des variables globales sur les diff rents sites composant le syst me sont d finis par le programmeur dans le programme dSL La d finition d un site est effectu e gr ce SITE nom site id site liste variables globales END SITE 17 o id site est l identificateur du site et liste variales
125. l ex cution d une partie de tache est termin e la partie n cessaire du contexte de la t che est transf r e sur le site de la partie de code suivante le contexte est restaur et la premi re instruction de celle ci est ex cut e La distribution statique permet donc de simplifier la gestion du code aucun code n est dupliqu ou transf r de limiter au maximum les messages chang s entre les sites seules les valeurs n cessaires sont transf r es et en outre de connaitre la charge exacte de chaque site Les communications inter sites sont donc d finies la compilation de mani re statique automatique et transparente en fonction de la r partition des variables globales Nous verrons plus loin comment la r partition est fournie par le programmeur du syst me dans le code du programme dSL 5 Event driven Comme son pr d cesseur dSL est un langage event driven utilis pour mod liser des syst mes n cessitant une r action imm diate un v nement et son traitement instantan Le contr le de processus industriel recquiert en effet ce type de comportement C est le principe de causalit action r action d finissant les syst mes r actifs d crits dans le chapitre 7 Introduction La conception 12 d un syst me en dSL passe donc par la d finition des v nements auxquels le syst me devra r agir Lorsqu un v nement se produit en l occurence ici lorsqu une condition bool enne d finie sur des variables g
126. la m thode ainsi que les valeurs des param tres de celle ci L ordre de ces param tres est fix par la d finition de la m thode dans le programme dSL Il n est donc pas n cessaire de transmettre les identificateurs des variables pass es dans le message La syntaxe de la fonction de cr ation et d envoi du message est reprise dans la figure 5 7 o id est l identificateur de la m thode site est l identificateur du site de distribution de la m thode c est dire la destination du message et n para contient le nombre de param tres transmettre la m thode Ces param tres sont transmis sous forme d une liste d arguments de longueur variable va list Une va list est un type C qui va repr senter chaque argument pass une fonction tour de r le En r sum il faudra acc der n para fois une variable de ce type pour acc der aux H para param tres transmis la place des dans la d finition de la fonction void LAUNCH ID COLOR int site int id int n para Figure 5 7 Fonction d envoi d une demande d ex cution d une m thode 58 Dans le cas d une demande d ex cution d une partie de s quence le message doit contenir l identificateur de la s quence l identificateur de la partie et les valeurs des param tres de la s quence ou des variables actives du contexte cf 2 2 Le distributeur Il sera n cessaire de transmettre les identificateurs des variables pass es dans le message Nous revi
127. la s quence traitement message consiste en l extraction des informations du message savoir la partie de s quence ex cuter et la valeur des param tres ou des variables actives 66 void graph_id label 1 code de la premi re partie de la s quence label 2 code de migration goto dispatch label 3 code de la troisi me partie de la s quence dispatch attente message re u traitement message goto label message i Figure 5 14 Pseudo code d une tache de s quence Le m canisme goto n tant pas disponibe sous legOS nous l avons mis en oeuvre par l utilisation d une boucle infinie contenant un switch sur l identificateur de la partie de s quence ex cuter La traduction en code C de la figure 5 14 est reprise la figure 5 15 void graph_id D claration des param tres D claration des variables locales int nextBasicBlock HOP_WAIT_ID while true switch nextBasicBlock case label 1 code de la premi re partie de s quence HOP id_site id label 2 nextBasicBlock HOP WAIT ID break case label 3 code de la troisi me partie de s quence nextBasicBlock HOP WAIT ID break case HOP WAIT ID startwait mise jour de nextBasicBlock extraction des param tres break case default error ERR UNKNOWN HOP ID halt 3 Figure 5 15 Code d une tache de s quence Deux case suppl mentaires sont ajout s par s quence case default
128. le code de la figure 2 3 avec les variables x et y situ es sur des sites diff rents La contrainte atomique emp che de distribuer ce code La figure 2 4 pr sente les deux possibilit s offertes au programmeur pour relacher cette contrainte La premi re requiert la d finition d une m thode ou d une s quence ex cutant le traitement de l v nement en l occurence ici y 0 et qui sera distribu e sur le site de y Le WHEN sera trait sur le site de x et enverra un ordre d ex cution au site de distribution de la m thode ou de la s quence celui de y La deuxi me permet de distribuer le WHEN sur le site de d finition de y A chaque fois que x sera assign e un message sera envoy au site de y pour signaler le changement de valeur La condition sera v rifi e d s le traitement du message En pratique lorsqu une variable est assign e les WHEN portant sur cette variable sont examin s WHEN x 0 THEN LAUNCH y egal O 1 END WHEN WHEN x gt 0 THEN y 0 2 END WHEN Figure 2 4 Relachement de la contrainte atomique 7 Avantages de dSL Le langage dSL offre plusieurs avantages par rapport son anc tre SL notamment Tout d abord les programmes dSL font preuve de flexibilit Une modification d un dispositif d entr e ou de sortie c est dire essentiellement la modification de l emplacement d un senseur ne n cessite priori aucun changement dans le code du
129. lobales du syst me passe de l tat faux ou inconnue cf 9 La syntaxe de dSL l tat vrai la s quence d instructions associ e l v nement est ex cut e 6 Code atomique et s quentiel Le paradigme utilis dans le monde des syst mes industriels recquiert une r action imm diate aux v nements et leurs traitements instantan s Le design de dSL est dict par ce paradigme Cela implique qu en pratique il n y ait aucune synchronisation qui pourrait retarder l ex cution Une distinction entre deux types de code est effectu e dans le cas de programmes crits en dSL D une part le code atomique ou event driven ex cut de facon atomique et non distribu D autre part le code non atomique ou s quentiel qui peut tre distribu entre les diff rents sites Les instructions s quentielles d un programme dSL peuvent tre d coup es en partitions r parties sur diff rents sites Par d faut le code des v nements c est dire les instructions d une construction WHEN et celui des m thodes est consid r comme atomique et doit donc tre conserv sur un m me site Toutes les variables apparaissant dans la condition ou dans le traitement de l v nement doivent donc obligatoirement tre situ es sur le m me site La figure 2 3 montre un exemple de WHEN ot les variables x et y doivent tre r parties sur le m me site VHEN x gt 0 THEN END WHEN Figure 2 3 Exemple de WHEN Ce
130. ls de m thodes Exemple de m thode deux param tres avec variables locales Programme dSL avec exemples de m thodes Exemple de m thode incorrecte et de sa correction Exemples de m thode non atomique Exemple de s quence dSL Exemple de s quence dSL deux param tres Exemple de d clarations d v nements Exemple de WHEN IN Legos Mindstorms La brique RCX source http www legomug gr jp images etc rcx gif La brique RCX et ses accessoires 104 Figure 3 3 Figure 3 4 Figure 3 5 Figure 3 6 Communications RCX PC source http www robotbooks com LEGO_MINDSTORMS IR jpg Format des messages Inp La compilation vers LegOS L architecture d une brique RCX sous LegOS Chapitre 4 Compilation et distribution Figure 4 1 Chemin de compilation Figure 4 2 Exemple de graphe de contr le de flot d un if imbriqu dans un while Figure 4 3 Graphe de contr le de flot de la figure 4 2 apr s optimisation Figure 4 4 Formules de In B et Out B Chapitre 5 G n ration automatique du code LegOS pour Lego Mindstorms Figure 5 1 Figure 5 2 Figure 5 3 Figure 5 4 Figure 5 5 Figure 5 6 Figure 5 7 Figure 5 8 Figure 5 9 Figure 5 10 Figure 5 11 Figure 5 12 Figure 5 13 Figure 5 14 Figure 5 15 Figure 5 16 Figure 5 17 Figure 5 18 Figure 5 19 Figure 5 20 Figure 5 21 Figure 5 22 Figure 5 23 Figure 5 24 Figure 5 25 Figu
131. n between the expressions of a gSL program that satisfies the locality and access constraints resulting from the symmetric reflerive and transitive closure of Re where ezpriR erpro Var expri N Var expra 9 V AW W2 expri Ezpr Wi Aezpre Expr W2 A Wi We V 3instr Var expri U Var expra C Var instr Definition 6 Let 1 N be the indices of the equivalence classes defined by and let i 1 N Expr denote these classes Definition 7 Let IV ar be the input variables in Var Expr Definition 8 Let OVari be the output variables in Var Ezpri 110 2 State In this section we define the state that is used in structural operational semantics of a qSL program based on the equivalence classes defined in the previous section A state is a 6 tuple e Y Var x 1 N T L a valuation for a given process of the global variables inputs and outputs e F 1 N x 1 N o E where E Varx T 1 Ust list The fifo channels that interconnect the different processes containing either variables and their values or statements to be executed e S 1 N 2 list the bodies of sequences that are sleeping in a given process e A 1 N o 2 the bodies of sequences that are active awaiting execution in a given process e M 1 N 2 list the bodies of sequences that are being transferred to a certain process ey 1 N Input Msg Process Output the phase of each p
132. n particulier le langage de programmation ainsi que le protocole de communication utilis s y sont d crits Le chapitre IV explique les adaptations effectu es au compilateur dSL existant et d crit en d tails la g n ration de code vers le langage de destination choisi Le chapitre V pr sente une tude de cas comportant la construction et l impl mentation dSL de l application ainsi qu une valuation de la solution Les annexes reprennent un ensemble de documentations de supports techniques et autres qui sont en lien direct avec ce travail Chapitre II Le Langage dSL Dans ce chapitre nous d crirons bri vement ce qu est le Supervision Language ses inconv nients et les concepts de son successeur le distributed Supervisor Language Nous d taillerons les probl mes li s la distribution de code et la notion de code atomique et s quentiel Nous terminerons par la d finition formelle de la syntaxe et de la s mantique de dSL 1 Introduction au langage SL Nous donnerons ici un apercu du Supervision Language SL ses concepts et ses possibilit s ainsi qu une br ve introduction de sa syntaxe SL est un langage imp ratif simple bas sur le langage ST de la norme industrielle IEC1131 3 Il est le pr dec sseur du langage dSL Il a t d velopp par la soci t Macq electronique pour mod liser des syst mes industriels distribu s et organis s selon le sch ma de la figure 2 1 en distinguant trois entit s les
133. nce Au paragraphe Les taches nous avons vu que pour des raisons de simplicit de gestion du contexte local une s quence est traduite par une tache continue Pour toute s quence une t che est cr e d s l initialisation du syst me sur chaque site sur lequel au moins une de ses parties est distribu e La fonction contenant le code de la tache est identifi e de la m me mani re que les m thodes c est dire par void graph_id ou id est l identificateur de la s quence Cette fonction ne prend jamais de param tre L identificateur de la t che cr e est stock dans une variable globale thread da dont l utilit sera expliqu e plus loin Le code de la t che contient 1 la d claration des param tres et des variables locales de la s quence et 2 le code de toutes les parties de la s quence distribu es sur le site La tache se met en attente de la r ception d un message de demande d ex cution d une partie de la s quence Une fois r veill e elle ex cute la partie de s quence demand e Le pseudo code de la figure 5 14 exprime le comportement d une tache de s quence d coup e en trois blocs de base dont le deuxi me est distribu sur un autre site code de migration correspond la demande d ex cution de la deuxi me partie de la s quence avec le transfert des ventuelles variables actives attente message requ correspond l attente de r ception d un message de demande d ex cution d une partie de
134. ndition THEN liste instructions 1 END IF est traduite par l instruction conditionnelle C if condition liste instructions 1 CY En ce qui concerne les instructions conditionnelles utilis es dans une s quence la g n ration de code est un peu plus complexe car elle conserve la structure en blocs de base Elle est expliqu e dans le paragraphe 7 2 Les s quences 9 5 Les instructions d it ration Une instruction d it ration dSL utilis e en dehors d une s quence WHILE condition DO liste instructions END WHILE est traduite par l instruction d it ration C while condition liste instructions C 1 o liste instructions C est la traduction C de liste instructions En ce qui concerne les instructions d it ration utilis es dans une s quence la g n ration de code conserve la structure en blocs de base Elle est expliqu e dans le paragraphe 72 Les s quences 9 4 Les instructions d attente Une instruction d attente n a pas d quivalent en C Il faut donc g n rer du code C de comportement quivalent celle d une instruction d attente Lors de l ex cution d une instruction d attente la s quence est mise en attente jusqu ce que la condition soit vraie Une s quence quivaut a une tache La condition est test e par la tache de la s quence puisque elle peut contenir des variables locales Si la condition est fausse la tache s endort A cha
135. ne suite d instructions cons cutives telle que le contr le rentre en son d but et ne peut tre ni arr t ni en sortir avant la fin de celui ci c est dire avant d avoir ex cut la derni re de ses instructions Un bloc de base est constitu soit d une suite d instructions d assignation soit d un saut vers un autre bloc de base conditionnel ou inconditionnel avec ou sans param tre soit un appel vers un autre graphe Un graphe de flot de contr le ou control flow graph repr sente la structure du programme 50 c est dire les relations entre les blocs de base constituant ce programme II s agit d un graphe orient avec ventuellement des cycles Les noeuds sont les blocs de base Un arc orient joint un bloc de base a un autre si lors de l ex cution du programme le contr le peut passer de la derni re instruction du premier bloc de base a la premi re instruction du deuxi me Remarquons que parfois certains blocs de base interm diaires vides sont ajout s par le parser C est le cas par exemple dans le graphe de flot de contr le d une instruction conditionnelle IF La figure 4 2 reprend un graphe de flot de contr le repr sentant un IF imbriqu dans un WHILE Tant que la condition du WHILE sera vraie le contr le passera par les blocs de base de gauche c est dire ceux du IF Si la condition du IF est vraie le contr le va passer par le ou les blocs de base de gauche sinon ceux de droite Lorsque la condition du WHIL
136. nombre param tres param tres o id est l identificateur de la m thode site son site de distribution nombre param tres le nombre de param tres transmettre et param tres la liste des param tres Lorsqu un message d appel d une m thode est recu args est extrait du message par handleMsg et transmis la fonction handleExec int id unsigned char args Cette derni re est charg e d appeler 65 la fonction graph id args ou graph id suivant que la m thode poss de ou non des param tres L extraction des param tres est effectu e dans le code de la m thode apr s la d claration des param tres et des variables locales Le code de handleExec id args est d fini la compilation Il est g n r dans le fichier c du site sous la forme d un switch sur l identificateur de la m thode Pour chaque m thode d un site un case est g n r selon le format case id m thode graph id m thode param break o id m thode est l identificateur de la m thode et param est si la m thode n a pas de param tre args sinon 12 Les s quences Le code d une s quence est d coup par le compilateur en plusieurs blocs de base distribu s sur plusieurs sites et reli s par des points de migration Ces derniers correspondent des messages de demande d ex cution d une partie de s quence qui contiennent les valeurs des variables actives mettre jour dans le contexte local de la s que
137. ommunications n cessaires transfert de valeur ex cution de m thode etc En outre tout ce qui concerne la mise en ceuvre de t ches est g r e par le compilateur La simplicit d impl mentation est manifeste si on compare le nombre d instructions produire pour programmer un syst me Dans tous les exemples que nous avons impl ment au cours du d veloppement du compilateur nous avons pu constater en g n ral une diminution du nombre d instructions entre le programme dSL et le code LegOS quivalent En ce qui concerne l tude de cas si nous comparons la taille du fichier dSL environ 400 lignes avec une estimation du nombre d instructions qui auraient t n cessaires pour impl menter le syst me directement en C pour LegOS entre 200 et 400 lignes suivant le site pour 2000 lignes au total nous pouvons estimer le gain environ 75 De plus en cas par exemple de changement de position d un capteur les modifications apporter au programme dSL sont minimes Pour finir les principales constructions LegOS sont impl mentables en dSL Par exemple la notion d v nement LegOS est facilement impl mentable sous forme de WHEN ou de WAIT Bien entendu l utilisation de dSL pour impl menter un syst me LegOS a des d savantages Le premier est la non modularit de dSL Le respect de la contrainte atomique impose parfois quelques difficult s de programmation De plus l ensemble des instructions disponibles en dSL ne recouvrent
138. on un v nement issu de l environnement un traitement est ex cut Un v nement est sp cifi par le changement de valeur d une condition bool enne portant sur une ou plusieurs variables globales Son traitement est d fini par une suite d instructions de base de lancement de m thode ou de s quence Par exemple WHEN x 0 then run motor d clenchera l ex cution de la m thode run motor chaque fois que la valeur de x passe d une valeur positive nulle ou inconnue cf 6 5 La valeur UNKNOWN une valeur n gative Le code des m thodes et des s quences est d fini ailleurs dans le programme La syntaxe compl te du langage dSL est reprise l Annexe A 9 1 Les identificateurs En dSL il est possible de d finir des variables des m thodes des s quences et des v nements Chacune de ces entit s doit avoir un nom son identificateur pour tre univoquement d sign e l int rieur du programme Les identificateurs sont r gis par les r gles usuelles savoir qu ils peuvent tre compos s de une ou plusieurs lettres sans accentuation particuli re ou chiffres mais que le premier symbole doit tre une lettre ou le caract re Tous les caract res d un identificateur sont significatifs id lettre _ lettre chiffre 9 2 La structure du programme Un programme dSL est constitu de cing l ments Les d clarations des variables globales et notamment des entr es
139. oniquement la deuxi me et la quatri me appelle acc l rer asynchroniquement avec comme param tre 2 et plus La troisi me est un appel synchrone avancer dsl vm arg est un vecteur de caract re d fini globalement dans dsl vm h Il n est utilis que pour les appels synchrones La fonction ADD TO CHAR unsigned char int est une macro d finie dans dsl vm h LAUNCH ID COLOR 1 5 0 LAUNCH ID COLOR 1 4 1 2 ADD TO CHAR dsl vm arg plus graph 5 dsl vm arg LAUNCH ID COLOR 1 4 1 plus Figure 5 30 Exemples d appels de m thodes g n r s 14 8 La gestion des variables tild es La figure 5 31 reprend un exemple de g n ration de code d une fonction handleWarn id val pour un site utilisant deux variables tild es x et y respectivement d identificateur 25 et 26 void handleWarn int id int val switch id case 25 x val break case 26 y val break case default error ERR UNKNOWN WARN ID halt Figure 5 31 Exemple de g n ration de code pour une fonction handleWarn 14 9 Les s quences Un exemple de s quence distribu e sur trois sites est pr sent dans la figure 2 29 Les figures 5 32 5 33 et 5 34 reprennent le code g n r correspondant a cette s quence respectivement pour le site 1 2 et 3 Remarquons la g n ration de code pour une instruction conditionnelle dans une s quence 74 Une analyse de variables actives perme
140. op rateurs arithm tiques relationnels et logiques sont traduits par le m me mot cl En ce qui concerne l op rateur de lancement il n cessite un traitement particulier d taill aux paragraphes 71 Les m thodes et 12 Les s quences 9 Les instructions 9 1 Les instructions d assignation Une instruction d assignation dSL nom variable expression est traduite par l instruction C nom variable expression C 5 ou expression C est la traduction C de expression Lorsqu une assignation est effectu e sur une variable tild e le compilateur doit g n rer le code de l envoi de la nouvelle valeur de la variable aux sites sur lesquels cette variable est utilis e cf 10 La gestion des tildes Lorsqu une assignation est effectu e sur une variable apparaissant dans au moins une condition d un v nement du site un appel la fonction handleWhen est g n r cf 13 Les v nements 9 2 Les instructions conditionnelles Une instruction conditionnelle dSL utilis e en dehors d une s quence IF condition THEN liste instructions 1 ELSE liste instructions 2 END IF est traduite par l instruction conditionnelle C if condition liste instructions 1 C else liste instructions 2 CY o liste instructions x C est la traduction C de liste instructions x 62 De m me une instruction conditionnelle dSL en dehors d une s quence IF co
141. our modifier cette valeur il ne suffit que d une modification dans le code En cas de define le pr processeur traduit automatiquement les TRESHOLD en la valeur d finie en d but de code Pour rappel un v nement dSL est d fini par une condition et par une suite d instructions de traitement Cette construction est soumise la contrainte atomique Deux m canismes permettent de contourner cette contrainte les tildes et les LAUNCH Une certaine dualit existe entre ces deux m canismes Il a t prouv dans DMM03 2 que toute instruction LAUNCH et que toute s quence peuvent tre traduites de mani re quivalente en un code n utilisant que des WHEN et des tildes Cela dit en pratique il est pr f rable de n utiliser un tilde uniquement si la valeur de la variable est utilis e dans l valuation d une expression telle que celle d une assignation Nous aurions pu par exemple tilder la valeur d un capteur de lumi re dans l expression d une condition d un v nement distribu e sur le site du chariot mobile par exemple chaque fois que ce capteur va relever une valeur diff rente de la pr c dente un message sera envoy En pratique c est souvent le cas cause de l extr me sensibilit des capteurs de lumi re M me si rien ne passe devant eux ils rel vent de petites variations de luminosit Dans le cas qui nous int resse ici il est donc pr f rable d utiliser des m canismes LAUNCH Un seul message est envoy d s
142. ous message sending this semaphore will be posted when the message is acknowledged sem t sem ack Linked list points to the next element struct mess NEXT MESS Nbrief Structure used to store other communicating sites EF typedef struct site The distant site s id 255 different ids supported unsigned char ID Send and reception bit used in the alternating bit protocol bitO send bitl recv unsigned char RSBIT Linked list of sites struct site NEXT Pending messages outgoing for this site struct mess LIST SITE if AB STATIC struct pool element brief A pool element points to a pre allocated chunk of memory Basic implementation uses a linked list of pool elements each of which can be free or taken Wi typedef struct pool element 126 The pre allocated memory zone void coni The next zone struct pool element next Indicates if this chunk is free or not char free pool el brief A pool is a set of pre allocated chunks of memory Basic implementation uses a pointer to the first allocated chunk of memory and a semaphore that indicated the number of free elements Ay typedef struct Semaphore indicates the number of free elements sem t size The first element pool el head pool ndif Naddtogroup ab interface
143. pas non plus que les syst mes impl ment s sont critiques Dans le cas d une usine de traitement de produits chimiques il est ais d imaginer que la perte d un message de demande d ex cution d une proc dure d vacuation est inconcevable 15 1 Fonctionnement A notre connaissance aucun protocole fiable n a t impl ment pour les Lego Mindstorms Nous avons donc pris la d cision d en impl menter un par nous m me Ce protocole est bas sur le protocole d alternating bit appel par la suite protocole ab Il est ad quat par rapport la typologie du r seau En effet le r seau infrarouge est sans m moire Les messages envoy s ne sont pas retard s Ils se propagent sans encombre dans le r seau Le protocole est fiable 100 En effet un message ne sera jamais consid r comme transmis alors qu il ne l a pas t Si maintenant un site n est pas en tat de recevoir un message liaison infrarouge impossible ou crash du site le message va tre continuellement renvoy Le protocole ab est tr s simple Il s agit en fait d un protocole fen tre glissante de taille 1 Pour un metteur et un r cepteur donn s il y a constamment un seul message en cours d envoi Le num ro identifiant le message alterne entre 0 et 1 Soit une station d envoi et une station de r ception chacune maintient un bit savoir respectivement un bit d envoi et de r ception qui permet d identifier la v racit du message Ces 79 bi
144. pl ment 1 Les taches En vue de g n rer du code ayant un comportement quivalent a celui du programme dSL source nous serons amen a g rer des taches et plus pr cis ment a les cr er les param trer les mettre en attente et les r veiller Dans la suite nous appelerons tache un bout de programme contenu en m moire et qui s ex cute sans perturber le fonctionnement des autres taches Outre le code de ses instructions elle poss de un contexte local c est a dire ses variables locales sous forme de pile et un program counter qui pr cise ot la tache en est dans son ex cution LegOS est un syst me multitache pr emptif dans lequel chaque tache poss de une priorit En fonction de ces priorit s le syst me d exploitation va donner le contr le a la ou les t ches les plus prioritaires A tout moment il peut reprendre le contr le une t che pour le donner a une nouvelle t che plus prioritaire par exemple La priorit d une t che est d finie lors de sa cr ation Il faut galement pr ciser les instructions que la tache ex cutera ses param tres et la taille de la m moire qui lui sera accord e pour stocker son contexte En legOS les priorit s vont de 1 20 Les instructions sont sp cifi es par l interm diaire d une fonction Le code de la fonction correspond aux instructions que la tache ex cutera Les param tres de la t che sont les param tres de cette fonction Ils sont pass s sous forme d un vecteur de cha
145. que assignation d une variable de la condition la tache est r veill e pour qu elle teste nouveau la condition et se rendort si elle est fausse Donc chaque fois qu une variable apparaissant dans la condition d une instruction d attente d une s quence est assign e il faut 1 tester si la s quence est en attente 2 et si oui passer le contr le la s quence en attente 1 Pour chaque s quence contenant au moins une instruction d attente une variable globale bool enne est d finie Elle indique si oui ou non la s quence est en train d attendre Ces variables sont appel es les variables d tat de s quences et sont g n r es selon la syntaxe bool is waitingid s quence o id s quence est l identificateur de la s quence Elles sont mises vrai avant le test de la condition et mises faux apr s le r veil de la s quence 63 2 Puisque le contr le est pass une s quence il doit tre rendu a la t che appelante Lorsqu une tache effectue une modification sur une variable d instruction d attente et passe le contr le une s quence en attente elle doit placer son identificateur de t che sur le stack de contr le cf 1 Les t ches L instruction d attente dSL WAIT condition est traduite par la suite d instructions C reprise la figure 5 13 o id sequence est l identificateur de la s quence is waitingid s quence TRUE WHILE condition startwait is
146. r e En effet ils utilisent chacun le tapis roulant mobile pour ramener les colis sur le tapis principal Lorsqu un colis se pr sente l extr mit d un des tapis d entr e celui ci s arr te et demande au tapis mobile de venir chercher le colis Le tapis se remet en route lorsqu il est s r que le tapis mobile est situ en face de lui et qu il peut donc lui transmettre son colis 2 3 Section critique de l ascenceur et du tapis de sortie L ascenceur est un l ment int ressant de la chaine de montage Le tapis inf rieur doit attendre sa disponibilit c est dire que l ascenceur soit en bas avant de faire avancer le colis l int rieur de celui ci Idem en ce qui concerne le tapis roulant mobile de la sortie 87 2 4 Communications inter site De par les disponibilit s limit es offertes par les briques Lego trois entr es et trois sorties chacune des briques sera charg e d un l ment particulier de la chaine de montage Un tr s grand nombre de messages de communication vont donc tre transmis entre ces briques pour la bonne mise en ceuvre du syst me L utilisation du protocole de communication fiable permet d tre certain de la fiabilit des messages Cela dit nous veillerons galement disposer les briques Lego d une mani re telle que celles qui devront s changer des messages ne soient pas a l oppos l une de l autre Si tel est le cas il est possible d introduire des miroirs dans la construction pour relaye
147. r les communications infrarouges 3 Mod lisation Lego Mindstorms du syst me En vue de r aliser le syst me en Lego Mindstorms un certain nombre de simplifications ont t apport es a l id e de base de la chaine de montage Celles ci r sident essentiellement dans la mod lisation des colis Ceux ci sont de simples briques Lego Aucune op ration sur les briques n est effectu e lors des tapes de construction du colis Un simple temps d arr t est marqu Par la suite nous allons d tailler la conception des diff rents l ments de la chaine de montage savoir le tapis roulant le tapis roulant mobile et l ascenceur En ce qui concerne les tapis ils sont constitu s d une chenille plac e sur deux roulements dont l un des deux est actionn par un moteur Un capteur de lumi re permet de savoir lorsqu un colis se trouve en fin de tapis L annexe F de ce texte expose la mani re dont ces tapis roulants ont t construits En ce qui concerne les tapis roulants mobiles ils consistent en un simple tapis roulant plac sur un chariot mobile L annexe H pr sente comment ce chariot mobile a t con u Il s agit d un chariot rotatif Le moteur du chariot va actionner un engrenage qui va permettre de le faire pivoter Des capteurs de toucher permettent de savoir lorsque le tapis est arriv une position correcte Nous avons simplifi la gestion du chariot mobile en pla ant le tapis principal face l un des deux tapis d entr e
148. r pouvoir r veiller la t che qui lui a transmis le contr le Le passage de contr le entre les t ches va se faire via un jeton de contr le En pratique ce jeton consiste en une variable globale current_thread_id contenant l identificateur de la t che autoris e s ex cuter c est dire la t che qui a obtenu ou qui doit obtenir le contr le Lorsqu une t che est mise en attente elle attend en fait que le jeton soit pour elle c est dire que la variable globale contienne son propre identificateur accessible gr ce au mot cl LegOS cpid La mise en attente d une t che est possible en LegOS par l interm diaire d un v nement appel par la suite v nement LegOS Cela consiste suspendre l ex cution d une t che dans l attente qu un certain v nement se produise La figure 5 3 pr cise la syntaxe de la d finition d un v nement LegOS o id est l identificateur de l v nement et param tres les param tres de l v nement Le code d un v nement est constitu d une suite d instructions avec ventuellement des d clarations de variables locales et se termine par une instruction de retour portant sur une expression bool enne Cette expression constitue la condition qui d finit l v nement En pratique le syst me d exploitation va r guli rement v rifier les conditions des v nements Si une t che est en attente sur une condition et que celle i devient vraie la t che change son status de sleeping
149. r un code utilisant des WHENS et des tildes cf DMM03 2 Pour plus de pr cisions se r f rer ce document ou la s mantique compl te de dSL l Annexe B 11 1 Notations utiles Tout d abord il est n cessaire de pr ciser les notations qui seront utilis es dans la suite Var D l ensemble des variables non tild es apparaissant dans le programme P Var P l ensemble des variables de Var P qui correspondent des variables d entr es Var P l ensemble des variables de Var P qui correspondent des variables de sorties Var P l ensemble des variables de Var P qui correspondent des variables internes Var w l ensemble des variables non tild es apparaissant dans le when w Var e l ensemble des variables tild es ou non apparaissant dans l expression e lt v P l op rateur de l ordre dans lequel les variables du programme P sont d clar es Cet ordre sera utilis pour d terminer l ordre dans lequel les variables d entr es et de sorties seront respectivement lues ou mises jour When D l ensemble des when apparaissant dans le programme P lt w P lop rateur de l ordre dans lequel les when d un programme P sont d clar s Cet ordre sera utilis pour d terminer l ordre dans lequel les WHEN seront ex cut s Cond w la condition du WHEN w Body w la liste d instructions du WHEN w OldCond W oldcond w e W avec oldcond l valuation pr c dente de Cond w
150. ration Cette derni re doit tre unique et ant rieure tout appel Dans le code de la m thode seules les variables locales la m thode y compris les param tres et les variables globales peuvent tre utilis es Il est possible de r f rencer les variables de l instance courante de la classe via self cf 8 8 e L op rateur De plus le code d une m thode doit respecter la contrainte atomique cf 6 Code atomique et s quentiel Signalons aussi qu en dSL les appels r cursifs ne sont pas permis pour des raisons de v rification du code cause du nombre d appels qui pourrait tre infini 9 12 Les s quences La forme g n rale d une s quence est SEQUENCE id s quence param tres liste instructions END SEQUENCE ou id sequence est l identificateur de la s quence autrement dit son nom param tres l ventuelle liste des param tres de la s quence et liste instructions une suite d instructions pr c d e ventuellement d un bloc de d claration des variables locales de la s quence cf 9 6 Les variables Dans le code de la s quence seules les variables locales la s quence y compris ses param tres et les variables globales peuvent tre utilis es 9 13 Les v nements La forme g n rale d une instruction d v nement est WHEN condition THEN liste instructions END WHEN ou condition est l expression logique d finissant l v nement et liste instr
151. re 2 Le Figure 2 1 Figure 2 2 Figure 2 3 Figure 2 4 Figure 2 5 Figure 2 6 Figure 2 7 Figure 2 8 Figure 2 0 Figure 2 10 Figure 2 11 Figure 2 12 Figure 2 13 Figure 2 14 Figure 2 15 Figure 2 16 Figure 2 17 Figure 2 18 Figure 2 19 Figure 2 20 Figure 2 21 Figure 2 22 Figure 2 23 Figure 2 24 Figure 2 25 Figure 2 26 Figure 2 27 Figure 2 28 Figure 2 29 Figure 2 30 Figure 2 31 Figure 2 32 Chapitre 3 Les Figure 3 1 Figure 3 2 Liste des illustrations langage dSL Architecture d un syst me SL Architecture d un syst me dSL Exemple de WHEN Rel chement de la contrainte atomique Ensemble des primitives de conversion Op rateurs arithm tiques dSL Priorit s des op rateurs arithm tiques dSL Op rateurs relationnels dSL Exemples d identificateurs corrects dSL Squelette d un programme dSL Exemple de d claration de variables globales Exemple de d claration de classe Exemple de d finition de sites Exemple de d finition de site avec une classe Exemples d expression arithm tiques et leurs r sultats Valeurs des variable utilis e dans la figure 2 17 Exemples d expressions bool ennes dSL Exemples d assignation dSL Exemple d assignations sur une classe Exemple d instructions conditionnelles dSL Exemple d instructions d it ration dSL Exemple d instructions d attente dSL Exemple de d claration de classe Exemples d appe
152. re 5 26 Figure 5 27 Figure 5 28 Figure 5 29 Figure 5 30 Figure 5 31 Figure 5 32 Figure 5 33 Figure 5 34 Figure 5 35 Fonction de cr ation d une tache LegOS Exemple de s quence distribu e Syntaxe d un v nement LegOS Syntaxe de m thode de mise en attente d une tache LegOS Fonctions C de mise en attente et de r veil de tache LegOS Fonction de la tache de la machine virtuelle Fonction d envoi d une demande d ex cution d une m thode Fonction d envoi d une demande d ex cution d une partie de s quence Fonction d envoi d un transfert de valeur d une variable tild e Correspondance entre les types dSL et C Correspondance entre param tres de variables dSL et p riph riques Lego Correspondance des directions des moteurs legOS Traduction d une instruction d attente Pseudo code d une tache de s quence Code d une t che de s quence Structure de la fonction getID Traduction d un instruction conditionnelle dans une s quence Traduction d une instruction d it ration dans une s quence Code d inspection d une codition Exemple de fonction d initialisation g n r e Exemples de d claration de variables globales Exemple de d clarations de variables globales g n r es Exemple de d claration d entr es sorties dSL Exemple de mise jour des dispositifs Exemples d instructions d assignation g n r es Exemple d instructions conditionnelles g n r es Exemple d ins
153. recte c est dire que le programme distribu de mani re transparente est conforme avec la s mantique du probl me original Le langage dSL est toujours en plein d veloppement Il peut donc tre raffin par l ajout de nouveaux types de donn es plus complexes comme les pointeurs et les structures de constructions suppl mentaires Programmation Orient Objet s maphores etc ainsi que par des librairies d automatisation qui r duiront la tache du programmeur Signalons aussi qu il reste quelques fonctionnalit s dSL qui ne sont pas encore prises en compte par le compilateur essentiellement tout ce qui concerne les vecteurs 101 Bibliographie ASU00 BGT00 Bau00 BGJ91 Ber98 BD91 CPHP87 Dew02 DMM03 A Aho R Sethi J Ullman Compilers Principles techniques and tools Ed Dunod 2000 D Baum M Gasperi R Hempel et L Villa Extreme Mindstorms An advanced guide to Lego Mindstorms Ed Apress 2000 D Baum Definitive Guide To Lego Mindstorms Ed Apress 2000 A Benveniste P Le Guernic et C Jacquemot Synchronous programming with events and relations the Signal Language and its semantics Dans Science of Computer Programming 16 2 103 149 Sept 1991 G rard Berry The Foundations of Esterel Dans Proof Language and Interaction Essays in Honour of Robin Milner G Plotkin C Stirling and M Tofte MIT Press 1998 Fr d ric Boussinot et Robert De Simone The Esterel
154. rhside lt gt rhside rhside rhside rhside MOD thside rhside 4 rhside rhside rhside rhside rhside rhside rhside NOT rhside rhside IS UNKNOWN rhside a Ihside TRUE FALSE NUMBER 108 call lhside lt LAUNCH Ihside lt LAUNCH ID rhside list rhside list rhside rhside list T Means 1 at least one T T Means T ore T is a literal Tis a terminal 109 Annexe B S mantique dSL 1 Equivalence relation Definition 1 Let Var e Expr 2 4 be the function that maps an expression to the variables appearing in that ezpression id e id _ J Var ei oS ee Var e Var ei UVar e e e1 Ver e 1 Nee ezT ezlezid Let Var E Uee EVar e Definition 2 Let Var instr Instr 2 be the function that maps an instruction to the variables that appear in the immediate constituents of that instruction id UVar erpr i id expr Var i 4 Var ezpr i while expr do st list end while Var ezpr i if expr then st_list end_if Let Var I UierVar i Definition 3 Let Ermi denote all expressions that appear in a given when W Definition 4 Let be the equivalence relation between the whens of a gSL program resulting from the symmetric reflerive and transitive closure of Rw where Wi R Ws amp Var Ezpr Wi N Var Erpr W2 9 Definition 5 Let be the equivalence relatio
155. rocess respectively sampling the inputs handling messages from other processes executing sequences and writ ing outputs We will use the notation S for S i idem for A M and Fi for i j 3 Transitions 3 1 Input Input 4 i 1 ari ee mr elen HRH Um Wa st if S bie Input e s s Vz IVar Viol f z Vj 1 NJA i Fig Fi x f x The first part takes the inputs and assigns them to the input variables of process i while the second part sends the new values to all other processes e 1 k Wk are the whens associated to process i sai sj pj H Msg Ai H Si Si 4 Input is done so pass to the process phase and make all inactive sequence waiting for execution 3 2 Handling messages Read value i a lt e JN gt gt gt 8 gt lt gt gt gt EG NEE gt if s pj Msg A3j 1 N IM E Fj z val M sai sF r M This transition reads a message of the form z val that was sent by process j It will process its assignment using the rules defined in section 3 3 111 Read execution i i 76 Yes 8 gt H lt lt gt S Mee 8 gt if s pj Msg 3j 1 N AaM X Fji S M e s s Zj H M This transition reads an execution caused by a launch that came from process j It will process this execution using the rules defined in section 3 3 Read sequence i i lt gt gt gt ps gt lt gt NN gt gt gt s gt if
156. rrent thread id functions declarations int startSequences void handleWarn int id int val void handleExec int id unsigned char args void handleWhens void sampleInputs void writeOutputs void handleMsg void timer int start int i 0 while true builtin cms sys time sampleInputs handleWhens handleMsg writeOutputs void error int i cputs error cputw i dsound system 0 sleep 1 read input int sample int i switch 1 case 1 return SENSOR_1 break case 2 return SENSOR 2 119 break case 3 return SENSOR 3 return 0 wakeup t getControl wakeup t pid return unsigned int current thread id pid data manipulation void pushStack pid t pid if SIZE STACK gt SIZE MAX error ERR OUT OF MEMORY halt else dsl vm stack SIZE STACK pid SIZE STACK SIZE STACK qz pid t popStack if SIZE STACK lt 0 error ERR STACK EMPTY halt else SIZE STACK SIZE STACK 1 return dsl vm stack SIZE STACK define StackIsEmpty SIZE STACK 0 void startwait if StackIsEmpty current thread id popStack wait event amp getControl unsigned int cpid void wakeup pid t id pushStack pid t cpid current thread id id w
157. ructions conditionnelles ou d it ration la structure en blocs de base est conserv e La mise jour du prochain case ex cuter se fait donc en fonction du test de la condition Une instruction conditionnelle dSL dans une s quence IF condition THEN liste instructions 1 ELSE liste instructions 2 END IF 68 est traduite par les intructions reprises dans la figure 5 17 o iste instructions x C est la traduction C de liste instructions x et label y contient le code des instructions suivant l instruction conditionnelle dSL case label x if condition nextBasicBlock label 1 else nextBasicBlock abel 2 break case label 1 liste instructions 1 C nextBasicBlock abel y break case label 2 liste instructions 2 C nextBasicBlock abel y break case label y Figure 5 17 Traduction d un instruction conditionnelle dans une s quence Une instruction d it ration dSL dans une s quence WHILE condition DO liste instructions END WHILE est traduite par la suite d instructions reprises dans la figure 5 18 o iste instructions C est la traduction C de liste instructions et label y contient le code des instructions suivant l instruction d it ration dSL case label x if condition nextBasicBlock label z else nextBasicBlock abel y break case label z liste instructions C nextBasicBlock abel x break case label y e
158. s un byte de donn es Cette limite peut tre d pass e en remplacant le firmware par un nouveau syst me d exploitation Le choix du langage utilis pour la programmation des briques s av re donc important 3 Les diff rents syst mes d exploitation et leurs langages Hormis le langage Mindscript d fini originellement par le software Lego il existe diff rents langages et syst mes d exploitation qui ont t d velopp s au fil des ann es 90 pour programmer la brique RCX Not Quit C LegOS brickOS LejOS Pbforth etc Nous allons pr sent d tailler les caract ristques principales de chacun de ces langages et syst mes d exploitation Not Quit C Bau00 BGT00 Not Quit C est un langage de programmation qui a t d velopp par Dave Baum Comme son nom l indique il est proche du C En fait il en reprend la syntaxe en y incorporant les commandes Mindstorms Les programmes binaires obtenus apr s compilation sont compatibles avec le firmware fourni par Lego D s lors ce langage offre l avantage de pouvoir utiliser simultan ment des programmes Mindscript d velopp s avec l environnement graphique propos par Lego et des programmes Not Quit C 43 Cependant il impose galement de respecter les diff rentes contraintes impos es par le firmware comme par exemple le type des variables uniquement des entiers ou encore le nombre de celles ci au maximum 32 globales et 16 locales Pour le probl me qui nous motive ici
159. s d attente Remarquons qu il est n cessaire d attendre que l ascenceur soit libre avant de lancer la s quence t3 to t4 car il ne peut y avoir plus d une instance d une s quence en cours d ex cution 96 carry brick from t 2 bo t 34 SEQUENCE t2 to t3 get the moving cart in position 2 c l go in two wait c l state TRUE AND c_1 position FALSE launch the two conveyer belts c l rotor go LAUNCH t 2 go brick on conveyer belt of conveyer belt wait c l rotor light TRESHOLD get the moving cart in position 2 LAUNCH c 1 go in one wait c l state TRUE AND c l position TRUI Gl wait the next conv belt to be free wait t_3 free TRUE t 3 free FALSE launch the two conveyer belts t 3 go c 1 rotor lt go brick on conveyer belt 3 wait t 3 light TRESHOLD t 3 stop c l rotor stop wait the elevator to be free wait a l free TRUE a l free FALSE launch the next sequence LAUNCH t3 to t4 free the moving cart c l free TRUE END SEQUENCE Figure 6 11 Code de la s quence t2 to t3 Le traitement est similaire pour le tapis mobile sup rieur et pour l ascenceur La figure 6 12 reprend le code de la s quence t3 to t4 Elle lance une des s quences suivantes savoir une fois t4 to t5 et une fois c4 to t6
160. s E v Msg AAS M es s M Mi S Ai A U SJ This transition takes a distributed execution that was sent by another process and puts it in the active set It will get executed in the processing phase End of message reading i i 70 puse Iu if s v Msg e s s i Processing At any time process i can stop reading messages and pass on to the processing phase 3 3 Processing transitions Assignment i i nn 7 lt lt lt cm epris ls c Wig Mall gt if s y Processing Msg Var ezpr U x Var Ezpr e ai s V 9 V D expr Ai A U Sa Vj D N PNG Fig Fu GV GE The first part evaluates the expr and updates the variable with the new value the second part puts the rest of the instructions in the waiting set and finally the third part sends the new value to all other processes e 1 k W are the whens associated to process i e 3j s A A U Si ol Some of the sleeping sequences may have their wait condition go true Make them awaiting execution Assignment zm expr S2 ere ps if s yi Processing Msg Var ezpr U z C Var Ezprj j i e s s Mj MU x expr S2 Since process i can t evaluate the expression or do the assignment the sequence is sent over to the process that can 112 If i i TN lt if expr then S end if S s gt 4 lt S S2 s gt if s yi Processing Ms
161. s qui seront examin s pendant le traitement L union de tous les environnements locaux des CPs composant le syst me forme l environnement global du syst me Le superviseur permet ainsi l op rateur d acc der l tat global du syst me Un CP est responsable de la gestion de ses entr es et sorties ainsi que de l ex cution des taches qu il doit effectuer Le concept traditionnel d automate induit que chaque CP ex cute une boucle appel e par la suite boucle nput Process Output divis e en trois phases 1 Input les diff rents senseurs d entr e sont acc d s et leurs valeurs sont stock es en m moire et transmises au superviseur 2 Process le programme s ex cute en fonction de ses nouveaux inputs et des flags mis jour par le superviseur Les r sultats sont stock s dans la m moire du CP et transmis au superviseur 3 Output les dispositifs de sorties sont mis jour via la couche hardware Les CPs utilis s sont des contr leurs PIP 4000 1634 dont le langage de programmation est un langage de bas niveau avec un large set d instructions Une d finition compl te de ce langage peut tre trouv e dans Language de programmation du PIP4000 1634 de Macq Electronique En ce qui concerne les p riph riques d entr e sortie chaque CP poss de plusieurs racks Un rack est un ensemble de cartes dont chacune poss de un certain nombre de connecteurs ou slot auxquels sont branch s les dispositifs d entr e sortie Un p riph
162. s s coule entre deux envois successifs du m me message En pratique la tache ab va ex cuter simultan ment les deux fonctions qui lui sont attribu es et attendre un temps invers ment proportionnel aux nombres de messages dans la liste des messages recus Le pseudo code de la tache est repris a la figure 5 47 thread ab while true traitement des messages recus traitement des messages envoyer msleep 10 taille liste msg recu t1 Figure 5 47 Pseudo code de la tache ab En r sum trois l ments sont n cessaires pour l impl mentation du protocole une fonction d envoi appel e ab write un gestionnaire des messages re us appel ab portHandler etune t che continue appel e tnread ab A cela il faut ajouter les structures de donn es suivantes une liste de messages envoyer etune liste de messages recus Pour permettre l usage du protocole il est n cessaire de l initialiser avec la fonction init ab protocol et de lui fournir en param tre un pointeur vers le portHandler de l utilisateur ainsi que l identificateur du site Celui ci est n cessaire pour la conception des en t tes et la s lection des messages recus par le ab portHandler Cette fonction initialisera les diff rentes structures les s maphores ainsi que la tache tnread ab Le code du protocole de communication est disponible en Annexe E 85 Chapitre VI Etude de cas chaine de montage Dans ce chapitre
163. s unsigned char le ngth free omess MESS mess free mess free imess MESS mess free mess T HEAD ER SIZE length ROR RRR Kk K K K Kk K K K Kk K K K Kk K K K Kk K K K Kk K K K Kk K K Kk Kk K K Kk Kk K K Kk Kk K K Kk Kk K K Kk Kk K K Kk K K K Kk K K K Kk K K Kk Kk K K Kk Kk K K Kk k Kk K Kk K ROR RRR K K K K Kk K K K Kk K K K Kk K K K Kk K K K Kk K K K Kk K K K Kk K K Kk Kk K K Kk Kk K K Kk Kk K K KC Kk K K K k K K Kk Kk K K Kk Kk K K Kk k K K Kk k K K Kk K AB PROTOCOL define flip_sb rs rs 0x1 define flip_rb rs rs 0x2 define get_sb rs rs amp 0x1 define get_rb rs rs amp 0x2 1 Ri st brief Erases the first message for a given site param site The site atic void erase SITE site M ESS msg msg Site gt LIST if msg Site gt LIST msg gt NEXT free omess msg brief Creates a new messag The header for th param header 7 param msg n The message param length 7 The length of msg new message s definitions of MSG xxxx 131 param wait If 1 wil param io Used to t warning if AB STATIC i have no control on memory alloc l block until ake from pool s not used memory is freep INCOMING or OUTGOING the wait parameter is ignored
164. sage param destination The destination for the message return A pointer to the MESS structure if successfully added to the list ULL otherwise N MESS ab_awrite const unsigned char message unsigned char length unsigned c har destination char msg header DEFAULT HEADER SIZE SITE site MESS mess NULL MSG HEAD msg header 0 MSG SOURCE msg header id site MSG DEST msg header destination sem wait amp sem ab write site search and add destination sem post amp sem ab write if site mess new msg msg header message length 0 OUTGOING if mess sem_wait amp sem_ab write add site mess sem post amp sem ab write return mess brief Use this function to synchronously send a message The message is added to the list and will be sent as soon as possible The unction returns when an acknowledgment is received for the message param message The message to send param length The length of the message param destination The destination for the message return A pointer to the MESS structure if success NULL otherwise ESS ab swrite const unsigned char message unsigned char length unsigned char destination MESS mess ab awrite message length destination if mess sem wait amp mess sem ack return mess 136 Annexe F Format des 3 types de messages chang s
165. se memory allocation problems 127 warning When AB STATIC is not used the parameters n_sites incoming and ougoing are ignored Ki int init ab protocol void u_portHandler const unsigned char message unsigned char length unsigned char id site unsigned char n sites unsigned char incoming unsigned char outgoing ndif ab c include ab h Implementation of the alternating bit protocol on top of LNP for LegOS BrickOS Copyright C 2004 Bram De Wachter This program is free software you can redistribute it and or modify it under the terms of the GNU General Public License as published by the Free Software Foundation either version 2 of the License or at your option any later version This program is distributed in the hope that it will be useful but WITHOUT ANY WARRANTY without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE See the GNU General Public License for more details You should have received a copy of the GNU General Public License along with this program if not write to the Free Software Foundation Inc 59 Temple Place Suite 330 Boston MA 02111 1307 USA K Naddtogroup ab internals Q if DEBUG
166. since we ation return a new message or NULL if memory was not available and wait is false Wi static MESS new msg const unsigned char header const unsigned char msg unsigned char length unsigned char wait unsigned char io MESS m if AB STATIC if wait if io INCOMING m wait alloc imess length else m wait alloc omess length else if io INCOMING m alloc imess length else m alloc omess length ls m alloc mess length ndif i if m return NULL Combine the two mallocs to only one make m gt MSG point to the area after the MESS structure m gt MSG char m sizeof MESS m gt LENGTH length DEFAULT HEADER SIZE sem_init amp m gt sem_ack 1 0 memcpy m gt MSG header DEFAULT HEADER SIZE memcpy m gt MSG DEFAULT HEADER SIZE msg length m gt NEXT NULL return m brief Creates a new sit param id site The new site s id return a fresh SIT E E xj static SITE new site un ST EE Xs if s alloc site s gt ID SITE id site s LIST 0 B s gt RSBIT 0 return s Adds a message to the param site The destin param m The messag e 7 E si or NULL if no more memory available signed char id site NULL return NULL outgoing messages to a certain site ation site e M te ESS m static void add SIT
167. ssage 0 1 2 3 4 257 258 TYPE LENGTH SOURCE DEST DATA CHK Figure 3 4 Formats des messages Inp La structure des paquets du protocole LNP est reprise la figure 3 4 Un champ de type permet de sp cifier le type du message le champ LENGTH sa longueur Dans le cas d un message adress deux champs de soucre et de destinataire sont n cessaires Le champ CHK checksum permet de tester la correction des donn es En ce qui concerne LejOS certaines classes Java ont t sp cialement d finies pour les communications RCX LNP est disponible gr ce josx rcxcomm LNP Il est possible d envoyer et de recevoir des messages d int grit ou d adressage mais ce n est pas fiable titre d information compl mentaire signalons qu il existe actuellement des langages en cours de d veloppement pour la communication inter robots tels que Combot Il sera int ressant de suivre l volution de ceux ci dans le futur pour l am lioration du comportement et des performances des robots 5 Choix d un syst me d exploitation D une part LejOS fournit un OS alternatif au firmware standard une machine virtuelle un protocole de communication un ensemble de librairies une grande portabilit Au vu de la portabilit offerte par le langage Java LejOS peut s av rer tre un choix judicieux En effet le travail effectu pourra tre facilement transporter d autres situations
168. sur un site distant END WHEN WHEN a 0 THEN site2 cEGALd END WHEN Figure 2 31 Exemple de d clarations d v nements Il est possible de d finir un v nement sur un type de variable gr ce WHEN IN La figure 2 32 reprend un exemple d utilisation de cette construction 34 WHEN IN CD self c 0 THEN LAUNCH self cEGALd END WHEN Figure 2 32 Exemple de WHEN IN 11 La s mantique Dans ce chapitre nous allons pr senter la s mantique du langage dSL Apr s avoir introduit certaines notations utiles nous nous attacherons la notion de distribution maximale Ensuite nous nous pencherons sur quelques d finitions importantes telles que celles de syst me transitions tiquet es ou d environnement d ex cution Pour finir nous d taillerons les r gles de s mantique op rationnelle structurelle de dSL La s mantique qui suit est tir e de DMM03 2 En fait il s agit de la s mantique d un sous ensemble de dSL En effet pour des raisons de simplicit certaines restrictions ont t faites Les m thodes sont suppos es inline Ce qui implique que les appels r cursifs ne sont pas permis D s lors toutes les variables sont consid r es comme d clar es globalement Les s quences et les instructions de lancement ne sont pas consid r es Il est possible d exprimer une s quence ou un LAUNCH de mani re quivalente pa
169. syntaxe et s mantique en d crivant les probl mes li s la distribution du code et les m canismes mis en oeuvre 3 Concepts de dSL Le langage dSL DMM03 est un langage de programmation orient objet qui fournit une distribution de code transparente utilisant des m canismes de bas niveau Il permet de concevoir des syst mes de contr le distribu s et permet au concepteur de ne pas devoir g rer explicitement les aspects de distribution du code et de communication entre les contr leurs du syst me Un programme dSL est congu comme si l environnement entier est accessible et fournit une vision centralis e d une application distribu e Le distributeur dSL se chargera de r partir le code en plusieurs programmes correspondant aux diff rents sites sur lesquels le syst me sera distribu A l instar de son pr d cesseur SL dSL est un langage de supervision La diff rence entre ces deux langages r side dans la repr sentation du syst me Selon l approche dSL le syst me est constitu d un ensemble d automates interconnect s par un r seau et qui voluent ind pendemment les uns des autres Il n y a plus de notion de superviseur ind pendant Les communications ne se font plus via le superviseur mais directement entre les contr leurs Comme le montre la figure 2 2 un syst me impl ment en dSL peut tre vu comme une association de deux entit s diff rentes le syst me et l environnement qui interagissent l un avec l autre au mo
170. t 1 ach define set_ack msg val SG HEAD msg val MSG HEAD msg 0x2 MSG HEAD msg amp 0xFD define set ack 1 msg SG HEAD msg 0x2 define set ack O0 msg SG HEAD msg amp OxFD define is ack msg MSG HEAD msg amp 0x2 define set bit msg val SG HEAD msg val MSG HEAD msg 0x1 MSG HEAD msg amp OxFE define set bit 1 msg SG HEAD msg 0x1 define set bit 0 msg SG HEAD msg amp OxFE define get bit msg MSG HEAD msg amp 0x1 if AB STATIC K Hk K K K K K K K K K K 3K 3K 3K 3 K K K K K K K 3K 3 K K K K K K K 3K 3 K K K K K K K K 3 K K K K K K K K 3 K K K K K K K K K Kk K K K K K K K Kk Kk k Kk k k f Memory pool functions A RRR RK Kk K K K k K K K K K K K Kk K K K Kk K K K Kk K K K Kk K K K K K K Kk Kk K K Kk Kk K K Kk Kk K K Kk Kk K K Kk K K K Kk K K Kk Kk K K Kk Kk K K Kk k K K Kk k K Kk Kk K ym brief Initialises a pool This function populates a pool with chunks of memory of the same size using malloc 129 param p The pool param n The number of elements param s The size of each element return 0 if successfull 1 if not enough memory Wi char init pool pool p int n int s pool el pe sem init amp p gt size 1 n for p gt head NULL n gt 0 n if pe malloc st sizeof pool el NULL return 1 pe gt next p gt head pe gt free 135 pe cont char pe sizeof pool el p gt head pe return 0
171. t de se rendre compte que la variable 1 d identificateur 23 doit tre transmise lors de la demande d ex cution du bloc de base d identificateur 14 distribu sur le site 1 Le code de la demande d ex cution se trouve dans le case 13 de la figure 5 33 d extraction des param tres a donc t g n r pour le site 1 Le code void graph 6 distri int i int nbVal int nextBasicBlock HOP WAIT ID while true switch nextBasicBlock case HOP WAIT ID startwait nextBasicBlock dsl vm id nbVal READ INT FROM CHAR dsl vm args while nbVal switch READ INT FROM CHAR dsl vm args case 23 l READ INT FROM CHAR dsl vm args break case default error ERR UNKNOWN PARAM ID halt break case 10 if a 0 nextBasicBlock 11 else nextBasicBlock 12 break case 11 b 1 HOP 2 6 13 0 nextBasicBlock break case 12 b 0 HOP 2 6 13 0 nextBasicBlock break case 14 b a b 1 HOP 3 6 15 0 nextBasicBlock break case 16 g a b 1 nextBasicBlock HOP WAIT ID break HOP WAIT ID HOP WAIT ID HOP WAIT ID Figure 5 32 Exemple de code g n r pour une s quence distribu e l re partie 75 void graph Gil distri int 1 int nextBasicBlock HOP WAIT ID while true switch nextBasicBlock case HOP WAIT ID
172. t le bit d envoi correspondant la station r ceptrice et envoie le message Si un acquittement est re u le bit fourni par celui ci est v rifi S il coincide avec le bit d envoi le message a bien t transmis Sinon il faut renvoyer le dernier message envoy RECEPTION bit 0 message b b bit ack b bit 1 bit b bit ack b ENVOI bit 0 envoi de message message bit maj TEMPO ackb b bit bit 1 bit b bit message bit maj TEMPO tempo message bit Figure 5 39 Pseudo code du protocole ab 15 2 Impl mentation Les messages sont tous broadcast s Le protocole de communication est donc charg de v rifier la destination du message et de transmettre a la fonction de traitement des messages re us uniquement les messages qui lui sont destin s L objectif de cette d marche est d obtenir un protocole fiable tout en veillant ce que l impl mentation soit r utilisable En LegOS une fonction appel e portHandler est assign e la tache de r ception des messages D s qu un message est recu sur le port infrarouge le syst me d exploitation lance l ex cution du portHandler qui doit tre d fini par l utilisateur et qui a pour r le de traiter les messages Imaginons maintenant qu un utilisateur d sire utiliser un protocole de communication fiable La d marche naturelle est de remplacer le portHandler de l utilisateur courant par un portHandler ass
173. t les p riph riques disponibles en legOS savoir les capteurs de toucher de lumi re et de rotation pour les entr es l cran LCD et les moteurs pour les sorties La figure 5 11 reprend cette correspondance ainsi que la mani re dont les emplacements sont sp cifi s Sur une brique Lego il y a trois p riph riques d entr e identifi s par les chiffres 1 2 et 3 et trois p riph riques de sortie identifi s par les lettres A B et C cf 777 1 Introduction aux Lego Mindstorms Pour rappel les param tres dSL d une variable d entr e sortie sont constitu s de trois nombres card rack slot Le premier n est pas utilis le second correspond la position le dernier au type du dispositif VARIABLE D INPUT Type 0 Lumi re 1 Toucher Figure 5 11 Correspondance entre param tres de variables dSL et p riph riques Lego Nous avons vu dans le paragraphe 2 La t che Input Process Output que les fonctions samplelnputs et writeOutputs sont responsables de la gestion des entr es et des sorties du site La fonction samplelnputs consiste d une part relever les valeurs des dispositifs d entr e par l interm diaire de la fonction sample position qui renvoie la valeur du dispositif situ l emplacement position et d autre part les assigner la variable globale correspondante Remarquons qu il s agit d une modification de la valeur d une variable D s lors si la variable est tild e il est
174. t thread_AB I SITE ZG MESS M t unsigned char MSG char ack DEFAULT HEADER SIZE while 1 sem wait amp sem todo sem post amp sem todo sem wait amp sem ab write treatment of received messages sem wait amp sem ab portHandler M M FIRST M FIRST NULL 133 sem post amp sem ab portHandler while M NULL _MSG M gt MSG sem trywait amp sem todo if is ack MSG DEBUG AB cputs ack ACK RECEIVED sem wait amp sem ab write S search and add MSG if S if get sb S RSBIT sem post amp S gt LIST erase S SOURCE MSG get_bit _MSG gt sem ack flip sb S gt RSBIT sem_post amp sem_ab write else Message received answer with an ack containing same bit MSG SOURCE ack MSG DEST MSG MSG DEST ack MSG SOURCE _MSG MSG HEAD ack 0 set ack 1 ack set bit ack SE bit _MSG Send ack lnp integrity write a msleep 0 Find the site that Ck DEFAULT HEADER SIZE sent this message sem wait amp sem ab write S search _ and _ add MSG Site found if bit if S if get_rb S gt RSBIT user portHandler M gt L flip rb S gt RSBIT SOURCE _ MSG corresponds call user get bit MSG MSG DEFAULT HEADER SIZE
175. ta deed al rdum anes 4 2 D finition de l environnement Lego Mindstorms ss ssessseseessessreseosseesesressesseesresseeseese 42 3 Les diff rents syst mes d exploitation et leurs langages s nnssssnneesesseessesessressessrssresseese 43 4 Les communications eer eelere 45 5 Choix d un syst me eet EE 46 6 Laicompilation vers Bes5 au co xa i cce dre e a eed x d C A s 47 Chapitre IV Compilation et distribution L ee chemin des compilation eege odo ete ie totae det 2 La structure du compillateur uio andere tice ba ee dad Ge ve bao i ed ds Chapitre V G n ration automatique de code LegOS pour Lego Mindstorms Lin OS TAC OG E La t che Input Process Output ios i deo te RO dae ose lesa o Nas oer M te pede Modo sug a Les m ssa g s neninn a Su CDI M uM CAN nc DEAN TUE Lesddentitic AQUES ioo ciego led Uo ren 76 dateien eae a Les typesrde variable AE nn otv DR ONSE Roo eal ar I edid oa iE e LES CHIENS SOUS ee dons d cu ee E Les OP LAtCULS T o9 n1 9o Mr YN I es3nstructlOns ss nea ete abate ee tette cete pii plier gestion des LAGS LR A A aee vie et dea Suse dene ei MES methodess tad sass gabe Candia ev an NIE DR dae Ged nn es ueri d 9 eee t N BETEN Oo EE a ANT a Re ee NNNM m JE Exemples de g n ration de code ee geiert dere er ege eege Zeg UT Le protocole de communication EE Chapitre VI Etude de cas chaine de montage 1 L
176. taill e dans le paragraphe 12 Les v nements Le contenu de handleMsg est explicit dans le paragraphe suivant au point 3 3 Le traitement des messages La t che nput Process Output est cr e dans la fonction d intialisation du site c est dire la fonction main du fichier c du site Une priorit inf rieure celle des taches des s quences lui est accord e 3 Les messages 3 1 Les types de messages Etant donn la nature distribu e du syst me des messages seront chang s entre les sites et cela pour diverses raisons 57 1 Lancement de m thodes et de s quences sur des sites distants Dans le cas d une instruction de lancement d une m thode ou d une s quence cf 7 6 8 f Op rateurs de lancement LAUNCH et lt le site de distribution de la m thode ou de la premi re instruction de la s quence peut tre diff rent de celui sur lequel l instruction de lancement est distribu e L ex cution de l instruction n cessite un message entre ces deux sites Il sera parfois n cessaire de transmettre les valeurs des param tres de la m thode ou de la s quence 2 Points de migration Lorsque les instructions d une s quence sont localis es sur des sites diff rents le compilateur g n re des points de migration du contr le cf 2 2 Le distributeur Ces points de migration sont traduits par des messages de demande d ex cution d une partie de s quence Rappelons qu il sera ventuellement n c
177. tor motor 1 1 END SITE 1 SITE s5 INPUT c 2 touch one 0 0 1 INPUT c 2 touch two 0 1 1 INPUT c 2 rotor light 0 2 0 OUTPUT c 2 motor 1 0 1 OUTPUT c 2 rotor motor 1 2 1 END SITE SITE s6 INPUT t 5 light 0 0 0 INPUT t 6 light 0 1 0 QUTPUT t 5 motor i 1 0 1 OUTPUT t 6 motor qe ek END SITE KKKKKK K KKK Kk K K K k K K K k K K K k K K K k Kk x CLASS FUNCTIONALITIES KKK KKK Kk K K K k K K K k K K K k K Kk k Kk k K Kk KKK rende c nveyor be LEE ARE METHOD conveyor belt go self motor 20 END METHOD METHOD conveyor belt stop self motor 0 END METHOD moving Cart METHOD moving cart go in one IF self touch one 0 THEN self state FALSE self rotor stop self motor 30 END IF END METHOD 147 METHOD moving cart go_in_ two IF self touch two 0 THEN self state FALSE self rotor motor 0 self motor 30 ND_IF END METHOD METHOD moving cart stop self motor 0 self state TRUE END METHOD self position TRUE self stop END WHEN self position FALSE self stop END WHEN elevator METHOD elevator up IF self touch up lt 0 THEN self state FALSE self rotor stop self motor
178. touch sensor position 2 rotor conveyor belt position BOOL TRUE position 1 FALSE position 2 state BOOL TRUE running FALSE stopped free BOOL END CLASS CLASS elevator kk kk GLO END SIT motor INT touch up INT touch sensor position up touch down INT touch sensor position down rotor conveyor belt position BOOL TRUE up FALSE down state BOOL TRUE running FALSE stopped free BOOL END CLASS kkk k k k k k k k k k k k k k k k k k kk s ADISTRIBUTIONAFEK AA KkKKk KKK K Kk K K Kk K K K k K Kk K k KKK BAL VAR t 1 t 2 t 3 t 4 t 5 t 6 conveyor belt c_l c 2 moving cart i a 1 elevator ask one ask two BOOL last in last out BOOL VAR E sl INPUT t 1 light 0 0 0 INPUT t 2 light OL 146 OUTPUT t_1 motor 1 0 1 OUTPUT t 2 motor De opts eo s END SITE SITE s2 INPUT c l touch one 0 0 1 INPUT c 1 touch two OS INPUT c l rotor light 0 2 OUTPUT c l motor 1 0 1 OUTPUT c l rotor motor 1 2 END SITE SITE s3 INPUT t 3 light 0 0 0 INPUT t 4 light 0 1 0 OUTPUT t 3 motor LO T lt OUTPUT t 4 motor Tdi END SITE SITE s4 INPUT a 1 touch down 0 0 1 Gate INPUT a l touch up 0 Sak 1 INPUT a l rotor light 0 2 0 OUTPUT a l motor 010 7 OUTPUT a l ro
179. tre 6 Etude de cas chaine de montage Sch ma de la chaine de montage vue de profil Sch ma de la chaine de montage vue de haut R capitulatif des entr es sorties par l ment du syst me Distribution des dispositifs d entr e sortie du syst me Code dSL de la classe conveyor belt Code dSL de la classe elevator Code dSL de la classe moving cart Code des v nements d arr t des tapis d entr e et de mise jour des variables ask one etask two Code des v nements de lancement des s quences ti to t3 ett2 to t3 Code des v nements de mise en route des tapis d entr e Code dela s quence t2 to t3 Code de la s quence t3 to t4 106 Annexe A Grammaire dSL root dsl program declaration list declaration class global variables local variables variable declaration list variable declaration non empty id list site localization list localization localizable lhside localizable lhside list kind when when in PARSE DSL PROGRAM sl program PARSE LHSIDES localizable lhside list declaration list declaration class global_vanables site when when_in method sequence CLASS ID variable declaration list END CLASS GLOBAL VAR vanable declaration list END VAR LOCAL VAR variable declaration list END VAR variable declaration non empty id list type ID ID SITE ID localization list END SITE localization
180. tructions conditionnelles Exemple de d clarations de m thodes g n r es Exemple de fonction handleExec Exemples d appels de m thodes g n r s Exemple de g n ration de code pour une fonction handleWarn Exemple de code g n r pour une s quence distribu e 1 re partie Exemple de code g n r pour une s quence distribu e 2 me partie Exemple de code g n r pour une s quence distribu e 3 me partie Exemple de code g n r pour une s quence deux param tres et avec une instruction d attente 105 Figure 5 36 Figure 5 37 Figure 5 38 Figure 5 39 Figure 5 40 Figure 5 41 Figure 5 42 Figure 5 43 Figure 5 44 Figure 5 45 Figure 5 46 Figure 5 47 Figure 6 1 Figure 6 2 Figure 6 3 Figure 6 4 Figure 6 5 Figure 6 6 Figure 6 7 Figure 6 8 Figure 6 9 Figure 6 10 Figure 6 11 Figure 6 12 Exemple de g n ration de code pour des v nements l re partie Exemple de g n ration de code pour des v nements 2 me partie Exemple de messages chang s avec un protocole ab Pseudo code du protocole ab Comparaison sans avec protocole ab Repr sentation de la structure des messages envoyer Format des messages ab Chemin parcouru par un message envoy Repr sentation de la structure des messages recus Format d un acquittement ab Parcours d un message envoy Pseudo code de la t che ab Chapi
181. tructure des messages a envoyer Dans notre impl mentation nous avons pr vu deux types d envoi synchrone et asynchrone L envoi synchrone d un message se fait via la fonction ab_swrite int site unsigned char message int length ou site est la destination du message message le message et length sa longueur L envoi asynchrone d un message se fait via la fonction ab_awrite int site unsigned char message int length L envoi synchrone assure que le message est transmis la fin de l ex cution de la fonction Les deux fonctions 1 cr ent l en t te du message et forme le message envoyer 2 cherchent la liste de messages du site de destination en la cr ant si besoin est et 3 ajoutent le message avec en t te en fin de liste des messages envoyer L ajout en fin de liste pr serve l ordre des messages Le format g n ral des messages ab est repris la figure 5 42 En pratique l en t te est constitu e de trois bytes Un byte concernant l identification du message contenant le bit d envoi 8 et le bit d acquittement 2 et deux bytes identifiant la source et la destination du message 82 DA SOURCE DESTINATION MESSAGE Figure 5 42 Format des messages ab Le chemin parcouru par un message envoy est repris la figure 5 43 Pour cela diff rentes taches vont s ex cuter en parall le 1 les applications utilisateur 2 le syst me d exploit
182. ts sont initialis s la m me valeur de part et d autre typiquement 0 Le r seau est suppos vide a l initialisation Lorsque la station d envoi pr pare son message a envoyer elle y ins re le bit d envoi en question La station r ceptrice v rifie le bit contenu dans l en t te Si celui ci correspond a son bit de r ception le message est d barrass de son en t te et transmis a l utilisateur Le bit sur la station de r ception est invers D s r ception d un message un acquittement contenant le bit du message est envoy m me si le bit du message recu ne correspond pas Lorsque la station mettrice re oit l acquittement elle v rifie sa v racit en comparant le bit avec celui du message envoy et inverse son bit d envoi si le message a bien t acquitt La station mettrice peut alors passer a l envoi d un nouveau message Lorsqu aucun acquittement n est re u apr s un certain temps ou lorsque la station mettrice recoit un acquittement avec un bit incorrect le message en cours est renvoy Dans la figure 5 38 sont repr sent s diff rents cas qui peuvent se poser dans l usage d un protocle ab MSG correspond au message j envoy avec avec un bit i TEMPO signifie que le temps d attente d un acquittement est coul et qu il faut r envoyer le message envoi r ception user 0MSG 1 MSG 1 OJACK 1 PCR 1 MSG 2 PERDU eec ead OY site bit 1 TEMPO
183. tte contrainte appel e contrainte atomique limite les possibilit s du syst me I a donc t n cessaire de d finir un moyen de relacher cette contrainte Deux m canismes ont t mis au point 1 LAUNCH qui permet d appeler une s quence ou une m thode sur un autre site de mani re asynchrone Il faut remarquer que plusieurs instances d une s quence ne peuvent tre ex cut es simultan ment 2 TILDE qui permet de mettre en ceuvre une copie locale d une variable distribu e sur un autre site La copie locale fera r f rence la derni re valeur connue d une variable tild e Dans certaines circonstances l usage de ce tilde peut causer des probl mes si la diff rence entre la valeur tild e et la vraie valeur porte cons quence En pratique le programmeur devra veiller minimiser les impacts n fastes que les temps de transfert de valeur pourraient avoir pour que ceux ci ne mettent pas en danger le bon comportement du syst me Ces deux m canismes doivent tre introduits par le concepteur du programme Ils ne sont pas g n r s automatiquement par le compilateur pour des raisons de s ret et de performance L usage du LAUNCH impose une communication inter site pour ordonner l ex cution d une m thode ou d une s quence L usage d un tilde impose des communications inter site chaque fois que la variable tild e est assign e pour mettre jour les diff rentes copies distantes de la variable 13 Soit
184. u instance classe est l identificateur de l instance de la classe sur laquelle va s ex cuter la m thode m thode est l identificateur de la m thode et param tres les param tres transmis la m thode Dans le premier cas c est dire sans LAUNCH l ex cution de la m thode est synchrone et la fin de celle ci est attendue avant de continuer l ex cution des instructions suivantes Dans le second cas l ex cution de la m thode se fait de mani re asynchrone L ex cution des instructions suivant l appel la m thode se fait sans attendre la fin de la m thode Le lancement toujours asynchrone d une s quence se fait par l interm diaire de LAUNCH selon la syntaxe suivante LAUNCH id s quence parame tres 3 22 9 11 Les m thodes La forme g n rale de la d finition d une m thode est METHOD classe id m thode param tres liste instructions END METHOD ou classe est l identificateur de la classe a laquelle se rapporte la m thode id m thode est l identificateur de la m thode param tres sont les ventuels param tres de la m thode et liste instructions est le code de la m thode contenant ventuellement une d finition de variables locales en d but de bloc Les param tres d une m thode consistent en une suite de d clarations de variables s par es par des virgules Lors d un appel de m thode l ordre et le type des param tres doit respecter ceux d finis par la d cla
185. uctions est la liste des instructions constituant le traitement de l v nement Elles sont ex cut es lorsque la condition de l v nement passe de faux vrai Celles ci sont ventuellement pr c d es d un bloc de d claration de variables locales Le code d un v nement doit respecter la contrainte atomique cf 6 Code atomique et s quentiel 23 La syntaxe suivante WHEN IN id type condition THEN liste_instructions END WHEN permet de d finir un v nement sur un type particulier de variable En d autres termes l v nement sera d fini pour toutes les variables de type id type Il est possible de r f rencer les variables de l instance courante de la classe via self cf 8 8 e L op rateur 9 14 L initialisation En dSL une initialisation est possible Pour cela il suffit de d clarer une s quence sans param tre identifi e par MAIN Cette s quence sera ex cut e d s l initialisation du syst me 10 Exemples 10 1 Les identificateurs Les identificateurs permis sont les chaines de caract res respectant la r gle syntaxique pr sent e plus haut cf 9 1 Les identificateurs Ils peuvent contenir des lettres des chiffres ou le caract re _ sans restriction de longueur Le premier caract re ne peut pas tre un chiffre Les majuscules sont permises mais pas les accentuations La figure 2 9 reprend un ensemble d exemples d identificateurs corrects et incorrects cont
186. uence he moving cart KKK KKK KK Kk Kk Kk K K K k Kk K k k Kk Kk Kk Kk k x KKK KK k k X XINHENS k k k k x x x x KKK KKK Kk K K K K K K K k k K k k k K k KKK W EN t input 1 ligh conveyor belts always turning C2 TRESHOLD THEN t I go1 D WHEN 2 go D WHE EN t 2 light gt TRESHOLD THEN t z WHEN uo AMA L G t 2 1igh ESTION lt TRESHOLD AND ask two FALSE THE t 2 stop ask two TRUI Lr D WHEN ask two FALSE EN stop one TRUI C D WHEN ask one FALSE D WHEN EN E ask one c l free FA LAUNCH tl ro last in TRUE AG S D WHEN WHI F EN ask_one FALSE c l free FALSE LAUNCH t2 to t3 last in FALSE EN D WHEN WHI RUE ia hy EN ask one c l free FALS EN t 2 light gt TRESHOLD AND ask two TRU t l light TRESHOLD AND ask one FALS EN t l light gt TRESHOLD AND ask one TRU AND ask two FALSE AND ask two TRUE AND ask two TRUE THE THE THE THE AND c l free TRUE take control of the moving cart THE AND c l free TRUE take control of the moving cart
187. uiert une sortie les deux moteurs qui seront connect s ensemble et deux entr es les capteurs de toucher La figure 6 4 reprend l ensemble des entr es et sorties n cessaires pour la r alisation de la chaine de montage 88 ainsi que la distribution utilis e Au total six briques sont n cessaires La premi re contr le les deux tapis roulants d entr e La seconde se charge du tapis roulant mobile inf rieur La troisi me s occupe des deux tapis roulants interm diaires La quatri me est responsable de l ascenceur la cinqui me du chariot mobile sup rieur et la derni re des deux tapis roulants de sortie Entr e Sortie Nombre D tails Nombre D tails Tapis roulant 1 capteur de lumi re 1 moteur Chariot mobile 2 capteurs de toucher 1 moteur Ascenceur 2 capteurs de toucher 2 moteurs Figure 6 3 R capitulatif des entr es sorties par l ment du syst me 89 tapis roulant d entr e tapis roulant d entr e tapis roulant inf rieur tapis roulant sup rieur tapis roulant chariot mobile tapis roulant chariot mobile tapis roulant ascenceur tapis roulant de sortie tapis roulant de sortie Figure 6 4 Distribution des dispositifs d entr e sortie du syst me 4 Impl mentation dSL du syst me Dans ce paragraphe nous d taillerons l impl mentation des diff rents l ments du syst me savoir les tapis roulants l ascenceur et l
188. urant la fiabilit des messages et transmettant les messages corrects au portHandler de l utilisateur pour un traitement ad quat La figure 5 40 reprend les hi rarchies de couches sans ou avec protocole ab Applications Utilisateur Applications Utilisateur Ap OS OS Routines Routines d interruptions d interruptions Figure 5 40 Comparaison sans avec protocole ab 81 Sur un site donn pour chaque site avec lequel il y aura change de message envoi ou r ception il faut conserver 1 l identificateur du site 2 la liste des messages a envoyer contenant le message en cours d envoi 3 le bit d envoi 4 et le bit de r ception Ces l ments sont stock s dans une structure sous forme d une liste de site Pour chaque site l identificateur du site ID SITE les bits d envoi S BIT et de r ception R_BIT ainsi que la liste des messages envoyer LIST sont stock s Cette derni re contient les suites des caract res composant les messages MSG et leur longueur LENGTH Une repr sentation de cette structure est d taill e la figure 5 41 FIRST LAST site site ID SITE S BIT NEXT ID SITE S BIT NEXT i LIST R_BIT LIST R_BIT ess ess MSG LENGTH NEXT MSG LENGTH NEXT i Figure 5 41 Repr sentation de la s
189. ussi envisager le cas de briques mobiles 4 simplicit il faut toujours garder l esprit que l espace m moire disponible est limit Lorsqu on parle de protocole de transferts de donn es nous pensons imm diatement aux deux protocoles de communication UDP et TCP UDP assure la correction des donn es mais n est pas fiable Il est sans connexion contrairement TCP qui tablit une connexion entre les deux stations communicantes TCP par contre est un protocole fiable orient connexion La connexion tablie entre deux stations appel es sockets est bidirectionnelle Il assure galement la correction des donn es mais n cessite plus de ressources m moire pour tre mis en ceuvre Le protocole LNP est un protocole qui a t d velopp pour LegOS brickOS Il est UDP like Il permet l envoi de messages point point c est dire d finis entre deux RCX et deux seulement Il permet en outre l envoi de messages de plusieurs bytes en les incluant dans un paquet Le paquet est g n ralement constitu d un byte de d but du ou des bytes de messages et d un byte de fin Il existe 2 types de messages g n r s les messages adress s addressing message c est dire pour lesquels un destinataire unique est sp cifi et les messages d di s toutes les briques du r seau dits d int grit integrity message 45 Message d int grit 0 1 2 257 258 TYPE LENGTH DATA CHK Message d adre
190. veau permettant de contr ler la RCX on off affichage son Le driver ROM lancera le firmware un software stock dans la m moire RAM externe D origine il contient un interpr teur de code binaire qui ne laisse que 6kb de RAM aux autres programmes Ceci aura une influence plus tard sur le choix du langage de programmation La RAM externe est r f renc e dans le range 0x8000 0xFFFF une partie de cet espace d adressage est r serv e pour les entr es sorties D autres parties de la m moire sont r serv es pour l affichage de l cran LCD le contr le du moteur les registres shadow des ports I O et le vecteur d interruptions La RAM est divis e en deux parties noyau et utilisateur La partie noyau concerne le firmware ou POS alternatif la partie utilisateur correspond aux programmes et aux donn es Le microcontr leur H8 3292 est en outre quip d un certain nombre de sous syst mes Une horloge 16 bits les ports infrarouges un convertisseur analogique digital et enfin un module de timer 8 bits avec deux canaux Ces derniers tant utilis s pour g n rer les signaux envoy s au haut parleur et pour les communications infrarouges Deux briques RCX peuvent communiquer par l interm diaire de leurs ports infrarouges Cette fonctionnalit est essentielle pour les syst mes que nous impl menterons Les diff rentes briques devront par exemple s changer des valeurs de variables L utilisation du firmware standard limite les transfert
191. waitingid s quence FALSE Figure 5 13 Traduction d une instruction d attente Toute instruction g n r e d assignation d une variable apparaissant dans la condition d une instruction d attente est suivie par if is waitingid s quence wakeup thread id s quence o id sequence est l identificateur de la s quence r veiller Nous aurions pu envisager d utiliser la notion d v nement LegOS et de g n rer l expression bool enne de l v nement LegOS sur base de la condition d attente de l instruction dSL C est impossible puisque la condition peut contenir des variables locales 10 La gestion des variables tild es Une variable tild e est d finie sur tous les sites sur lesquels elle est utilis e chaque assignation sur une variable tild e le code du transfert de la nouvelle valeur doit tre g n r La s mantique dSL impose un broadcast des messages de changement de valeur Cependant les fonctions de cr ation et d envoi de messages ainsi que le protocole de communication fiable sont d finis tels que le message est adress un site de destination en particulier En pratique nous avons donc g n r l envoi du message pour chaque site o la variable est utilis e Cet envoi se fait via l instruction SEND ID WARN int site int id int val Nous avons vu dans le paragraphe 3 3 Traitement des messages que dans le cas de la r ception d un message de transfert d
192. x instances de la classe sont d finies globalement 25 CLASS voiture vitesse INT marche BOOL END CLASS GLOBAL VAR vl v2 voiture ND VAR Figure 2 12 Exemple de d claration de classe E De mani re similaire il est possible de d finir des variables locales une m thode une s quence ou un v nement La d claration de variables locales est illustr e aux exemples concernant ces diff rentes constructions 10 4 Les sites Les variables globales peuvent tre r parties sur les diff rents sites du syst me La figure 2 13 reprend un exemple de r partition de variables globales Pour chacune d elles qui correspondent un dispositif d entr e ou de sortie la sorte et les param tres doivent tre sp cifi s GLOBAL VAR ntre Ty ntree2 INT sortiel sortie2 BOOL internel LONG END VAR SITE sitel 1 INPUT entreel 0 0 1 OUTPUT sortiel 1 1 1 END SITE SITE site2 2 INPUT entree2 0 0 1 OUTPUT sortie2 1 0 1 END SITE Figure 2 13 Exemple de d finition de sites Dans le cas d une classe il est n cessaire de d finir le type de toutes les variables d une instance Un exemple de r partition d une instance de classe est repris la figure 2 14 26 GLOBAL VAR ab AB ND VAR E SITE sitel 1 INTERNAL ab a END SITE SITE site2
193. yen des senseurs des contr leurs composant le syst me En fonction de l tat de l environnement accessible via les senseurs d entr e et de sortie le syst me effectue les traitements ad quats avec ventuellement des mises jour des senseurs de sorties Il est constitu d un ensemble d automates ou CPs appel s par la suite sites sur lesquels seront r partis les diff rentes parties du code Chaque site effectuera une boucle nput Process Output pr sent e plus haut Il prend en charge la gestion des senseurs en acc dant r guli rement les senseurs d entr e et en mettant jour les senseurs de sortie La partie Process consistera donc la gestion des communications inter site mais aussi au traitement des v nements 10 Environnement lt H de ROC eh D Lo interface Figure 2 2 Architecture d un syst me dSL Remarquons qu un CP peut tre utilis comme lien entre le programmeur et le syst me Dans ce cas une interface graphique telle que l interface OBViews d velopp e par Macq Electronique permet de consulter et de modifier la valeur des variables dans le programme 4 Le probl me de la distribution du code Le code d un programme dSL est distribu sur les diff rents sites du syst me Deux probl mes se posent 1 le probl me de localisation des variables de par la nature distribu e du syst me une variable peut tre utilis

Génération de code de systèmes distribués

Contents

Download Pdf Manuals

Related Search

Related Contents

G&eacute;n&eacute;ration de code de syst&egrave;mes distribu&eacute;s

Contents

Download Pdf Manuals

Related Search

Related Contents

Génération de code de systèmes distribués