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:

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.

scultpure

En d'autres mots:

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.

sculpture with object flow

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]").

activity diagram example

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

Lectures complémentaires

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:

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 ?

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:

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 ?

Markov model

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.

interview

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.

LTS example

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.

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).

door

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.

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.

ATM (a) and (b)ATM (c)ATM d,e,f

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

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:

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:

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.

ATM (g)

 

 

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:

UML state diagramcourse

Lectures complémentaires

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:

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:

timer semantics

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.

timer example


Course notes - Gregor v. Bochmann - University of Ottawa. Created January 2011, last update: January 15,  2015