OSGI : Architecture

Nous avions vu dans un précédent article ce qu'était OSGI dans ses grandes lignes et ses principaux concepts [uetteu-osgi]. Dans celui ci, je vous propose de rentrer un peu plus dans le côté technique de cette technologie en détaillant globalement les utilisations de celle ci (surtout pour rappel), d’identifier son écosystème et ensuite de passer en revue la construction des bundles, leur constitution, leur cycle de vie et la déclaration et consommation des services.

À la suite de cela, nous nous intéresserons alors aux différents implémentations du framework réalisé au fil de ces dernières années pour enfin étudier (sommairement) leur différentes intégrations au sein des serveurs d’application Java les plus connu (à notre insu)

Architecture: Vue d’ensemble

Nous avions vu dans ce dernier article [uetteu-osgi] que OSGI était un framework Java modulaire orienté service permettant la modélisation et l'exécution de composants nommés bundle.

Ils permettent à mise en oeuvre d’application dans des contextes d'équipement à ressources limitées, s’appuient sur un modèle de collaboration utilisant une registry pour le partage de services et facilitant l'accès à ces derniers pour les consommateurs.

OSGI permet aussi une gestion à chaud de ses bundles offrant ainsi la possibilité de chargement, mise à jour et déchargement de fonctionnalité dynamiquement sans interruption de service.

Enfin OSGI offre un cycle de vie fourni un cycle de vie à ces bundles et services (que nous verrons dans un des chapitres suivant) permettant la mise en oeuvre d’une gestion intelligente des fonctionnalités mis en ligne.

C’est pour ces différentes raisons que OSGI est aujourd’hui intégrée par défaut dans la grande majorité des serveurs d’applications JEE permettant l’ajout de fonctionnalité java standard de manière plus aisé et ce même dans un contexte JEE.

Environnement d'exécution

De par son côté modulaire, OSGI offre donc la possibilité de construire des applications via une logique de puzzle où de briques, constitué selon des niveaux fonctionnelles différentes. Cette approche a donc permis de constituer un catalogue riche et varié de bundles offrant une multitude de services métiers et ou technique [tuto-osgi-oscar].

On trouvera ainsi facilement sous la forme de bundle des

• services de base permettant l’utilisation de logs
• bundle de gestion de configuration
• bundles de gestions de Préférences
• Services HTTP (e.g :servlets, ou Spark [uetteu-spark]))
• Gestion des utilisateurs
• Parseurs XML
• Gestion de droits,
• Politique de sécurité
• Monitoring
• de l'intégration JEE [integ-jee]
• …

Supervisory Control Theory

Introduction

Supervisory Control Theory ou théorie de la supervision des systèmes à évènements discrets introduit par P.J.Ramadge et W.M.Wonham [1] se base sur la théorie des langages et des automates [10]. Elle définit l’utilisation de trois entités : le SED, une spécification souhaitée et un superviseur. Cette théorie définit la possibilité de synthétiser un modèle de superviseur dit valide à partir du modèle du SED et de la spécification. Le premier objectif de cette démarche est de fiabiliser un système susceptible d’avoir un comportement qui peut être gênant ou dangereux. Le deuxième objectif est la possibilité pour un système dit ouvert, dont les comportements possibles sont multiples, de réaliser différents superviseurs dont les rôles seront de contraindre le système dans un comportement donné pour un contexte donné.

Principe de la théorie de la supervision

La théorie  de la supervision définit que ces trois entités, le SED, la spécification souhaitée et le superviseur sont modélisés par leurs langages conformément à la théorie des langages et des automates. Ceci permet de bénéficier des opérations liées aux langages et aux automates à états finis puisque les langages utilisés sont des langages réguliers. Dans l’ensemble de ce chapitre, ces entités sont considérées comme des automates notés G pour le système, K pour la spécification et S pour le superviseur de langage respectif L(G), L(K) et L(S).


Idéalement, le superviseur, une fois réalisé, est composé avec le SED pour former le système supervisé. A chaque changement d’état du système, le superviseur va suivre l’évolution du système et lui notifier l’ensemble des évènements qu’il est autorisé à générer (figure 35). Cependant, deux situations prises en compte par la théorie peuvent survenir. La première est que certains évènements, par nature, ne peuvent pas être interdits. La seconde situation est que certaines transitions du système ne peuvent être vues par le superviseur, l’empêchant de fournir un ensemble d’évènements autorisés cohérent. Ces deux situations sont définies dans la théorie de la supervision sous les notions de commandabilité et d’observabilité. Ainsi, un alphabet  est divisé en plusieurs ensembles notés c pour l'alphabet des évènements commandables, uc l'alphabet des évènements non commandable, o l'alphabet des évènements observables et uo l'alphabet des évènements non observables tel que

ce qui signifie qu'un évènement peut être à la fois non commandable et non observable, commandable et non observable, observable mais non commandable ou enfin commandable et observable. Ces notions de commandabilité et d'observabilité sont très importantes car elles vont conditionner les limites du superviseur et sa réalisation. De nombreux travaux approfondissent ces notions dans [1], [3], [5], [6].
Pour la réalisation du système supervisé, la théorie de la supervision définit que le modèle du superviseur, donc le langage L(S), peut être concrétisé par une fonction ou une table d'associations qui à une séquence d'évènements donnée renvoie une liste d'évènements autorisés. Une autre approche, illustrée par la figure 36, utilise l’intersection (ou le produit strict pour les automates) du langage du système et celui du superviseur afin d’obtenir le langage du système supervisé. Ainsi, le modèle du système supervisé est obtenu par:





La théorie de la supervision définit enfin la notion de superviseur bloquant par L(S/G)=Lmpréf(S/G).

Définition d'une spécification

La définition de la spécification est l'opération la plus difficile pour la théorie de la supervision car celle-ci doit répondre à différents critères afin d'être utilisable pour la génération du superviseur [1], [9]. Le but de la spécification est de définir le comportement du système bouclé, ainsi, si K est un automate décrivant la spécification valide, il faut avoir L(K)=L(S/G), comme illustré par la figure 37.




Pour cela, une méthode consiste à définir une première spécification par un automate E en considérant le comportement global voulu en s'intéressant à tous les évènements présents dans le système. Il est possible de réaliser l'opération de produit synchronisé de façon à obtenir L(K) qui sera égal à l'intersection de L(E) et de L(G), comme illustré par la figure 38.




Une autre méthode permet de définir le comportement voulu en ne considérant que certains évènements. Cependant, la spécification E doit être augmentée afin de correspondre au système. Ainsi, l'opération de produit synchronisé permet d'obtenir cette spécification (illustré par la figure 39). Cette méthode a pour avantage d’être simple mais elle implique une attention particulière aux évènements non utilisés pour la définition de E à cause du produit synchronisé qui va augmenter son langage.





L’opération de produit synchronisé est alors utilisée dans les deux cas tels que : K=G||sE car dans la première approche cela amène à faire un produit strict puisque E et G ont le même alphabet, dans la deuxième approche, cela va permettre l'augmentation du langage de E sur la considération du comportement intrinsèque de G. Enfin, il est nécessaire de valider la spécification K obtenue pour le système en vérifiant que celle-ci est non bloquante.

Une autre approche est de définir un automate qui invalide une séquence donnée. Ainsi, un automate est réalisé pour modéliser cette séquence dont tous les états sont marqués sauf le dernier qui représente la survenue de l'évènement qui réalise la séquence comme illustré par la figure 40. Ceci permet de réaliser des spécifications ciblées pour certains cas précis.





Il faut retenir que la théorie de la supervision ne fait pas état de méthode générique pour la définition de spécification. Chose qui n'est d'ailleurs pas son objectif puisque son but n'est que la synthèse d'un superviseur par la validation de la spécification K souhaitée sur le principe du blocage et de l'inclusion dans le langage de SED G. La réalisation d'une spécification reste donc un problème dans la démarche de synthèse de superviseur.

Synthèse du superviseur

La spécification étant définie, la synthèse du superviseur selon [1], [10] s’effectue par le produit du système G et de la spécification K suivi de l’opération Trim. Ceci est la base de la démarche pour la synthèse du superviseur mais elle ne prend pas en compte les aspects liés à la commandabilité et à l’observabilité des évènements. Cette opération de base s’explique par la relation

qui existe entre le superviseur, la spécification et le système, comme ré-illustré par la figure 41. Cette relation signifie que la spécification est l’objectif du système supervisé par l’égalité L(S/G)=L(K). Elle signifie également que le  langage du superviseur ne se limite pas nécessairement au langage de la spécification.

Commandabilité et Observabilité dans la synthèse du superviseur

Les notions de commandabilité et d’observabilité du superviseur pour le système sont liées aux événements commandables et observables. La nature de ces événements amène des particularités dans la relation entre le système et le superviseur lors de la supervision. Les événements non commandables ne peuvent pas être interdits par le superviseur et le système sera toujours susceptible de les réaliser. Les événements non observables ne permettent pas au superviseur de suivre l’évolution du système de manière cohérente. Le superviseur est alors susceptible après la survenue d’un évènement non observable de fournir une commande erronée.

Problèmes liés à la commandabilité

Comme il a été dit précédemment, les évènements non commandables ne peuvent pas être interdit pas le superviseur. Cette particularité, si elle n’est pas prise en compte lors de la synthèse amène à la réalisation d’un superviseur qui composé avec le système sera susceptible de violer la spécification comme illustré par la figure 42.



Pour prendre en compte cette particularité, la spécification est alors l’élément sur lequel vont intervenir les éventuelles corrections pour que la synthèse donne un superviseur commandable. La théorie de la supervision définit alors une spécification comme étant commandable si


Si la spécification n’est pas commandable, alors la théorie de la supervision définit qu'il existe un langage suprême commandable L(K') inclus dans L(K) qui est commandable (illustré par la figure 43). Ce langage est obtenu à l’aide de l’algorithme de Kumar [5]. Cet algorithme identifie dans l’automate K les états à partir desquels, dans le système, des évènements non commandables sont susceptibles d’être générés.

Problémes liés à l’observabilité

La notion d’observabilité caractérise les évènements de l’alphabet selon deux types, les évènements observables et les évènements non observables. Lors de la supervision, à chaque changement d’état du système, le superviseur, par la lecture de l’évènement qui vient d’être réalisé, est mis à jour afin de produire un nouvel ensemble d’évènements autorisés. Lors de la survenue d’un évènement non observable, le superviseur n’est pas notifié du changement d’état du système et n’est pas capable de fournir un ensemble d’évènements autorisés cohérent. Pour cela, la théorie de la supervision impose que la commande souhaitée pour le système soit la même avant et après un évènement non observable sinon le superviseur synthétisé sera non observable et la spécification risque alors d’être violée comme l’illustre les figures 44 et 45.

Exemple:
En considérant "c" comme étant non observable, si l'état 4 est interdit dans le système G alors il y a un problème d'observabilité dans la spécification K qui définit une commande différente avant et après l’évènement non observable. Un superviseur ne pourra donc pas savoir s'il se trouve dans l'état 1 ou l'état 3.








La théorie de la supervision caractérise alors la spécification K comme étant observable si elle permet la synthèse d’un superviseur observable. Si K n’est pas observable alors, contrairement à la notion de commandabilité, il n’existe pas de langage suprême observable qui puisse être calculé. Dans pareil cas, il est nécessaire de se rattacher à la notion de normalité.

Normalité et observabilité

La normalité, c’est l’invariance d’un langage par rapport à un autre suivant un alphabet donné. La normalité permet de vérifier qu’un langage prend en compte tous les évènements contenus dans un alphabet pour un autre langage. Dans le cadre de la théorie de la supervision, la normalité est rapprochée de l’observabilité en définissant l’alphabet intéressant comme étant celui des évènements non observables. Ainsi, la spécification K est définie comme normale pour le système G et pour les évènements non observable si :

La notion de normalité décrite dans [1] et [11] est très pratique car elle permet d'assimiler la notion d'observabilité. En fait, si un langage est normal alors il est observable et de plus il est possible de la même manière que pour la commandabilité de construire un langage suprême normal (cf. algorithme de Kumar [5]) si K n'est pas normal. A cela, il faut tout de même observer quelques restrictions, c'est à dire qu'il faut considérer les évènements non observables comme étant non commadables et ainsi il y a équivalence entre observabilité et normalité.

Supervision modulaire

La supervision modulaire, illustrée à la figure 46 et définie dans [1], [6], [11], [12] a pour intérêt de diviser le problème de la définition de la spécification en plusieurs modules. Pour un système G, n spécifications K seront définies qui permettront la génération de n superviseurs. Ceci permet de limiter la taille et la complexité de la spécification globale si plusieurs objectifs de commandes sont à réaliser. L'intersection des n superviseurs donnera alors le superviseur global. Les spécifications ne doivent pas être en conflit sinon le superviseur sera bloquant. Ainsi, si pour K1 et K2, deux spécifications, l'égalité

 
est respectée alors elles ne sont pas en conflits. Si K1 et K2 sont commandables alors leur intersection l'est aussi sinon leur langage suprême commandable l'est. Pour l'observabilité, il faut utiliser la notion de normalité afin d'obtenir un langage normal pour que le superviseur soit observable.

Supervision décentralisée

La supervision décentralisée [1], [11], [12], illustrée à la figure 47, propose de voir le système sous plusieurs points de vues locaux (en utilisant la projection) et de définir pour chaque point de vue une spécification restreinte afin de générer un superviseur local. Chaque superviseur aura la responsabilité de la gestion d'un sous-ensemble de l'alphabet du système, ces différents sous-ensembles de l’alphabet ne devant pas avoir d’intersection non vide sans un risque de conflit entre les différents superviseurs. Pour le superviseur généré en local, la supervision du système G revient à considérer les évènements supprimés par la projection comme non observables. Il ne va donc s'intéresser qu'à l'aspect du système pour lequel il a été conçu.





La conjonction des différents superviseurs va être réalisée par l'intersection des différents superviseurs en ayant réalisée une projection inverse sur l'ensemble de l'alphabet afin de préserver leurs comportements respectifs. Il faut cependant rester prudent car, si par l'utilisation de la supervision décentralisée il est possible de simplifier localement le problème en plusieurs sous système, la supervision ne prendra pas en compte les interactions possibles entre ces sous systèmes et ces dernières ne pourront pas être supervisées.

Conclusions

La théorie de la supervision donne un cadre théorique idéal pour la modélisation et la commande de systèmes à évènements discrets par la génération d'un superviseur valide en prenant en compte de nombreux aspects susceptibles de poser des problèmes tels que ceux liés aux événements non commandables ou non observables. Ceci reste un cadre théorique qui ne prend pas en compte les problèmes liés à l'implantation d'un superviseur dans un environnement d’exécution. Cet environnement n’est pas défini dans le cadre théorique de la supervision mais importe pourtant dans la réalisation de modèles de SED cohérents et dans la manière dont le ciblage sera effectué. Pour cela, l'ingénierie dirigée par les modèles propose une approche pour la définition et la transformation de modèles et établit alors comment réaliser et cibler un système supervisé dans un environnement d'exécution spécifique.

Références

[1] Ramadge P.J., Wonham W.M. The control of discrete-event systems. IEEE Transactions on Automatic Control, 1989, Vol. 77, N° 1, p. 81-98.

[3] V. K. Garg, R. Kumar, S. I. Marcus. On controllability and Normality of discrete event dynamical systems. Systems and control letters, 1991, Vol. 13, N°3, p. 157-168.

[5] R. Kumar, M. A. Shayman. Formulae relating controllability, observability and Co-observability. Automatica, 1998, Vol. 34, p. 211-215.

[6] H. Flordal. Modular controllability verification and synthesis of discrete event systems, Mémoire de these, Chalmers University of Technology, 2001.

[9] A. Overkamp, and J. H. van Schuppen. Control of discrete event systems. Amsterdam (NL), Stichting Mathematisch Centrum, 1994 p. 453-467.

[10] C. G. Cassandras, and S. Lafortune. Introduction to discrete event systems, Kluwer Academic Publishers, 1999, ISBN: 0-7923-8609-4.

[11] M. H. Lamouchi. Synthèse de superviseur pour des systèmes à évènements discrets partiellement observés,  Mémoire de thèse, Université de Montréal, département de génie électrique et de génie informatique de l'école polytechnique de Montréal, 2002.

[12] B. Gaudin. Synthèse de contrôleurs sur des systèmes à évènements discrets structurés. Mémoire de thèse, Université de Rennes, Institut de Formation Supérieure en Informatique et Communication, 2004.

Finite State Machine

Dans l'article sur les SED , nous avons vu que les langages offrent un cadre théorique éprouvé, pour la modélisation et la manipulation des systèmes à événements discrets. Cependant, l’utilisation et la manipulation directe des ensembles décrivant les langages n'est pas réaliste. Ainsi, il est nécessaire d’expliquer les notions liées aux automates à états, modèles des langages, qui sont plus concrets et plus faciles à manipuler.

Les automates à états sont, par définition, des outils mathématiques permettant la modélisation et la manipulation de langages décrivant le comportement des SED. Ils peuvent avoir une représentation graphique grâce aux diagrammes à états permettant une analyse visuelle. 

Un automate à état, est un n-uplet noté G=(X, S,  f,  x0, Xm) tel que :

·         X : Ensemble des états de l’automate.

·         S : Alphabet ou ensemble des événements réalisables par l’automate.

·         f : Relation de transition qui définit pour un état courant et un événement appartenant à l’alphabet un second état qui devient l’état courant.

·         x0 : l’état initial de l’automate

·         Xm : l’ensemble des états marqués de l’automate permettant la validation de séquence d’événements.

Exemple:Si G un automate tel que : 

     X = {0,1,2} 

     S = {a,b,c} 

     f = {(0,a)->1,(1,b)->0,(1,c)->1,(0,c)->2} 

     x0= 0 

     Xm= {1} 

Ce type d’automate est très général et peut avoir un nombre infini d’états empêchant une implémentation concrète. Dans cette étude on se limite aux automates à états finis qui se caractérisent par le fait que l'ensemble des états doit être fini. Les automates à états finis sont des implantations pour les langages dits réguliers

Langage des automates à états finis

Un automate à états finis décrit deux langages, comme illustré par la figure 8. Le premier langage est dit le langage généré par l’automate. Il correspond à toutes les possibilités de transitions offertes par la relation de transition. Le second langage est le langage marqué, il correspond à la réalisation de toutes les possibilités de transitions offertes par la relation de transition menant à un état final marqué. Le marquage est utile dans le cadre de la définition de comportements valides pour l’automate.



L’utilisation d'un automate à états finis permet de voir un SED dans sa globalité grâce au langage généré mais aussi de voir ce SED dans son comportement souhaité via le langage marqué. La différence entre ces deux langages permet de définir le langage bloquant de l’automate. En effet, le langage marqué est inclus ou égal au langage généré de l’automate. La caractérisation du langage bloquant d’un automate est alors mise en évidence par la différence des langages marqués et générés comme cela est illustré par la figure 9. Mathématiquement, pour un automate G, avec L(G) son langage généré et Lm(G) son langage marqué, l’automate est bloquant si  Lmpréf(G) inclu dans L(G). Il est non bloquant si Lmpréf(G)=L(G).

Exemple:Si G un automate, illustré en figurer 10, tel que: 

X  = {0,1,2} 

  = {a,b,c} 

f  = {(0,a)->1,(1,b)->1,(0,c)->2} 

x0 = 0 

Xm = {1} 

On a:

L(G) = {epsilon, c, ab*}
Lm(G) = {ab*}
Lmpréf(G) = {epsilon, ab*}Et Lmpréf(G) inclu dans L(G) donc G est bloquant (voir figure 10)

Opérations sur les automates à états finis

Les automates d’états finis étant les modèles des langages réguliers, toutes les opérations présentées sur les langages leur sont applicables. Certaines variations existent dans les termes utilisés pour les nommer. Il est donc nécessaire de les présenter dans le détail afin de clarifier la dénomination utilisée.

Calcul de la partie accessible : L'opération calculant la partie accessible d'un automate supprime les états dans l'automate à la suite d’une séquence d’évènements.
Calcul de la partie coaccessible : L'opération de permet de rendre non bloquant un automate bloquant en supprimant les états à partir desquels il n’existe pas de séquences d’évènements permettant d’atteindre un état marqué.

Opération Trim

L’opération Trim réalise successivement les opérations d'accessibilité et de coaccessibilité ou inversement. Cette opération est importante car elle permet de rendre le langage généré de l'automate égal à la fermeture préfixée du langage marqué. (L(G)=Lmpréf(G))

Exemple:
Dans l’automate G, illustrée par la figure 11, l'état 3 n'est pas accessible et l'état 2 ne permet pas d'accéder à un état marqué. Via l'opération Trim, ces états seront supprimés (figure 12)

Projection

La projection d'un automate est directement issue de la projection des langages puisqu'un automate est le modèle d'un langage. Même si le mécanisme reste le même au niveau langage, il est un peu plus complexe à mettre en œuvre au niveau d'un automate. Pour projeter un automate, il faut identifier les transitions à supprimer et ensuite raccorder les états afin de restaurer le langage projeté.

Exemple:
La projection, illustrée par les figures 13 et 14, de l’automate G de langage L(G)={bd,abc} sur l’alphabet ={b,d} renvoie un automate dont le langage est P(L,)={b,bd} conforme à la projection définie pour les langages.



Remarque:
Le résultat peut donner un automate à états finis non déterministe. En effet, sur la figure 14 de l’exemple, l’état 0 génère un événement b menant à l’état 2 et 4.
La projection peut rendre des états non atteignables.

Projection inverse

De la même façon que la projection inverse d'un langage, sur un automate cette opération va compléter chaque état avec les événements non présents dans l'alphabet de l'automate.

Exemple:
La projection inverse, illustrée par les figures 15 et 16, d’un automate G de langage L(G)={ab} définit sur l’alphabet ={a,c} renvoie un automate G’ de langage L(G')={c*ac*bc*}.



Il faut noter que l’évènement "a" faisant déjà partie de l'alphabet n'a pas fait l'objet de l'opération de projection inverse. En terme de SED et d'état, cela signifie que "a" est une action importante qui ne peut être ignorée, contrairement à l’événement "c" qui sera ignoré (en terme d’évolution de l’automate, pas en terme de langage) puisqu'il reste dans l'état courant.

Union

L’union fusionne les états initiaux des différents automates réalisant ainsi l'union des langages. Cette opération peut également amener à un automate non déterministe si les états initiaux génèrent des évènements identiques, comme illustré par les figures 17, 18 et 19.

Exemple:

Produit libre

Le produit libre entre automates permet la fusion de leur langage, cela signifie qu’il est toujours possible d’évoluer à chaque instant dans l’automate résultant de cette opération, de la même façon que les automates d’origines fonctionnant en parallèle. En terme de SED, cela correspond à la visualisation de deux systèmes fonctionnant en parallèle sans communication ni synchronisation. Le langage résultant de cette opération est donc bien plus important que leur simple somme qui correspondrait plutôt à l'union. Ainsi cette opération met en évidence que la modélisation des SED devient rapidement complexe dès que de nombreux systèmes mis en parallèles sont modélisés. Le produit libre est  illustré en figure 20 montrant toutes les combinaisons des deux automates, il est noté ||.




Exemple:
Cet exemple illustre plus concrètement le produit libre de deux automates, G1 (figure 21) et G2 (figure 22). La figure 23 illustre la complexité du résultat des deux automates (de l’ordre n*m, n étant le nombre d’états du premier automate et m celui du second).

Produit strict 

Le produit strict (ou produit cartésien dans la littérature [10], [1]) est une opération permettant de réaliser l'intersection des langages. Comme illustré par les figures 24, 25 et 26, cette opération réalise le produit cartésien des états et relie ces derniers sur les transitions communes aux différents automates.

En terme de SED, le produit strict représente la synchronisation totale des systèmes. Ils doivent réaliser les mêmes actions en même temps, si cela n'est pas possible alors aucune action n'est réalisée. Le produit strict est noté x.

Exemple:

Produit synchronisé

Le produit synchronisé est un produit permettant de modéliser le comportement de plusieurs SED mis en parallèle (comme pour le produit libre). Les automates dont certains événements de leur alphabet sont synchronisés transitent ensemble sur ces derniers, les autres évènements restant libres. Plusieurs cas sont à prendre en compte. Si les alphabets sont totalement disjoints, le produit synchronisé revient à la réalisation d'un produit libre. Si les alphabets sont égaux, le produit synchronisé revient à la réalisation d'un produit strict. Si les alphabets ont une intersection non vide alors la combinaison des deux opérations (libre et strict) est réalisée puisque le comportement commun est extrait sur les évènements communs, et les comportements libres des automates sont ajoutés pour les évènements non communs.

Le produit synchronisé a la particularité d’être réalisable à partir d’opérations déjà définies comme la projection inverse et le produit strict, comme illustré par les figures 27, 28 et 29. Si L1 et L2 sont deux langages alors L3=intersect(IP(L1,2),IP(L2,1)) est le produit synchronisé. Pour plus de souplesse, ce produit est noté      L3=L1 ||s L2. Il est nécessaire de préciser que la manipulation des alphabets permet de modifier la configuration du produit synchrone et donc son résultat, un événement défini dans l'alphabet ne se trouve pas forcement dans la relation de transition de l'automate, comme illustré par les figures 30, 31 et 32.

Exemple:
Si L1(G1)={(ab)*} et L2(G2)={(ac)*} avec 1={a,b} et 2={a,c} alors L(G1||sG2)=intersect(IP(L1,2),IP(L2,1))={(a(bc|cb))*}




Par contre, si 1={a,b,c} et 2={a,c,b} avec L1(G1)={(ab)*} et L2(G2)={(ac)*} alors L3=interssect(IP(L1,2),IP(L2,1))={a} c’est à dire le produit strict.

Remarque sur les automates d’états finis non déterministes

Le problème du déterminisme dans les automates à états apparaît dans de nombreuses opérations comme celle de projection ou d’union ou encore du produit libre. Le non-déterminisme d’un automate est caractérisé par une particularité dans la relation de transition. Cette particularité est que pour un état et un évènement donné, la relation de transition donne deux états possibles. Dans le cadre d’une implémentation et d‘une exécution, il est impossible de définir dans quel état se trouve l’automate.

En terme de langage, la notion de déterminisme n’existe pas [1] et [10], par contre la théorie des langages définis que s’il existe plusieurs automates modèles d’un même langage, ces derniers peuvent être déterministes ou non. Il existe une relation d’équivalence (en terme de langage) entre ces automates permettant de transformer un automate non déterministe en un automate déterministe tout en préservant le langage comme illustré par les figures 33 et 34. Il est nécessaire de noter qu’un automate possédant plusieurs états initiaux est considéré comme non déterministe car il est possible de construire un état initial  à partir duquel partiront des transitions epsilons allant vers chaque état initial de l’automate.

Exemple :

Conclusions

La théorie des langages et des automates à états offre un cadre idéal à la modélisation et à la manipulation des SED grâce aux diverses opérations comme le produit synchronisé ou celles issues de la théorie des ensembles comme l’union, le produit strict etc. De nombreuses particularités sont aussi à prendre en compte afin de rester dans un cadre d’implémentation réalisable comme les problèmes liés au non-déterminisme ou la nécessité d’utiliser les langages réguliers et les automates à états finis. Les éléments présenté dans ce chapitre sont les bases essentielles à l’étude de la théorie de la supervision définie par P.J.Ramadge et W.M.Wonham.

References

[1] Ramadge P.J., Wonham W.M. The control of discrete-event systems. IEEE Transactions on Automatic Control, 1989, Vol. 77, N° 1, p. 81-98.

[10] C. G. Cassandras, and S. Lafortune. Introduction to discrete event systems, Kluwer Academic Publishers, 1999, ISBN: 0-7923-8609-4

Systèmes à événements discrets

Les systèmes à événements discrets (SED) sont des systèmes caractérisés par une structure à états et à transitions étiquetées par des événements. L’exécution d’un SED se déroule par la génération d’un événement lors du passage d’un état à un autre via une transition donnée. L’ensemble des événements réalisables par le SED est appelé alphabet et la génération successive de plusieurs événements de cet alphabet défini un mot ou une chaîne d’actions. Un SED peut être modélisé par un langage ou par un automate à états. Un automate est également le modèle d'un langage.

Le langage

Pour comprendre les notions liées à la théorie de la supervision, il est nécessaire de présenter celles liées à la théorie des langages. La théorie des langages est fondée sur la théorie des ensembles. Il s’agit donc d’une théorie éprouvée pour la modélisation et la manipulation des SED. Un langage est composé de deux ensembles, un alphabet noté S et un ensemble de mots noté L. L’alphabet est constitué de l'ensemble des événements ou des actions réalisables par le SED. La concaténation des éléments de l’alphabet forme des mots ou traces qui sont des modèles de séquences d’événements ou séquences d’actions. La théorie des langages définit e qui représente à la fois la chaîne vide et l’événement vide.

Exemple:

Soit S={a,b,c,d} et L={ab,bc}, le langage de L définit sur S compte les 2 mots ab et bc.

Opérations sur les langages

La théorie des langages étant fondée sur la théorie des ensembles, elle bénéficie des opérations telles que l’union, l’intersection, la différence etc. De façon à rester cohérent avec la théorie de la supervision, seules les opérations fondamentales sont présentées.

Fermeture de kleene

La fermeture de Kleene d'un langage consiste en la réalisation d'un langage noté S* modélisant toutes les combinaisons d'événements possibles à partir de S incluant la chaîne vide e.

Exemple:

Si S={a,b}; L={ab,bc} alors S*=(a|b)* (le symbole * sur un événement signifie que ce dernier peut apparaître de 0 à n fois. Le langage constitué de L'=a* équivaut à L'={e,a,aa,aaa,aaaa,aaaaaa,…})

 Fermeture préfixée

La fermeture préfixée est l'augmentation du langage à l'aide de tous les préfixes des mots contenus dans le langage incluant e. Le préfixe d’un mot est une partie antécédente du mot qui n’est pas e.

Exemple:

Si S={a,b,c}; L={ab,bc}  alors Lpréf={e,a,b,ab,bc}

Union

L'union est l’opération permettant de mettre dans un seul langage l’ensemble des mots des différents langages.

Exemple:

Si S1={a,b,c}; L1={ab,bc} et S2={a,b,y,z}; L2={ab,yz} alors, L1 U L2 = L3 tel que : S3={a,b,c,d,y,z}; L3={ab,bc,yz}

L'intersection

L'intersection est une opération permettant de créer un langage à partir des mots se trouvant dans les deux langages.

Exemple:

Si S1={a,b,c}; L1={ab,bc} et S2={a,b,c,d}; L2={ab,bbd,dc} alors, INTER(L1,L2) =L3 tel que : S3={a,b}; L3={ab,b}

Le complement

Le complément d'un langage L1 correspond au langage L2 = L1comp contenant tous les mots réalisables avec l'alphabet de L1 moins les traces de L1. Mathématiquement, cela correspond à réaliser L2=S1*-L1.

Exemple:

Si S1={a}; L1={aa} alors L1comp=L2={a|aaa(a)* }

 La projection

L'opération de projection d'un langage s'effectue par rapport à un alphabet de projection, ce dernier étant inclus ou égal à l’alphabet du langage. Cette opération est assimilable à un filtrage sur les événements contenus dans les mots du langage. Les événements restant dans les mots étant les événements présents dans l’alphabet de projection.

Exemple:

Si S1={a,b,c}; L1={ab,bc} et Sp={b,c} l'alphabet sur lequel L1 est projeté alors P(L1,Sp)={b,bc}.

La projection inverse

L'opération de projection inverse permet de compléter un langage avec des événements non contenus dans son alphabet. Ces événements vont être insérés entre chaque événement de chaque mot du langage de façon à construire un langage de taille maximale. La projection inverse permet pour le langage de considérer les nouveaux événements ajoutés comme étant possibles à chaque instant. La projection inverse sera notée IP tels que si A est la projection inverse de B suivant un alphabet S alors A=IP(B,S). Il est nécessaire de préciser que les opérations de projection et de projection inverse ne sont pas des réciproques.

Exemple:

Si S1={a,b,c}; L1={ab,bc} et Sp={b,d} l'alphabet sur lequel la projection inverse est réalisée alors IP(L1,Sp)={d*ad*bd*,d*bd*cd*}

References:

Ramadge P.J., Wonham W.M. The control of discrete-event systems. IEEE Transactions on Automatic Control, 1989, Vol. 77, N° 1, p. 81-98
C. G. Cassandras, and S. Lafortune. Introduction to discrete event systems, Kluwer Academic Publishers, 1999, ISBN: 0-7923-8609-4.