Travaux Dirigés N 1 Ingénierie Des Protocoles - Réseaux De .

3y ago
47 Views
3 Downloads
666.46 KB
12 Pages
Last View : 8d ago
Last Download : 5m ago
Upload by : Philip Renner
Transcription

M1 Info Ing. Protocoles 2008 09(D'apres TD ENSEEIHT)Travaux Dirigés n 1Ingénierie des protocoles - Réseaux de PetriCorrectionQuestion 1. Modélisation d’un atelier de fabricationordreproduitQuestion 1.1. Modélisation d’une machine de fabrication simpleConsidérons une première analyse du système selon une approche à la UML. Le diagramme descas d’utilisation ci-dessous donne l’ensemble des acteurs externes du système ainsi que epteurToutefois, cette figure n’aide par à préciser le mode des interactions entre les deux acteurs et lamachine : est-ce une communication synchrone, du type rendez-vous, ou asynchrone ? Pourrépondre à cette question, il est nécessaire d’imaginer plusieurs scénarios.La machine est décomposée, selon l’énoncé, en deux machines organisées en pipe-line : unemachine d’exécution et une machine d’envoi. On peut alors décrire l’ensemble des scénarios pardes diagrammes de séquences. Trois scénarios sont envisageables :1er scénario :ordreacteurrécepteurdébut execExecenvoi ordreMachined'envoiIdle envoiacteurordonnateurIdle execMachined'exécutionproduit prêt à envoyerEnvoidébut envoifin envoiproduit délivréréception produitIdle envoiIdle execfin execCe premier scénario montre les états et les événements présents dans le système. Les étatsIdle exec, Exec, Idle envoi et Envoi deviendront des places, tandis que les événementsenvoi ordre, début exec, fin exec réception produit deviendront des transitions. Toutefois,ce premier scénario n’indique toujours pas le besoin en synchronisation entre les différentesparties du système. Ce besoin apparaît avec les deux scénarios suivants.Page 1 sur 122008 2009

M1 Info Ing. Protocoles 2008 09(D'apres TD ENSEEIHT)2ème scénario : arrivée d’un ordre alors que la machine d’exécution ned'envoiacteurrécepteurordreproduit prêt à envoyerordreproduit délivréproduit prêt à envoyerproduit délivrénécessité de "stoker" le second ordre reçu analogue à une communication asynchroneCe second scénario montre que la communication entre l’acteur ordonnateur et la machined’exécution nécessite une place pour stocker les ordres (qui seront donc modélisés comme desjetons) en attendant leur traitement par la machine.3ème scénario : sortie d’un produit à envoyer alors que la machine d’envoi ned'envoiacteurrécepteurordreordreproduit prêt à envoyerproduit prêt à envoyerproduit délivréproduit délivrénécessité de "stoker" le second produit avant son envoi analogue à une communication asynchroneCe troisième scénario montre que la communication entre la machine d’exécution et la machined’envoi nécessite une place pour stocker les produits à envoyer (qui seront donc modéliséscomme des jetons) en attendant leur traitement par la machine d’envoi.De même on fera l’hypothèse que la communication entre la machine d’envoi et l’acteurrécepteur est asynchrone. Les produits délivrés seront stockés dans une place avant réceptioneffective (événement réception produit) par l’acteur récepteur.Modélisation de l’acteur « ordonnateur » :L’acteur « ordonnateur » se contente, d’après ces trois scénarios, d’envoyer un ordreindépendamment de l’état des machines. Cet ordre est stocké en attendant son traitement par lamachine. Ce comportement peut être modélisé par le RdP suivant :envoi ordreP OrdresPage 2 sur 122008 2009

M1 Info Ing. Protocoles 2008 09(D'apres TD ENSEEIHT)La place P Ordres contiendra autant de jetons que d’ordres émis et en attente de traitement.Cette place assurera la communication de type asynchrone entre l’acteur ordonnateur et lamachine d’exécution identifiée par le deuxième scénario. L’envoi d’un ordre est modélisé par letir de la transition « envoi ordre », transition qui n’a aucune précondition, et qui peut donc êtretirée à tout moment.Modélisation de la machine d’exécution :Un modèle simple de cette machine est donné par le RdP suivant :P Idle execP Ordresdébut execP Execfin execP produit prêt à envoyerCette machine, selon ce modèle, a deux états : idle et en exécution. Ces deux étatscorrespondent aux deux places P Idle exec et P Exec. On retrouve les deux états identifiés surle digramme de séquence du premier scénario. La fin d’une exécution provoque la productiond’un produit à envoyer, modélisé par un jeton dans la place « P produit prêt à envoyer ».Cette dernière place assurera la communication de type asynchrone entre les machinesd’exécution et d’envoi identifiée par le troisième scénario.Modélisation de la machine d’envoi :La machine d’envoi est similaire à la machine d’exécution :P produit prêt à envoyerP Idle envoidébut envoiP Envoifin envoiP produit délivréCette machine a deux états : idle et en envoi. Elle passe d’idle à envoi sur réception d’un produità envoyer. Enfin, la fin de l’envoi provoque la production d’un « produit délivré » modélisé parla production d’un jeton dans la place P produit délivré. Cette dernière place assurera lacommunication de type asynchrone entre la machine d’envoi et l’acteur récepteur.Modélisation de l’acteur « récepteur » :L’acteur « récepteur » se contente, d’après ces trois scénarios, d’attendre et consommer les« produits » les uns après les autres dès que ceux-ci sont délivrés. Ce comportement peut êtremodélisé par le RdP suivant :Page 3 sur 122008 2009

M1 Info Ing. Protocoles 2008 09(D'apres TD ENSEEIHT)P produit délivréréception produitModélisation du système global :Les communications entre les différents acteurs et machines étant asynchrones, le modèle globalest construit en fusionnant les places de même nom. Ce qui donne le modèle RdP suivant :envoi ordreP Idle execP Ordresdébut execP Execfin execP Idle envoiP produit prêt à envoyerdébut envoiP Envoifin envoiP produit délivréréception produitIl apparaît clairement que la place « P ordres » n’est pas bornée. De même, les places« P produit prêt à envoyer » et « P produit délivré » ne sont pas bornées (il est facile deconstruire un marquage M1 tel que M1(P Idle exec) 1, M1(P Idle envoi) 1,M1(P produit prêt à envoyer) 1 et M1(P produit délivré) 1 et M1(p) 0 pour toutes lesautres places p. Ce marquage est strictement supérieur au marquage initial, en particulier pourles places « P produit prêt à envoyer » et « P produit délivré », ce qui montre que ces placesne sont pas bornées.Ce caractère non borné traduit une incorrection dans la modélisation. Pour corriger ce problème,il est nécessaire d’introduire une capacité maximale pour ces places, capacités notéesrespectivement k1, k2 et k3, et introduire un mécanisme interdisant la production d’un ordre,d’un produit prêt à être envoyé, et d’un produit délivré, lorsque ces capacités sontrespectivement atteintes. Un tel mécanisme peut être modélisé par l’ajout de placessupplémentaires caractérisant les « cases » libres pouvant stocker des ordres, des produits prêtsà êtres envoyés, et des produits délivrés. Le modèle global est donné par le RdP suivant :Page 4 sur 122008 2009

M1 Info Ing. Protocoles 2008 09(D'apres TD ENSEEIHT)envoi ordreP Idle execP1 cases libresP Ordres(initialement,k1 jetons)début execP Execfin execP2 cases libresP Idle envoiP produit prêt à envoyer(initialement,k2 jetons)début envoiP EnvoiP3 cases libres(initialement,k3 jetons)fin envoiP produit délivréréception produitSelon ce nouveau modèle, l’acteur ordonnateur ne peut envoyer un ordre que s’il y a encore aumoins un jeton dans la place P1 cases-libres, c’est-à-dire s’il y a encore un espace pour stockercet ordre. De même pour la production d’un produit prêt à être envoyé et d’un produit délivré.Il est facile de voir que les couples de places (« P1 cases libres », « P ordres »),(« P2 cases libres »,« P produit prêt à envoyer »)et(« P3 cases libres »,« P produit délivré ») forme chacun des composantes conservatives positives. Le nombre dejetons contenus dans ces places est donc borné, et cette borne est donnée par le marquageinitial : le nombre maximum de jetons dans P ordres est k1 le nombre maximum de jetons dans P produit prêt à envoyer est k2 le nombre maximum de jetons dans P produit délivré est k3Question 1.2. Modélisation d’un atelier de fabricationOn suppose que les machines sont maintenant atomiques. Nous ne modéliserons donc plus à ceniveau le fonctionnement interne de chaque machine comme dans la question précédente, maisnous nous concentrerons en revanche sur le fonctionnement global de l’atelier.La première étape de l’atelier est composée de la machine M1 avec les deux opérateurs F1 etF2. A ce niveau, M1, F1 et F2 peuvent être modélisés comme des sémaphores, c’est-à-dire desressources libres ou utilisées. Cette étape peut être modélisée par le RdP suivant :Page 5 sur 122008 2009

M1 Info Ing. Protocoles 2008 09(D'apres TD ENSEEIHT)P F1P F1M1début exec M1F1envoi ordrefin exec M1F1P M1P ordres M2ouM3P ordres M1P F2M1début exec M1F2fin exec M1F2P F2L’envoi d’un ordre provoque la production d’un jeton dans la place P ordres M1 (notons quelà encore nous avons fait le choix d’une communication asynchrone entre l’atelier et l’acteurordonnateur externe). Ensuite, si la machine M1 est libre (un jeton dans P M1) et si l’opérateurF1 (resp. F2) est libre (un jeton dans P F1 (resp. dans P F2)), alors la transitiondébut exec M1F1 est franchissable, ce qui conduit à occuper M1 et F1 (resp. F2) (on retire lejeton dans P M1 et P F1 (resp. P F2)), et produire un jeton dans P M1F1 (resp. P M1F2). Enfin d’exécution, on rend à nouveau disponible la machine et l’opérateur en remettant un jetondans les places respectives, puis on produit un ordre vers la seconde étape de l’atelier (un jetondans P ordres M2ouM3).La seconde étape est à peu près similaire à la seconde, à ceci près qu’elle met en jeu deuxmachines M2 (opérateur F1) et M3 (opérateur F3). La encore F1, F2, M2 et M3 sont vuscomme des sémaphores :P F1début exec M2F1P F1M2fin exec M2F1envoi produitP M2P ordres M2ouM3début exec M3F2P produitsP M3P F2M3fin exec M3F2P F2Il est clair que les places « P ordres M1 », « P ordres M2ouM3 » et « P produits » ne sontpas bornées. Par corriger ce problème on applique la même méthode que dans la questionprécédente.Page 6 sur 122008 2009

M1 Info Ing. Protocoles 2008 09(D'apres TD ENSEEIHT)Question 2. Protocole Producteur ConsommateurQuestion 2.1. Médium buffer à une caseOn modélise séparément le producteur et le consommateur et fait fait l’hypothèse (naturelle) quele médium agit comme un buffer assurant une communication asynchrone entre le producteur etle consommateur.Modèle du producteur :P Idle prodactivation prodP Init prodP messages à émettrefin init prodP prêt à émettreP médium libre(initialement,N jetons)émission prodP médium occupé messageP messages émisP médium occupé déconnexionNdéconnexion prodP Off prodLe producteur, selon ce modèle, se comporte tout d’abord comme une séquence d’action(activation prod, puis fin init prod) pour arriver ensuite dans un état où il est prêt à émettre. Ilpeut alors émettre si le médium est libre (un jeton dans P médium libre), et s’il a encore unmessage à émettre. Notons que la place P messages à émettre contient autant de jeton que demessages à émettre, soit N jetons. Notons que nous ne modélisons pas explicitement lesmessages, mais uniquement le fait qu’un message soit être émis ou a déjà été émis. Après chaqueémission, on produit un jeton dans la place P message émis de manière à compter le nombre demessage produits, puis le processus revient dans l’état prêt à émettre puis recommence. Lorsquele nombre de messages émis est égal à N, c’est-à-dire lorsque tous les messages ont été émis,alors le processus émet un message de déconnexion (si le médium est libre bien entendu), puiss’arrête (arrivée dans la place P Off prod).Modèle du consommateur :Page 7 sur 122008 2009

M1 Info Ing. Protocoles 2008 09(D'apres TD ENSEEIHT)P Idle consactivation consP Init consfin init consP prêt à consommerP médium occupé messageconsommationP traitement consP médium librefin traitement consdéconnexion consP médium occupé déconnexionP Off consLa composition des deux modèles est obtenue par fusion des places de même nom. Dans lemodèle global ainsi construit, la synchronisation « lâche » entre le producteur et leconsommateur se fait par les places « P médium ». Le producteur ne peut émettre que si lemédium est libre, y compris un message de déconnexion, et le consommateur ne peutconsommer que si le médium est occupé, y compris par un message de déconnexion. Le médiumne contenant qu’une case, on peut être certain que le message de déconnexion n’arrivera qu’unefois que les messages de données auront été consommés par le consommateur. Dès que leconsommateur reçoit un message de déconnexion, il peut donc commencer sa procédure dedéconnexion.Question 2.2. Médium buffer à K casesModèle du producteur :Le modèle du producteur reste sans changement, mis à part le nombre de jeton dans la placeP médium libre qui passe de 1 à K. Chaque jeton dans cette place représente ainsi une case libredans le médium. Chaque jeton dans la place P médium occupé message représentera alors unmessage en transit dans le médium (il peut y en avoir simultanément K).Page 8 sur 122008 2009

M1 Info Ing. Protocoles 2008 09(D'apres TD ENSEEIHT)P Idle prodactivation prodP Init prodP messages à émettrefin init prodP médium libreP prêt à émettre(initialement,K jetons)(initialement,N jetons)émission prodP médium occupé messageP messages émisP médium occupé déconnexionNdéconnexion prodP Off prodModèle du consommateur :En revanche, le modèle du consommateur est légèrement différent. Parmi les messages en transitdans le médium peut figurer un message de déconnexion. Aucune hypothèse n’étant fait sur lemédium, il se peut que ce message transite sur le médium en même temps que des messages dedonnées (bien qu’il ait été émis après) puis double ces deniers. Le consommateur devra doncs’assurer, avant de consommer le message de déconnexion, qu’il a consommer tous les messagesde données, c’est-à-dire qu’il a vidé le médium de ces deniers. Pour ce faire, ne pouvant testerque la place P médium occupé message est vide, on testera que la place P médium librecontient K-1 cases libres (une place étant occupée par le message de déconnexion).Page 9 sur 122008 2009

M1 Info Ing. Protocoles 2008 09(D'apres TD ENSEEIHT)P Idle consactivation consP Init consfin init consP prêt à consommerP médium occupé messageconsommationP médium libreP traitement cons(initialement,K jetons)Kfin traitement consdéconnexion consK-1P Off consP médium occupé déconnexionLà encore le modèle global est obtenu par fusion des places de même nom. Dans le modèleglobal ainsi construit, la synchronisation « lâche » entre le producteur et le consommateur se faitpar les places « P médium ». Le producteur ne peut émettre que si le médium contient aumoins une place libre (au moins un jeton dans « P médium libre »), y compris un message dedéconnexion, et le consommateur ne peut consommer que si le médium contient au moins unmessage (au moins un jeton dans « P médium occupé »), y compris un message dedéconnexion. Le médium contenant plusieurs cases, on ne peut plus être certain que le messagede déconnexion arrivera après que les messages de données aient été consommés. Dès lors,lorsque le consommateur reçoit un message de déconnexion, il ne peut commencer sa procédurede déconnexion que si le médium est entièrement vide à l’exception du message de déconnexion(c’est-à-dire contient K-1 cases libres).Question 3. Un service d’établissement de connexionQuestion 3.1.L’entité appelante se considère connectée dès qu’elle a envoyé CR ; l’entité appelée estconnectée dès qu’elle a reçue CR. De même, l’entité appelante se considère déconnectée dèsqu’elle a envoyé DR ; l’entité appelée est connectée dès qu’elle a reçue DR.Selon ce protocole, il n’y a pas de synchronisation entre l’entité appelante et l’entité appelée.Le médium met en œuvre une communication asynchrone. Ce médium sera modélisé par uneplace dans laquelle l’entité appelante placera un jeton lorsqu’il émettra un (N)PDU, qui seraconsommé ensuite par l’entité appelée.Ce protocole peut être modélisé par le RdP suivant (protocole monodirectionnel, figure 3.1).Page 10 sur 122008 2009

M1 Info Ing. Protocoles 2008 09Entité appelante(D'apres TD ENSEEIHT)MédiumAppelant-IdleEntité téAppelant-connectéDR?DR!DR-envoyéfigure 3.1 : protocole monodirectionnelMalheureusement, ce modèle est non borné. Les places CR envoyé et DR envoyé peuventaccueillir un nombre quelconque non borné de jeton. Cela traduit en fait une carence au sein duprotocole qui est l’absence de synchronisation entre l’appelant et l’appelé. Ce protocole estdonc faux.Une correction possible peut consister en l’ajout d’un mécanisme d’acquittement. Chaquedemande de connexion et de déconnexion doit être acquittée avant d’être considérée commeeffective. Dans ce cas, l’appelant doit attendre l’acquittement avant de poursuivre sondéroulement. Ce protocole corrigé peut être modélisé par le RdP figure 3.2 (protocolemonodirectionnel corrigé).figure 3.2 : protocole monodirectionnel corrigéCe réseau est borné. Ce résultat peut être obtenu en montrant que ce RdP contient troiscomposantes conservatives positives qui le recouvrent entièrement (elles correspondent auxtrois cycles dans le RdP). Ces composantes sont : {Appelant Idle, Appelant attente1, Appelant connecté, Appelant attente2} {Appelé Idle, Appelé trait1, Appelé connecté, Appelé trait2} {Appelant Idle, CR envoyé, Appelé trait1, Ack CR envoyé, Appelant connecté, DR envoyé, Appelé trait2, Ack DR envoyé}Les entités sont maintenant correctement synchronisées.Question 3.2.On complète maintenant le protocole pour que les deux entités puissent être à l’origine de lademande de connexion. Elles sont donc maintenant symétriques.L’opération de connexion et de déconnexion étant similaires, on ne traitera que la première.Une première solution pourrait consister en la généralisation du modèle précédent. Danschaque entité, on modélise une branche demandant la connexion, et une l’attendant (figure 3.3protocole bidirectionnel).Page 11 sur 122008 2009

M1 Info Ing. Protocoles 2008 09(D'apres TD ENSEEIHT)figure 3.3 : protocole bidirectionnelSelon ce modèle, chaque entité peut demander la connexion puis se synchronise avec l’autreentité sur l’attente de l’acquittement de connexion.Toutefois, ce modèle présente une situation de blocage. Cette situation survient lorsque lesdeux entités demandent la connexion en même temps. Dans ce cas, A franchit la transition A CR! puis attend un jeton d’acquittement. Dans le même temps B franchit la transition B CR!puis attend également un jeton d’acquittement. Chaque entité se retrouve en attente d’unacquittement et ne peut donc plus recevoir la demande de connexion émise, et a fortioril’acquitter. Il s’agit d’une situation de deadlock du protocole, révélée par une situation deblocage du modèle RdP.On peut corriger ce protocole par un mécanisme de « poignée de main ». En cas de demande deconnexion simultanée, chaque entité considèrera la demande de l’autre entité comme unacquittement de sa propre demande, et donc passera dans le mode connecté. Cette correctionpeut être modélisée par le RdP figure 3.4 (protocole bidirectionnel corrigé). Sur cette figure, lacorrection apportée consiste en l’ajout de deux transtions (une dans chaque entité). Ces ajoutssont dessinés en trait fort.Entité AMédiumA-IdleEntité ?B-connectéA-connecté figure 3.4 : protocole bidirectionnel corrigéPage 12 sur 122008 2009

Travaux Dirigés n 1 Ingénierie des protocoles - Réseaux de Petri Correction Question 1. Modélisation d’un atelier de fabrication Question 1.1. Modélisation d’une machine de fabrication simple Considérons une première analyse du système selon une approche à la UML. Le diagramme des

Related Documents:

Ce polycopi e rassemble les cours et travaux dirig es (avec corrig es) du module Algorithmique de l'ENS Lyon. A l'origine pr evu pour la premi ere ann ee du Magist ere d'Informatique, le module s'int egre d esormais dans la troisi eme ann ee de la Licence d'Informatique. Et dire que personne ne s'est rendu compte du changement!

CCTP VRD 21-févr.-14 3 I. ETENDUE DES TRAVAUX – REGLEMENTATIONS – NORMES 1. Etendue des travaux Les travaux à réaliser par l'entreprise dans le cadre du présent C.C.T.P. sont essentiellement les suivants : Travaux de VRD, terrassement et aménagement des espaces extérieurs sur l’ensemble des

Th eor eme d’Amp ere TD.8. Induction Enonc es des travaux dirig es, corrig es de certains exerc ices, annales (partiels et examens des . D eterminer l’intensit e et la direction du champ electrostatique au centre de ce carr e Oet au point P, milieu du segment ( q,q

Éditions Nathan 2012 5 Activité 2 Pendant la lecture des Douze travaux d’Hercule Dominante : Lecture / Oral Objectif : Aider les petits lecteurs à connaître l’œuvre Support: Christian Grenier, Les douze travaux d’Hercule : pp. 65-245. Compétence 1: maîtrise de la langue française, item 1-4 : « Dégager, par écrit ou oralement, l’essentiel d’un texte lu » et item 1-5 .

Le plan de ges-tion des répercussions des travaux sur la circulation doit être préparé ainsi que le plan de signalisa-tion de travaux. Enfin, les principaux travaux prévus dans les plans et devis préliminaires sont sou- . Les étapes de réalisation d’un projet routier . Boul. McConnell-Laramée / Gatineau 3Construction d’un .

comptables en référence à une seule norme internationale a conduit les comptables du . Constatation du stock final des travaux . Compte de résultat au 31/12/N . Charges par nature 9000 5 Trésorerie 9000 Charges engagées 31/12/N 1 31341 Travaux en cours 9000 71341 Variations des stocks de travaux 9000 .

la bibliographie (ou la médiagraphie). Pour les travaux manuscrits, plusieurs enseignantes et enseignants exigent l'interligne double. 4 Marges Pour les travaux effectués au traitement de texte, la valeur des marges doit rtre d'environ 3 cm à gauche et à droite, et d'environ 2,5 cm en haut et en bas.

Guide de présentation formelle des travaux écrits Ce guide aide les étudiant·e·s à réaliser leurs travaux en respectant les directives concernant . noms du/de la deuxième auteur·trice (il s'agit de garder l'ordre des auteur·trice tel il/elle apparaît dans la source) ; Charlier, B. (1998).