Un exemple d'analyse d'accessibilité (pris de [Braek])

Note: Ceci était inclus dans les notes de cours de 2010. La notation pour les états globaux est un peu différente que dans les notes de cours de 2011. - page avec les diagrammes seulement

On peut essayer à explorer toutes les pas d'exécution qui peuvent arriver avec des séquences entrées différentes et toutes les interlacements possibles de la concurrence interne. Cela est appelé une analyse d'accessibilité (on analyse quels états du systèmes global sont accessible à partir de l'état initial). Un état du système global est constitué des états de tous les processus concurrents et tous les message en transit (ou dans le cas d'SDL, du contenu - en terme de messages en attente - de toutes les files d'entrées des processus). 

Un exemple d'une tel analyse est montré dans le livre de Braek: Figure 12.1 montre deux processus SDL. La figure 12.2 montre des diagrammes de transitions avec des états intermédiaires (entre la lecture d'une entrée et la production d'une sortie dans la même transition SDL).

Figure 12.3 (ci-dessous) montre le résultat d'une analyse d'accessibilité (incomplète, certaines branches ne sont pas explorées). Chaque transition dans ce graphe correspond à une entrée lue par un processusou à une sortie produit par un processus. L'état en bas représente un blocage : aucune autre transition est possible à partir de cet état. Notation: Un état global, représenté par un oval, est identifié par "x1, s1 / x2, s2z" où si (i = 1 ou 2) est l'état de la machine d'état à gauche ou à droite, respectivement, et xi est le contenu de sa file d'entrée. Notes:

• L'état (2) (et d'autres) montré dans la figure 12.2 est un état intermédiaire. Le processus ne peut pas accepter un message de la file d'entrée dans un tel état intermédiaire.
• Les transitions notées "!Ra", "!Rb", "!Ea" et "!Eb" sont dues à l'environnement qui génère un message Ra ou Rb, respectivement.
  • Système ouvert: Ici, aucune hypothèse est faite sur l'environnement des deux processus A et B. Cela veut dire que les entrée de l'environnement peuvent arriver n'importe quand dans un ordre quelconque.
  • Une hypothèse plus raisonnable pourrait être la construction d'un Système fermé: il faut ajouter une spécification du comportement de l'environnement. Dans le cas de notre exemple, on pourrait prévoir deux processus supplémentaires Ua et Ub qui communiquent avec les processus A et B, respectivement. Ils pourraient avoir le comportement suivant: (1) envoyer un signal Rx, (2) attentre un signal Ax, (3) envoyer un signal Ex et recommencer au point (1). Note: un Système fermé n'a pas d'interactions avec son environnement.
• La figure 12.3 contient deux états étiquettés en deux lignes. Chaque ligne représente, en effet, un état différent. Il aurait été mieux de dessiner deux états différents dans chaque cas. Par exemple, la transition "!Rb" mene dans l'état "-3/Sb.Rb,1" (partie gauche du diagramme), ce que veut dire que le process A (a gauche) est dans l'état 3 et a une file d'entrée vide, et le processus B (a droite) est dans l'état 1 et sa file contien Sb puis Rb). Cet état global peut générer la transition "?Sb" qui donne lieu à une "reception non spécifiée", c'est-à-dire, le processus B (qui est dans l'état 1) n'a pas de transition spécifiée pour le cas que l'entrée Sb est reçu. Pour SDL, cela veut dire que le message est perdu, mais cela pourrait aussi dire que les deux processus ne sont pas compatible l'un avec l'autre et que ceci est une erreur de conception.
• La partie mise à jaune dans le diagramme montre une vue plus abstraite de l'analyse d'accessibilité où les états intermédiaire de la figure 12.2 ne sont par explicitement représentés. Dans une telle analyse, chaque transition SDL est considérée comme une transaction qui est exécutée au complet, en exclusion mutuelle avec les transitions des autres processus du système. Une telle analyse donne lieu à moins d'états, mais l'hypothese d'exécution des transitions en exclusion mutuelle n'est pas réaliste; il faut donc être prudent avec un tel approche.
• Comme mentionné ci-haut, l'état "-,3 / -,3" est un blocage. Cet état est atteint après que les messages Sa et Sb, générés à partir de l'état global "-,2 / -,2", soient perdu parce qu'ils représentent une reception non spécifiée dans l'état acceptant 3 dans les deux machines. Après avoir analysé le comportement du système pour le cas qu'un seul message Ra ou Rb est reçu de l'environnement (les deux machines retournent dans leur état initial), on peut être surpris de détecter ce blocage. Question: Comment peut-on éviter un tel blocage ? - Comment devrait-on reviser la specification de ce système pour obtenir une spécification sans problème ? - Il n'y a pas de reponse générale à cette question. Néanmoins, dans beaucoup de cas où des receptions non spécifiées sont rencontrées, on peut ajouter une transition à la spécification originale pour consommer l'entrée non spécifiée; mais quel devrait être le comportement à la suite de cette reception ? - Dans beaucoup de cas, de tels problèmes sont dus à des "initiatives en compétition" (comme dans notre exemple où les deux côtés prennent des initiatives contradictoires). Dans un article de 1984, Gouda propose que le concepteur devrait donner la priorité à une des deux côtés. Si, dans notre exemple, nous donnons la priorité à la partie à droite, la machine à droite peut ignorer un message Sb dans l'état 3, mais la machine à gauche, quand il reçoit un message Sa dans l'état 3, devrait suivre la "proposition prioritaire" de la droite et faire ce qui est prévu pour la reception de ce message, c'est-à-dire envoyer un message Ga et aller dans l'état 8.