LES APPROCHES MIXTES ASYNCHRONES UML POUR LE TEMPS REEL

Télécharger le fichier pdf d’un mémoire de fin d’études

Gestion de la complexité

Concernant la gestion de la complexité6, nous nous sommes plus particulièrement concentrés sur :
• Les difficultés de l’obtention précoce d’une compréhension globale et synthétique du système en cours de développement,
• La définition ou l’utilisation de représentations communes afin de faciliter le dialogue entre les clients et les différents métiers d’ingénieurs spécialisés dans le développement de parties du système,
• Les problèmes de structuration posés par la gestion d’un grand nombre d’informations de modélisation.
En adoptant les principes de la modélisation orientée objet, nous apportons une première réponse à la structuration du système et par conséquent à cette gestion de la complexité. La technologie des objets et des composants a montré qu’elle est garante de certains facteurs de qualité tels que la modularité, la flexibilité, la réactivité et le suivi des besoins [Booch-1994] [Blair-1998]. Néanmoins, l’application des concepts de la modélisation à objets au domaine du temps réel n’est pas immédiate. En effet, bien que les concepts OO (Orienté Objet) puissent être étendus afin de prendre en compte directement le parallélisme, un certain nombre de difficultés demeurent. Nous détaillerons des adaptations possibles en §I.2.2.
En choisissant la notation UML, une deuxième réponse est apportée concernant la gestion de la complexité du système. UML est utilisé comme un langage commun facilitant les échanges et la communication entre les différentes équipes (commanditaires et clients compris) intervenant sur le développement du système. En §I.2.3, les avantages, mais aussi les limites, de l’utilisation d’UML pour le temps réel sont détaillés.

Maîtrise des aspects dynamiques

Par maîtrise de l’aspect dynamique, nous entendons la gestion du parallélisme et des 6 Nous reprenons l’utilisation de G. Booch de ce mot [Booch-1994]. Sous le terme complexité, nous regroupons les nombreux problèmes à traiter simultanément concernant les activités de développement (gestion de projet, gestion humaine,…), la difficulté de compréhension de l’environnement et du système (de par sa taille, sa nature…) synchronisations entre activités du système. De par la définition que nous avons donné précédemment aux contraintes temporelles, nous considérons que cette problématique (détaillée en §I.2.3) est étroitement liée à celle posée par la modélisation, la vérification et la validation des contraintes temporelles.
Cette nécessité de vérification et de validation conduit à l’utilisation de modèles formels. En effet, dans le cas des STR que nous étudions, il ne suffit pas de prouver que le système se comporte logiquement selon sa spécification. Il doit aussi répondre dans les délais de temps impartis. En §I.2.4 nous présentons les différents modèles formels qui pourraient être utilisés pour remplir ces objectifs et nous motivons notre choix pour l’un d’eux.
Toutefois, l’utilisation seule de méthodes formelles pose certains problèmes. L’un des plus importants reste la lisibilité et la compréhension des modèles, trop souvent réservées à des spécialistes et peu adaptées au franchissement des fameux « semantic gaps » [Fraser-1991]. Il devient difficile de communiquer avec les clients, les différents corps de métiers engagés dans le projet (automaticien, électronicien, spécialiste réseaux, spécialiste base de données…) et les utilisateurs. Or, ce souci de communication entre intervenants sur le projet est important dans la construction de systèmes aussi complexes et hétérogènes que les STR.

Vers une approche mixte

Les objectifs choisis, décrits dans les paragraphes précédents, nous ont donc incités à proposer une approche mixte mêlant l’utilisation de représentations UML (simples et facilement utilisables par un ingénieur) avec des modèles mathématiques formels. En effet, nous pensons qu’il est essentiel d’offrir aux utilisateurs une représentation la plus simple possible (semi-formelle) mais qui resterait issue d’une modélisation formelle.
Néanmoins, ce couplage soulève en lui-même un certain nombre de questions. Par exemple, comment rendre compatibles les modèles formels avec la représentation semi-formelle ? Quelles passerelles, transformations ou relations entre les représentations formelles et semi-formelles peuvent être définies ? Ces différents points sont détaillés au§I.2.5.

La modélisation objet et le temps réel

L’approche OO se distingue de l’approche fonctionnelle, par le fait qu’un système est considéré comme une collection d’entités « autonomes », composées d’un état et fournissant des services au monde extérieur. Ces entités, appelées plus communément des objets, collaborent à la réalisation des fonctionnalités du système. La communication entre les objets s’effectue selon le concept de client-serveur. Ce procédé a pour effet de protéger l’état des objets contre des accès accidentels de la part d’autres entités. L’objet est vu comme un module autonome, fortement cohérent et entretenant le minimum de relations de dépendances avec d’autres objets. En outre, l’approche OO offre deux mécanismes puissants d’abstraction à travers les hiérarchies de composition et d’héritage.
Cependant, cette utilisation des mécanismes OO dans le domaine du temps réel nécessite quelques adaptations. Comme dans la programmation OO concurrente [Briot-1996], deux grandes approches de modélisation des objets (nous parlerons de représentations) se retrouvent :
• La représentation applicative fournit une bibliothèque d’objets dédiés à la prise en compte des mécanismes de bas niveau pour la gestion du temps réel. Des classes comme « Ordonnanceur », « processus » et « sémaphores » sont ainsi définies. Cette représentation a tendance à laisser l’analyste-concepteur en charge de deux tâches distinctes : d’une part, la modélisation de l’application en terme d’objets et, d’autre part, la gestion du parallélisme et de la répartition (également exprimée en terme d’objets, mais pas les mêmes !).
• La représentation intégrée, à la différence de la précédente, vise à intégrer les mécanismes objets avec les mécanismes du parallélisme et de la répartition, au sein d’une même entité. Trois niveaux d’intégration sont constatés :
o Le premier niveau intègre la notion d’objet et d’activité (processus ou tâche).
L’objet (nommé « objet actif ») est considéré comme doté d’une ressource de calcul propre. Suivant les approches, l’objet traitera les requêtes de manière séquentielle ou simultanée. Dans le premier cas, la concurrence provient uniquement des activités indépendantes des divers objets (on parle alors de concurrence inter-objets). Si l’on permet à l’objet de traiter plusieurs requêtes simultanément, on parle de concurrence intra-objet.
o Une deuxième intégration associe la synchronisation à l’activation des objets. La transmission de messages est considérée comme une synchronisation implicite entre l’émetteur et le récepteur. On parle alors d’objets synchronisés. Différents protocoles de communication sont définies (synchrones, asynchrones…) et des mécanismes de contrôle de la concurrence des invocations sont précisés (par exemple en associant une garde au niveau de chaque méthode de l’objet).
o Enfin, le troisième niveau d’intégration considère l’objet comme unité de répartition, on parle alors d’objets répartis. Les objets sont vus comme des entités pouvant être distribuées et dupliquées sur différents sites. La métaphore de la transmission de message est étendue à la communication à travers un réseau quelconque.
La représentation intégrée nous semble la plus intéressante. Outre le fait de simplifier la modélisation et d’éviter une structuration « à plat », elle permet d’intégrer les mécanismes du temps réel et de la distribution sur une seule entité : l’objet actif, synchronisé et réparti. Néanmoins, l’utilisation de la représentation intégrée dans le domaine du temps réel reste encore difficile car certains conflits ne sont pas totalement résolus (par exemple, le problème de l’héritage du comportement). Ces difficultés seront détaillées lorsqu’elles seront traitées dans la partie II de ce mémoire (cf. §II.2.1). Les choix concernant la stratégie de modélisation OO adaptée au temps réel ayant été motivés, UML est maintenant présentée.

UML et le temps réel

UML [OMG-1997b] a été définie par l’OMG (Object Management Group) en novembre 1997 comme la notation normalisée des méthodes OO. C’est une notation générique pouvant s’adapter à n’importe quelle méthode OO et pour n’importe quel type d’application.
Elle est devenue rapidement un standard de facto et elle est maintenant très utilisée dans le monde industriel. Différentes versions d’UML ont été depuis publiées. Pour notre part, nous utilisons dans ce mémoire la version 1.3 [OMG-1999b].
Nous supposons que le lecteur possède une première connaissance d’UML. De nombreux ouvrages expliquent la notation UML [Booch-1998] [Muller-1997]. Nous en proposons aussi un résumé [Delatour-2000].

Les bénéfices d’UML

Le principal argument en faveur d’UML est son statut de standard de facto. Parmi la multitude de méthodes OO (et les notations qui leur sont associées), disposer d’un consensus dans leur représentation est un avantage certain.
Bien qu’issu des notations OMT et OOD, UML possède un plus grand pouvoir d’expression que ses aînées et couvre une plus grande partie du cycle de développement. Dans la description des aspects statiques du système, la richesse de description est grande et rien ne semble avoir été oublié. La question de la représentation d’un objet ou d’une classe et de ses relations statiques ne se pose plus.
Cet état de fait nous permet d’espérer un meilleur dialogue avec les clients, qui n’ont plus qu’un seul formalisme à connaître (puisque UML est un standard). De plus, les diagrammes UML sont assez intuitifs et aisés à comprendre, car ils sont une reprise de formalismes éprouvés et utilisés depuis une décennie.
Par ailleurs, les possibilités d’extension [Alhir-1999] de cette notation la rendent extrêmement adaptable. Ces mécanismes d’extension sont multiples et très intéressants. En effet, UML repose sur une description en 4 couches afin d’être compatible avec le standard MOF (Meta-Object Facility) [OMG-1997a] de l’OMG. Chaque couche est une instance de sa couche supérieure, la plus haute couche étant une instance d’elle-même. Ces quatre couches sont :
• Le méta-méta-modèle : Il définit la structure du méta-modèle et le langage nécessaire à la définition du méta-modèle. Il est défini de manière réflexive.
• Le méta-modèle : C’est une instance du méta-méta-modèle. Il définit le langage de la couche « modèle », en l’occurrence ici les diagrammes et les éléments UML.
• Le modèle : Il représente l’ensemble des modèles permettant de décrire un domaine d’information. Ce sont, par exemple, les classes définies pour le système en construction.
• Les objets utilisateur : C’est une instance du modèle. Ce sont les objets du système exécuté.
Il est ainsi possible de définir des extensions au niveau du modèle ou au niveau du méta-modèle. Cela se fait, par exemple, en spécialisation certains éléments UML (par utilisation des stéréotypes et des valeurs étiquetées). Les extensions du méta-modèle pouvant être regroupées dans un profil UML, elles peuvent être alors directement employées dans des modèles UML adaptés à un domaine d’étude particulier. En §I.2.6.2 d’autres avantages apportés par cette structuration en 4 couches sont détaillés.
Enfin, la disponibilité d’AGL (Atelier de Génie Logiciel) UML libres permettent d’implémenter des prototypes et d’intégrer des techniques et des concepts issues du monde de la recherche.

Les limites d’UML pour le temps réel

Parmi les lacunes d’UML (voir par exemple [Hay-1998] [Simons-1998;Simons-1999] [Sourrouille-1998]), nous n’évoquerons que les plus générales concernant les aspects comportementaux.

Une sémantique UML imprécise

La plus importante critique est liée à l’absence d’une sémantique formelle des modèles UML décrivant le comportement du système [Breu-1997] [Boas-1998] [Lano-1998]. Cette dynamique peut être exprimée, soit à l’aide des diagrammes d’interactions (diagrammes de séquence et de collaboration), soit à l’aide des diagrammes d’états (diagrammes d’états/transitions et les diagrammes d’activités). Les premiers permettent la description d’une histoire (ou à la limite d’un ensemble d’histoires), tandis que les seconds permettent la représentation de tous les comportements possibles d’un objet et, par extension, du système.
En effet, malgré son titre, le document « UML Semantics » [OMG-1999a] ne décrit, pour ainsi dire, que la syntaxe d’UML (en précisant son méta-modèle à l’aide de diagrammes de classes et de contraintes OCL7). Concernant la sémantique, la description est insuffisamment précise. Elle laisse malheureusement un grand nombre de questions sans réponse. En outre, peu de règles sont définies pour vérifier la cohérence d’un diagramme et, encore moins pour vérifier la cohérence entre les diagrammes.
Ce constat touche particulièrement celui des diagrammes d’états/transitions. Signalons en premier lieu les divergences entre les diagrammes d’états/transitions et le formalisme dont ils sont issus : les Statecharts [Harel-1987]. Les hypothèses des Statecharts (à savoir, communication immédiate, primitives de gestion du temps, actions instantanées, capture immédiate et non-conservation des événements) ne sont plus respectées. Par ailleurs, des extensions comme les états de type synchStates ou l’utilisation de fourches d’alternatives font que les techniques existantes de validation pour les Statecharts ne sont donc plus directement applicables. Ainsi, même une simulation des diagrammes d’états/transitions est impossible. De nombreux chercheurs ([Lilius-1999a] [Gogolla-1998] [Gehrke-1998] [Geisler-1998] [Hamie-1998] [Reggio-1999]) ont signalé que de nombreuses règles étaient, soit manquantes (par exemple aucune politique de choix des évènements en attente n’est définie [Börger-2001]), soit simplement incohérentes (priorités de tir des transitions en conflit entre super et sous état [Simons-2000]). Certes, cette extension UML des Statecharts a gagné en convivialité graphique mais au détriment des vérifications formelles qui deviennent impossibles à effectuer sans définir une sémantique cohérente et précise [Schäfer-2001] [Börger-2000].
Afin de corriger cette lacune d’UML, de nombreuses propositions ont donc été effectuées par la communauté scientifique et l’OMG a lancé un RFP8 « Action Semantics » [OMG-1998]. Une première réponse a été apportée [OMG-2000]. Elle introduisait la notion d’occurrence et d’exécution des modèles UML [Pennaneac’h-2001] [Sunyé-2002]. Cette réponse levait alors un certain nombre d’ambiguïtés concernant la sémantique d’UML. Toutefois, ce travail n’a pas été repris dans les spécifications UML (1.4 et 1.5) dans lesquelles seule la partie présentant un langage permettant de spécifier des actions (création, destruction, expression conditionnelle, lecture/écriture…) est présente [OMG-2002a] [OMG-2002c]. Pour ces raisons, nous n’avons pas étudié plus en détail cette réponse au RFP et ne l’avons pas intégrée à notre recherche.

Une syntaxe insuffisante pour le temps réel

L’autre aspect déficient d’UML, par rapport à son utilisation pour les STR, est lié à sa mauvaise expression de l’aspect dynamique.

Pas de vue globale et synthétique de la dynamique du système

Malgré un grand nombre de représentations différentes (quatre) dédiées à la modélisation du comportement, UML ne propose pas de diagramme permettant de synthétiser la plupart de ces informations. Il est par conséquent difficile de disposer d’une vue globale d’un objet ou d’une partie du système. Ainsi, par exemple, le type de communication entre objets (synchrone ou asynchrone) ne peut être graphiquement représenté que sur les diagrammes d’interaction et non sur les diagrammes d’états/transitions9. Cette absence de diagramme synthétique est gênante quand il s’agit de communiquer avec plusieurs équipes travaillant sur un même projet. Il faut faire appel à plusieurs types de diagrammes pour parvenir à rassembler toute l’information concernant l’aspect dynamique. Par ailleurs, cela multiplie les risques d’incohérences entre les différentes vues.

A propos des diagrammes d’états/transitions UML

Puisque les diagrammes d’états/transitions sont issus du formalisme des Statecharts, nous retrouvons les mêmes bénéfices et controverses suscités par leurs aînés concernant la description de STR.
En effet, les Statecharts sont bien adaptés à des couches où la plupart des opérations sont séquentielles. En particulier, ils permettent de résoudre graphiquement le problème de l’explosion combinatoire par la généralisation et l’agrégation d’états. Ils permettent également de représenter « callEvent » (dans le cas d’une communication synchrone) ou par un « SignalEvent » (dans le cas d’une communication asynchrone).
En revanche, dès que les niveaux d’ordonnancement de processus, de tâches ou de structuration abstraite sont nécessaires, le parallélisme et la distribution deviennent conséquents. La lisibilité des Statecharts par des non-spécialistes est alors remise en question. Ils n’offrent, en particulier, aucun mécanisme graphique simple de représentation explicite des contraintes et des dépendances temporelles (délais, chiens de garde…). Dans les Statecharts, comme dans les diagrammes d’états/transitions UML, le temps est introduit à l’aide de fonctions renvoyant un booléen lorsqu’un certain laps de temps s’est écoulé. Les relations temporelles entre les différents événements sont alors implicitement traduites dans les diagrammes d’états/transitions. Il devient malaisé de suivre les chemins de commutations depuis un état initial jusqu’à un état final ou inversement [Giese-1999]. Pourtant, c’est un besoin important dans la modélisation des STR. En effet, dans le premier cas, cela permettrait de suivre l’ordre des événements. Dans le second cas, il serait alors possible de connaître les chemins et les états initiaux susceptibles de conduire le système dans un état donné (non désiré par exemple).
Par ailleurs, une autre critique concerne l’abstraction de comportement introduite par les Statecharts [Paludetto-1999]. La structuration offerte est typiquement celle d’une approche fonctionnelle. De ce fait, elle peut induire une répartition centralisée du contrôle : un objet centralisateur, représentatif d’un niveau système, distribue le contrôle à des objets de niveau inférieur. Or, une telle vision des liens comportementaux va à l’encontre de l’indépendance spatiale et temporelle10 préconisée par l’approche OO. En effet, dans une vision OO, un système se trouve dans un macro-état donné, défini par le vecteur d’états de ses sous-systèmes. En terme de dynamique, ce sont ces derniers qui, par leur coopération et leurs sous-états, définissent l’état de l’objet système.

Une représentation limitée du temps

L’expression des CT explicites reste limitée en UML 1.3.
Sur les diagrammes de séquence, le temps s’écoule de haut en bas. L’axe vertical peut être gradué afin d’exprimer des contraintes temporelles. Deux primitives (Event.ReceiveTime et Event.SendTime) permettent de différencier les instants où les messages entre objets sont envoyés et reçus. Pour le reste, des notes dans un format non spécifié, peuvent être utilisées afin de définir des contraintes temporelles.
Dans les diagrammes d’états, en plus d’Event.ReceiveTime et d’Event.SendTime, les primitives When et After peuvent être utilisées. When (date = janvier 1999) permet de spécifier un temps logique (ou échantillonné) absolu. After (x unités de temps) permet de représenter un temps relatif.
Il n’est donc pas possible, sans créer une extension à UML [Flake-2002a] [Sendall-2001] [Bodeveix-2002], de spécifier, par exemple : des événements ou des activités périodiques, de donner des informations probabilistes, de définir des relations entre temps physiques et temps logiques, de différencier simplement les CT internes et externes… Dans le chapitre suivant (§I.2.4), les besoins que nous avons identifiés concernant la modélisation des contraintes temporelles sont détaillés.
Conscient de ce fait, l’OMG a lancé le RFP « UML Profile for Schedulability, Performance and Time » qui définit, entre autres, une syntaxe plus riche à UML sur cet aspect temporel. Une réponse [OMG-2002d], en phase finale d’adoption, est disponible. Les exemples donnés portent sur un enrichissement des diagrammes de séquence et d’activités par un ensemble de notes précisant le comportement temporel des éléments (événements et actions) de ces diagrammes (périodicité, durée, probabilité…). Nous avons pu vérifier que nos travaux sur les contraintes temporelles (en particulier sur leur représentation) sont compatibles avec cette réponse. Nous avons donc pu adapter, dans la mesure du possible, nos notations concernant les CT afin de respecter celles proposées par cette réponse. Cependant, cette adaptation ne reste que syntaxique et n’est pas complète pour trois raisons :
• La réponse est arrivée récemment et nous n’avons pas eu le temps de l’intégrer complètement à nos travaux.
• Elle modifie actuellement le méta-modèle UML1.4 pour faire apparaître la notion d’exécution d’action (ce qu’un profil UML n’est pas autorisé à faire, en théorie).
• La définition du temps proposée entre en contradiction avec des réponses à d’autres RFP (par exemple avec « Action Semantics »).
Toutefois, une révision de cette réponse est en cours pour le futur UML 2.0 et ces lacunes devraient disparaître.

Problèmes abordés sur les contraintes temporelles

Problèmes liés à la modélisation des CT

La plus importante difficulté concernant la modélisation des CT réside dans la grande diversité d’expression des relations d’ordre. Remarquons qu’elles sont données sous différentes formes (pas forcément exprimées en termes de contraintes temporelles explicites) et de différentes manières par les clients. Par exemple, le freinage d’une voiture peut être défini en terme de synchronisation des roues, en terme d’une vitesse différentielle tolérable entre les roues… Pour le système informatique, cela peut correspondre à la définition d’une contrainte temporelle synchronisant la vitesse angulaire des deux roues.
En outre, les CT externes peuvent être exprimées dans différents types de temps, tandis que les CT internes sont exprimées dans un temps informatique (échantillonné ou logique). Cette diversité dans l’expression des CT externes provient de l’hétérogénéité de l’environnement. Ce dernier peut effectivement être composé de différents équipements mesurant et utilisant le temps différemment. Certains d’entre eux manipulent un temps continu, d’autres un temps échantillonné, d’autres encore des séquences d’événements. Par ailleurs, le système informatique peut lui-même être décomposé en sous-systèmes, répartis sur plusieurs nœuds ne fonctionnant pas à la même cadence ou ne partageant pas une même horloge globale.
Une autre difficulté est liée à la nécessité d’exprimer certains besoins dans différentes échelles de temps. Par exemple, dans un atelier, une procédure automatique de diagnostic peut être lancée toutes les semaines, tandis que la commande d’un bras de robot sera exprimée en millisecondes. Cette granularité des temps impose de définir des correspondances ou des intervalles de correspondance entre ces différentes échelles. Il faudrait donc au moins disposer d’un formalisme permettant l’expression d’intervalles temporels (voir [Corsetti-1991] pour une description détaillée de cette problématique).
Une première solution est de disposer d’un formalisme unifié, suffisamment riche, de modélisation de ces différents types de temps. Ce formalisme doit idéalement pouvoir exprimer toutes les catégories de CT, qu’elles soient implicites, explicites, déterministes, probabilistes, sous formes de durées ou d’intervalles.

Problèmes liés à la vérification des CT

L’analyste-concepteur devra naturellement veiller à ce que les CT internes qu’il définit, respectent les CT externes. Or, établir des correspondances entre les CT externes et les CT internes est délicat. Une même CT externe peut être en relation avec une multitude de CT internes. Ainsi, dans le cas simple d’un temps de réponse entre un stimulus et une réponse, cette CT externe va être en relation avec plusieurs CT internes. Nous aurons des CT sur la phase de capture du stimulus, sa ou ses transformations successives et sa génération sous forme de réponse. L’identification de ces dépendances n’est pas simple ou immédiate. Il sera toujours difficile pour le concepteur d’envisager les conséquences de la modification d’une CT sur le reste des CT ou tout simplement de vérifier leur cohérence.
De plus, l’analyste-concepteur doit pouvoir disposer de moyens de dérivation de CT à partir d’autres CT, en termes de composition ou de décomposition. Cela lui permet de raisonner successivement sur des vues globales puis détaillées.
Par ailleurs, on retrouve les problèmes classiques de la synchronisation : le partage de ressources et les possibilités de famines et de blocages qui en découlent [Chang-1993]. Toutefois, puisque nous ne nous sommes intéressés qu’aux premières étapes du développement, nous n’avons pas abordé les problèmes de conception détaillée rencontrés lors de l’ordonnancement des activités sur des processeurs.
Pour un système de grande taille, il est indispensable que cette activité de vérification soit automatisée et repose sur un modèle formel. Les modèles, aptes à répondre à l’ensemble des critères énumérés, sont maintenant présentés.

Les modèles formels pour le temps réel

Afin de présenter les modèles formels adaptés au traitement temporel, nous avons privilégié une taxonomie basée sur deux critères : le premier est lié aux techniques d’analyse offertes, le second aux paradigmes de modélisation. Par conséquent, un rappel sur les techniques d’analyse est d’abord effectué, puis la taxonomie est donnée. Enfin, notre choix pour un modèle formel conclut ce chapitre.

Rappels sur les techniques d’analyses formelles

Il existe essentiellement deux types de techniques d’analyse formelle : celles fondées sur la démonstration de théorèmes (theorem­proving) et celles basées sur les évaluations de modèles (model­checking). Elles ont été étudiées intensivement dans la littérature et de nombreux algorithmes et outils ont été développés (voir par exemple [L’Her-1997]).
Les démonstrations de théorème
Avec les démonstrations de théorèmes, le modèle du système et les propriétés désirées sont exprimés comme des formules d’une logique [Clarke-1996a]. A partir de l’ensemble des formules représentant le système, les propriétés doivent être retrouvées par des mécanismes de déduction et de substitution. Aux différentes étapes de cette preuve, les formules représentant le système sont réécrites en respectant un ensemble de règles jusqu’à l’obtention de la propriété.
Cette technique est puissante : elle permet de prouver des propriétés sur des systèmes de toute taille (à la limite infinie). Cependant, si elle permet de montrer qu’un système est correct, elle n’indique pas clairement les erreurs lorsqu’elles existent. C’est donc une méthode utilisée généralement en dernière phase de vérification.
Le plus gros problème pour son utilisation est qu’elle n’est pas automatisable (et ne le sera jamais11). C’est pourquoi la technique entièrement automatisée des évaluations de modèles est généralement préférée [Clarke-1996b].

Taxonomie des modèles formels

Par rapport aux techniques d’analyse

Trois grands groupes peuvent se dégager12 [Bucci-1995] :
• Les modèles déclaratifs, qui se fondent sur les notations mathématiques (axiomes, clauses,…) et qui donnent une vue abstraite de l’espace d’état à l’aide d’équations logiques et algébriques. Le système est décrit en spécifiant ses propriétés globales. Ce type d’approche privilégie l’analyse formelle de type démonstration de théorème. Dans cette approche se retrouvent : les logiques temporelles (RTL [Jahanian-1986], TLA [Lamport-1994], TRIO+ [Mandrioli-1992],…), les langages déclaratifs à flots de données comme LUSTRE [Halbwachs-1991] ou SIGNAL [Benveniste-1990], les méthodes algébriques de type VDM [Jones-1993], VDM++[Dürr-1995], Z [Spivey-1989]…
• Les modèles opérationnels (ou impératifs), qui se définissent en terme d’états et de transitions. Ils sont, par conséquent, intrinsèquement exécutables. La simulation est généralement possible et des analyses formelles (par model-checking) sont généralement proposées. Dans cette famille se retrouvent : les formalismes comme les RdP [Petri-1962], SDL [Union-1992], les modèles basés sur CCS de Milner [Milner-1980] et sur CSP de Hoare [Hoare-1978] comme les algèbres de processus telles que LOTOS [Eijk-1989] ou RT-LOTOS, les automates temporisés, les dérivés formels (comme Modecharts [Jahanian-1988]) des Statecharts [Harel-1987], les langages impératifs de type ESTEREL [Berry-1992]….
• Les modèles duaux, qui essaient d’intégrer à la fois les caractéristiques des modèles opérationnels et déclaratifs en les faisant cohabiter. ESM/RTTL [Ostroff-1987], qui couple des machines étendues à la logique temporelle d’intervalles, est représentative de ce type d’approche.

Par rapport aux paradigmes de modélisation

Afin de simplifier les tâches de vérification et de validation du système, diverses hypothèses simplificatrices de modélisation, concernant essentiellement les CT, peuvent être émises. Suivant le respect de ces hypothèses de modélisation, trois paradigmes de synchronisation peuvent être distingués [Carcagno-1995] :
• Paradigme synchrone fort : Dans cette approche, les actions et les communications sont considérées comme immédiates et de dynamiques négligeables par rapport à la dynamique du procédé. Le temps manipulé est défini par rapport aux arrivées successives des événements. C’est une vision multiforme du temps, car il y a autant de temps que d’événements externes indépendants. Le système évolue par l’arrivée d’événements. La phase de transition (ou transitoire) entre deux états est considérée comme immédiate. Par ailleurs, on suppose une communication synchrone par diffusion large (broadcasting) : toutes les communications sont diffusées à tous les composants. Le système est donc un système réflexe (les réactions sont supposées instantanées).
• Paradigme synchrone faible : Cette approche, par rapport au synchrone fort, permet de mieux maîtriser les temps de communication et d’exécution. Ceux-ci ne sont plus supposés nuls, mais sont uniformisés et fixés arbitrairement à une même constante. Le comportement du système peut donc se synthétiser par une suite temporelle d’instants équidistants, le système réagissant aux changements survenus depuis le dernier instant. Pour fonctionner, un tel système doit être cadencé par une horloge globale (ou un ensemble d’horloges locales synchronisées). Le temps de réaction correspond alors à une unité de temps de cette horloge. Une communication par broadcasting est là aussi supposée. Le système n’est plus réflexe mais périodique.
• Paradigme asynchrone : Avec ce paradigme, la durée des actions et les temps de communication sont considérés comme bornés (mais peuvent varier dans des intervalles). Les délais de transitions du système ne sont pas supposés constants (une transition pouvant prendre un nombre variable de cycles de calcul). Lorsque des synchronisations sont nécessaires entre nœuds, elles sont faites de manière explicite par des communications. La communication par diffusion n’est plus supposée par défaut.
Ainsi, dans les approches synchrones, nous retrouvons les logiques temporelles, les langages de type SIGNAL, ESTEREL, LUSTRE, les dérivés de Statecharts…
Avec le paradigme asynchrone, nous retrouvons les algèbres de processus (CSP, SDL), les langages déclaratifs de type ELECTRE [Cassez-1995] ou les RdP.
Notons que, dans un contexte de système distribué, il peut y avoir une utilisation de modèles synchrones, pour la description du comportement des nœuds et, de modèles asynchrones pour la description des communications entre les nœuds (voir par exemple [Carcagno-1995]).

Approches UML basées sur des réseaux de Petri

Avant de présenter les approches UML basées sur les RdP, nous faisons un rappel les différentes techniques de couplage des RdP avec une modélisation OO ainsi que sur les classes de RdP permettant la manipulation explicite de CT. Nous supposons que le lecteur possède une connaissance du formalisme des RdP.

Les RdP et la modélisation OO

Rappels sur la modélisation par RdP

Modéliser un système complexe, à l’aide de RdP, consiste à structurer ce système en deux parties [Valette-2000] : une partie « contrôle » et une partie « données ». La partie « contrôle » décrit essentiellement les enchaînements possibles des activités. La partie « données » correspond à l’ensemble des structures de données internes au système et des calculs effectués sur ces données.
Le RdP décrit la structure de contrôle du système. La modélisation des données est souvent réalisée par des jetons ayant une structure de données. Elle nécessite alors l’utilisation de RdP dits de haut niveau (RdP Colorés [Jensen-1981], Prédicat/Transition [Genrich-1986] ou Objet [Sibertin-Blanc-1991] [Lakos-1990 ]).
L’interprétation du RdP revient à spécifier les liens entre la partie « contrôle » et la partie « données ». On peut la traduire en associant :
• Des conditions aux transitions (ainsi que sur la partie structure de données du jeton).
• Des actions aux transitions (entraînant par exemple la modification des données du jeton).
Rappelons que le RdP n’est pas un outil facilitant la structuration de système. Il n’apporte qu’un seul concept dans l’organisation dudit système : celui de permettre une délimitation claire entre la structure de contrôle (décrite par le graphe lui-même) et la structure de données (décrite en complément du graphe et constituant l’interprétation du réseau de Petri). Une approche hiérarchisée est certes possible [Valette-1979], mais elle doit résulter d’une volonté du concepteur et s’appuyer sur des règles et des méthodes extérieures au RdP.
Pour cette raison, la structuration du système est souvent apportée par un autre mécanisme que les RdP. C’est pourquoi, différentes méthodes ont été définies afin de coupler des RdP à des approches OO.

Le couplage RdP et OO

Différentes études comparatives des couplages entre RdP et l’approche OO ont été effectuées [Zapf-1999] [Lakos-1997] [Valk-2000]. Trois grandes démarches sont identifiées [Bastide-1995] :
• Intégration des concepts à objets dans les RdP.
• Intégration des RdP dans les concepts à objets.
• Intégration mutuelle des concepts OO et des RdP.
Dans la première catégorie, les RdP modélisent toute la structure de contrôle du système. Les jetons modélisent les objets, ces derniers étant généralement représentatifs des propriétés statiques du système. Nous pouvons citer dans cette catégorie : LOOPN [Lakos-1990 ], MacroNet [Keller-1994], MOBY [Fleischhack-1993], OBJSA [Battiston-1988], THORN [Schöf-1995], SimCom [Verkoulen-1998]… Cependant, ce type d’approches est rapidement confronté à la complexité de modélisation d’un système, les RdP modélisant à plat toute la structure de contrôle du système. Dans la seconde catégorie, les RdP sont utilisés afin de décrire le comportement des objets actifs (et parfois passifs) ainsi que les communications inter-objets. Les RdP sont « à l’intérieur » des objets, on parle alors d’approches « Objet à RdP »(Petri Net Object). Différentes classes de RdP (prédicat/transition, colorés, etc.) peuvent être utilisées suivant la classe de système modélisée. Un grand nombre de formalismes est proposé dans cette catégorie, citons HOOD Nets [Di Stefano-1991], HOOD/PNO [Paludetto-1991], OOBM [Hanisch-1997], OBM [Kappel-1991], OCPN [Maier-1997], PAM [Bachatène-1995], PN-TOX [Holvoet-1995]… La structuration est en général supportée par une méthode OO (HOOD, OMT, UML…).
Dans la dernière catégorie, une classe de RdP particulière est développée afin de directement prendre en compte les aspects OO (héritage, instanciation…). Cette classe de RdP, souvent appelée « RdP à Objet » (Object Petri Net)[Sibertin-Blanc-1985;Sibertin-Blanc-1991] connaît diverses déclinaisons. Nous retrouvons des formalismes comme CLOWN [Battiston-1995], CO-OPN/2 [Biberstein-1997], HOON [Löwe-1995], LOOPN++ [Lakos-1995b], OPN [Valk-1996]… Ces modèles peuvent être couplés à des méthodes OO ou définir leur propre formalisme.

Les classes de RdP adaptées au traitement de CT explicites

Un RdP modélise, par sa structure, des relations d’ordre entre les transitions et dès lors, des relations d’ordre entre tirs de transition. Cela permet donc une manipulation de CT qualitatives et un RdP ordinaire peut modéliser toutes les relations d’Allen [Allen-1983] [Sénac-1996]. Mais pour manipuler des CT explicites, il faut l’enrichir de considérations quantitatives.
Un RdP étant un graphe biparti, il est naturel de placer ces considérations, soit sur les places, soit sur les transitions, mais on peut aussi les placer sur les arcs des transitions ou sur les jetons. En outre, les contraintes temporelles peuvent être représentées par des durées (classe de RdP temporisé) ou par des intervalles (classe de RdP temporel). Enfin, ces CT peuvent être soit déterministes, soit stochastiques. Cette liberté de choix dans l’affectation des CT permet d’obtenir une large variété de RdP ayant des pouvoirs d’expression temporelle plus ou moins grands et des capacités d’analyse plus ou moins réduites.
Nous présentons brièvement les classes de RdP les plus usuelles que sont les classes de RdP temporisé, t-temporel et stochastique. Nous conseillons au lecteur, intéressé par une comparaison détaillée de ces différentes classes, la consultation de la thèse de Marc Boyer [Boyer-2001].

Réseaux de Pétri Temporisés (RdPTé)

Définitions

Deux classes de RdP Temporisé (RdPTé) (Timed Petri Net) se distinguent :
• Les p-RdPTé [Sifakis-1977] : Une durée est associée à chaque place. La sémantique de cette durée correspond au temps de séjour minimum d’un jeton (son temps d’indisponibilité) dans une place.
• Les t-RdPTé [Ramchandani-1974] : A chaque transition est associée une durée dont la sémantique correspond à la durée de tir de la transition. Le jeton ayant sensibilisé la transition n’est plus disponible pendant toute cette durée.
Ces deux classes de RdP sont, en fait, équivalentes [Sifakis-1979] et proposent la même idée : dissocier le marquage en deux parties : les jetons libres et les jetons indisponibles. Un jeton indisponible ne peut plus sensibiliser une transition et donc participer à un franchissement.

Critiques

La notion d’indisponibilité des jetons est l’une des lacunes des RdPTé car il devient extrêmement difficile de modéliser des mécanismes préemptifs de type « chiens de garde ». En effet, les jetons sont absorbés par les transitions (ou les places). Ils ne sont alors plus disponibles pour le tir d’autres transitions. En outre, rien dans la définition de ces modèles ne permet de forcer le tir d’une transition franchissable : le ou les jetons participant à sa sensibilisation peuvent rester indéfiniment dans leur place et la transition ne sera jamais tirée. Il est toutefois possible de définir un fonctionnement au plus tôt où la transition est tirée dès sa sensibilisation. Dans ce cas, il est possible d’établir un graphe de marquage de tir au plus tôt et de quantifier les durées des chemins. Cette technique d’analyse a été utilisée pour l’optimisation de système de production [Gaubert-1999], mais elle doit être couplée avec des heuristiques et des techniques de calculs extérieures. En effet, la politique de tir au plus tôt n’est pas suffisante, par exemple, pour déterminer un parcours minimum (en ordonnancement, il est connu qu’il faut parfois attendre pour gagner ensuite du temps).
Un dernier inconvénient des RdPTé réside dans leur incapacité à exprimer la notion d’indéterminisme temporel. En effet, dans de nombreux cas (connaissance incomplète du système, gigue temporelle, variabilité temporelle de la durée d’un traitement), la durée d’un traitement n’est pas exactement connue et peut être comprise dans un intervalle de temps min-max.

Réseau de Petri à transitions temporelles (t-RdPTl)

Comme pour un t-RdPTé, un RdP t-temporel peut comporter des informations temporelles sur ces transitions ti, mais ici exprimées par des intervalles temporels [ai,bi] (avec 0≤ ai≤ bi).
Pour être franchie, une transition ti doit être sensibilisée de manière continue pendant le délai minimum ai avant de pouvoir être franchie. Elle ne peut rester validée au-delà du délai maximum bi. Grâce à ce mécanisme, des incertitudes de tir d’une transition peuvent être exprimées. De plus, le jeton sensibilisant une transition reste disponible pour d’autres transitions.
Différentes sémantiques de fonctionnement d’un t-RdPTl sont possibles concernant :
• Le traitement de la multi-sensibilisation d’une transition et,
• La sémantique temporelle de tir des transitions.

Table des matières

Introduction générale
Partie I Vers une approche mixte UML pour le temps réel
I.1. TERMINOLOGIE
I.2. PROBLEMES ABORDES ET CHOIX DE L’AXE DE RECHERCHE
I.3. LES APPROCHES MIXTES ASYNCHRONES UML POUR LE TEMPS REEL
I.4. CONCLUSION
Partie II La structuration dans UML/PNO
II.1. LES CONFLITS DU PARADIGME OO INTEGRE
II.2. PROPOSITIONS POUR LIMITER LES CONFLITS DU PARADIGME OO INTEGRE
II.3. RESUME SUR LA STRUCTURATION DANS UML/PNO
Partie III Formalisation du comportement
III.1. LES DIAGRAMMES A RESEAUX DE PETRI
III.2. LE DIAGRAMME DE COMPORTEMENT EXTERNE D’UN CC
III.3. LE DIAGRAMME DE COMPORTEMENT INTERNE D’UN CC
III.4. RESUME SUR LA DYNAMIQUE DANS UML/PNO
Partie IV Dérivation et validation partielles des diagrammes UML dynamiques
IV.1. LA DERIVATION DES DIAGRAMMES UML
IV.2. LES REGLES DE DERIVATION DES DIAGRAMMES UML
IV.3. VALIDATION PARTIELLE DES DIAGRAMMES UML
IV.4. RESUME SUR LA DERIVATION ET LA VALIDATION PARTIELLES
Partie V Vérification des contraintes temporelles
V.1. VERIFICATION DES CT A L’AIDE DU GRAPHE DE CLASSE
V.2. VERIFICATION DES CT A L’AIDE DE LA LOGIQUE LINEAIRE
V.3. DEMARCHE DE VERIFICATION UML/PNO DES CONTRAINTES TEMPORELLES
V.4. UN PROTOTYPE D’AGL UML ET RDP
V.5. RESUME SUR LA VERIFICATION DES CONTRAINTES TEMPORELLES
Partie VI Conclusion générale
VI.1. CONTRIBUTIONS
VI.2. PROSPECTIVES
Publications associées à UML/PNO
Références bibliographique
Partie VII Annexe : règles de dérivation des diagrammes de séquence
VII.1. PROCESSUS DE PASSAGE
VII.2. LES COMMUNICATIONS ENTRANTES ET SORTANTES
VII.3. LES EFFETS OBSERVABLES DES INVOCATIONS
VII.4. LES CONTRAINTES TEMPORELLES
VII.5. LES ALTERNATIVES
VII.6. LES BOUCLES
VII.7. LES INFORMATIONS NON TRADUITES DES DIAGRAMMES DE SEQUENCE

Télécharger le rapport complet