Notes de cours SEG-2506
On fait des fois la distinction entre:
La structure composite d'un système peut être décrite par un diagramme informel (comme j'utilise souvent - voir par exemple la machine à café. - notez, ces diagrammes représentent un système fermé - l'usager est inclus), ou par un diagramme UML de structure composite (voir exemple - note: ce diagramme représente un système ouvert). En UML, un port (interface) peut être un port d'entrée (acceptant seulement des interactions d'entrée) ou un port de sortie (seulement supportant la génération de sorties), ou les deux. Un diagramme UML de structure composite peut aussi contenir des connecteurs qui connectent des ports des composantes, ou qui connectent un port externe du système avec un port d'une composante qui effectivement réalise ce port externe du système. Évidemment, l'interconnection des ports devrait être telle que les ports interconnectés soient compatibles au point de vue des interactions échangées.
Les processus parallèles (concurrents) donnent lieu à un très grand nombre de séquences d'interactions possibles parce que les séquences d'exécution des différents processus peuvent être interlacées de beaucoup de manières. Dans le cas des processus indépendants, comme définis dans le régions parallèles des diagrammes d'états UML, on suppose par défaut qu'il n'y a pas de relation entre les processus (pas de communication, pas de variables ou autres ressources partagées). Ceci donne l'avantage que le comportement de chaque processus peut être analysé séparément des autres processus. Cependant, le nombre des séquences d'exécution globales est le plus large, parce que les interactions des différents processus peuvent être entrelacées de manière quelconque.Un exemple est montré dans le diagramme ci-dessous, où (a) et (b) représentent deux processus parallèles, définis en formes de LTSs, et (c) montre le comportement global résultant (aussi dans la forme d'un LTS). Dans cet exemple, on suppose que les transitions des LTS ne prennent aucun temps, donc on peut supposer que les transitions des différents LTS ne se font jamais en même temps; et si dans un état du système, des transitions sont possibles dans les deux processus, leur ordre d'exécution n'est pas défini, elles sont exécutées séquentiellement dans un ordre quelconque. Donc, cette sorte de concurrence introduit un certain non-déterminisme. Ceci est appelé la sémantique d'entrelacement. La situation devient plus complexe si on fait l'hypothèse que chaque transition prend un certain temps; alors il faut considérer la situation quand deux transitions s'exécutent en même temps. On peut modéliser cela avec un modèle d'intrelacement si on introduit deux événéments pour chaque interaction: le début et la fin de son exécution. On remarque que cela devient assez complexe, et ceci n'est pas considéré dans ce cours.
Nous considérons dans ce chapître plusieurs machines à états qui fonctionnent en même temps, mais pas complètement indépendamment (comme dans les régions concurrentes en UML). Nous considérons que le comportement d'une machine peut être influencé par le comportement d'autres machines. Ces dépendances peuvent être modélisées de différentes manières. Les paradigmes de communication les plus importants on été discutés au chapître précédent. Dans ce cours nous considérons seulement la communication par rendez-vous, l'appel de procédures et la communication par échange asynchrone de messages.
Nous considérons maintenant un exemple où il y a une certaine communication-collaboration entre deux agents différents (possiblement localisés sur des sites différents). Nous considérons d'abord la vue globale (qui pourrait correspondre à un modèle fonctionnel qui représente les exigences du système). Comme avant, nous montrons ici deux modèles différents, un diagramme de machine d'états UML (a), et une diagramme d'activités UML (b), et les deux modèles sont équivalents (ils ont le même sens - sémantique). Les actions a et b sont exécutées par l'agent A et les actions c et d sont exécutées par l'agent B, et l'ordre d'exécution de ces actions devrait être comme montré par les diagrammes ci-dessous: On note que la contrainte d'ordonnancement définie par ces diagrammes implique probablement qu'il y a quelques données produites par l'action b et des données produites par l'action c qui sont nécessaires pour exécuter l'action d.
.jpg)
.jpg)
.jpg)
Pour comprendre le sens de ces deux diagrammes, nous considérons la sémantique de traces, c'est-à-dire, nous posons la question: Quelles sont les traces valides (c'est-à-dire, les séquences d'exécution des actions) ? - Notre compréhension intuitive des diagrammes ci-hauts devrait nous amener à considérer l'ensemble suivant de trace valides: <a, b, c, d>, <a, c, b, d>, et <c, a, b, d>. Ce sont aussi les séquences d'exécution définies par le LTS montré dans le diagramme (c). C'est pourquoi ce LTS a le même sens (sémantique) que les deux diagrammes UML ci-dessus.
Tous les trois diagrammes montrent le comportement fonctionnel d'un point de vue global; le fait que deux agents différents sont impliqués n'est pas montré explicitement. Maintenant, nous considérons une structure de système particulière où il y a deux composantes A et B, chacune responsable pour un sous-ensemble des interactions, comme montré dans le diagramme suivant:
Le diagramme montre qu'il y a deux interfaces du système, réalisés par les composantes A et B, respectivement. A est impliqué dans les interactions a et b, tandis que B fait tles interactions c et d. Le type des interactions entre les deux composantes n'est pas spécifié.
Dans cette sous-section, nous considérons la communication par rendez-vous entre les deux agents. Vu la compréhension du comportement global du système désiré, comme décrit ci-haut, il est clair que l'agent B doit attendre que l'agent A ait complété l'action b avant de faire l'action d. C'est pourquoi on pourrait introduire une interaction de rendez-vous entre les deux agents avec le nom b-done qui devrait être exécuté par B avant l'action d et par A après avoir terminé l'action b.
On peut commencer par une définition du comportement pour A et B obtenue par projection (voir explication de ce concept dans le chapître 1) du comportement global (voir diagramme (c) ci-haut) sur l'ensemble des interactions de chaque agent. Ceci nous donne les modèles de comportement suivants:
Si nous adoptons ces comportements pour les deux agents (sans communication entre les deux, voir diagrammes (ax) et (bx) ci-dessous), nous obtenons le comportement global (la concurrence independante) montré par le diagramme (x) ci-dessous. Ce comportement inclut toutes les traces définies par le comportement donné par le diagramme (c) ci-dessus, mais aussi certaines autres traces, par exemple <c, d, a, b>; cette dernière trace n'est pas valide d'après de comportement du diagramme (c). On doit donc trouver des comportements pour les agents qui sont plus restrictifs.
Une façon d'introduire des restrictions est l'introduction de points de synchronisation (interactions rendez-vous) entre les deux agents. Suivant cette approche, nous pourrions ajouter un rendez-vous b-done entre les deux agents, en définissant les traces suivantes pour le comportement des deux agents (les deux comportements sont caractérisés par une seule trace): comportement de l'agent A = { <a, b, b-done> }; comportement de l'agent B = { c, <b-done, d> }. Ces comportements sont représentés dans le diagrammes (a) et (b) ci-dessous:
Ceci semble être une conception raisonnable pour le comportement des deux agents, mais il faut le vérifier. Cela veut dire qu'il faut dériver le comportement global du système de la définition donnée des comportements des deux agents, et comparer le comportement global obtenu avec le comportement désiré (montré dans le diagramme (c) ci-dessus). Cela veut dire que nous devrions trouver des méthodes pour résoudre les deux problèmes suivants:
Ce problème, pour des spécifications en forme de LTS, peut être résolu en construisant ce que l'on appelle le produit des composantes. Ce produit est encore un LTS dont chaque état représente un état global du système, c'est-à-dire, chaque état est caractérisé par les états des deux composantes. Comme exemple, nous montrons comment le produit des deux agents LTS ci-hauts peut être obtenu. L'état initial est (1, 1) - les deux agents sont dans leur état initial. Dans cet état, ou l'agent A peut faire une transition a, ou l'agent B peut faire une transition c (ce qui nous amène dans deux états globaux différents: (2, 1) ou (1, 2), etc. Le LTS global résultant est montré dans le diagramme (a) ci-dessous. Si on explore d'un façon systématique touts les états et toutes transitions du produit global, le processus de construction de ce comportement global est appelé l'analyse d'accessibilité (reachability analysis); notez que certains états globaux ne peuvent être atteints, comme l'état (1,4) dans cet exemple.
Nous serions contents si le comportement de ce LTS global était le même que le comportement défini pour le système (voir diagramme (c) ci-haut). Il n'est pas le même pour les raisons suivantes:
Quel critère devrait-on utiliser pour comparer le comportement global d'un système composé de plusieurs composantes et le comportement dynamique défini par les exigences du système ? - On compare deux comportements globaux: (a) le comportement du système composé (modèle plus détaillé), et (b) le comportement défini par les exigences (un modèle plus abstrait). Par quel critère peut-on dire que le comportement (a) satisfait les exigences (b) ? - D'abord, nous faisons abstraction des interactions internes dans le modèle (a), puisque ces interactions ne sont pas inclues dans le modèle (b). Puis, nous considérons deux critères.
Il est important de noter que le comportement de plusieurs composantes, après avoir éliminé les interactions internes entre les composantes, souvent donne lieu à un comportement non déterministe, vu de l'extérieur. Cela veut dire qu'un observateur, qui regarde les interactions qui apparaissent sur les interfaces externes du système, ne peut pas toujours savoir dans quel état le système se trouve et, donc, ne peut pas savoir quelles interactions seront possibles dans l'instant qui nous intéresse.
Parfois on utilise un comportement non déterministe pour modéliser une composante qui décide le choix entre plusieurs alternatives. Un exemple bien connu est montré ci-dessus. Les deux composantes A et B ont un choix entre les interactions b ou c. Dans le diagramme (a), on ne peut pas dire qui va faire le choix (possiblement déterminé par l'environnement, ou par choix aléatoire). Dans le diagramme (b), il est assez clair que la composante B fait le choix parce qu'après une interaction interne (à l'intérieur de l'agent B), il n'a plus de choix et il va forcer l'agent A à faire le même choix que lui. On peut dire que B fait le choix, et A le suit. Si on a deux agents qui font leur choix, comme montré par le diagramme (c), il se peut que le système entre en blocage ("deadlock") si les deux agents ont fait des choix contradictoires.
Maintenant nous considérons des composantes qui communiquent par messages asyncrones, c'est-à-dire, pour chaque message échangé, il y a deux événements: l'envoi et la réception. On suppose que le délai de transmission est variable et non connu. Dans la suite, nous faisons l'hypothèse qu'un message n'est jamais perdu.
Note: Normalement, on suppose que la composante de destination a une file de messages où un message arrivant est gardé avant d'être consommé par la composante. Parfois, on considère des files séparées pour les différents ports de communication d'une composante. Normalement, on suppose que la file est servie en ordre FIFO, mais il y a aussi des modèles où la composante peut déterminer dans quel ordre elle consomme des messages reçus. Dans le langage SDL, on peut indiquer qu'un message est "sauvé" (SAVE) dans un état donné, ce qui veut dire que le message reste dans la file (FIFO) et pourrait être consommé quand la composante atteint un autre état. En UML, on dit que l'événement est différé (voir UML "Unexpected event reception"). Ceci est souvent très utile, mais ne sera pas discuté dans ce cours. Dans la suite, nous supposons que les messages sont placés dans une file FIFO avant d'être consommés par la machine à états.
Dans la suite, nous considérons encore l'exemple abcd. Comme avant, les interactions a et b sont exécutées par la composante A, et c et d sont exécutées par B. Mais en plus, nous supposons que les résultats de ces actions doivent être partagés avec l'autre composante. Un tel partage peut être réalisé par l'envoi de messages. Donc, on est amené à considérer le diagramme de séquencement suivant qui décrit le comportement du système. Nous considérons alors que ce diagramme représente les exigences globales du système, c'est-à-dire, les deux composantes devraient réaliser ce diagramme de séquencement.
Comme dans la section qui traite de la communication par rendez-vous (ci-haut), nous aimerions encore montrer comment on peut dériver le comportement des deux agents à partir du diagramme de séquencement ci-dessus. Ce diagramme est considéré comme un cas d'utilisation.
Une méthode de conception typique (pour ce but) est de regarder la séquence des actions réalisées par la composante qui nous intéresse, comme données par les diagrammes de séquencement qui sont à réaliser (dans notre cas seulement un). Ce diagramme de séquencement montre pour l'agent A la séquence des actions suivantes: <!a, !b, ?c, ?d>, où le symbole "!" veut dire envoi, et "?" veut dire recevoir. Similairement, pour l'agent B on obtient la séquence <!c, ?a, ?b, !d>. Ce comportement des agents est montré par les machines à état ci-dessus.
La prochaine étape lors de la conception du comportement des agents est de vérifier que le comportement, comme nous l'avons défini, donne lieu à un comportement global valable. Encore une fois, nous avons les deux problèmes à résoudre: (1) Comment obtenir le comportement du système global à partir des comportements des composantes, et (2) comment comparer le comportement global obtenu avec le comportement défini par les exigences. Dans la suite, nous discutons le premier problème.
Comme dans le cas de la communication par rendez-vous, discuté ci-haut, nous avons à établir le comportement du système composé des deux composantes, mais maintenant communicant par messages, et à déterminer si le comportement correspond aux exigences globales, c'est-à-dire, au diagramme de séquencement ci-haut. Comme avant, on commence avec l'analyse d'accessibilité pour obtenir le comportement global du système.
Mais dans ce cas-ci, l'analyse d'accessibilité est plus difficile à faire que dans le cas des communications par rendez-vous. Dans les systèmes à rendez-vous, on ne considère jamais un état dans lequel un message est en transit. Mais avec la communication par messages, il faut considérer que des messages peuvent être en transit pendant que les composantes sont dans certains états respectifs. Il est important de noter que les messages en transit influencent les états futurs du système global. C'est pourquoi il faut les inclure dans les états globaux pendant l'analyse d'accessibilité.
Les flèches pointillées avec des étiquette d'interaction en rouge indiquent que dans ces états, il y a la possibilité d'une réception non spécifiée. Ceci est une situation où pour le prochain message à être reçu par un agent (déjà dans la file d'entrée), il n'y a pas de transition définie pour recevoir ce message dans l'état actuel de l'agent. Par exemple, dans l'état global " : 2 | a: 1 ", le message a attend d'être reçu, mais l'agent B dans l'état 1 n'a pas de transition pour ce message. La présence de tels états globaux dans le graphe de l'analyse d'accessibilité montre que le comportement des deux agents n'est pas complètement compatible l'un avec l'autre. Dans le cas de notre exemple, nous concluons que le comportement des agents comme défini par notre conception initiale n'est pas complètement satisfaisant.
Puisque les transitions initialement inclues dans le comportement des agents étaient nécessaires pour réaliser le diagramme de séquencement de notre cas d'utilisation, les seules modification de comportement que nous pourrions apporter aux comportement des agents A et B sont des ajouts de transitions. En effet, en regardant les situations de réception non spécifiée dans le diagramme d'analyse d'accessibilité ci-haut, nous constatons que l'agent A devrait être capable de recevoir le message c dans les états 1 et 2, et l'agent B devrait être capable de recevoir le message a dans l'état 1. Nous proposons donc d'ajouter les transitions en rouge montrées dans les diagrammes des agents ci-dessous. Note: Il faut aussi choisir les prochains états d'une façon appropriée - pour cela je ne connais pas de méthodologie.
La raison pour les réceptions non spécifiées rencontrées dans notre exemple viennent du fait que le délai de transmission des messages peut être beaucoup plus court que montré par le diagramme de séquencement, et les messages transmis pourraient déjà arriver dans l'état initial de l'agent recepteur. Puisque l'agent A pourrait envoyer deux messages, a et b, très vite, il se peut que les deux messages arrivent à l'agent B avant qu'il n'envoie son message c. Pour cette raison, nous avons ajouté une autre transition (en bleu) dans le comportement de l'agent B. Notez que nous avons aussi inclu plusieurs autres transitions (en vert) dans le nouveau comportement des agents. Ces transitions ont été introduites pour produire les envois des messages qui sont prévus dans notre diagramme de séquencement initial.
Après avoir obtenu une conception de comportement amélioré pour les deux agents, il faut de nouveau vérifier si cette conception améliorée satisfait les exigences et n'a plus de situation de réception non spécifiée. Faisant de nouveau l'analyse d'accessibilité, nous obtenons le comportement global montré par le diagramme ci-dessus (à droite). Les couleurs de transitions dans le graphe d'accessibilité correspondent aux couleurs des transitions des agents. Pour chaque état qui avait une réception non spécifiée dans le version précédente, le nouveau graphe d'accessibilité contient un nouvel état (en rouge), et la transition en bleu de l'agent B donne aussi lieu à un nouvel état global. Comme on pouvait prévoir, le nouveau graphe inclut le graphe précédent (puisque nous avons seulement ajouté des transitions).
Notez que le nouveau graphe n'a pas de réceptions non spécifiées; cela veut dire que les comportements des deux agents sont compatibles (il n'y a pas de problème en considérant le système comme une boîte noire). Ceci correspond à la consistence interne du système. Mais il faut aussi vérifier que le comportement défini par les exigences est réalisé. Dans notre exemple, il était défini par le diagramme de séquencement - on verra qu'il y a un petit problème.
Le diagramme de séquencement qui décrit le comportement désiré (exigences) est de nouveau montré ci-dessous (à gauche). Quelle est la signification d'un tel diagramme de séquencement ? - (une réponse est expliquée en 1978 dans un article de Leslie Lamport qui parle de "temps logique" et l'ordre partiel entre événements).
Le fait que certains événements ne sont pas ordonnés l'un par rapport à l'autre dans un diagramme de séquencement, veut dire que les exigences de ce diagramme ne définit pas d'ordre entre eux, et différentes séquences d'exécution sont possibles. Pour notre exemple, elles sont montrées dans le premier graphe d'accessibilité. Il est important de noter par contre, que les séquences d'exécution définies par le deuxième graphe d'accessibilité ne sout pas toutes conformes au diagramme de séquencement. Ces séquencements et les diagrammes de séquencements correspondants sont appelés "scénarios impliqués". Par exemple, le deuxième graphe d'accessibilité contient la séquence qui correspond aux états gras dans ce graphe - cette séquence correspond au diagramme de séquencement montré ci-dessous à droite. La différence réside dans l'ordre entre la réception de a et l'envoi de c par l'agent B.
Nous avons la conclusion qu'un diagramme de séquencement, dans beaucoup de cas, ne peut pas être réalisé par des comportements des composantes impliquées sans que ces comportements ne produisent aussi d'autres séquences d'exécution qui correspondent à d'autres diagrammes de séquencement. Ces autres séquencements sont appelés des scénarios impliqués (ils sont impliqués par le diagramme de séquencement original).
Voici un autre exemple d'analyse d'accessibilité (des notes de cours de 2010)
Si l'analyse d'accessibilité identifie des problèmes de conception, alors la spécification du système devrait être revisée. Voici quelques suggestions de certaines stratégies de revision.
