Modélisation de comportement par états et transitions

Dans ce chapitre, nous donnons une introduction aux concepts principaux pour la modélisation du comportement de systèmes, et en même temps, nous introduisons des paradigmes de modélisation de base, comme les cas d'utilisation, les diagrammes de séquencement, les diagrammes d'activités, différentes formes de machines à états (telles que les modèles de Markov, les systèmes à transitions étiquettées (Labelled Transition Systems, LTS), les automates accepteurs, les automate d'entrée et de sorties (Input-Output Automata, IOA), les machines à états finis (Finite State Machines, FSM), et des modèles de machine à états étendus, comme les diagrammes d'états de UML.

Notez que nous distinguons dans ce qui suit entre propriétés qui ont un sens "formel", et d'autres propriétés que restent définies d'une façon informelle (c'est-à-dire, qui sont essentiellement décrites en français (ou un autre langage naturel) - étant un complément au modèle formel.

La relation entre actions et états

Choix entre modèles orientés états et orientés actions - la nature des transitions

Comme exemple, nous considérons dans la suite le processus par lequel un artiste crée une sculpture en bois (je me souviens que je le faisais quand j'étais jeune): (1) L'artiste trouve l'idée de la sculpture, (2) l'artiste prend un morceau de bois et prépare la sculpture en grand lignes, (3) la sculpture est détaillée, et finalement, (4) la sculpture est polie (et peut être admirée). Voici plusieurs représentations de ce processus:

• (a) un diagramme d'activités (à la UML),
• (b) un diagramme "Use Case Map" (UCM),
• (c) un diagramme d'états (à la UML) représentant les états du sculpteur qui fait le travail, et
• (d) un diagramme d'états (à la UML) représentant les états de la sculpture.
• Les symboles arrondis sont des états ou activités, les flèches sont des transitions. Notez que la flèche du point noir n'est pas vraiment une transition, mais simplement une indication de l'état (ou activité) initial(e) du système. Similairement, la flèche vers le point noir avec cercle; elle indique l'état (ou activité) final(e).

Il est important de noter que les diagrammes (a), (b), et (c) représentent la même "sémantique", tandis que le diagramme (d) représente le processus par une autre perspective, du point de vue de l'objet qui est manipulé. Dans les diagrammes (a) à (c), les transitions entre les activités/états sont courtes, tandis que des périodes de temps plus longues s'écoulent pendant les activités (ou pendant les actions impliquées par les noms des états - dans le diagramme (c)). Dans la perspective de l'objet manipulé (diagramme (d)), les transitions prennent plus de temps, et les états représentent des "milestones" - des états identifiables pendant le processus de création de l'objet. Je dirais que les diagrammes (a) à (c) représentent des modèles orientés actions, tandis que le diagramme (d) représente un modèle orienté états. Si on compare les diagrammes (c) et (d), on voit que les actions deviennent des états et des états deviennent des actions. Il est important de noter que les deux approches peuvent être utilisées pour modéliser la même réalité. Quelle approche est préférable dépend du but de la modélisation.

En d'autres mots:

• Diagramme (a) est un diagramme d'activité UML. Chaque ovale représente une activité, c'est-à-dire, une action. Quand une action termine, la flèche (une transition) indique quelle(s) est (sont) les prochaines activités à exécuter. Une telle transition est appelée (en UML) transition de terminaison ("completion transition") - elle est exécutée quand l'action précédante est terminée. Note: Ou est-ce que la traduction transition d'achèvement est meilleure ?
• Diagramme (b) est un "Use Case Map". Il a le même sens. Une croix représente une activité, appelé "responsabilité" dans les Use Case Maps.
• Diagramme (c) est un diagramme d'états UML. Chaque rectangle arrondi représente un état. Dans cet exemple, chaque état représente une activité qui est exécutée par quelqu'un quand le système est dans l'état en question. Donc, ceci est un exemple d'un modèle orienté actions (c'est-à-dire, le diagramme ovale - ici l'état - represente une action) - chaque état représente une action, les flèches représentent les transitions d'une action à l'autre. Encore, elle sont des transitions de terminaison.
• Diagramme (d) est aussi un diagramme d'états UML. Mais il est orienté états - chaque état du diagramme représente effectivement un état d'un certain objet. Ici, l'objet est un pièce d'art. Les transitions entre états représentent des actions qui sont exécutées pour transformer l'état de l'objet en question. Les transitions ne sont pas des transitions de terminaison (sauf la dernière qui amène à l'état final) - elles représentent des actions.
  • Je pense que l'orientation états est la façon normale d'utiliser les modèles de machines à états.

La même réalité peut aussi être modélisée par le diagramme d'activité UML ci-dessous qui inclue des flux d'objets (data flow). Ce diagramme inclue les deux perspectives, orienté actions et orienté états. Ici, les objets de données (représentés par les rectengles) représentent la sculpture dans ses différents états. Note: Ici les transitions sont associées avec les objets de données qui sont produits par une activité et consommés par la prochaine activité - en effet, ils sont des sorties et des entrées pour ces actions, les activitées dans le diagramme.

Agents (acteurs), composantes et ressources

Des diagrammes d'activités et des UCMs peuvent aussi être utilisés pour définir des agents. Ces agents représentent des acteurs, le système, des composantes du système ou des ressources qui sont impliqués dans les activités identifiées. Dans les diagrammes d'activités de UML, ces entités sont appelées "swimlanes", et en UCM "components". En pratique, ces entités représentent souvent des acteurs à l'extérieur du système, ou des composantes qui font partie du système modélisé. Ces entités représentent des ressources qui sont dédiées à une instance particulière du diagramme d'activités, ou qui sont partagées entre plusieurs instances. Elles sont aussi appelé "agents" et on peut distinguer entre agents actifs et passifs. Par exemple, un acteur humain doit être considéré comme un agent actif, aussi des systèmes réactifs qui prennent l'initiative pour certaines actions. Des instances d'objets qui fournissent une interface d'appel de procédures sont passives, puisqu'elle ne prennent pas d'initiatives. Voici un exemple d'un diagramme d'activités UML incluant des "swimlanes" et du flux d'objets. (Note: la ligne horizontale dans la colonne du "customer" est probablement une erreur et devrait être un rectangle avec le texte "o:Order [prepared]").

Voici une courte comparaison entre diagrammes d'activités et UCMs et des concepts qui peuvent être modélisés.

Lectures complémentaires

• Modèles de Markov: Voir "Markov chain"dans Wikipedia (ou version française)
• Diagrammes d'activités UML: Voir le livre recommandé [Booch] ou Wikipedia
• Use Case Maps: Voir UseCaseMaps.org
• Diagrammes d'états UML: Voir notes de cours imprimés tirées du livre recommandé [Booch]

Différentes sémantiques pour les modèles à états et transitions

La signification des symboles arrondis

Comme discuté ci-haut, un modèle représenté par un ensemble d'états et des transitions entre eux peut avoir des sens différents. (Notez que "sens" est aussi appelé "sémantique"). En général, chaque état et chaque transition a un nom pour le distinguer des autres entités dans le modèle. Comme vu dans l'exemple ci-haut, il y a essentiellement deux sémantiques pour les modéles à états et transitions:

• Sémantique orientée actions (comme dans les exemples (a), (b) et (c) ci-haut, et en général pour les diagrammes d'activités de UML): Les états représentent des actions qui sont exécutées par des acteurs souvent non-spécifiés. Les transitions sont normalement des transitions de terminaison.
• Sémantique orientée états (comme dans l'exemple (d) ci-haut): Les états représentent les états possibles d'un objet particulier - le modèle représente le comportement de cet objet. Dans ce cas, les transitions représentent des actions, normalement exécutées par l'objet en question. Il se peut aussi que les transitions représentent des "interactions", c'est-à-dire, des actions qui sont exécutées conjointement par plusieurs composantes du système - elles représentent une interaction entre une composante (l'objet en question) avec des composantes dans son environnement.
  • Note: Dans un modèle orienté action où les actions sont représentées par des transitions, les noms des transitions sont évidemment très importants. Souvent les noms des états ne sont pas importants. En effet, si les noms des états changent, cela n'affectera pas l'ordre dans lequel les actions des transitions peuvent être exécutées - et souvent on est principalement intéressé par les ordres possibles dans lequels les actions peuvent être exécutées.
  • Inversement: Dans le cas de la sémantique orienté actions, quand les symboles arrondis représentent des actions (comme dans le cas des diagrammes d'activités UML), les noms des symboles arrondis sont très importants, et les états souvent n'ont pas de nom.
  • Les diagrammes d'états UML supportent les deux sémantiques: orientée états et orientée actions. En général, la sémantique orientée états est prévue, mais en associant une DO-Action avec un état, on peut spécifier que dans cet état l'action DU-Action doit être exécutée.

Le déclenchement des transitions

Il existent aussi des sémantiques différentes en se qui concerne comment les transitions sont déclenchées. C'est-à-dire, sous quelle condition une transition est-elle exécutée ?

• Transitions spontanées. Ces transitions sont initiées par la machine d'une façon spontanée quand la machine est dans un état où la condition de déclenchement est satisfaite. Cette sorte de sémantique correspond aux commandes gardés de Dijkstra où chaque énoncé est une transition, appelée commande gardée, qui contient une condition de déclenchement (dépendant de variables locales), appelée garde, et une commande à être exécutée qui normalement changera les valeurs de certaines variables. Une commande gardée est seulement exécutée quand la garde est vraie, et au maximum une commande est exécutée à la fois.
  • Si la garde est vraie, il n'est pas nécessaire d'exécuter la commande tout de suite.
  • Si dans un état il y a plusieurs transitions spontanées exécutables, le comportement est non déterministe, c'est-à-dire, la spécification ne dit pas quelle transition sera exécutée la prochaine.
  • En UML, de telles transitions sont appelées transitions de terminaison.
• Transitions déclenchées par des événements. On peut considérer des types d'événements suivants:
  • Un message reçu de l'environnement de la machine.
  • La valeur d'une variable visible a changé. Ceci suppose que la transition a une condition qui dépend de cette variable, et que la valeur précédant de la variable donnait une condition fausse. Évidemment, pour déclencher la transition, la nouvelle valeur de la variable doit donner la condition vraie.
  • La variable en question pourrait être une variable visible dans l'environnement de la machine. En particulier, elle pourrait représenter l'état d'une autre machine à état dans l'environnement.
• Une période de temps a écoulée. Ceci suppose qu'il y a un temporisateur (timer). Un temporisateur peut être déclenché par l'action d'une transition pour donner un signal après une période de temps déterminée. Quand la période est écoulée, un signal (time-out) est produit qui peut déclencher une transition associée à ce signal - sauf si le temporisateur est arrêté par l'action d'une autre transition.

Différentes sortes d'interactions avec l'environnement

Il y a différentes sémantiques orientées états en ce qui concerne les interactions de la machine avec son environnement. Dans ce cours, nous considérons les sémantiques suivantes:

• Aucune interaction - seulement des transitions internes. Avec les modèles simples que nous considérons ici, une composante du système modélisé est dans un certain état. Il y a un nombre (fini) d'états possibles. L'état de la composante détermine le comportement dynamique futur de la composante. Chaque état a un nom, et on suppose que l'état actuel de la composante peut être déterminé par une procédure d'observation quelconque. Le modèle spécifie aussi la présence d'un certain nombre de transitions entre états. Ces transitions peuvent être prises par le modèle pour changer d'état. Les transitions n'ont pas de nom "formel" - même si chaque transition a normalement une certaine signification (appelé aussi "sémantique") qui restent cependant informelle. Ces transitions ne représent pas des interactions avec l'environnement, elles restent internes. Souvent, les transitions sont associées avec des probabilités de transition: de tel modèles sont appellés des Modèles de Markov.
• Interactions rendez-vous. Ces interactions sont utilisées avec les modèles de machines à états connus sous le nom Système à transitions étiquettées (Labelled Transition Systems, LTS). Ceci est un formalisme de modélisation très simple. Il y a un nombre fini d'états et un nombre fini de transitions qui sont étiquettés. Les étiquettes jouent le rôle de nom, mais notez que dans un LTS il peut y avoir plusieurs transitions avec la même étiquette. Chaque étiquette représente une certaine interaction de l'objet modélisé avec son environnement, et le diagramme de transition définit dans quel ordre ces interactions peuvent être exécutées. Figure (b) ci-dessous est un exemple qui représente le comportement d'un journaliste qui vient pour un entrevue. Le diagramme (b) implique qu'après l'action shake hands le journaliste ne peut pas faire une deuxième fois un shake hands.
• Note: Les actions dans un modèle LTS font abstraction de la distinction d'entrée et sortie, et il n'est pas indiqué qui prend l'initiative pour l'interaction, l'objet modélisé ou un acteur dans son environnement.
• Quand on considère la collaboration entre plusieurs modèles LTS, et les deux modèles ont une transition étiquetté "xxx", alors une interaction "xxx" peut seulement arriver si les deux modèles sont dans un état où il y a une transition étiquettée "xxx". C'est pourquoi ces interactions sont appelées interactions par rendez-vous (elles sont déclenchées conjointement par tous les participants - seulement si tous sont prêts pour une telle interaction).
• Distinction entrée-sortie. Cette distinction permet à répondre à la question importante: Qui est l'initiateur d'une interaction.
  • L'entrée à une composante de système n'est pas décidée par la composante qui reçoit l'entrée; la composante ne sait pas quelle sera la prochaine entrée à venir, et quand elle viendra. La composante peut néanmoins faire certains hypothèses sur ces question en accord avec sa spécification (voir spécification avec hypothèses et garanties).
    • Si pour un état donné, la spécification fait l'hypothèse qu'un message X ne sera pas reçu, alors il n'est pas nécessaire de prévoir une transition dans la composante pour la réception d'un tel message. Si, pendant l'exécution du système, quand même un tel message est reçu dans cet état, ceci est une situation de réception non spécifiée. L'occurence d'une telle situation indique qu'il y a une erreur de conception dans le système. Ou la spécification devrait être revisée pour indiquer quoi faire dans un tel cas, ou le comportement des composantes dans l'environnement devrait être changer de telle manière que cette situation n'arrive plus.
      • Note: La détection de situations de réceptions non spécifiées pendant la phase de conception d'un système est un outil utile pour détecter des erreurs de spécification qui, autrement, sont souvent difficiles à détecter. Des outils automatiques, comme LTSA, peuvent être utilisés à cet effet.
  • La sortie d'une composante est initiée par la composante elle-même en fonction des garanties données par sa spécification. La production de sortie peut se faire à l'intérieur de l'action d'une transition spontanée, ou elle peut être faite en réponse à une entrée reçue.
  • Il y a différents types de machines à états qui distinguent les entrées et sorties:
    • Automates accepteurs: Ce sont des machines à états qui ne produisent pas de sorties. Les entrées qui donnent lieu à des transitions sont fournies par l'environnement de la machine, et le but de la machine est de déterminer si la séquence des entrées fournies est acceptable d'après un critère donné (pour plus de détails, voir le chapitre sur l'analyse lexicale dans ce cours). Pour cela, chaque état de l'automate est ou acceptant ou non acceptant. Quand l'automate est dans un état acceptant, la séquence des entrées fournie jusqu'alors est acceptable.
    • Automates accepteurs non déterministes: Ces accepteurs ont quelques transitions spontanées qui ne consomment pas d'entrées. La possibilité de leur exécution peut résulter en un comportement non déterministe (pour plus de détails, voir le chapitre sur l'analyse lexicale dans ce cours).
    • Machines à états avec sémantique d'appel de procédure: Un certain nombre de prodécures (méthodes) sont définies pour la machine et chaque transition est associée avec une des méthodes. Une transition est déclenchée quand l'environnenent appelle la méthode associée à la transition. Le processus appelant doit attendre jusqu'à ce que la procédure retourne (comme normalement) avant d'entreprendre d'autres actions. Ceci est un point de variation sémantique des diagrammes d'états UML, et elle a été implantée comme option de base par l'outil Umpl.
    • Machines à états finis: (Finite State Machines - FSM): Ce sont des machines à états où une transition peut produire un message de sortie qui est envoyé à l'environnement avant que la machine entre dans le nouveau état défini par la transition. Ce type de modèle est aussi appelé machine de Mealy, d'après G.H.Mealy qui utilisait ce formalisme en 1955 pour décrire le comportement de circuits électroniques.
      • Note: Un autre modèle de machines à états finis sont les machines de Moore (pas considérées dans ce cours). Ces machines sont similaires aux machines de Mealy, excepté que la sortie produite n'est pas déterminée par la transition, mais seulement par le prochain état qui est atteint par la transition. Ce paradigme de modélisation a été utilisé par E.F.Moore en 1956 pour des circuits de matériel. Ce paradigme est assez naturel pour du matériel contrôlé par une horloge où la valeur sur un circuit reste constante entre deux impulsions de l'horloge. Une machine de Moore reste dans son état actuel entre deux impulsions de l'horloge et fait une transition pendant la prochaine impulsion, basé sur son état actuel et les valeurs des circuits d'entrées qui sont normalement déterminées par les états d'autres machines de Moore représentant d'autres composantes dans le système. La sortie d'une machine de Moore (dans un état donné) est donc considérée comme une valeur constante (qui peut seulement changer quand l'état de la machine change), et non pas comme un événement (comme c'est la cas pour une machine de Mealy).
    • Automates d'entrée-sortie (Input-Output Automata, IOA): Ces machines sont similaires au FSM (Mealy), sauf que chaque transition est ou une transition déclenchée par une entrée et sans sortie, ou une transition spontanée avec une sortie.
  • Échange de messages: Pour les modèles FSM (Mealy) et IOA, on adopte normalement la sémantique d'échange de messages asyncrone pour la transmission d'une sortie d'une composante qui devient l'entrée d'une autre composante. L'action de production d'une sortie par une transition produit un message qui va déclencher une transition dans la composante de destination. Donc, chaque action de sortie doit aussi spécifier à quelle composante le message de sortie doit être acheminé. Normalement on suppose que chaque composante modélisée par machine à états a une file d'entrée (avec discpline FIFO) où les messages qui arrivent sont gardés pendant que la composante est occupée d'exécuter d'autres transitions. Une autre sémantique pour le passage de messages est de prévoir dans chaque composante un tampon (non ordonné) où les messages qui arrivent sont gardés jusqu'à ce que la machine à états choisisse un message qui correspond à une transition qui peut être exécutée à partir de l'état actuel de la machine - ceci est très utile quand des messages peuvent arriver de différentes composantes et leur ordre n'est pas à prévoir [lecture complémentaire: On the realizability of collaborative services ( H. N. Castejòn, G. v. Bochmann and R. Braek )  Journal of Software and Systems Modeling, Vol. 10 (12 October 2011), pp. 1-21. -  PDF ]

Des exemples simples

Modèle de Markov

Le diagramme suivant montre un modèle d'un système qui peut tomber en panne (transition failed) et qui peut être réparé (transition repaired). Si l'on ajoute à chaque transition un taux de transition (transition rate) - c'est-à-dire, la probabilité que la transition sera prise pendant la prochaine unité de temps quand le système est dans l'état de départ de la transition - alors on obtient un modèle de Markov qui permet la prédiction de la probabilité que le système (dans un moment quelconque) sera dans un état particulier. Exemple: Quelle sera la disponibilité du système modélisé par le diagramme ci-haut si le taux de la transition "failed" est 1/1000 et le taux de la transition "repaired" est 1/100 ?

LTS avec la communication par rendez-vous

Voici un exemple simple. Le modèle montre une collaboration entre trois agents qui exécutent plusieurs actions rendez-vous dans un ordre prescrit. Il s'agit d'un interview impliquant trois agents: le directeur de la compagnie, un journaliste et la secrétaire. Il y a les rendez-vous suivants: un bonjour (shake hands), la discussion d'interview, et un au-revoir (bye) exécutés conjointement par le directeur et le journaliste; et les sous-collaborations "discussion avec secrétaire", entrée et sortie de la secrétaire exécutées conjointement par le directeur et la secrétaire (on suppose que le directeur donne la permission à la secrétaire d'entrer, et indique quand elle devrait sortir). Un séquencement raisonnable de ces sous-collaborations est défini par le diagramme d'états ci-dessous (diagramme (a)). On note que l'interview est interrompu quand la secrétaire entre dans la pièce jusqu'à ce qu'elle quitte.

On remarque que le diagramme (a) décrit aussi le comportement du directeur (puisqu'il participe dans toutes les sous-collaborations). Les diagrammes (b) et (c) montrent le comportement du journaliste et de la secrétaire, respectivement.

Note: Dans cet exemple (et en général quand on utilise un modèle LTS), on utilise une approche orienté états - où les actions sont modélisées par les transitions. En effet, ces transitions-ci représentent des collaborations entre plusieurs agents (des rendez-vous, comme discuté plus haut). Les transitions LTS peuvent aussi représenter des simples interactions entre le système modélisé et son environnement, comme on discutera plus bas pour les systèmes client-serveur. Cette approche est similaire au diagramme (d) de l'exemple de l'artiste, même si dans ce diagramme les actions ne sont pas explicitement mentionnées, puisque l'emphase était sur les états de l'objet.

• La sémantique des LTS: Pour un LTS, on est normalement intéressé à connaître toutes les séquences dans lesquelles les transitions du modèle peuvent être exécutées, à partir de l'état initial jusqu'à un état final. On appelle trace d'exécution une telle séquence d'étiquettes de transitions.
  • Quand on est seulement intéressé par cet ensemble de traces possibles, on appelle cela la sémantique de traces. Pour le LTS (a) ci-dessous, une trace est ou vide (c'est-à-dire, elle n'inclue aucune étiquette - aucune transition a été exécutée) ou elle commence par un a; ensuite, il peut y avoir zéro ou plusieurs b, et il peut y avoir un a à la fin.
  • Parfois, on est aussi intéressé par les possibilités de blocage. Par exemple, le LTS (a) ci-dessus bloque pour l'interaction (étiquette) b dans l'état initial, et quand deux interactions a ont eu lieu dans la trace.
    • Si on a un LTS déterministe (c'est-à-dire, un LTS pour lequel on peut savoir son état actuel quand on sait la trace exécutée jusqu'à présent - comme dans le LTS (a) ci-dessus), alors un blocage pour une interaction donnée peut être déduit de la connaissance de l'ensemble de toutes les traces: Le LTS bloque après une trace exécutée donnée pour une nouvelle interaction donnée, si et seulement s'il n'y a pas de trace qui est égale à la trace déjà exécutée suivi par l'interaction en question (comment prouver ceci ?).
      • Voir les opérations supportées par l'outil LTSA concernant la vérification de propriétés: exemple "check properties".
        • trouver des bloquages
        • exécution de séquences de test
        • la projection
        • vérification de propriétés en forme d'inclusion des traces
      • Voir exemple machine à café (la partie LTS au début)
    • Cela n'est pas vrai si le LTS est non déterministe.Le diagramme (b) ci-dessous montre un LTS non déterministe (après la trace <a>, il peut être dans deux états différents). Ce LTS pourrait bloquer après la trace <a, b, b> pour l'interaction c (s'il est allé dans l'état 4), même si le LTS admet aussi la trace étendue <a, b, b, c> (quand il va dans l'état 2). Ces considérations sur les possibilités de bloquage des LTS non déterministes sont appelées "failure semantics".

Un autre example de LTS: l'exemple de l'Hôtel

Automates accepteurs

La possibilité d'utiliser un LTS pour définir un ensemble de traces acceptables est la raison pourquoi les LTS sont utilisés pour l'analyse de langue naturelles et les langages de programmation. Considérons un agent avec un comportement comme défini par le LTS (c) ci-dessus (nous supposons que seulement l'état en haut à droite est acceptant). Ce LTS admet comme traces toutes les séquences de caractères qui représentent un nombre décimal sans zéros au début. Si on met ce LTS en rendez-vous avec un lecteur de caractères qui fournit comme sortie le prochain caractère lu sur un fichier d'entrée, alors on obtient un système qui a une réception non spécifiée quand on découvre une erreur dans la représentation du nombre décimal dans le fichier d'entrée, et lorsque l'automate est dans l'état acceptant quand on est arrivé à la fin de la chaîne des caractères, alors la chaîne représente un nombre valide. - Ceci est discuté en plus de détails dans le module 2 de ce cours.

Systèmes client-serveur

Nous considérons maintenant la collaboration entre un agent actif et un agent passif, comme dans le cas des systèmes client-serveur. Le serveur fournit un interface qui permet au client d'appeler certaines méthodes.

• Si ces méthodes peuvent être appelées dans un ordre quelconque, comme c'est souvent le cas, alors on peut dire que le serveur est toujours dans le même état.
• Mais souvent l'état interne du serveur détermine le résultat qui sera retourné lors d'un appel de méthode. Considérez par exemple un objet FIFO avec les méthodes put et get. On peut distinguer les états vide, plein et moitié-plein. Le résultat de la méthode sera différent quand l'état est plein.

Combinaison d'entrée et rendez-vous

Parfois, un modèle client-serveur (où il est évident quel côté initie l'interaction) a une sémantique de rendez-vous pour l'initiation des interactions, c'est-à-dire, le serveur pourrait refuser de participer dans certaines actions, dépendant de l'état actuel. Par exemple, pour une machine à café, la fente pour entrer la monnaie pourrait être bloquée quand la machine est vide, ou le bouton pour demander un café pourrait être inactif avant que suffisamment d'argent ait été entré. Comme exemple, on peut considérer le modèle d'une porte comme montré ci-dessous. Il est évident que la transition open n'est pas possible quand la porte est dans l'état lock (la porte bloque cette transition dans cet état).

• Note: Ce modèle UML suppose que la machine à états est un FSM où les transitions n'ont aucune sortie. Avec cette sémantique, l'entrée open dans l'état lock donnerait lieu à une réception non spécifiée. Ceci n'est évidemment pas la bonne sémantique. Ce diagramme donne un exemple où la sémantique du modèle est inconsistante avec la réalité. Les diagrammes d'états UML ont plusieurs points de variation sémantique, et malheureusement, les auteurs ignorent souvent ce fait et les difficultés qui en résultent.

Entrée-sortie asynchrones

Avec la communication asynchrone, il n'y a pas d'instance quand les deux parties sont impliquées dans l'interaction - normalement, l'agent qui envoie le message va ensuite faire d'autres activités pendant que le message se propage vers sa destination.

• Il est important de noter que l'échange de messages peut être utilisé pour réaliser une communication synchrone; c'est la cas pour les appels à distance (Remote Procedure Call, RPC) où l'agent appelant envoie un message au serveur contenant l'information sur la méthode à exécuter et les valeurs des paramètres d'entrée, et un deuxième message est retourné par le serveur à l'agent appelant (qui attend ce message avant de continuer son travail) avec les résultats de l'opération exécutée.

Voir l'exemple de la machine à café

Des variantes de machine à états avec la même sémantique

Dans ce qui suit, nous discutons comme exemple le développement de plusieurs modèles d'un guichet automatique bancaire (Automated Teller Machine, ATM). Les figures (a) et (b) ci-dessous donnent la même information, dans les formes de diagramme d'activité et de LTS, respectivement. La description des activités (et les étiquettes de mêmes noms dans le LTS) reste assez informelle.

Les autres modèles distinguent explicitement les entrée et sortie.

• La figure (c) n'est pas une machine à états. Elle montre un diagramme de séquencement qui définit le comportement d'un ATM en termes d'échanges entre l'ATM et l'usager. Ici, chaque activité de la figure (a) a été remplacée par un message d'entrée de l'usager et un ou deux messages de sortie produits par l'ATM. Beaucoup des messages de sortie sont en fait des affichages de textes sur l'écran de l'ATM. Ce modèle fournit plus de détails que les modèles (a) et (b): il montre quel agent prend l'initiative pour les différentes actions (principalement l'envoi de messages); il montre aussi plus de détails sur l'interface de l'usager (les textes affichés lors des différentes étapes du processus).
• Basé sur la figure (c), la machine d'états UML de la figure (d) a été développée. Il est un FSM et inclut les changements suivants par rapport à la figure (c):
  • Les noms de messages de l'usager vers l'ATM ont été remplacés par des noms d'événements qui reflètent mieux la nature des interactions avec l'usager. E.g. le message "card" a été remplacé par l'événement "card_entered".
  • La deuxième transition inclut une condition qui est supposée vraie pour le comportement suivant; cette condition est écrite "[NIP is correct]".
  • Certaines opérations d'envoi de messages ont été remplacées par des noms d'actions locales qui reflètent mieux la nature de ces interactions avec l'usager. E.g. l'envoi du message "money" est remplacé par l'appel de la procédure locale "dispense_money()".
  • Le diagramme (e) ci-dessus représente le même comportement que le diagramme (d) - mais il est dans la forme d'un IOA (chaque transition a ou une interaction d'entrée ou de sortie, seulement).
  • Le diagramme (f) montre le même comportement dans la forme d'une machine de Moore (les sorties sont associées aux états, et non pas aux transitions).

Modèles étendus de machines d'états

Les modèles à la FSM, IOA ou Moore sont caractérisés par un ensemble fini d'entrées possibles, un ensemble fini de sorties, et un ensemble fini d'état, ainsi que par un état initial et la fonction de transition (comme discuté ci-haut). Pour la plupart des tâches de modélisation, de tels modèles formels sont trop restrictifs. Par exemple, pour l'ATM montré ci-haut, on a déjà introduit certaines extensions: il y a une grande nombre de valeur de NIP possibles. Dans un modèle FSM formel, on devrait ou ignorer ces différentes valeurs, ou introduire un message séparé pour chaque valeur possible de NIP. On suppose aussi qu'il y a un moyen de déterminer si un NIP est valide. Et puis, on devrait aussi modéliser le fait que la carte n'est par retournée si l'usager fournit 3 valeurs de NIP non valides.

Dans les exemples ci-hauts, ces extensions étaient modélisées d'une façon informelle en utilisant certains noms et/ou commentaires qui suggèrent certaines propriétés. Néanmoins, il serait mieux de formaliser ces aspects. Pour cela, des paradigmes de modélisation par machines d'états sont souvent étendus en introduisant les concepts suivants:

• Les interactions d'entrée et de sortie peuvent avoir des paramètres. Ces paramètres sont déclarés dans la définition de l'interface, et leur type de données est indiqué.
• Une instance d'une machine à états peut avoir des variables d'états (comme des attributs d'un objet) - en plus de la variable implicite "STATE" qui contient l'état courant de la machine. Ces variables sont déclarées comme des variables locales. En UML, les attributs de la Classe représentant la machine d'états peuvent être utilisés pour cela.
• Chaque transition est associée avec une condition de déclenchement (enabling condition) qui doit être vraie quand la transition est exécutée. En général, cette condition peut dépendre des variables d'état de l'instance de la machine et des valeurs des paramètres de l'entrée. En l'absence d'une condition explicite, on suppose que la condition est vraie, par défaut.
• Chaque transition est associée avec une action qui est exécutée quand la transition s'exécute. Cette action peut représenter un algorithme complexe (comme dans le cas du langage SDL). De toute façon, cette action inclut normalement: (a) l'exécution d'énoncés d'affectation pour mettre à jour les variables d'états, et (b) la préparation de certains messages de sortie incluant des expressions qui définissent les valeurs des paramètres de la sortie. Ces expressions et les expressions dans les énoncés d'affectation (comme les conditions de déclenchement) peuvent dépendre des valeurs courantes des variables d'état et des valeurs des paramètres de l'entrée qui a déclenché la transition.

Exemple: un modèle de machine à états étendu pour une machine ATM

Vous trouvez ci-dessous un exemple d'un modèle ATM qui inclut des spécifications formelles de certaines propriétés avec les formalismes étendus décrits ci-haut, utilisant la notation UML. On suppose ici que la machine a deux variables d'état:

• un entier available qui représente le nombre de cents disponibles dans le compte de l'usager, et
• un entier attempts qui compte le nombre de mauvais NIP soumis par l'usager.

On suppose aussi que l'entrée amount_entered contient un paramètre entier, appelé request, qui représente le nombre de cents que l'usager veut retirer de son compte, et que la sortie display contient un paramètre de type String qui contient le texte à être présenté à l'usager. Les éléments de la spécification ci-dessous qui réfèrent à ces variables ou interactions sont écrits en gras. La notation pour décrire les conditions de déclenchement et les expressions pour les affectations et les paramètres de sortie est normalement empruntée du langage qui est utilisé par l'outil UML pour la génération de code exécutable ou pour la simulation (pour simplifier ce processus de génération de code). Dans l'exemple ci-dessous, j'ai utilisé la syntaxe de Java.

Caractéristique des diagrammes UML d'activités et d'états

Il y a plusieurs langages de modélisation de machines à états qui sont basés sur les concepts ci-hauts, et certains ont été normalisés. Des outils CASE ont été développés pour plusieurs de ces langages. Ces outils aident avec l'édition des modèles, la réalisation d'exécutions simulées, possiblement avec la génération diagrammes de séquencement correspondants (pour la vérification et validation des spécifications) et pour la génération automatique de codes d'implantation, possiblement prêts pour être intégrés avec d'autres composantes de logiciel. Nous mentionnons en particulier:

• Diagrammes d'activités UML. Les caractéristiques principales sont discutés dans la présentation d'Al Osman avec quelques exemples. La sémantique des diagrammes d'activités sont la base de certains autres langages pour la description de processus de travail ("workflow"), comme BPMN (Business Process Modeling Notation).
  • Note: Ceci ne fait pas partie du cours.
• SDL: C'est un langage graphique qui a été développé et normalisé depuis les 1980 par l'Union International des Télécommunication (ITU). Récemment, les caractéristiques de ce langage ont été incluses dans la version 2 de UML, et SDL est défini comme un profil de UML. SDL contient des caractéristiques intéressantes, telles que des symboles graphiques pour les entrées et les sorties (voir exemple) et la notation pour définir des structures de sous-composantes. Quelques outils de vérification ont été développés par la compagnie suédoise (maintenant achetée par IBM).
  • Note: Ceci ne fait pas partie du cours.
• Diagramme d'états de UML: Cette notation inclut beaucoup de "features" en plus de ceux montrés par l'exemple simple ci-dessus. Cette notation peut être utilisée pour représenter des modèles de FSM, IOR, ou machines de Moore. Voici un sommaire des "features":
  • La génération d'un message de sortie est simplement un cas particulier d'une "action". Parmi les actions, il y a aussi l'appel d'une procédure locale, ou l'exécution d'un énoncé d'affectation à une variable d'état locale.
  • Des actions peuvent être associées à des transitions (à la Mealy). Des actions peuvent aussi être associées à l'entrée à un état (appelée "entry action"), ou à la sortie ( "exit action") (exécutées quand on entre dans cet état, ou quand on en sort, respectivement). En plus, une action "do" peut être associée à un état; elle est exécutée pendant que le système est dans cet état. En général, quand l'exécution d'une transition est déclenchée (seulement quand sa condition de déclenchement est satisfaite), d'abord l'action de sortie de l'état actuel est exécutée, ensuite la transition d'état est exécutée et l'action d'entrée du nouvel état est exécutée (en parallèle avec l'action "do" de cet état, si elle existe).
    • Note: Dans l'exemple (c) au début de cette page, les noms des états représentent en effet des DO-Actions. D'ailleurs, cet exemple montre la similariié entre diagrammes UML d'activités et d'états. Les activités d'un diagramme d'activités peuvent être réécrites en forme d'états avec des DO-Actions qui correspondent au noms des activités. Néanmoins, dans le cas de diagrammes avec concurrence, les diagrammes d'états imposent certaines restrictions sur le flux de contrôle qui n'existe pas pour les diagrammes d'activités.
  • Un état peut être structuré hiérarchiquement en sous-états, un concept introduit avec les State Charts de Harel, appelés aussi machines à états hiérarchiques. La notation d'états structurés permet certaines abbréviations:
    • Une transition qui quitte l'état structuré est équivalente à une telle transition à partir de chaque sous-état de l'état structuré.
    • On peut définir un "état historique" (H) dans un état structuré. Une transition qui amène à cet état effectivement va faire une transition au dernier sous-état qui était actif. Par exemple, une transition déclenchée par l'événement e qui quitte l'état structuré et va vers l'état historique est équivalente à des transitions boucle (loop-back) déclenchées par e à partir de chaque sous-état de l'état structuré.
  • Il se peut que les sous-états d'un état sont partitionnés en plusieurs sous-machines concurrentes. Ces sous-machines sont actives en parallèle et impliquent normalement des interactions d'entrée et de sorties différentes. On suppose que les différentes sous-machines fonctionnent d'une façon indépendante l'une de l'autre.

Lectures complémentaires

• Diagrammes de machines d'états: [Booch] chapitres 21 - 25 (pour machines d'états, voir notes de cours imprimées) et chapitre 11 (pour les interfaces)
• Notation SDL: un tutorial "developing a coffee machine"
• Les notes de cours d' Al Osman sur les machines d'états

La modélisation du temps réel

Les paradigmes de modélisation discutés ci-hauts (excepté les modèles de Markov) décrivent seulement l'ordre dans lequel les différentes interactions sur les différentes interfaces du système peuvent apparaître. Souvent, il y a aussi des exigences de performance qui doivent être respectées:

• Propriétés de performance statistiques: Ce sont des énoncés qui disent qu'un certain délai entre deux événements, en moyenne, sera égal, plus petit, ou plus grand qu'une durée de temps déterminée. Souvent, on décrit aussi des propriétés concernant la distribution (statistiques) des délais, par exemple, que le délai sera dans 95% des cas plus petit qu'une valeur donnée.
• Contraintes de temps réel dures: Ces énoncés disent qu'un certain délai doit être toujours être égal, plus petit, ou plus grand qu'une durée de temps donnée.

Si les exigences du système incluent des propriétés de performance statistiques ou de temps réel dures, on dit que le système est un système en temps réel. Normalement, ces systèmes sont des systèmes réactifs (voir ci-dessus).

Paradigme de modélisation (a): une variable de temps réel NOW

Dans beaucoup de situations, on utilise une variable spéciale, appelé NOW ou similaire, qui contient toujours le temps réel courant (cette fonctionnalité est fournie par le système d'exploitation). Le temps d'un événement modélisé peut être documenté en copiant NOW dans une variable locale. Plus tard, on peut tester le temps écoulé en comparant la valeur de NOW avec la variable locale.

Paradigme de modélisation (b): "Timed automata"

Le modèle formel d'un "Timed Automaton" est une machine à état LTS étendu par un certain nombre d'horloges qui avancent toujours avec le temps. Chaque horloge peut être remise à zéro par une transition (pour montrer, dans le futur, le temps écoulé depuis cette transition). D'autres transitions pourraient contenir des conditions de déclenchement qui dépendent de contraintes sur les valeurs des horloges. Plusieurs outils CASE ont été construits pour analyser de tels modèles de systèmes de temps réel. (Pas discuté plus dans ce cours).

Paradigme de modélisation (c): Horloge ("timer") et message d'expiration de temps ("time-out")

Des horloges qui peuvent émettre des messages d'expiration de temps sont souvent utilisées pour spécifier des propriétés de temps réel. Ils fonctionnent comme une alarme. Il semble que cela n'est pas supporté par UML.

SDL supporte cette modélisation: une machine d'état peut être associée avec une ou plusieurs horloges. Une horloge est initialement dans un état inactif. Elle peut être mise en marche par la primitive SET en indiquant le temps d'expiration. Quand ce temps arrive, un message d'expiration est envoyé à la machine d'état. La spécification du comportement de la machine devrait donc prévoir la réception d'un tel message dans les états appropriés. Voici un diagramme montrant le comportement d'une horloge:

Note: SDL et UML supportent la variable NOW. Voir aussi Dr. Williams' slides (slides 22 - 25)

L'exemple suivant montre des fragments du comportement d'une machine d'états en SDL (appelé la notation orientée transition en UML). La machine inclut une horloge appelée door_timeout qui est activée avant que le système entre l'état Opening. Une expiration arrive si le signal Opened n'est pas reçu avant 10 unités de temps. Si le signal est reçu avant ce temps, l'horloge est remise en marche avec un nouveau temps d'expiration. Cette expiration arrive si le signal Closed n'est pas reçu avant 30 unités de temps.