Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

1 Chapitre 2 Spécification des protocoles Machines à états w3.uqo.ca/luigi INF6

1 Chapitre 2 Spécification des protocoles Machines à états w3.uqo.ca/luigi INF6001 Chap 2 2 Exemple: un automate qui modèle le comportement d’un ordinateur Au début il est en état éteint L’événement allumer le met en état allumé L’événement CtrAltDel le met en état login L’événement login le fait passer à un des deux états:  Login accepté  Login refusé S’il accepte, l’événement clique sur icône Word le fait passer en état: prêt pour WordProcessing Noter:  Ce qui précède est une abstraction. Certaines choses ne sont pas dites: p.ex. quel sera le résultat si CtrAltDel ne sont pas frappés simultanément On frappe CtrAltDel avant d’allumer On fait des erreurs de frappe pendant le login Etc. INF6001 Chap 2 3 Concept d’état Le concept d’état du système est une abstraction utile Représente une instantanée (snapshot) du contenu de la machine à un moment donné Déterminé par ce qui s’est produit dans la machine avant Détermine ce qui peut se produire dans le futur État: global: état de tout le système dans son entièreté local: état d’une entité dans le système Transitions d’état: événements qui causent changements d’états INF6001 Chap 2 4 Machines à états Comportements possibles de cette machine: Elle peut: Envoyer un message 1, Puis recevoir un message 3 Puis envoyer un 4 Recevoir un 5, etc. Ou Recevoir un message 2 Puis recevoir un message 5 Puis envoyer un message 4 et retourner à pouvoir recevoir 5, etc. L’état 5 est un état ‘final’ ! 4 état 1 état 2 état 3 état 4 ! 1 ? 2 ? 3 ? 5 état 5 ? 2 INF6001 Chap 2 5 Tableaux de transition d’états état 1 état 2 état 3 état 4 ! 1 ? 2 ? 3 ? 5 ! 4 !1 !4 ?2 ?3 ?5 1 3 2 2 4 3 4 4 2 5 Machine partiellement spécifiée: Les transitions impossibles ne sont pas spécifiées. Nous pouvons interpréter ces transitions comme transitions à un état erreur état 5 ? 2 INF6001 Chap 2 6 Différents modèles à états Les machines à états, aussi appelés automates, sont un concept très utilisé en informatique Un bon nombre de défs existe, chacune avec sa propre théorie avec des légères différences Tous les modèles suivants sont utilisés dans la conception des protocoles, et aussi dans la conception de circuits INF6001 Chap 2 7 Systèmes de transition Le concept le plus général Nous avons un ensemble d’états (pas nécess. fini) et une relation de successeur entre états Exemple de s.d.t.: état 1 état 2 état 3 état 4 INF6001 Chap 2 8 Systèmes de transition étiquetés (LTS, labeled transition systems) Les transitions sont nommées état 1 état 2 état 3 état 4 a b c d e INF6001 Chap 2 9 Utilisation des étiquettes Nous pouvons donner une signification aux étiquettes, p.ex. ?x Veut dire une entrée (input) d’une valeur x !y Veut dire une sortie (output) d’une valeur y état 1 état 2 état 3 état 4 ! 1 ? 2 ? 3 ? 5 ! 4 INF6001 Chap 2 10 Notation + et – sont aussi utilisés pour indiquer la réception ou l’envoi d’un message, respectivement ? et ! sont plus utilisés récemment INF6001 Chap 2 11 Machines de Mealy Chaque arête est étiquetée par une paire Entrée/Sortie Voulant dire que quand une entrée comme spécifié se vérifie, il y a la sortie spécifiée et la transition d’état a aussi lieu état 1 état 2 état 3 état 4 1/b 2/a 3/d 5/c 4/b Quand l’entité spécifiée reçoit un 2 en état 1, elle fait sortir un a et le système effectue une transition à l’état 2 INF6001 Chap 2 12 Machines de Moore Plus semblables aux systèmes de transitions étiquetés Chaque arête est associé à un symbole, qui dénote un événement abstrait (une entrée,une sortie…) qui cause la transition état 1 état 2 état 3 état 4 b a d c b INF6001 Chap 2 13 Le passage du temps dans les machines En principe, les transitions sont instantanées Le temps passe quand le système est dans un état Cependant il y a plusieurs variations à ce concept Différents types de machines temporisées INF6001 Chap 2 14 Machines communicantes Une machine à états peut définir un système entier ou une partie de système Si elle définit une partie d’un système, elle sera composée avec autres machines Plusieurs méthodes de communications ont été utilisées Nous en discuterons ici deux: Synchrones Asynchrones INF6001 Chap 2 15 Communication asynchrone Dans la communication asynchrone, les machines communiquent par des canaux pouvant contenir des primitives de communication (PDUs ou SDUs) Normalement modélisés par des files FIFO infinies et sans pertes de données Ces canaux sont une abstraction pour le fournisseur de service sous- jacent Une machine peut donc mettre des données dans une file et continuer son travail, peut être mettant d’autres données dans la même file plus tard L’autre machine prendra des données de la file quand elle le voudra. … … CAB CBA Machine A Machine B A B Service Provider INF6001 Chap 2 16 Modèles de machines à états finis communicantes asynchrones (appelés aussi CSM ou CFSM, Communicating Finite-state Machines) Machines à états finis communicantes à moyen de files d’attentes P.Ex un client et serveur. 1 requête d’accès 2 permission d’accès 3 refus d’accès 4 terminaison d’accès … … !1 ?3 ?2 !4 10 11 12 ?1 !3 !2 20 21 22 Files FIFO et sans pertes C12 C21 ?4 INF6001 Chap 2 17 Exécution du système L’état global initial est  l’ensemble de tous les états initiaux des composants  et l’ensemble de tous les contenus de files initiales Dans ce cas <10,20>,<ε, ε> ε file vide… Dans cet état, le seul événement qui peut se produire est l’envoi d’un 1 par le client Il est mis dans la file, puis qui peut se produire est la réception de 1 de la part du serveur client serveur … … !1 ?3 ?2 !4 10 11 12 ?1 !3 !2 20 21 22 Files FIFO et sans pertes C 12 C 21 … … !1 ?3 ?2 !4 10 11 12 ?1 !3 !2 20 21 22 Files FIFO et sans pertes … … … … !1 ?3 ?2 !4 10 11 12 ?1 !3 !2 20 21 22 Files FIFO et sans pertes C 12 C 21 ?4 INF6001 Chap 2 18 Construction de la machine globale du système Chaque état global du système spécifie:  L’état des deux machines communicantes  Le contenu des deux files Par exemple, au début les deux machines sont dans leur état initial Le seul premier événement possible est que le client met 1 dans la file et passe à l’état suivant, tandis que la deuxième machine reste sur son état Le serveur peut puis recevoir Après ça, le serveur peut envoyer  un 3, ce qui change l’état global à <11,20>, avec un 3 dans la file de sortie du serveur  ou un 2, ce qui change l’état global à <11,22>, avec un 2 dans la file de sortie du serveur Etc. … … !1 ?3 ?2 !4 10 11 12 ?1 !3 !2 20 21 22 Files FIFO et sans pertes C 12 C 21 … … … … !1 ?3 ?2 !4 10 11 12 ?1 !3 !2 20 21 22 Files FIFO et sans pertes C 12 C 21 C 12 C 21 ?4 Transitions possibles à l’état initial? INF6001 Chap 2 19 … … !1 ?3 ?2 !4 10 11 12 ?1 !3 !2 20 21 22 Files FIFO et sans pertes C12 C21 ?4 Transitions possibles à l’état initial? Transitions possibles? INF6001 Chap 2 20 … … !1 ?3 ?2 !4 10 11 12 ?1 !3 !2 20 21 22 Files FIFO et sans pertes C12 C21 ?4 1 Transitions possibles? INF6001 Chap 2 21 … … !1 ?3 ?2 !4 10 11 12 ?1 !3 !2 20 21 22 Files FIFO et sans pertes C12 C21 ?4 Retrouver un état précédent INF6001 Chap 2 22 … … !1 ?3 ?2 !4 10 11 12 ?1 !3 !2 20 21 22 Files FIFO et sans pertes C12 C21 ?4 Après la trace: !1, ?1, !3 nous nous retrouvons à l’état global suivant: 3 La seule transition possible nous ramène à un état déjà vu. INF6001 Chap 2 23 La machine globale du système (composition asynchrone) <10,20>,<ε, ε> <11,20>,<1, ε> <11,21>,< ε, ε> <11,20>,< ε, 3> <11,22>,< ε, 2> <12,22>,< ε, ε > <10,22>,< 4, ε > <11,22>,<[4,1], ε > … … !1 ?3 ?2 !4 10 11 12 ?1 !3 !2 20 21 22 Files FIFO et sans pertes C12 C21 … … !1 ?3 ?2 !4 10 11 12 ?1 !3 !2 20 21 22 Files FIFO et sans pertes C12 C21 C12 C21 !1 ?1 !3 !2 ?2 !4 !1 ?4 ?4 ε : canal vide [4,1] :canal contenant 4 puis 1 ?4 ?3 INF6001 Chap 2 24 Équivalence d’états Pourquoi sommes-nous retournés à uploads/Industriel/ chap02-fsm-mpssr-ht.pdf