88
MINISTERE DE L’ENSEIGNEMENT SUPERIEUR ET DE LA RECHERCHE SCIENTIFIQUE Faculté des Ingénieurs Département d’Informatique MEMOIRE d’Ingénieur d’Etat en Informatique Option Matériels & logiciels Restructuration d’Applications Java Temps-Réel Par KAMEL MOUATS

Restructuration d applications Java Temps réel

Embed Size (px)

DESCRIPTION

La restructuration de programmes consiste à apporter des modifications sur la structure interne de ces programmes, pour différents buts tels que la facilité de compréhension et de maintenance, l’optimisation, l’ordonnancement de tâches, la facilité de conversion d’un langage à un autre, ou la détermination de modules réutilisables. Dans ce travail, nous avons conçu et implémenté un système de restructuration de programmes Java temps réel, qui permet d’obtenir une sensible amélioration de l’ordonnançabilité de ce type d’applications. En effet, les programmes associés à des systèmes temps réel doivent être logiquement corrects et doivent s’exécuter sans fautes temporelles. Afin de satisfaire leurs échéances, les tâches de ces systèmes sont ordonnancées par des techniques adéquates. Dans le cas par exemple, où un ensemble de tâches serait non ordonnançable, le programmeur procède à des opérations manuelles de modification, de réglage et de restructuration de l’application, afin de la rendre ordonnançable. De telles opérations sont lentes, coûteuses, et non contrôlables. Les solutions existantes dans ce domaine, sont de nature à améliorer l’ordonnançabilité d’une tâche. Etant donné que Java est un langage de programmation purement orienté objet, nous avons utilisé les modèles de représentation de dépendances qui tiennent compte des différents aspects des systèmes orientées objets tels que la réutilisation et le polymorphisme.

Citation preview

Page 1: Restructuration d applications Java Temps réel

MINISTERE DE L’ENSEIGNEMENT SUPERIEUR ET DE LA RECHERCHE SCIENTIFIQUE

Faculté des Ingénieurs Département d’Informatique

MEMOIRE

d’Ingénieur d’Etat en Informatique Option Matériels & logiciels

Restructuration d’Applications Java Temps-Réel

Par

KAMEL MOUATS

Page 2: Restructuration d applications Java Temps réel

INTRODUCTION

La décomposition d’ un système temps réel résulte en une col lection de processus, chacun est responsable d’ une portion spécif ique de la tâche globale. La correspondance entre les modules du logiciel et les entités du monde réel n’ est souvent pas apparente à partir de la structure du code. Ce qui rend difficile la compréhension et la maintenance du code. De plus, traiter les systèmes temps réel comme étant des groupes de processus contraints par le temps, oriente la conception vers une vue «événement - action»: les événements sont générés par les enti tés du monde réel ou par les processus logiciel; les actions doivent être effectuées par les processus logiciels en réponse temporelle à ces événements.

Malheureusement, dans plusieurs systèmes temps réel, les événements discrets sont des approximations d’ activités réellement continues. Dans ces systèmes, les contraintes de temps sont plus naturellement vues comme étant des contraintes de cohérences temporel les d’ information. Par exemple, dans plusieurs systèmes robotiques, l ’ interface logicielle du manipulateur physique entraîne le manipulateur physique à lire périodiquement son état et à émettre des commandes d’ actionneurs. Le logiciel dans un tel système, contient une image du manipulateur physique. Cette image doit être tenue cohérente avec l ’ état courant du manipulateur physique, sinon le planificateur de mouvements pourrait générer des plans de mouvements inappropriés. A l ’ implémentation, cette contrainte de cohérence est transformée en contrainte de temps de n unités de temps de périodes de scrutation.

De plus, dans la plupart des systèmes temps réel, une approximation de la concurrence doit être faite par l ’ exécution de plusieurs processus sur des ressources partagées. L’ ordonnancement de l’ exécution de ces processus est souvent basées sur les temps d’ exécution au pire des cas, obtenus au moyen de différentes techniques d’ estimation. Ceci pose le problème de réservation excessive des ressources, lorsque le temps moyen d’ uti l isation s’ éloigne des temps au pire des cas.

Le comportement temporel est une caractéristique de base pour les systèmes

informatiques où les programmes doivent être logiquement correct, en s’exécutant sans erreurs de temps. Les erreurs temporelles sont particulièrement produites quand on a un ensemble de tâches provoquant un surcharge et un défaut dans l’ordre d’exécution, ce qui ramène le système à une phase d’échec. Les développeurs remédient ces anomalies par des opérations intensivement manuelles, telles que l’ instrumentation, prise de mesure et éventuellement une reconception complète du système. De telles opérations sont coûteuses, lentes et incontrôlables.

Dans le but d’aider à prévenir une ordonnançabilité complète, une approche est adoptée, et qui généralise les solutions précédentes à deux niveaux. Dans un premier, elle consiste, pour la perspective d’ordonnancement, à restructurer une large classe de programmes temps réel qui peut être complexe et contenant une collection de procédures. Dans un deuxième niveau, la méthode de restructuration utilise le concept des tranches de programmes (interprocéduraux) et un modèle de dépendance amélioré, permettant par la suite d’améliorer l’ordonnançabilité d’un ensemble de tâches, soit par rendre leurs échéances flexibles, ou bien par décomposition d’une ou de plusieurs tâches en sous tâches, de telle façon qu’on puisse utiliser les méthodes d’ordonnancement généralisées, de priorités fixes, qui permettent l’augmentation de l’ordonnançabilité d’un ensemble de tâches, à un niveau supérieur de celui fourni par l’algorithme Rate-Monotonic.

Page 3: Restructuration d applications Java Temps réel

111

1 1

Le Monde Des Systèmes Temps Réel 1

PARTIE 1:Système Temps Réel «Concepts & Conception»: Objectif:

Ce chapitre a pour but d’ introduire les systèmes temps réel. Il i l lustre certaines des diff icultés que l ’ on rencontre lorsque l ’ on implémente ce genre de système. Un système temps réel est correct en fonction de ses résultats et du moment auwquel i l les produit. Les contraintes de temps et de ressources sont déterminantes pour le fonctionnement de ces systèmes.. I - Introduction:

Au fur et à mesure que le prix sur le matériel diminue, on intègre des ordinateurs dans de plus en plus de systèmes. Ces logiciels interagissent directement avec des périphériques matériels, et leurs logiciels doivent pouvoir réagir suffisamment vite aux événements dont le système assure le suivi et le contrôle. Du fait de ce besoin, pour le logiciel, de répondre à des événements «temps réel», le système logiciel de contrôle a été qualif ié de système «temps réel». Un système temps réel consiste en un ensemble d’entités contrôlées et un sous-système de contrôle. Ce dernier est formé d’un ensemble de systèmes d’ordinateurs, tandis que les entités contrôlées peuvent être un large éventail de systèmes à comportement mécanique ou tout dispositif, du simple mélangeur au robot [Stankovic91]. Typiquement, le sous-système de contrôle exécute des programmes de contrôle pour recevoir des données de l’environnement et/ou pour émettre des commandes aux entités contrôlées [Chung95].

Un système temps réel (STR) est un système dédié à des applications spécifiques, en particulier, les systèmes de contrôle. Des capteurs recueillent de l’ information qu’ ils fournissent au calculateur(ordinateur). Ce dernier s’occupe de réaliser le contrôle désiré et donne les résultats pour d’éventuelles interventions.

Les systèmes embarqués constituent un sous-ensemble de systèmes temps réel, caractérisés par leur contrôle de systèmes mécaniques tels que les systèmes de contrôle de bateaux, de véhicules, de machines à laver, etc.

Comme on a besoin de répondre à des événements qui arrivent à n’ importe quel moment, on doit organiser l ’ architecture d’ un système temps réel de manière à pouvoir transférer le contrôle au composant approprié dès la réception d’ un événement. C’est pourquoi, on conçoit le système comme un ensemble de processus parallèles, et qui coopèrent entre eux. Une partie du système temps réel (quelquefois appelée exécutif temps réel) est dédiée à la gestion de ces processus.

I I -Définition d’un système temps réel:

Avant d’aller plus loin, il est utile d’essayer de définir la phrase: «Système Temps Réel» (STR) avec plus de précision. Il y a une multitude d’ interprétations de la nature exacte d’un STR; cependant, elles ont tous en commun la notion du «temps de réponse (le temps nécessaire pour qu’un système puisse générer des sorties à partir d’entrées associées). Le «Oxford Dictionary of Computing» donne la définition suivante pour un STR: «C’est n’ importe quel système dans lequel le temps, au bout duquel la sortie est produite, est significatif. C’est généralement dû au fait que l’entrée correspond à certains flux dans le monde physique, et la sortie doit appartenir aux même flux. La différence entre le temps de l’entrée et celui de la sortie doit être suffisamment petite pour avoir un temps de réponse acceptable.» Ici, le mot «temps de réponse» est pris dans le contexte du système total. Par exemple, dans un système de contrôle de missiles téléguidées, la sortie est exigée dans quelques

Page 4: Restructuration d applications Java Temps réel

222

2 2

Le Monde Des Systèmes Temps Réel 1

millisecondes, cependant, dans les systèmes de contrôle d’assemblage de voitures, la réponse peut être exigée seulement dans une seconde. Young[1982] définit un STR comme suit: «C’est tout système ou activité de traitement d’ information qui doit répondre à une entrée stimulée, extérieurement générée, dans une période finie et bien spécifique.» Dans le sens le plus général, ces deux définitions couvrent une catégorie plus large d’activités d’ordinateur. Par exemple, un système d’exploitation comme UNIX peut être considéré comme un STR dans le cas où un utilisateur introduit une commande et il va attendre pour (recevoir) une réponse dans quelques secondes. Heureusement, il n’est pas généralement désastreux si la réponse n’est pas rapide. Ces types de systèmes peuvent être distingués de ceux où la panne dans la réponse peut être considérée aussi mauvaise qu’une réponse fausse. Bien entendu, c’est cet aspect qui distingue un STR de ceux où le temps de réponse est important mais n’est pas crucial. Par conséquent, la correction d’un STR ne dépend pas seulement de la logique des résultats d’un calcul, mais de plus, du temps dans lequel les résultats sont produits. Les praticiens dans le domaine de la conception des systèmes d’ordinateur à temps réel distinguent généralement entre les STR hards(stricts) et les STR soft(relatifs). Les STR hards sont ceux où il est absolument impératif que les réponses se produisent dans un échéance spécifié. Les STR softs sont ceux où les temps de réponse sont importants mais le système restera fonctionner correctement si les échéances sont occasionnellement perdus. Les systèmes softs peuvent être distingués par eux même des systèmes interactifs dans lesquels il n’y a pas des échéances explicites. Dans un STR soft ou hard, l’ordinateur a généralement une interface directe avec quelques équipements physiques et il est orienté à contrôler ou à couvrir l’opération de ces équipements. Une caractéristique clé de toutes ces applications est le rôle de l’ordinateur comme un composant de traitement d’ information dans un système d’ ingénierie large. Il est pour cette raison que de telles applications sont reconnues comme des Systèmes Temps Réel. I I I -Exemples de systèmes temps réel: I I I -1-Contôle de processus:

La première utilisation d’un ordinateur comme un composant dans un système d’ ingénierie s’est faite à la fin de 1960 dans le contrôle des processus industriels. Considérons l’exemple montré dans la figure I-1, où l’ordinateur effectue une seule activité: c’est d’assurer le passage d’un flux de liquide donné dans un pipe par le biais d’une vanne. Si on détecte une augmentation dans le flux, l’ordinateur doit répondre en alternant l’angle de la vanne; cette réponse doit se produire dans un temps fini si le dispositif de réception en fin du pipe ne se surchargera pas.

I I I -2-La production:

L’utilisation des ordinateurs dans la production est devenue essentielle de telle manière qu’on puisse garder les coûts de la production minimaux avec amélioration de la productivité. L’ordinateur coordonne entre une variété d’engins tels que des manipulateurs, machines à outils, …etc. I I I -3-Communication, commande et contrôle:

On peut citer comme exemple, la réservation de places sur avion, les centres médicaux pour le suivi automatique des malades et la gestion des comptes bancaires.

Page 5: Restructuration d applications Java Temps réel

333

3 3

Le Monde Des Systèmes Temps Réel 1

Tous ces systèmes se composent d’un ensemble d’agents (opérateurs) complexes, des

dispositifs de collection d’ informations et de procédures administratives permettant de supporter les décisions et fournissent la manière par laquelle ils peuvent être implémentés.

Il est évident que les dispositifs de saisie de l’ information et les instruments demandés pour implémenter les décisions sont distribués sur une zone géographique large.

I I I -4-Systèmes temps réel généralisés:

Dans chacun des exemples précédents, l’ordinateur a une interface directe avec les équipements physique dans le monde réel. Afin de contrôler ces dispositifs du monde réel, l’ordinateur aura besoin de consulter des dispositifs de prise de mesures à des intervalles de temps réguliers, pour cette raison, une horloge de temps réel est exigée.

Généralement, il y a aussi une console d’opérateur permettant toute intervention manuelle. Un agent doit rester informé de l’état du système par des unités de visualisation de différents types.

Les changements d’état du système sont enregistrés dans une base d’ information qui peut être interrogée par les opérateurs (agents), ultérieurement, soit pour restaurer le contexte du système, en cas d’un déséquilibre de son état, ou bien afin de fournir des informations pour des besoins administratifs.

La structure d’un STR embarqué typique est représentée dans la figure I-2. Le logiciel qui contrôle les opérations du système peut être conçu de manière modulaire reflétant la nature physique de l’environnement. Généralement, on fera appel à un module contenant les algorithmes nécessaires pour le contrôle physique des dispositifs, un deuxième responsable de l’enregistrement des changements d’état, un troisième pour l’extraction et l’affichage de ces changements et un dernier pour l’ interaction avec l’opérateur.

IV- Caractér istiques des STR:

Un STR possède plusieurs caractéristiques spéciales (soit héritées ou imposées). Cependant, tous les STR n’ont pas ces mêmes caractéristiques, mais tout langage à objectif

Lecture du flux d’entrée

Traitement

Angle de la

vanne en sortie

vanne

Fluxmètre

Fig I -1: Système de contrôle d’un fluide

Temps

Page 6: Restructuration d applications Java Temps réel

444

4 4

Le Monde Des Systèmes Temps Réel 1

général, qui sera utilisé pour la programmation effective des STR, doit supporter, et facilement ces caractéristiques. IV-1-Taille et complexité:

Il est souvent constaté que la plupart des problèmes associés au développement des logiciels sont ceux relatifs à la taille et la complexité. Ecrire de petits programmes présente un problème non significatif, comme il peut être conçu, codé, maintenu et compris par une seule personne. Si cette personne quitte la compagnie ou cette institution qui utilise ce logiciel, une autre personne peut apprendre et comprendre ce programme en une durée relativement petite. Malheureusement, tous les logiciels ne présentent cette caractéristique qu’on veut bien l’atteindre et l’avoir.

Lehman et Belady[1985], dans une tentative de caractérisation des systèmes répandus,

rejettent la notion simple et intuitive, que la taille est simplement proportionnelle au nombre d’ instructions, lignes de code ou modules.

Par définition, les STR doivent répondre aux événements du monde réel. La variété associée à ces événements doit être traitée attentivement.

Le coût de la reconception ou la réécriture du logiciel répondant aux exigences du changement continu du monde réel est extrêmement important. De ce fait, les STR doivent être extensibles pour faciliter leur maintenance et améliorer leur performance.

Horloge Temps réel

Base de données

Console d’un opérateur

Real Time computer

Algorithmes pour le contrôle digital

Insertion de données (enrichissement)

Extraction de données et affichage

Interface opérateur

interface Système

d’ ingénierie

Dispositifs d’affichage

Fig I -2:STR typique

Système de contrôle distant

Page 7: Restructuration d applications Java Temps réel

555

5 5

Le Monde Des Systèmes Temps Réel 1

IV-2- Manipulation des nombres réels: Un STR implique le contrôle d’un processus industriel manipulant des données. Ces

dernières servent de paramètres de prise de décision et d’ intervention en cas de situations anormales.

IV-3- Fiabilité et sécurité:

Les STR interviennent dans des situations critiques demandant le contrôle des fonctionnalités. Une panne d’un système, impliquée dans le cas du transfert automatique d’argent entre banques mènera à une perte de millions de dollars sans pouvoir les récupérer ; un composant erroné dans la génération de l’électricité peut exposer la vie, dans une unité sanitaire, à des dangers irrémédiables…etc. Ces exemples dramatiques illustrent que l’ensemble du matériels et logiciels informatiques doivent être fiables et protectifs. De ce fait, on a intérêt à concevoir et implémenter des systèmes dont leur fonctionnement est suivi par un autre système de contrôle. De plus, dans le cas où on exige une interaction avec un agent, on doit être prudent dans la conception de cette interface afin de minimiser les effets de toute erreurs humaines qui peut survenir. IV-4-Contrôle de la concurrence des composants séparés du système:

Un STR tente de composer des ordinateurs et des éléments externes coexistants, avec lesquels, les programmes de l’ordinateur doivent interagir simultanément. Dans un cas typique, le programme doit interagir avec un système d’ ingénierie (qui se compose d’éléments de fonctionnalités parallèles, telles que des robots, capteurs, actionneurs,…etc.) et les unités d’affichage de l’ordinateur, la console de l’opérateur et l’horloge du temps réel. Heureusement, la vitesse des ordinateurs nous donne l’ impression qu’ il s’agit d’un traitement simultané. Cependant, dans d’autres situations, ce n’est pas le cas, par exemple, dans le cas où les données doivent être rassemblées, traitées dans des sites géographiquement distribués, où le temps de réponse d’un composant simple ne peut pas être déduit par un seul ordinateur. Dans ces cas, il est nécessaire de considérer des STR distribués et multiprocesseurs. Un problème majeur associé à la production de logiciels qui traitent la concurrence, c’est comment exprimer la concurrence dans la structure des programmes. Une des approche consiste à charger le programmeur pour construire son système qui implique l’exécution cyclique d’une séquence de programmes manipulant différentes tâches concurrentes. Notez que cette approche de développement n’est en aucun cas applicables vu les raisons suivantes : � La complication de la tâche de l’utilisateur le met dans des considérations de structures

qui sont inadéquates pour le contrôle des tâches. � Les programmes résultants seront illisibles et non élégants. � Les programmes corrects deviennent difficiles. � La décomposition du problème sera compliquée. � Une réalisation difficile pour faire exécuter des programmes parallèles sur plus d’un seul

processeur. � La correction d’un code ayant des erreurs est plus problématique. IV-5-Contrôle du temps réel:

Le temps de réponse est crucial dans tout STR. Malheureusement, il est très difficile de concevoir et implémenter un système qui va garantir que la sortie appropriée se générera dans les délais prescrits et sous toute condition possible. La réalisation de tel système, en permettant une utilisation complète de toutes les ressources à tout moment, est une tâche relativement impossible. Pour cette raison, les STR sont généralement construits en utilisant des processeurs ayant des capacités partagées, afin de

Page 8: Restructuration d applications Java Temps réel

666

6 6

Le Monde Des Systèmes Temps Réel 1

s’assurer que le comportement, au pire des cas, ne produise aucun retard défavorable durant les périodes critiques du fonctionnement du système. En fournissant une puissance de traitement adéquate, en exigeant le support d’exécution, on permettra au programmeur de : � Spécifier les temps dans lesquels les actions doivent être accomplies. � Spécifier les temps dans lesquels les actions doivent se terminer. � Répondre à des situations où les exigences temporelles se changent de manière

dynamique. IV-6-Interaction avec les interfaces du matériel:

La nature des STR exige que les composants de l’ordinateur doivent interagir avec le monde extérieur. Ils ont besoin de capteurs et actionneurs pour une large gamme de dispositifs du monde réel. Ces dispositifs interagissent avec l’ordinateur via des registres d’entrées/sorties. Les dispositifs peuvent générer des interruptions afin de signaler au processeur que certaines opérations sont accomplies ou qu’ il y avait des erreurs qui se sont produites. De nos jours, vu la variété des dispositifs et la nature du temps critique de leurs interactions associées, leur contrôle doit être direct et non pas à travers les fonctions du système d’exploitation. IV-7-Implémentation efficiente:

Vu la nécessité du traitement du temps critique dans les STR, l’ implémentation efficiente (de haute qualité, efficace …) de ces systèmes devient de plus en plus nécessaire et importante. Il est intéressant que l’un des bénéfices majeurs de l’utilisation d’un langage de haut niveau est qu’ il permet au programmeur de réaliser une implémentation abstraite loin de tout détail, en se concentrant sur la résolution du problème. Le programmeur doit toujours être concerné par le coût de l’utilisation de caractéristiques particulières d’un langage. Par exemple, si la réponse à quelques entrées doit apparaître au bout d’une micro-seconde, ce n’est plus la peine d’aller utiliser un langage dont l’exécution prend une milli-seconde.

V-Spécification des besoins:

Tout projet informatique doit impérativement commencer par une description informelle des objectifs à atteindre. Cela devra être suivi par une analyse des besoins. C’est à ce stade que la fonctionnalité du système est définie. Dans le terme de «facteurs spécifiques temps réels», le comportement temporel du système doit être explicite, tout comme les besoins en fiabilité et comportementaux du logiciel en cas où une panne d’un composant survienne. De plus, cette phase définit quels sont les tests d’acceptante à appliquer au logiciel. Il est de plus nécessaire de construire un modèle de l’environnement de l’application. C’est une caractéristique des STR qu’ ils ont des interactions importantes avec leur environnement. Après la phase d’analyse vient celle de la concrétisation de la spécification des besoins. C’est à partir de cette étape qu’apparaît la conception. C’est une phase critique dans le cycle de vie d’un logiciel passant à un niveau plus élevé dans la mise au point du STR. VI-Motivations de conception:

Dans cette section, nous synthétisons les différentes étapes de conception de systèmes temps réel. Ces étapes se basent sur des paramètres de qualité de service [ IEEE97] et elles doivent prendre en compte les besoins d’évolution et donc de la maintenance.

Dans un système intégré à grande échelle, l ’ une des étapes du processus de conception consiste à concevoir les systèmes, et à partager les fonctions entre matériel et

Page 9: Restructuration d applications Java Temps réel

777

7 7

Le Monde Des Systèmes Temps Réel 1

logiciel. On peut considérer que le processus de conception des systèmes intégrés suit une série d’ étapes: (1) Identifier les événements que le système doit traiter et les réactions associées. (2) Identifier les contraintes de temps à appliquer à chaque événement, ainsi qu’ à la

réponse qui lui est associée. (3) Regrouper le traitement des événements et des réactions dans différents processus

paral lèles. Un bon modèle d’ architecture consiste à associer un processus à chaque classe d’ événement et à chaque classe de réaction, comme dans la figure I-2. Pour chaque événement et chaque réaction, concevoir les algorithmes qui effectueront le traitement nécessaire. On doit développer la conception des algorithmes à ce stade afin d’ avoir une idée du temps de traitement nécessaire.

(4) Concevoir un système d’ordonnancement qui permettra de démarrer chaque processus au moment opportun afin qu’ i l puisse effectuer son traitement dans des contraintes de temps données.

(5) Intégrer le système avec un exécutif temps réel. Naturel lement, c’ est un processus itérati f [Wil l iam96, gestion des itérations

Computer97]. Une fois qu’ i l a établi l ’ architecture (découpage en processus) et choisi la stratégie d’ordonnancement, le concepteur doit effectuer des estimations et des simulations complètes du système pour vérifier qu’ i l respectera ses contraintes de temps.

Dans beaucoup de cas, ces simulations vont révéler des défauts de comportement

du système. L’ architecture, ou l ’ ordonnancement, ou l ’ exécutif, ou les trois à la fois devront être reconçus afin de pouvoir «tenir» les contraintes de temps. Il est diff icile d’ estimer le temps d’ exécution d’un système temps réel. Du fait de la nature imprévisible des événements apériodiques, les concepteurs doivent faire des hypothèses sur la probabilité pour qu’ i ls apparaissent (et donc demandent un service) à un instant donné. Ces hypothèses peuvent s’ avérer incorrectes et les performances du système délivré ne seront pas suffisantes. Dasarathy [DAS85] traite de la val idation des temps d’ exécution.

Du fait que les processus d’un système temps réel doivent coopérer, le concepteur doit coordonner les communications entre processus. Les mécanismes de coordination des

Réponse

Contrôleur du Capteur

Contrôle de l’Actionneur

Traitement des Données

Capteur

Actionneur

Fig.I .3 Architecture d’ un système de contrôle

Page 10: Restructuration d applications Java Temps réel

888

8 8

Le Monde Des Systèmes Temps Réel 1

processus assurent l’exclusion mutuelle lors de l’accès à des ressources partagées. Lorsqu’un processus est en train de modifier une ressource partagée, les autres processus ne peuvent pas en faire de même. Parmi les mécanismes d’exclusion mutuelle on trouve les sémaphores, les moniteurs et les régions critiques.

Le langage choisi pour l’ implémentation de systèmes temps réel peut avoir lui aussi une influence sur la conception. Ada [Taft92] a été conçu à l’origine, pour implémenter des systèmes intégrés, et il dispose de caractéristiques comme la gestion des tâches, les exceptions et les clauses de représentation. La notion de rendez-vous représente un bon mécanisme pour la synchronisation des tâches. Malheureusement, ce mécanisme n’est pas adapté à l’ implémentation de systèmes temps réel durs.

Les systèmes temps réel durs sont souvent écrits en assembleur pour pouvoir tenir les contraintes de temps. Parmi les autres langages, on trouve des langages de niveau système comme C. Ils nécessitent un noyau d’exécution supplémentaire pour gérer le parallélisme.

Afin de pouvoir gérer le développement des STR complexes, deux approches complémentaires sont souvent utilisées: décomposition et abstraction. Toutes les deux forment des concepts de base des méthodes de génie logiciel. La décomposition, comme son nom l’ indique, implique le partitionnement systématique d’un système complexe en parties plus fines jusqu’à ce qu’on puisse isoler ses composants, afin de pouvoir les gérer de manière décentralisée. A chaque niveau de décomposition, on fait correspondre un autre niveau de description et une méthode de documentation de cette description. L’abstraction permet de considérer les détails et les particularités concernant l’ implémentation. Cela permet de simplifier la vision en vers le système et les objectifs à atteindre en gardant ses propriétés et caractéristiques. VI-1-Encapsulation:

La conception hiérarchique d’un logiciel permet la spécification et le développement des sous-composants d’un programme. Le besoin à l’abstraction implique que ces sous-composants doivent être bien définis en terme de rôle, clairs et avoir des interconnexions et interfaces non-ambigües. Si la spécification entière du système logiciel peut être vérifiée seulement en terme de spécification des sous-composants immédiats, alors la décomposition est dite compositionnelle. C’est une propriété importante quand on veut analyser formellement les programmes. Les programmes séquentiels sont particulièrement amenés à des méthodes compositionnelles et un nombre de techniques sont utilisées pour encapsuler et représenter les sous-composants. VI -2-Cohésion et couplage:

Les deux formes d’encapsulation discutées dans la section précédante nous amène à l’utilisation de modules avec des interfaces bien définies (et abstraites). Mais comment un grand système peut être décomposé en modules? La réponse est liée aux méthodes de décomposition des logiciels. Cependant, avant de discuter ces méthodes, il est approprié de considérer des principes plus généraux nous permettant une bonne encapsulation. Cohésion et couplage sont deux parmi les métriques décrivant les relations entre les modules. La cohésion est liée à la bonne concordance entre les modules. Allworth & Zobel[1987] donnent six mesures de cohésion: 1. Coïncidence: les éléments du module ne sont pas liés autre que dans un contexte très

superficiel. 2. Logique: les éléments du module appartiennent à la même famille, en terme de vision

globale du système, mais non pas en ce qui concerne l’application (logiciel) en cours.

Page 11: Restructuration d applications Java Temps réel

999

9 9

Le Monde Des Systèmes Temps Réel 1

3. Temporel: les éléments du module sont exécutés à des temps similaires. 4. Procédural: les éléments du module sont utilisés ensembles dans la même section du

programme. 5. Communication: les éléments du module travaillent sur la même structure de données. 6. Fonctionnel: les éléments du module travaillent en collaboration afin de contribuer à la

performance d’une seule fonction du système. Le couplage, par comparaison, est une mesure d’ interdépendance des modules du programmes. Deux modules ont un couplage fort s’ ils échangent entre eux des informations de contrôle. Par contre, ils perdent le couplage si les modules ne communiquent que des données. Une autre façon de voir le couplage est de considérer la facilité de changer un module (d’un système complet ) et le remplacer par un autre. Dans toutes les méthodes de conception, la meilleure, et celle ayant une bonne décomposition, vérifie une forte cohésion et un couplage minimum. Ce principe est également vrai dans les domaines de la programmation séquentielle et concurrente. VI-3-Approches formelles:

Elle consiste à modéliser le comportement des systèmes concurrents par l’utilisation des réseaux Petri [Brauer 1980]. Vue la variété des représentations obtenues, on introduit, dans le processus de modélisation, le concept des réseaux de transition prédicatives. La notion CSP (Communicating Sequential Processes) est développée, permettant la spécification et l’analyse des systèmes concurrents. Une logique temporelle (extension de la logique des prédicats et propositionnelle) a été introduite avec de nouveaux opérateurs afin de pouvoir exprimer les propriétés temporelles. VII -Méthodes de conception:

L’ industrie du temps réel utilise des méthodes structurées et les approches du génie logiciel pour la mise en œuvre des STR, vu que ces techniques sont applicables à tous les systèmes de traitement d’ information. Ces méthodes ne fournissent pas un support spécifique au domaine du temps réel, et ils manquent en richesse voulue quand on épuise toutes les potentialités des langages d’ implémentation utilisés. Typiquement, une méthode de conception structurée utilise un diagramme, dans lequel des arcs orientés schématisent le flux de données à travers le système, et les nœuds désignés représentent les sites dans lesquels les données sont transformées et donc traitées. Dans la littérature, on trouve les méthodes JSD (Jackson’s System Development), Mascot3 et PAMELA. Dans la méthode JSD, on utilise une notation pour la spécification et l’ implémentation (conception détaillée). Bien entendu, l’ implémentation n’est pas seulement une description détaillée de la spécification, mais de plus, elle est le résultat de l’application de transformations à cette dernière afin d’améliorer l’efficience. La méthode est basée sur un graphe comportant des processus et un réseau de connexions. Les processus sont de trois catégories: 1. Processus d’entrée: détectant les actions dans l’environnement en les faisant passer au

système. 2. Processus de sorti : passant les réponses du système à l’environnement. 3. Processus internes. Les processus peuvent être liés de deux manières différentes: 1. Par des connexions asynchrones de blocs de données qui sont sauvegardées. 2. Par des connexions de vecteurs d’état (ou inspection).

Page 12: Restructuration d applications Java Temps réel

101010

10 10

Le Monde Des Systèmes Temps Réel 1

Une connexion du vecteur d’état permet à un processus de connaître l’état interne d’un autre processus sans avoir besoin de transfert d’ information. Notez que la structure de graphe adoptée vise à représenter l’architecture du système. Malheureusement, JSD n’a pas une technique standard pour incorporer les contraintes de temps. De ce fait, on doit rajouter des dénotations aux diagrammes. Evidemment, JSD fournit une expression de la conception et non pas une conception. La conception incorpore inévitablement l’expérience et la créativité du concepteur. Il est souvent dit que les méthodes structurées et formelles sont orientées enrichissement de la créativité! Ce n’est pas vrai. Ces techniques offrent une notation bien claire et comprise de l’expression de la conception, et un moyen pour la vérification du bon placement de l’ idée adoptée, de ce fait, la conception a besoin de la spécification, et le logiciel implémente cette conception. Le point le plus important dans une conception JSD est le flux de données. Une bonne conception est celle qui intègre ce flux naturel. L’avantage de ce flux de données est qu’ il permet l’expression des contraintes de temps comme étant des attributs de données circulant dans le système. Une interruption génère un signal de contrôle ; le signal de contrôle est une transformation de l’ interruption. Ces transformations sont prises dans des processus en consommant du temps. Un choix approprié des processus va générer des échéances très visibles qui peuvent être ordonnancées. Une fois la conception est obtenue, son implémentation doit être effectuée de manière systématique. Avec un modèle de concurrence basé message, dans le langage de l’ implémentation, ce sera une tâche relativement facile, tout comme les processus de conception et les flux de données bufferisés qui peuvent être codés sous la forme de processus de programme. Malheureusement, cela peut produire une prolifération des processus et une implémentation anarchique. Afin de remédier à ces problèmes, on peut procéder de deux manières : 1. Transformation de la conception de telle sorte qu’on aura besoin d’un minimum que

possible de processus. 2. Obtention d’un programme de processus excessif et le transformer afin de réduire le

nombre d’objets concurrents. La méthode JSD est une transformation qui consiste à remplacer le processus de conception par une procédure avec un seul processus d’ordonnancement, contrôlant l’exécution d’une collection de ces procédures. De plus, les contraintes de temps provoque un problème majeur, qui est la difficulté de préserver les durées. En dépit de tout cela, la méthode JSD est appliquée avec succès dans les STR les plus complexes. La méthode Mascot a été développée pour la conception, construction et exécution des applications temps réel. Les descriptions de Mascot doivent contenir: � Les sous-systèmes. � IDAs (general Intercommunication Data Areas) . � Les processus. � Des canaux (un IDA se comportant comme un buffer). � Des poules (un IDA véhiculant et repositionnant l’ information). � Des serveurs (un élément de conception communicant avec les dispositifs du matériel

externe).

Page 13: Restructuration d applications Java Temps réel

111111

11 11

Le Monde Des Systèmes Temps Réel 1

VI I I -Implémentation: Le langage de programmation est une interface importante et primordiale entre la

spécification des besoins et l’exécution du code machine. La conception d’un langage reste un domaine de recherche actif. Malgré le passage naturel de la conception des systèmes vers l’ implémentation, les possibilités expressives des langages récents ne sont pas liées aux méthodologies de conception adoptées. Cette adoption poursuit logiquement l’étape de compréhension prévisible de l’étape d’ implémentation. Il est possible d’ identifier trois classes de langages de programmation qui sont utilisées dans le développement des systèmes temps réels. Ces langages sont: le langage d’assemblage, les langages d’ implémentation séquentielle des systèmes et les langages concurrents de haut niveau. IX-Cr itères da base d’un langage de conception:

Un langage de programmation des STR peut être conçu seulement pour répondre aux besoins du système. Cependant, il est rarement limité à cette fin. La plupart des langages temps réel sont aussi utilisés comme des langages d’ implémentation des systèmes à objectifs généraux, pour des applications spéciales telles que les compilateurs et les systèmes d’exploitation. Young[1982] liste les six critères de base d’un langage de conception temps réel: 1. La sécurité: la sécurité, dans la conception d’un langage, mesure la possibilité de détecter

des erreurs de programmation, d’une manière automatique, par le compilateur ou par le support d’exécution. Evidemment, il y a une limite pour les types et nombres d’erreurs que le système du langage peut détecter. L a sécurité implique la possibilité de: � Détecter facilement des erreurs et très tôt durant le développement du programme, et

par conséquent, une réduction dans le coût de la correction et la maintenance. � Avoir une compilation facile ne provoquant aucune extension au temps, donc le

programme peut être exécuté autant de fois qu’on le compile. L’ inconvénient de la sécurité est la complication dans sa mise au point, dans le cas d’un langage complexe, ce qui implique un surcoût dans le temps de la compilation et l’exécution.

2. La lisibilité: la lisibilité d’un langage dépend d’une multitude de facteurs concernant le choix des mots clés appropriés, la possibilité de définir des types et la facilité de modulariser un programme. De ce fait, on offre un langage avec une clarté suffisante, permettant d’assimiler les principaux concepts d’opérations d’un programme particulier par une simple lecture du texte du programme. Une meilleure lisibilité implique: � La réduction des coûts de la documentation. � Une meilleure sécurité. � Une bonne et parfaite maintenabilité.

3. La flexibilité: un langage doit être suffisamment flexible, permettant au programmeur d’exprimer toutes les opérations demandées d’une manière cohérente et graphique.

4. La simplicité: la simplicité possède les avantages suivants: � Minimisation de l’effort exigé pour produire les compilateurs. � Réduction du coût associé à l’apprentissage du programmeur. � Diminution de la possibilité de commettre des erreurs de programmation.

5. La portabilité: un programme doit être indépendant du matériel de l’exécution. pour un STR, cela est difficile à réaliser, car c’est comme si on va remplacer une partie du programme par une autre, ce qui implique des manipulations de ressources matérielles.

Page 14: Restructuration d applications Java Temps réel

121212

12 12

Le Monde Des Systèmes Temps Réel 1

Cependant, un programme doit être capable d’ isoler les parties d’un programme dépendantes de la machine de celles qui sont indépendantes.

6. L’efficience: dans un STR, les temps de réponse doivent être garantis. De ce fait, le langage doit être efficient. On doit, par conséquent, éliminer tout mécanisme provoquant une extension dans le temps.

X-Langages de programmation des systèmes temps réel:

L’ implémentation d’une application temps réel est étroitement liée au choix du langage de programmation, les facilités et les avantages dont il dispose.

On a pu identifier trois classes de langage de programmation utilisés dans le développement des STR qu’on va les présenter. X-1-Les langages d’assemblage:

Initialement, la plupart des STR ont été programmés dans le langage d’assemblage, à cause du manque du support des langages de haut niveau sur les ordinateurs, et le langage d’assemblage qui semblait être le seul moyen réalisant des implémentations efficaces, permettant l’accès et la manipulation des ressources matérielles. Le problème majeur, avec l’utilisation des langages d’assemblage, est qu’ ils sont orientés machine, au lieu que ça soit orienté problème. Le programmeur peut être gêné par des détails qui n’ont aucun rapport avec la programmation de ses algorithmes, ou même, par l’obscurité des algorithmes eux même. Par conséquent, les coûts des développements restent élevés, et les programmes seront difficilement, ou même inefficacement modifiés, et ceci à l’ intention de corriger des erreurs ou améliorer les performances. D’autre part, l’absence de la portabilité oblige les programmeurs à réécrire tout programme, en vu de le transférer d’une machine à une autre. De plus, une formation, bien complète, est exigée pour tous ceux qui sont concernés par l’utilisation et la programmation en langage d’assemblage. X-2-Langages séquentiels d’ implémentation des systèmes:

L’apparition d’ordinateurs puissants et la progression dans la technologie des compilateurs ont rendu l’écriture des logiciels temps réel plus avantageuse. On a pu constater le développement de plusieurs langages, spécialement conçus pour la programmation des systèmes embarqués. Ces langages ont en commun la propriété qu’ ils sont séquentiels. De plus, ils n’offrent pas aux STR le bon contrôle du temps réel ni la fiabilité adéquate. X-3-Langages de programmation concurrents de haut niveau:

Le langage de programmation Modula, développé par Wirth, a prouvé beaucoup de qualités pour la programmation et l’exploitation des dispositifs de la machine. Plusieurs expériences, basées sur l’ implémentation en Modula et son utilisation, sont arrivées à Modula-2, un langage d’ implémentation de systèmes généraux. De nouveaux langages apparaissent, tels que PERL, utilisés intensivement pour les applications de contrôle de processus, Mesa (Xerox Corporation 1985), utilisé par Xerox, dans ses bureaux, et CHILL qui a été développé afin de répondre aux besoins du CCITT dans les applications de télécommunication. Tous ces langages, et autres, sont destinés pour le développement des systèmes temps réel embarqués. Le langage Occam, apparu récemment et ses propriétés diverses, avait un rôle important dans l’apparition du domaine des applications embarquées couplées et distribuées.

Page 15: Restructuration d applications Java Temps réel

131313

13 13

Le Monde Des Systèmes Temps Réel 1

XI - Analyse des Contraintes de Tâches: Un modèle de tâches temps réel permet de spécif ier l ’ architecture fonctionnelle

d’ un système temps réel. Chaque tâche est définie par un ensemble d’attributs décrivant les contraintes auxquelles elle est soumise.

Traditionnellement, les applications temps réel étaient souvent décrites par le modèle des tâches périodiques [Liu73]. Ce modèle décrit une application temps réel par un ensemble fini (appelé aussi configuration) de tâches périodiques. Une variante de ce modèle consiste à prendre en compte les tâches apériodiques. Dans ce modèle, toutes les tâches doivent s’ exécuter jusqu’à leurs fins. Cependant, pour des besoins nouveaux des systèmes temps réel, certaines tâches n’ ont pas la contrainte de terminer nécessairement leur exécution. Ce qui a donné naissance à deux nouveaux types de modèles: le modèle des tâches incrémentales et le modèle des tâches à résultats imprécis.

Diverses variantes de ces modèles ont été développées. Certaines d’ entre elles sont le résultat d’ intégration des modèles existants. D’autres traitent des contraintes de type ressources ou synchronisation.

XI -1-Contraintes de temps:

La plupart des contraintes de temps sont celles introduites par les modèles de tâches périodiques et apériodiques. Ces deux types de modèles sont souvent uti l isés en temps réel. En effet, un système temps réel est souvent concerné par le contrôle d’un comportement continu (procédé) qui nécessite des actions répétitives (tâches périodiques) ou aléatoires (apériodiques).

Il existe trois types de tâches temps réel qui sont conçues pour superviser et contrôler les différentes fonctions: Les tâches périodiques, sporadiques et apériodiques [Klein94].

Les tâches périodiques sont les plus souvent trouvées dans les systèmes temps réel. Afin de superviser un système physique ou un processus, le système d’ ordinateur doit capter régulièrement des informations sur le processus et réagir quand des résultats appropriés sont obtenus ou des informations spécif iques sont lues. Cet échantil lonnage régulier d’ informations est effectué par la tâche périodique par une série continue d’ invocations régulières, commençant par une invocation initiale à un certain temps I. Les invocations se produisent périodiquement toutes les T unités de temps. Chacune de ces invocation possède un temps d’ exécution de C unités qui peut être déterministe ou stochastique. C indique souvent la borne maximale (ou le pire des cas) du temps d’ exécution.

Chaque invocation de tâche aura une contrainte de temps explicite, appelé l ’ échéance qui signif ie que l’ invocation doit se terminer avant un certain temps D après son passage à l ’ état prêt. Ainsi, la première invocation doit se terminer dans le temps I+D, la deuxième dans I+T+D, etc.

Les tâches périodiques sont habituel lement invoquées par les temporisateurs internes avec une périodicité choisie telle qu’ el le assure une latence suffisamment courte pour réagir aux événements de changement dans l ’ environnement en question.

Les tâches sporadiques et apériodiques sont invoquées à des intervalles irréguliers. La tâche sporadique possède une échéance stricte (hard) et une borne sur l ’ intervalle séparant deux invocations. La tâche apériodique peut s’ effectuer avec un intervalle aléatoire qui sépare deux invocations.

Par ai l leurs, un processus est une séquence d’opérations qui doivent être exécutées dans un ordre prescrit [Xu93]. Les processus peuvent être divisés en deux catégories: les tâches de la première catégorie ont une échéance «stricte» (hard), c’ est-à-dire que la satisfaction de ses échéances est critique pour le fonctionnement du système, cel les de la

Page 16: Restructuration d applications Java Temps réel

141414

14 14

Le Monde Des Systèmes Temps Réel 1

deuxième catégorie ont des échéances «relatives» (soft), en ce sens que bien qu’un court temps de réponse est souhaitable, un dépassement occasionnel de l ’ échéance peut être toléré. XI -2-Contraintes d’ importance: Les tâches d’ une application temps réel ne sont pas toutes aussi importantes les unes que les autres. En effet, du point de vue du concepteur d’une application, une tâche peut être plus importante qu’une autre. Cette caractéristique de la tâche est déterminée par des paramètres (poids, degré d’urgence, priorité externe, tâche cri tique, etc.). L’ échec d’ une tâche cri tique peut entraîner l ’ arrêt d’ exécution du système, situation qui peut être catastrophique. Par exemple, dans un système de contrôle de vol, le concepteur de l ’ application peut associer un poids fort à la tâche qui contrôle la stabil i té de l ’ avion, afin de refléter sa nature cri tique. Si cette tâche échoue dans le respect de son échéance, l ’ avion peut s’ écraser. Par contre, i l accorde un faible poids à la tâche qui contrôle l ’ enregistreur de vol. XI -3-Contrainte d’ interruption

Cette contrainte permet d’ exprimer si une tâche est interruptible ou non. Par exemple, dans un système temps réel réparti, une tâche qui ne fait que du calcul interne, peut être interrompue. Par contre, la tâche chargée de l ’ émission d’une trame ne peut être interrompue et elle doit se terminer. Si son émission est interrompue, elle doit la recommencer complètement. Une tâche interruptible peut être interrompue par une autre tâche prioritaire. Son exécution peut être reprise ultérieurement. Lorsqu’une tâche est interrompue, elle peut être forcée de libérer temporairement les ressources qu’elle a acquises.

XI -4-Contrainte de terminaison

Dans des conditions de surcharge, certaines applications temps réel se contentent d’ exécuter quelques tâches partiellement. De telles applications peuvent se contenter de résultats acceptables. La contrainte de terminaison ont été prises en compte dans les modèles de tâches incrémentales et les modèles de tâches à résultats imprécis.

XI -5-Contraintes événementielles:

Un événement peut démarrer certaines tâches et/ou terminer d’ autres. Les conditions d’ activation/terminaison de tâches peuvent être décrites par une combinaison d’ opérateurs de la logique temporelle (avant, après, etc.) [Chung95, Sahraoui85] avec des arguments qui sont (une date, un changement d’ état, une expiration d’un délai, etc.). Activation/terminaison d’ une tâche peut être uti l isé aussi bien pour décrire des contraintes temporelles que des contraintes décrivant son interaction avec d’ autres tâches. Comme ces contraintes peuvent exprimer d’ autres situations (autres que les contraintes de temps), cela justifie de les considérer indépendamment et dans la partie des contraintes intrinsèques à une tâche. XI -6-Les contraintes extrinsèques:

Les contraintes extrinsèques à une tâche décrivant les contraintes résultant de son interaction avec d’ autres tâches. Au cours de leur exécution, les tâches ne sont pas indépendantes les unes des autres (relations de coopérations, relations de compétition, etc.). Les relations de coopération indiquent l ’ existence d’ un ordre d’ exécution, de

Page 17: Restructuration d applications Java Temps réel

151515

15 15

Le Monde Des Systèmes Temps Réel 1

synchronisation, de communication, etc. Les relations de compétition indiquent la manière avec laquelle les tâches uti l isent des ressources partagées.

Généralement, dans les applications informatiques, la mise en œuvre des contraintes de coopération et de compétition est réalisée par des mécanismes de synchronisation (rendez-vous, moniteur,…), d’ exclusion mutuelle (sémaphores,…), de communication (boites aux lettres,…), et bien d’ autres.

XI -7-Contraintes d’accès aux ressources:

Les tâches util isent des ressources disponibles en nombre limité pour lesquelles elles entrent en compétition. La bonne uti l isation des ressources partagées se traduit par l ’ existence de contraintes de ressources. Parmi les contraintes de ressources on peut distinguer les contraintes liées à leur uti l isation et celles l iées à leur fonctionnement.

Une ressource est dite non préemptible (telle qu’une imprimante) si elle ne peut être retirée à une tâche Ti au profi t d’une autre tâche sans qu’ i l y ait avortement de la tâche Ti; une ressource est dite consommable (telle qu’ un missi le dans une application militaire) si après son util isation par une tâche, elle est consommée et donc n’ existe plus, etc.

Parmi les exemples des contraintes liées au fonctionnement des ressources, on peut citer [Liu94]: la durée d’ acquisition d’ une ressource, la durée de restitution d’une ressource et la durée de commutation de contexte. La durée d’ acquisition de ressources est la durée maximale qui peut être prise en compte par une tâche afin d’ acquérir une ressource oisive due aux propriétés de la ressource elle même. La durée de restitution d’ une ressource est la durée maximale séparant l ’ instant où une tâche libère la ressource et l ’ instant où la ressource n’ est plus dans le contexte de la tâche et donc disponible pour d’ autres tâches. La durée de commutation de contexte est la durée nécessaire pour commuter une ressource d’une tâche à une autre, généralement suite à une interruption de la première tâche par la seconde. Dans plusieurs cas, la durée de commutation de contexte d’une tâche est égale à la somme de durée d’ acquisition et de la durée de restitution de ressource. Cependant, ceci n’ est pas toujours le cas. En effet, dans le cas par exemple d’ un seul processeur, les informations de gestion de ce dernier telles que les contenus de registres, nécessitant d’ être sauvegardées et restaurées durant une commutation de contexte et pas pendant l ’ acquisition ou la restitution.

Les contraintes d’ accès de ressources associées à une tâche, indiquent, d’une part, le type de ressources indispensables à son exécution, et d’ autres part, le mode d’ accès (exclusif, partagé, etc.) qu’ exige la tâche sur les ressources. Pour ce dernier cas, l ’ expression de telles contraintes est nécessaire pour décrire les situations où la tâche désire un accès en exclusion mutuelle sur une ressource à n points d’ accès. En environnement temps réel, la connaissance des contraintes de ressources par l ’ algorithme d’ordonnancement est nécessaire pour qu’ i l puisse effectuer l ’ ordonnancement des tâches qui les uti l isent et réaliser leur gestion dans le cas où la gestion de ressources est une fonction de l ’ ordonnanceur.

XI -8-Contraintes de placement:

Le besoin d’ expression de contraintes de placement est spécif ique aux systèmes centralisés multiprocesseurs ou répartis. En effet, une tâche peut exiger que son exécution se fasse sur un certain processeur (pour des raisons de compatibil ité du code exécutable par exemple) ou sur un site donné (parce qu’elle fait des entrées/sorties sur un dispositi f particulier, par exemple).

Page 18: Restructuration d applications Java Temps réel

161616

16 16

Le Monde Des Systèmes Temps Réel 1

XI -9-Contraintes de tolérance aux fautes: En environnement temps réel, les contraintes de tolérance aux fautes, associées aux

tâches, sont capitales pour exiger que le respect de leur contraintes temporel les soit vérif ié, ceci même en présence de fautes liées aussi bien au système d’ exploitation, à l ’ exécution des tâches, qu’ au matériel (ordinateur, réseaux de communication, etc.).

XI I - Ar chitectures Temps Réel:

Dans la plupart des architectures de contrôle, la façon de partager les rôles de prises de décision nous révèle la manière de fonctionnement des architectures. Les rôles des différents aspects du problème de contrôle sont souvent partagés à travers les modules. Un rôle est constitué d’ un ensemble de responsabil ités homogènes conçues dans la perspective d’ un objecti f déterminé. On affecte à chaque module un ou plusieurs rôles. Les modules sont souvent interdépendants dans la perspective de réaliser leurs propres objecti fs ou ceux du système global. Ces dépendances sont habituel lement établies à travers des communications clairement définies entre les modules. Le type de communication entre les modules et les types de rôles affectés aux modules, ont un impact signif icati f sur la façon d’ interaction du système avec son environnement.

Le rôle de prise de décision dans un système temps réel peut être partagé comme étant une décomposition soigneusement ordonnée de tâches d’ un côté, et une étroite coopération entre ces tâches d’ un autre côté. Le premier cas est souvent considéré comme une forme de contrôle central isé, le second est un contrôle décentralisé.

XI I -1 Architecture centralisée:

Dans ce type d’ architecture, le système est consti tué d’ une seule unité de traitement, composée d’ un ou de plusieurs processeurs se partageant une mémoire commune. La principale caractéristique d’ une telle instal lation, par rapport à la suivante, est que la durée de transmission de l ’ information d’ une tâche à une autre est négligeable devant le temps qui s’écoule entre deux transitions d’ états (points observables). Cette unité de traitement est reliée par des interfaces à une série de capteurs et d’ actionneurs. La datation se fait par une horloge unique qui est uti l isée pour la gestion du temps (temporisation, chien de garde, etc.). La mémoire commune contient le contexte des tâches et les données de l ’ application. El le permet de mémoriser instantanément, l ’ état global du système. De plus, el le représente le mécanisme de base pour la communication et la synchronisation entre les tâches.

Les avantages de cette architecture sont ceux des systèmes centralisés: contexte centralisé, temps cohérent, applications simples à mettre en œuvre. Par contre, les perspectives d’ évolution d’un tel système sont l imitées par ses possibil i tés physiques. De même, le seul traitement à apporter aux surcharges est de fonctionner en mode dégradé.

Comme exemple de contrôle centralisé, considérons un système de robot dont la simple hiérarchie de contrôle consiste en un planif icateur de mouvement et un contrôleur de mouvement. Le planif icateur de mouvement doit acquérir des données de l ’ environnement au moyen des capteurs, construire un modèle interne de la réalité sur la base des données collectées et ensuite, faire le choix de la meil leure action. Le plan de l ’ action sera soumis au contrôleur de mouvement sous la forme d’une trajectoire de points dans certain cadre cartésien de coordonnées. Le rôle du contrôleur de mouvement est maintenant de suivre cette trajectoire autant précisément que possible.

Le contrôleur de mouvement a un rôle temps réel critique de conduire le robot tout au long d’un chemin passant par certains points. Tous les aspects de contraintes de temps au niveau du contrôleur de mouvement sont l iés à la capacité d’ effectuer un

Page 19: Restructuration d applications Java Temps réel

171717

17 17

Le Monde Des Systèmes Temps Réel 1

mouvement sans heurts avec des déviations minimales par rapport au chemin spécifié. La val idité de ce chemin incombe au planificateur de mouvement.

Les contraintes de temps du planif icateur de mouvement sont quelque peu moins sévères, et plus négociables que celles du contrôleur de mouvement. Dans ce type de système, chaque niveau travail le sur un sous problème spécif ié par un niveau supérieur. Dans ce sens, le contrôle est centralisé au sommet de la hiérarchie.

XI I -2 Architecture r épar tie:

Les fonctions de l ’ application peuvent être prises en compte par n’ importe quelle unité de traitement, grâce aux possibil ités de communication du médium. Les capteurs émettent sur le réseau les données (mesures ou événements) qui sont traitées dans un ou plusieurs sites.

En environnements répartis, de nouveaux problèmes se posent et auxquels i l faut faire face: le placement des tâches, la mise à jour des copies multiples de données, la synchronisation de tâches, etc. Les inconvénients des systèmes répartis sont: difficulté de la gestion répartie des ressources, incohérences des horloges locales, prise en compte des pannes, absence de contexte global, etc. Par contre, c’ est le schéma qui semble le plus souple par ses capacités d’ évolution, par ses possibil i tés de tolérance aux pannes et de répartition de la charge ou capacités de réponses aux surcharges. XI I I - Conclusion

Les systèmes temps réel sont souvent distribués et possèdent différentes contraintes de temps, de sécurité, de fiabil i té, et de robustesse, imposées par l ’ environnement de l ’ application. Comprendre et contrôler le comportement temporel constituent un aspect cri tique pour assurer la sécurité et la f iabi l ité.

La vitesse (vitesses de processeurs par exemple) seule, n’ est pas suffisante pour la satisfaction des contraintes de temps. Des techniques rigoureuses de gestion de ressources doivent aussi être uti l isées, afin de prévenir des situations dans lesquelles des tâches longues et à priorités réduites bloquent d’ autres tâches à priorités plus élevées et temps d’ exécution réduits.

Le principal guide de gestion des ressources des systèmes temps réel est la capacité de déterminer si le système peut satisfaire toutes ses contraintes de temps. Ce besoin de prévisibil ité nécessitent le développement et l ’ uti l isation de modèles d’ ordonnancement et des techniques analytiques. Leurs applications nécessitent l ’ intégration de certaines qualités de services, particulièrement en matière de prévisibi l ité des temps d’ exécution des tâches, de tolérance aux fautes, de disponibi l ité et de performances. Ils doivent présenter des interfaces util isateurs conviviales. La prévisibi l ité dans le contexte temps réel «hard» requiert une importance capitale. Ces systèmes peuvent comprendre des ressources hétérogènes tel les que les CPUs, les réseaux, et les périphériques d’ entrée/sortie qui doivent être ordonnancées de façon à être prévisibles, flexibles, et faciles à analyser mathématiquement.

La prévisibil i té nécessite le développement de modèles d’ ordonnancement et de techniques analytiques afin de déterminer si le système temps réel peut ou non satisfaire les contraintes de temps.

Les diff icultés de spécifications, analyse, et ordonnancements de processus dans les systèmes temps réel à contraintes de temps strictes (hard) sont augmentées par le fait que le système physique contrôlé consiste souvent en plusieurs sous-systèmes indépendants produisant des signaux asynchrones de capteurs et valeurs de contrôle [Kramer93]. De tels systèmes peuvent avoir besoin de logiciels de contrôle distribué

Page 20: Restructuration d applications Java Temps réel

181818

18 18

Le Monde Des Systèmes Temps Réel 1

fournissant des capacités adéquates de traitements et de temps de réactions pour effectuer des tâches périodiques avec des ordonnancements serrés et pour le traitement dans le temps requis d’événements arrivant de façon asynchrone.

Page 21: Restructuration d applications Java Temps réel

Ordonnancement Des Tâches 2

19

I - Types de tâches temps réel:

Nous utilisons une classification de ces tâches en fonction des propriétés de la liste de leurs

dates d'occurrences. Trois types de tâches ont été identifiées :

périodiques : Une tâche périodique est définie comme une tâche qui doit être prête à être

exécutée à des intervalles de temps fixés (ou périodes) et dont l'exécution doit être terminée

avant le début de la période suivante [Bestravos93]. Une autre définition dit qu'une tâche

périodique demande une allocation du temps processeur à des intervalles réguliers, ces temps

processeur devant être alloués de façon à ce que l'exécution de la tâche ne dépasse pas ses dates

limites [Howell94] [Gupta94].

apériodiques: [Burns90] L'activation d'une tâche apériodique est essentiellement due à un

événement aléatoire et est déclenchée généralement par une action externe au système. Sa date

limite est fixée par l'environnement extérieur. Les tâches apériodiques ont également des

contraintes de temps qui leurs sont associées, par exemple le démarrage de leur exécution à

l'intérieur d'une période de temps prédéfinie. Souvent les tâches apériodiques sont déclenchées

par les événements critiques de l'environnement externe du système, c'est pour cela que leurs

dates limites sont souvent contraintes.

sporadiques: Une tâche sporadique est comme pour une tâche apériodique souvent déclenchée

par un événement extérieur au système, mais on constate l'existence d'une durée minimum entre

deux événements apériodiques (issus de la même source). La tâche sera alors dite sporadique

[Howell94] [Burns90].

I I - Ordonnancement des applications temps réel:

Dans les systèmes temps réel, un problème d’ ordonnancement consiste, à partir d’ une

architecture matérielle (une ou plusieurs machines mono ou multiprocesseurs, un ou

plusieurs réseaux,…), d’ une architecture fonctionnelle, et d’ un ensemble d’objecti fs

souhaités, à trouver un planning d’ exécution des tâches de façon à garantir le respect des

contraintes de temps.

L’ ordonnancement joue un rôle important puisque c’ est lui qui définit le planning

d’ exécution de tâches de façon à ce que les contraintes de tâches soient vérifiées. Dans la

plupart de ces systèmes, le respect de ces contraintes de temps reste le principal critère à

satisfaire.

Page 22: Restructuration d applications Java Temps réel

Ordonnancement Des Tâches 2

20

Un problème d’ordonnancement dans un système temps réel est défini par le modèle

du système, les tâches et leurs natures, ainsi que les objectifs que l ’ algorithme

d’ ordonnancement doit réaliser.

Le modèle de système décrit l ’ architecture matériel le du système disponible

(machine(s), réseau(x), etc.), qu’ on appellera services, et les contraintes associées.

Les tâches et leurs natures sont décrites au niveau de la spécif ication fonctionnelle de

l ’ application et des contraintes associées. Comme exemple de ces contraintes, on peut citer

[Cardeira94]: les contraintes de temps, les contraintes de ressources, de précédence, etc.

Le challenge de l ’ ordonnancement est de garantir que toutes les contraintes du

problème sont satisfaites, particulièrement les contraintes de temps. L’ ordonnanceur

produit un planning d’ exécution de tâches, qui assure le respect des contraintes. Un

ordonnancement (planning) valide est un ordonnancement qui vérif ie, sur une durée infinie,

que toutes les contraintes sont satisfaites.

L’ intervention du temps fait des systèmes réactifs des systèmes temps réel. Le temps

est alors un facteur déterminant puisqu’ i l intervient aussi bien dans la définition des

critères de performances (par exemple, appliquer en une mill isecondes une commande

externe à chaque fois qu’un capteur détecte une mesure excédant une certaine valeur) que

dans le séquencement interne d’ un logiciel (par exemple, lancer une tâche de surveil lance

séquentiel lement toutes les 100 mil l isecondes).

Les méthodes du génie logiciel concernant les systèmes informatiques usuels font

appel à des modèles fonctionnels. En effet, la dynamique de ces systèmes étant pauvre, une

décomposition fonctionnelle structurée et l ’ identification des informations circulant entre

fonctions sont suffisantes pour spécif ier la plupart des problèmes [Vallotton91].

Les approches fonctionnelles ne sont pas satisfaisantes pour traiter la spécif ication

des systèmes réactifs, car les aspects émergeant de ces derniers sont essentiellement

dynamiques. Un système réactif n’ évolue pas seulement en fonction de ces entrées, mais

aussi des états internes. Un exemple trivial l ’ i l lustre: un logiciel qui doit exécuter une

routine d’ interruption sauf si elle survient alors qu’ i l est déjà en cours de traitement. Une

composante de son état est «être en cours de traitement de l ’ interruption», sa connaissance

est nécessaire pour prévoir le comportement du système.

Dès que l ’ on a affaire à un système temps réel d’ une certaine complexité, le point de

vue du comportement réacti f devient primordial. Il doit donc intervenir dans sa

Page 23: Restructuration d applications Java Temps réel

Ordonnancement Des Tâches 2

21

modélisation. Les méthodes spécifiques du temps réel introduisent généralement le

contrôle, mais davantage pour assurer la cohérence des modèles fonctionnels que pour

introduire de réels moyens de modéliser le comportement.

Dans la pratique, les portions temps cri tique des systèmes temps réel durs continuent

d’ être implémentées par des langages de programmation de bas niveau. El les sont

manuellement réglées afin de satisfaire toutes les contraintes. Les développeurs rencontrent

de grandes difficultés dans l ’ élaboration et l ’ analyse de codes complexes et ce, en

l ’ absence d’ un langage, supportant des outi ls appropriés de spécif ication des contraintes de

temps [Chung95, Gerber97].

La spécification des contraintes de temps de granularité très fine dans le contexte

d’ un langage de programmation de haut niveau n’ est pas encore possible. On établit

manuellement des portions de code en langage assembleur pour exprimer des contraintes

strictes de temps. Ce qui rend ces programmes très difficiles à écrire et à maintenir, et un

ordonnancement automatisé devient presque impossible. Les langages tels que Ada

[Taft92] ne permettent de spécifier les contraintes de temps qu’entre les tâches,

lexicographiquement adjacentes dans le code source, et ne permettent pas de les spécif ier

entre les instructions. Cette adjacence est aussi arti ficielle qu’ insuffisamment expressive.

I I I - Etude formelle

Dans les STR, garantir que les tâches s’exécutent en respectant leurs échéances prescrites

est un point critique pour assurer l’ intégrité de ces systèmes (systèmes en robotique) et la réussite

de ses missions.

Actionneur n

Actionneur m

Actionneur k

Actionneur2

Actionneur1

Capteur n

Capteur2

Capteur1

Flu

x d

’Inf

orm

atio

n

Ech

anti

llonn

age

Cap

teur

s Système de

Contrôle Temps Réel

Inte

rven

tion

e

t R

éact

ion

Fig I -4:Modélisation du fonctionnement d’un système temps réel

Page 24: Restructuration d applications Java Temps réel

Ordonnancement Des Tâches 2

22

Dans de tels systèmes, les tâches sont accomplies (exécutées) régulièrement et

périodiquement, dans le but de contrôler des processus physiques et le fonctionnement des

appareils de contrôle. Elles échantillonnent des informations pour effectuer un traitement

spécifique, dans le but de produire des commandes pour les actionneurs.

L’ invocation de ces tâches typiques se fait périodiquement, à chaque unité de temps T.

L’exigence la plus commune est qu’une invocation d’une tâche doit être achevée (complétée)

dans D unités de temps après qu’elle ne soit dans l’état Prêt. Les paramètres T et D sont appelés

respectivement la période et l’échéance.

Dans le cas où on confronte un problème de l’accomplissement de la tâche dans le temps

approprié, ou on marque la présence d’un flux dans la logique du programme, on pourra

marquer, par conséquent, des résultats catastrophiques dans les STR hards. On peut en déduire

que la rencontre de contraintes de temps est extrêmement importante dans de tels systèmes. Pour

satisfaire leurs échéances, les tâches doivent être ordonnées d’une manière adéquate.

Les algorithmes d’ordonnancement de tâches des les STR typiques confirment que les

temps d’exécution dans le plus pire des cas sont connus. Un tel système est conçu pour s’assurer

que toutes les tâches peuvent s’achever au bout de leurs échéances tant qu’ il n’y a pas une tâche

dans le système qui s’exécute pendant une durée supérieure au temps d’exécution dans le cas le

plus pire. Une tâche qui dépasse le temps d’exécution prévu, peut entraîner une perte d’échéance

et l’échec total du système.

Différents modèles et théories ont été développés et utilisés comme une base permettant

l’étude et l’analyse du comportement des STR. En particulier, la théorie d’ordonnancement avec

priorités fixes a prouvé sa capacité de développement d’une sorte de découverte théorique pour

l’analyse du comportement temporelle des systèmes et de conception de systèmes amenant à

réaliser cette analyse.

Dans un simple ordonnancement Rate-Monotonic, Gerber & Hong ont montré qu’ ils

peuvent améliorer l’ordonnançabilité en divisant le programme de la tâche en deux fragments. Le

premier dépend d’un événement observable, et le deuxième concerne un calcul interne (local) qui

peut être exécuté plus tard. Cependant, cette approche traite seulement des programmes simples

et monolitiques.

Dans le but de considérer une classe plus générale de problèmes d’ordonnancement,

Gonzalez, Härbour et al ont réalisé un travail de fond pour le raisonnement à propos du

Page 25: Restructuration d applications Java Temps réel

Ordonnancement Des Tâches 2

23

comportement temporel dans le contexte des tâches composées d’une série de sous-tâches qui

s’exécutent avec des priorités multiples (dynamique).

La notion d'ordonnanceur de tâches prend toute sa signification lorsqu'on souhaite faire

exécuter les tâches par une architecture matérielle. Il faut être capable en cours d'exécution du

système, d'allouer du temps CPU d'une ressource de l'architecture matérielle à toute tâche qui

ferait son apparition, et ce avant sa date limite d'exécution. Un algorithme qui alloue les temps

processeurs pour chaque tâche dans un système de tâches est un algorithme d'ordonnancement

[Burns90] [Howell94]. Ces algorithmes peuvent avoir diverses propriétés. On peut les qualifier :

• d'algorithme optimal : [Krithi94] [Di Natal] [Atanas94] [Howell94] Un

algorithme d'ordonnancement est optimal s'il peut correctement ordonnancer un système

de tâches chaque fois que ce système est ordonnançable ;

• d'algorithme NP-complet : [Di Natal] NP est la classe de tous les problèmes de

décision pouvant être résolus dans un temps polynomial par une machine non-

déterministe. Si un problème R appartient à la classe NP et que tous les problèmes de la

classe NP sont polynomialement transformables en R alors le problème R est reconnu

NP-complet. L'algorithme gérant ces problèmes décisions est alors NP-complet ;

• d'algorithme NP-hard : [Di Natal] NP est la classe de tous les problèmes de

décision pouvant être résolus dans un temps polynomial par une machine non-

déterministe. Si tous les problèmes de la classe NP sont polynomialement transformables

en un problème R mais qu'on ne peut pas prouver que ce problème R appartient lui-même

à la classe NP, alors le problème R est dit NP-hard. L'algorithme gérant ce problème de

décision est dit NP-hard.

I I I - Ordonnancement " à base de pr ior ités" :

Nous allons regarder le cas particulier de deux algorithmes (ces deux algorithmes sont très

étudiés au niveau de la recherche sur l'ordonnancement temps réel) : le Rate Monotonic et le

Earliest Deadline.

I I I -1- L 'algor ithme Rate Monotonic:

La notion d'ordonnancement Rate Monotonic a été introduite en premier par Liu et

Layland [Liu73] en 1973. L'ordonnancement Rate Monotonic est un ordonnancement statique et

ne s'applique que pour des tâches périodiques. Il s'agit d'un algorithme d'ordonnancement à

priorités fixes. L'avantage d'une allocation fixe des priorités est que les priorités, allouées une

Page 26: Restructuration d applications Java Temps réel

Ordonnancement Des Tâches 2

24

fois pour toutes, ne sont pas réévaluées au cours du temps. Le terme Rate Monotonic dérive de la

façon dont sont allouées les priorités aux différentes tâches, elles sont allouées selon une

fonction "Monotonic" du "Rate" (de la période) de la tâche. Plus la tâche a une période courte,

plus la priorité allouée sera importante. De nombreux travaux ont étendu l'application du Rate

Monotonic aux tâches synchronisées, à données partagées, aux systèmes avec des tâches

apériodiques...

I I I -2- L 'algor ithme Ear liest Deadline:

Tout comme pour le Rate Monotonic, la notion d'algorithme Earliest Deadline a été

introduite en premier par Liu et Layland [Liu73] en 1973. l'ordonnancement Earliest Deadline est

un ordonnancement dynamique. Il peut s'appliquer pour l'ordonnancement de tâches périodiques

ainsi qu'apériodiques car il s'agit d'un algorithme d'ordonnancement à priorités dynamiques. Le

terme Earliest Deadline vient de la façon dont les priorités sont allouées aux tâches. La tâche

dont la date limite qui arrive le plus tôt aura une priorité élevée. Les priorités sont constamment

réévaluées au cours du temps (par exemple dans le cas où une nouvelle tâche arrive et que sa

date limite est la plus proche).

I I -3- Cr itère d'ordonnançabilité pour chacun de ces algor ithmes:

Dans le cas de systèmes où seules des tâches périodiques doivent être ordonnancées, des

travaux ont été réalisés pour déterminer, connaissant l'ensemble des tâches, à partir de quel

pourcentage d'utilisation CPU les dates limites de ces tâches seront sûres d'être respectées

[Liu73].

Le taux d'utilisation CPU pour une tâche i est le rapport entre le temps d'exécution de cette

tâche et sa période . Le taux d'utilisation CPU pour un groupe de tâches est la somme de ces

rapports.

Pour l'algorithme d'ordonnancement Rate Monotonic le pourcentage d'utilisation CPU doit

respecter la relation suivante si on veut être sûr que toutes les dates limites des différentes tâches

soient garanties :

(1) Lorsque n devient important, on remarque que pour être sûre de respecter les dates

limites des différentes tâches en utilisant l'algorithme Rate Monotonic pour ordonnancer les

tâches, le processeur doit être utilisé à moins de 69 %. Dans le cas particulier où les périodes des

Page 27: Restructuration d applications Java Temps réel

Ordonnancement Des Tâches 2

25

différentes tâches sont harmoniques, une étude a montré que quelque soit le taux d'utilisation

CPU si l'ordonnancement est réalisable alors il pourra être réalisé.

Pour l'algorithme d'ordonnancement Earliest Deadline le pourcentage d'utilisation CPU

doit respecter la relation suivante si on veut être sûr que toutes les dates limites des différentes

tâches soient garanties :

(2) Même lorsque n devient important, on remarque que quelque soit le taux d'utilisation

CPU, si l'ordonnancement est réalisable, il pourra être réalisé.

I I I -4- Les limites des deux algor ithmes:

Ces algorithmes ne posent pas de problèmes d'application tant que l'on reste dans une

utilisation avec des tâches périodiques (dans le cas du Rate Monotonic seulement, le Earliest

Deadline pouvant prendre en compte les tâches apériodiques), pas de protocoles (partage de

données entre tâches, ...), pas de surcharges.

Des études ont permis l'amélioration de ces algorithmes pour prendre en compte les

différents cas cités ci-dessus.

IV- Modes d'ordonnancement:

L'ordonnancement est une fonction centrale dans un système temps réel. En fonction de

l'apparition des entrées en provenance du système contrôlé (entraînant la demande d'exécution

d'une tâche), il doit réorganiser l'affectation des ressources processeur en vue du respect des

dates limites de chaque tâche.

L'ordonnancement peut se faire de deux façons. La première façon d'ordonnancer est

l'ordonnancement «offline» pour lequel l'ordonnancement est planifié dès la conception, des

tables d'ordonnancement sont créées et vont être utilisées en fonctionnement. Durant le

fonctionnement, le système se contente de lancer les tâches aux dates prévues. La deuxième

façon est l'ordonnancement online pour lequel l'ordonnancement est réalisé à chaque instant du

fonctionnement du système. Si les ordonnancements réalisés offline donnent des systèmes très

rapides à l'exécution, et d'une grande fiabilité, ils ne peuvent s'appliquer qu'aux systèmes dont on

connaît entièrement a priori le système contrôlé. Dans le cas contraire, un ordonnancement

online est nécessaire pour replannifier les tâches à l'apparition d'un nouvel événement significatif

[Atanas94] [Howell94].

Les algorithmes d'ordonnancement peuvent également être dits statiques ou dynamiques.

Un algorithme d'ordonnancement est dit statique lorsque l'ordonnancement est prévisible avant la

Page 28: Restructuration d applications Java Temps réel

Ordonnancement Des Tâches 2

26

mise en fonctionnement du système, il faut pour cela connaître les tâches a priori. Un algorithme

d'ordonnancement est dit dynamique lorsque l'ordonnancement est créé au fur et a mesure de

l'arrivée des tâches dont on peut ne rien connaître a priori. Un ordonnancement statique est plus

fiable mais moins flexible qu'un ordonnancement dynamique (pour un ordonnancement statique

il faut connaître l'ensemble des tâches à réaliser, alors que pour un ordonnancement dynamique

ce n'est pas la peine de toutes les connaître) [Atanas94].

A partir de ces différentes propriétés qui sont associées aux algorithmes d'ordonnancement,

une classification de ces algorithmes ressort :

• les ordonnanceurs que l'on peut qualifier de "tout planifiés". Ces ordonnanceurs sont

des ordonnanceurs offline et statiques. En effet, un ordonnancement est créé à partir d'une

table d'ordonnancement qui est construite à l'aide des caractéristiques des différentes tâches.

Cet ordonnancement est ensuite appliqué sur le système. Cette approche ne peut s'appliquer

que pour l'ordonnancement de tâches périodiques (ou qui ont été transformées en tâches

périodiques) puisqu'il faut connaître à priori l'ensemble des tâches et de leurs caractéristiques.

Cette approche est hautement prédictible mais n'est pas flexible : un changement sur une des

tâches ou une de ses caractéristiques entraîne la reconstruction totale de la table [Krithi94] ;

• les ordonnanceurs que l'on peut qualifier d'ordonnanceurs "à base de priorités". Ces

ordonnanceurs sont online mais peuvent être statiques ou dynamiques. Des priorités sont

affectées aux tâches, l'ordonnanceur va ordonnancer les tâches suivant la valeur de la priorité

qui leur est affectée. Pour ce type d'ordonnancement apparaît la notion de préemptivité (si une

tâche de basse priorité est en train d'être exécutée et qu'une tâche de priorité plus haute est

déclenchée, la tâche de basse priorité sera interrompue et le processeur sera affecté à la

nouvelle arrivée) [Krithi94]. Un algorithme d'ordonnancement peut être à priorités fixes

(statiques) ou dynamiques [Atanas94]. Dans le cas d'un ordonnancement à priorités fixes, on

va associer à chaque tâche une priorité, cette priorité va rester la même tout au long du

fonctionnement du système. Dans le cas d'un ordonnancement à priorités dynamiques la

valeur de la priorité d'une tâche va évoluer au cours du fonctionnement du système ;

• les ordonnanceurs que l'on peut qualifier de "dynamiques". Ces ordonnanceurs sont

online et dynamiques. Il apparaît deux approches "dynamiques", les approches "Dynamic

Planning-Based" et les approches "Dynamic Best-Effort". Les approches "Dynamic Planning-

Based" lorsqu'une tâche apparaît vont, avant de l'exécuter, créer un plan d'exécution de cette

tâche et vérifier si ce plan va garantir son exécution. Si l'exécution de cette tâche n'est pas

Page 29: Restructuration d applications Java Temps réel

Ordonnancement Des Tâches 2

27

garantie alors d'autres alternatives seront envisagées (tel l'envoi de la nouvelle arrivée sur un

autre nœud du système pour un système distribué) [Krithi94]. Pour les approches "Dynamic

Best-Effort", les tâches vont être ordonnancées mais en aucun cas, leurs dates limites ne

seront garanties [Krithi94].

Pour le génie automatique, les ordonnanceurs du type "tout planifiés" ne peuvent pas

répondre aux problèmes posés par l'apparition à caractère aléatoire des événements issus du

système contrôlé. En effet il est impossible de planifier, avant la mise en route du système,

l'affectation des tâches sur le ou les processeurs du système contrôlant car on ne connaît pas les

dates de demande d'exécution. Les ordonnanceurs du type "dynamiques" ne peuvent pas

s'appliquer dans le domaine de l'automatique car les systèmes que nous étudions sont des

systèmes contraints et que dans le cas de ces ordonnanceurs on ne sait pas a priori si toutes les

dates limites pourront être garanties. Par contre les ordonnanceurs du type "à base de priorités"

sont très prisés par les acteurs du Génie Automatique. Nous allons donc dans la suite de notre

étude détailler ce type d'ordonnanceurs.

V- Création d'ordonnancements plus complexes:

Les algorithmes Rate Monotonic et Earliest Deadline sont complétés par d'autres

algorithmes ou protocoles dans le but de pouvoir répondre à des spécifications du système plus

compliquées (la prise en compte de tâches apériodiques, des protocoles tels le partage des

données ..., le traitement des surcharges transitoires).

V-1- Introduction des problèmes " d' inversion de pr ior ités" (dus aux par tages de données

par exemple):

Comme nous l'avons déjà vu, un algorithme d'ordonnancement est préemptif lorsqu'au

cours de l'ordonnancement il peut interrompre l'exécution d'une tâche et allouer le temps

processeur à une autre tâche. Par exemple lorsqu'une tâche de plus haute priorité arrive, le Rate

Monotonic ou le Earliest Deadline vont interrompre l'exécution de la tâche qui est en cours pour

exécuter la nouvelle arrivée. Une tâche peut être préemptée plusieurs fois sans aucune pénalité.

Les algorithmes non préemptifs ne peuvent pas interrompre l'exécution d'une tâche de cette façon

[Burns90] [Atanas94] [Sha93].

Dans les systèmes temps réel, les tâches interagissent pour satisfaire des spécifications plus

larges du système. Les formes que prennent ces interactions sont variées, allant de la simple

Page 30: Restructuration d applications Java Temps réel

Ordonnancement Des Tâches 2

28

synchronisation jusqu'à la protection par exclusion mutuelle sur les ressources non partageables,

et les relations d'antériorité. Pour cela, il existe des événements, des langages de programmation

concurrente fournissant des primitives de synchronisation (drapeaux, contrôleurs...). La difficulté

principale avec ces drapeaux, contrôleurs ou autres messages de base des systèmes, est que des

tâches à haute priorité peuvent être bloquées par des tâches à priorité plus basse. Ce phénomène

est connu sous le nom d'inversion de priorité. Quatre approches permettent de résoudre ce

problème :

• une approche appelée "prévention d'inversion de priorité"[Howell94],

• une approche appelée "héritage des priorités" [Klein90] dont le "Ceiling

Protocol" est un algorithme particulier [Klein90] [Di Natal]. Le travail de ce protocole lié

avec un ordonnanceur Rate Monotonic a été étudié par Sha et al. [Rajkumar90], et le

même protocole lié avec un ordonnanceur Earliest Deadline a été étudié par Chen et Lin

[Chen90],

• une approche appelée "Stark Ressource" [Di Natal].

L’adjonction de tels protocoles ne nous permet plus d'avoir une estimation de

l'ordonnançabilité des différentes tâches à ordonnancer.

V-2- Traitement des tâches apér iodiques ou sporadiques : les algor ithmes " bandwith

preserving" :

Beaucoup de systèmes temps réel doivent traiter des tâches périodiques ainsi que des

tâches apériodiques. Quand on veut prendre en compte des événements apériodiques, il faut

utiliser une approche dynamique, telle le Earliest Deadline. Mais malgré cela, l'exécution en cas

de surcharges transitoires pose des problèmes (Les dates limites qui ne sont pas respectées ne

sont pas forcément celles dont l'importance pour le système est la moindre), ce cas est traité dans

le paragraphe suivant.

Le Rate Monotonic a été adapté pour pouvoir gérer des tâches apériodiques. Pour cela, une

tâche périodique aura la fonction de servir une ou plusieurs tâches apériodiques. Différents

algorithmes permettent de gérer cela :

• le "Priority Exchange"[Sha87],

• le "Deferrable Server" [Sha87],

• le "Sporadic server" [Harbour91] [Sha87],

• le "Slack Stealing" [Davis93].

Page 31: Restructuration d applications Java Temps réel

Ordonnancement Des Tâches 2

29

V-3- Traitements en cas de surcharges transitoires:

(dus au fait que certaines tâches sont apériodiques).

Le fait de devoir gérer des tâches apériodiques peut entraîner un phénomène de surcharges

transitoires. Il peut se présenter des situations pour lesquelles il n'est pas possible de respecter les

dates limites, le système est alors dit en exécution de surcharge transitoire.

Malheureusement, une application directe du Rate Monotonic n'est pas appropriée dans le

cas de telles surcharges. Par exemple dans l'approche Rate Monotonic, une surcharge transitoire

va amener la tâche dont la période est la plus longue à dépasser sa date limite. Cette tâche peut

cependant être plus critique que les autres. La difficulté vient du fait que le concept de priorité

pour le Rate Monotonic est une indication de la période qui peut ne pas être une indication de

l'importance de la tâche vis à vis du système. Ce problème peut être résolu en transformant la

période dans le cas d'une tâche importante [Burns90].

Le Earliest Deadline est un algorithme optimal lorsqu'il n'y a pas de surcharge. Le

phénomène typique qui se produit en cas de surcharge avec le Earliest Deadline est l'effet

domino [Di Natal]. Pour contrôler les retards des tâches sous des conditions de surcharges, on

associe à chaque tâche une valeur reflétant l'importance de chaque tâche dans le système. Alors

la gestion des tâches à partir de ces valeurs peut être réalisée par l'algorithme de Smith" [Di

Natal]. Malheureusement, les contraintes d'antériorité sur les tâches sont souvent générales. Une

heuristique a été proposée dans le projet SPRING, où les dates limites et les algorithmes de coût

ont été combinés avec d'autres algorithmes pour revoir dynamiquement ces valeurs et accorder

les dates limites avec les contraintes d'antériorité. Certains algorithmes heuristiques, proposés

pour gérer les surcharges, améliorent l'exécution du Earliest Deadline [Livny91]

[Thambidurai89].

Page 32: Restructuration d applications Java Temps réel

JAVA Langage De L ’Avenir 4

30

Le langage JAVA

I - Introduction:

Java est un langage de programmation développé par Sun Micro-systems en 1990. Au

tout début, Java était destiné à la programmation de systèmes embarqués tels que ceux de

l’électroménagers et d’appareils électriques (vidéos, micro-ondes, lave-vaisselle, etc.). Ce

genre de programmation était auparavant effectué en assembleur ou en C. Ces deux langages

était coûteux car il fallait soit réécrire le code source lorsqu’un nouveau processeur sortait sur

le marché (assembleur) ou bien il fallait réécrire le compilateur (C ou C++). Java fut

développé pour être un langage universel, capable de s’adapter à n’ importe quelle type de

machine. Sun Micro-systems avait aussi comme but de faire un langage plus simple à utiliser

que l’assembleur, le C ou le C++.

Avec l’arrivée d’ Internet, on s’est vite aperçu que Java était le langage idéal pour faire

de la programmation sur le web car il est multi-plateforme. Mais que veut dire multi-

plateforme? Cela signifie qu’une application écrite en Java peut être utilisée soit sur un PC,

sur un Macintosh, sur une station Sun utilisant UNIX comme système d’exploitation, etc. Les

applications développées en Java ne sont pas dépendantes du système d’exploitation. Comme

l’ Internet relie tous les types d’ordinateurs imaginables, un seul choix s’ imposait en se qui a

trait à la programmation sur le web. Java semble le langage de l’avenir !

Mais un langage de programmation ne saurait être parfait. Pour pouvoir être multi-

plateforme, un élément important a dû être sacrifié : la vitesse. Java n’est pas un langage

exécuté, il est interprété. Mais quelle est la différence entre un langage exécuté et un autre

interprété? Les langages exécutés, comme le C ou le C++ par exemple, utilisent un

compilateur pour transformer le code source en langage machine. Le langage machine,

composé de “1” et de “0” , est la seule et unique chose qu’un ordinateur peut comprendre. Le

problème est que chaque processeur possède sont propre langage machine, c’est-à-dire que la

façon de disposer les “1” et les “0” est différente pour chacun d’entre eux. Heureusement, la

plupart des processeurs ont à peu près le même type d’ instruction, ce qui évite de faire un

compilateur pour chaque processeur. Imaginez un compilateur pour un Intel PII 233, un autre

pour un Intel PII 266, etc. On ne s’ y retrouverait plus ! À la place, les PC fonctionne sur le

même “ langage machine” . Il en va de même pour les Macintosh et les stations Sun pour n’en

nommer que quelques-uns.

Pour compliquer les choses, les systèmes d’exploitation ont eux aussi leur façon de

fonctionner. Développés par différentes compagnies à des périodes différentes, les systèmes

Page 33: Restructuration d applications Java Temps réel

JAVA Langage De L ’Avenir 4

31

d’exploitation n’ont pas eu la chance de bénéficier de la même technologie. On n’a qu’à

penser à DOS et à Windows 95. On ne peut pas faire des applications utilisant une interface

graphique pour être utilisées sous DOS. Il ne faut donc pas seulement un compilateur pour

chaque grande famille d’ordinateur, mais il faut en plus tenir compte des systèmes

d’exploitation !

C’est là qu’ intervient Java, un langage multi-plateforme. Java est aussi compilé. La

différence est que le compilateur Java ne crée pas de fichier exécutable (* .exe). À la place,

c’est du p-code qui est généré sous forme de fichiers classe (* .class). Le p-code, aussi appelé

bytecode, c’est comme si le code source était à moitié compilé. Le p-code n’est pas encore

lisible par tous les processeurs et par tous les systèmes d’exploitation. Il faut tout d’abord que

le p-code soit interprété. Interprété veut tout simplement dire qu’on termine de compiler juste

avant l’utilisation. Cette technique a pour avantage de rendre le code source multi-plateforme,

mais ralenti de beaucoup les performances de l’application. Par exemple, une application

développée en C++ va en moyenne 10 fois plus vite que si elle avait été écrite en Java. Donc

si vous attendez 2 secondes pour que l’application effectue une opération spécifique sous

C++, vous allez en attendre 20 secondes sous Java. Java est donc un bon langage pour créer

des applications qui ne requiert pas une très grande vitesse d’exécution.

I I - Java : Un langage or ienté objet:

Java, comme tous les langages de programmation qui permettent la création d’ interfaces

graphiques utilisateurs (Graphic User Interface ou GUI), n’est pas de type structuré mais bien

de type orienté objet. Mais quelle est la différence entre les deux? La programmation

structurée met l’accent sur les actions (les fonctions) tandis que la programmation orientée

objet se base sur les objets. Par exemple, si vous regardez le langage C, vous remarquerez

que, la plupart du temps, les noms de fonctions sont représentés par des verbes (Afficher,

Lire, Additionner, ...etc.). Dans la programmation orientée objet, on va plutôt définir chaque

objet avec toutes les actions et attributs qu’ il possède. Par exemple, on pourrait définir un

objet “voiture” ayant les actions avancer, reculer, accélérer, démarrer et s’arrêter pour n’en

nommer que quelques-uns. Les attributs de l’objet voiture pourrait être NbrePortes,

VitesseMaximale, NbreCheveauxVapeur,...etc. Vous voyez que l’approche est complètement

différente.

Tous les langages de programmation orienté objet fonctionnent sur le même principe

des objets. Lorsqu’on en connaît un, il devient très facile d’en apprendre d’autres. Java est

Page 34: Restructuration d applications Java Temps réel

JAVA Langage De L ’Avenir 4

32

totalement orienté objet, comparé au C++ dans lequel il est facile de retomber dans la

programmation structurée.

Note

En Java, comme dans tous les langages, il y a plusieurs façon de faire qui donne le

même résultat. Nous entendons par “ façon de faire” que le code source est différent mais que

l’exécution du programme est identique. Ce phénomène est d’autant plus vrai pour ce qui est

de la programmation d’ interfaces graphiques utilisateurs (GUI). En effet, on peut avoir deux

exécutions identiques mais avec des codes sources totalement différents. De plus, certains

fabricants de logiciels servant à écrire du code source en Java (comme Borland JBuilder et

Microsoft Visual J++) ont créés plusieurs nouvelles classes pouvant faciliter ou accélérer la

rédaction du code source.

I I I - Programme simple:

En Java, il est possible de faire deux types de programme: des applets et des

applications. Les applets sont destinées exclusivement aux pages web sur Internet tandis que

les applications sont semblables à des programmes développés en C, à savoir toutes les

applications autonomes, qu’elles soient développées avec une interface graphique ou non.

Le langage Java étant un langage orienté objet, tout le code doit se retrouver à l’ intérieur

de classes. Nous pouvons en avoir plusieurs, mais il se peut que vous en aillez qu’une seule.

Le nom de la classe doit absolument être identique au nom du fichier * .java contenant le code

source. Par exemple, le fichier App1.java doit obligatoirement contenir la classe App1. Cette

classe est appelée la classe principale du programme.

La classe principale doit avoir, dans le cas d’une application et non d’une applet, la

méthode “main” . Cette méthode est appelée automatiquement lors du démarrage de

l’application. Lorsque la méthode “main” est terminée, l’application est aussi terminée.

La seule différence est le mot “args” qui est une variable, donc qui peut s’écrire

presque n’ importe comment. Analysons chacun des mots qui composent la méthode

principale :

public : Signifie que la méthode est accessible à l’extérieur de la classe dans laquelle elle

se trouve. Cela permet à l’ interpréteur d’appeler la méthode “main” .

static: Indique que la méthode “main” s’applique à toute la classe.

void: Signifie que la méthode ne retourne rien.

main: Nom de la méthode. Doit demeurer inchangé.

Str ing args[]: Tableau contenant des chaînes de caractères. Ce sont les commandes

passées à l’application.

Page 35: Restructuration d applications Java Temps réel

JAVA Langage De L ’Avenir 4

33

Dans Java, nous n’avons pas à inclure le package de base à chaque fois que nous faisons

une application. En effet, le package “ java.lang” est inclus automatiquement. Ce package

contient toutes les classes de base d’une application. C’est entre autre le cas de la classe

“System”, qui contient elle-même “ in” et “out” (entrée et sortie). La partie “out” contient les

méthodes “print” et “println” , différentes seulement par le fait que la dernière ajoute un

changement de ligne après avoir afficher du texte. L’utilisation de ces deux méthodes est très

simple : il s’agit de mettre du texte entre guillemets dans les parenthèses et ce texte sera

affiché à l’écran. Ces méthodes sont l’équivalent de la fonction “printf” en C.

Classe

Structure de données qui comprend des attributs et des méthodes. Une classe est

comparable à une structure en C, avec quelques modifications.

Eléments importants à retenir :

• Les attributs déclarés dans une classe sont “private” par défaut.

• Il ne peut y avoir qu’une seule classe “public” dans un même fichier (* .java) et

cette classe doit avoir le même nom que le fichier. Les classes commencent

toujours par une lettre majuscule en Java.

Méthodes

Aussi appelées fonctions, fonctions membres ou procédures, elles jouent le même rôle

que les fonctions en C à la différence près qu’elles sont toujours définies à l’ intérieur d’une

classe.

Eléments importants à retenir :

• Les méthodes sont toujours définies à l’ intérieur d’une classe.

• Les méthodes peuvent être public, protected ou private.

• Les méthodes peuvent retourner des valeurs (int, double, …) ou non (void).

• Le nom d’une méthode ne peut pas contenir de caractères spéciaux (espace,

astérisque, etc.), exactement comme en C.

• Voir la “Surcharge” et la “Redéfinition” pour plus de détails.

• Les méthodes ont accès à tous les attributs de la classe sans avoir à les passer en

paramètre ou à les déclarer à l’ intérieur de celle-ci.

Attr ibuts

Un attribut, aussi appelé donnée, ce n’est ni plus, ni moins qu’une variable déclarée à

l’ intérieur d’une classe. Certains auteurs les appelleront aussi variables membres de la classe.

Page 36: Restructuration d applications Java Temps réel

JAVA Langage De L ’Avenir 4

34

Eléments importants à retenir :

• Un attribut peut être déclaré public, protected ou private. Par défaut, l’attribut est

private.

• Une instance d’une classe peut être un attribut d’une autre classe.

• Deux attributs ne peuvent pas avoir le même nom.

Instances

Dans la programmation orientée objet, les classes ne serviraient à rien si ce n’était pas

des instances. Une instance, c’est une variable qui a comme type une classe. Dans Java, toutes

les instances sont déclarées à l’ intérieur des classes. Elles deviennent donc des attributs. Pour

faire un parallèle avec le langage C, une instance pourrait être comparée avec une variable qui

a pour type une structure.

Toutefois, à la différence d’une variable, il faut appeler un constructeur de la classe

pour ensuite pouvoir l’utiliser. Les constructeurs sont traités dans la section du même nom.

Pour l’ instant, il faut seulement se rappeler que le constructeur n’est autre qu’une méthode

ayant le même nom que la classe et qu’ il est appelé à l’aide du mot réservé “new”.

Il y a aussi une deuxième façon de déclarer une instance, qui ressemble beaucoup à la

première. Il s’agit de faire la déclaration sur une première ligne et ensuite appeler le

constructeur sur une seconde.

PrismeRectangulaire

Profondeur

ModifierProfondeur Volume1 Volume2 AfficherVolume

Rectangle

Largeur Hauteur ModifierLargeur ModifierHauteur Périmètre Aire AfficherPerimetre AfficherAire Affichage

Ce symbole signifie que la classe du

dessous hérite de la classe au-dessus. Donc PrismeRectangulaire hérite de Rectangle.

Page 37: Restructuration d applications Java Temps réel

JAVA Langage De L ’Avenir 4

35

Véhicule à moteur

Moteur Réservoir d’essence Volant Cadrans Siège Roues

Accélérer Freiner Tourner

Voiture

Portes à pentures Carrosserie Ceintures Transmission Pneus Clignotant

Reculer

Train

Portes coulissantes Carrosserie Transmission Wagons

Reculer

Avion

Fuselage Ceintures Ailes Hublots App. de navigation Autonomie de vol

Décoller Atterrir Prendre de l’altitude

Moto

Roues avec rayons Transmission Pneus Clignotant

Rouler sur une roue

Avion à réaction

Pneus Cabine pressurisée Réacteurs

Voler à haute altitude

Hydravion

Flotteurs Hélice

Amerrir Flotter

Ultra-légers

Pneus Hélice

Avion de combat

Bombes Système de poursuite

Voler à l’envers

Transporteur

Télévisions Petite cuisine Réacteurs

Voler à haute altitude

Page 38: Restructuration d applications Java Temps réel

JAVA Langage De L ’Avenir 4

36

Avec une instance, on peut utiliser tout ce qui est déclaré “public” dans la définition de

la classe. Lorsqu’on dit “ tout ce qui est public” , on veut dire toutes les méthodes et tous les

attributs qui ne sont pas protected ou private.

Nous expliquerons en détail les différences entre les trois types dans la section portant sur les

3 principes de la programmation orientée objet. L’appel de ces attributs et de ces méthodes

déclarées “public” se fait par l’ intermédiaire d’un point situé entre l’ instance et l’attribut ou la

méthode.

Eléments importants à retenir :

• Une instance déclarée à l’ intérieur d’une classe devient un attribut de cette même

classe.

• À la différence de la déclaration de variables, la déclaration d’ instances requiert

l’appel d’un constructeur.

• Avec une instance, on peut utiliser tout ce qui est déclaré “public” dans la

définition de la classe.

Hér itage

L’héritage est extrêmement important dans la programmation orientée objet. Il permet

de faire une copie d’une classe et d’ y faire des modifications. On appelle “classe mère” ou en

anglais “super class” la classe sur laquelle la copie est faite. Vous vous en doutez sûrement, la

classe copie de la classe mère s’appelle “classe fille” ou “sub class” en anglais.

L’héritage permet de passer tous les attributs et toutes les méthodes de la classe mère à la

classe fille, bien que la classe fille n’a pas accès aux attributs et méthodes private de la mère.

Cela peut être difficile à comprendre, mais les attributs et méthodes private de la mère sont

bel et bien passés à la classe fille mais celle-ci n’ y a pas accès.

Eléments importants à retenir :

• Il est possible de faire plusieurs fois de l’héritage. Une classe fille peut, elle aussi,

avoir une ou des classes filles.

• Une classe mère peut avoir plusieurs classes filles.

• Il existe une grande quantité de classes déjà toutes faites et prêtes pour l’utilisation.

Ces classes, développées par Sun Micro-systems, vous sauverons beaucoup de

temps et bien des maux de tête.

Page 39: Restructuration d applications Java Temps réel

JAVA Langage De L ’Avenir 4

37

IV- Les trois pr incipes de la programmation or ientée objet:

Les trois principes de la programmation orientée objet, sont trois choses qu’on ne peut

normalement pas faire dans la programmation conventionnelle ou structurée. Il s’agit de

l’héritage, de l’encapsulation et du polymorphisme.

IV.I - L’Héritage:

Premièrement, lorsque l’on veut créer une interface graphique utilisateur (GUI), il est

extrêmement économique aux points de vu temps et argent d’utiliser l’héritage pour ne pas

avoir à réécrire du code qui existe déjà. Imaginez une seconde tout ce qu’ il faut spécifier pour

pouvoir créer une simple fenêtre. Ce serait énorme comme travail! Une application simple qui

prend une heure à développer prendrait plusieurs mois s’ il fallait tout refaire à chaque fois.

C’est pour cette raison que la programmation de fenêtres et de GUI en général ne peut être

accomplie que par des langages de programmation orientée objet.

De plus, l’héritage peut vous sauver d’écrire plusieurs fois la même chose dans

plusieurs classes. En effet, si vous avez plusieurs attributs et plusieurs méthodes communs à

vos classes, pourquoi ne pas faire une classe mère qui les contiendrait tous?

Dans notre exemple, nous ne voulons pas réécrire tous les attributs et toutes les

méthodes dans chacune des classes ou encore moins faire du “copier-coller” . En déclarant les

éléments des classes supérieures d’une façon public ou encore mieux, protected, on permet

aux classes inférieures d’en bénéficier.

Un autre avantage de l’héritage, c’est la correction des erreurs. Si vous regardez

l’exemple précédent, vous remarquerez sûrement qu’ il manque beaucoup d’attributs et de

méthodes. Toutefois, il est très facile d’en ajouter un autre. Par exemple, si l’on veut rajouter

un attribut à tous les véhicules, on a qu’à le déclarer public ou protected dans la classe

“Véhicule à moteur” et le tour est joué. De cette façon, on pourrait ajouter l’attribut

“Carburateur” à la classe “Véhicule à moteur” au lieu d’aller le placer dans chacune des 10

classes. On sauve du temps et de l’argent.

Mais la correction des erreurs ne s’arrête pas là. Il faut aussi être capable d’enlever ou

de modifier un attribut ou une méthode. Par exemple, on peut apercevoir, dans la classe

“Véhicule à moteur” , un attribut “Roues” . Toutefois, si nous voulons ajouter la classe fille

“Bateau” à la classe “Véhicule à moteur” , il y a un problème car les bateaux n’ont pas de

roues. Il en va de même pour l’hydravion. Mais, on pourrait choisir tout simplement d’ ignorer

l’attribut “Roues” dans les classes “Bateau” et “Hydravion” (faire comme s’ il n’existait pas).

On pourrait penser que cette pratique est de la mauvaise programmation, mais elle est parfois

nécessaire car il serait trop long de l’écrire dans toutes les classes. De plus, lorsqu’on fait du

Page 40: Restructuration d applications Java Temps réel

JAVA Langage De L ’Avenir 4

38

GUI, on hérite de classes déjà faites et on utilise normalement entre 5% et 10% des attributs et

méthodes héritées.

IV-2- Encapsulation:

Après avoir vu la différence entre les types public, protected et private, une question

nous brûle les lèvres : Pourquoi ne pas seulement déclarer des attributs et des méthodes de

type public? Il serait beaucoup plus facile de ne pas utiliser les types private et protected. La

raison à cela est l’encapsulation des données.

L’encapsulation des données est surtout utile lorsqu’on travaille en équipe ou

lorsqu’on fait un gros projet. Elle évite qu’un attribut ne prenne une mauvaise valeur pouvant

faire mal fonctionner le programme pendant l’exécution de celui-ci.

IV-3- Le polymorphisme:

Le troisième et dernier principe de la programmation orientée objet est peut-être le

plus difficile à appliquer. Il peut sembler simple au début mais il prend beaucoup de pratique

à assimiler.

Le polymorphisme vient des mots “poly” qui veut dire plusieurs et “morphe” qui

signifie forme. Dans la programmation orientée objet, on peut transformer les méthodes pour

qu’elles aient “plusieurs formes”. Mais avant de continuer, il devient impératif de décrire le

polymorphisme sous ses deux formes : La surcharge et la redéfinition.

Surcharge:

La surcharge, c’est lorsqu’on a deux ou plusieurs méthodes dans la même classe, qui

ont exactement le même nom mais leurs paramètres respectifs diffèrent en type et/ou en

nombre. Le terme anglais pour la surcharge est “overloading” .

On utilise surtout la surcharge lorsqu’on veut qu’une même méthode fasse plusieurs

choses différentes mais similaires, dépendament des paramètres qu’on y passe. Cette

technique s’avère particulièrement intéressante avec les constructeurs que nous allons voir un

peu plus loin.

Redéfinition:

La redéfinition, c’est lorsqu’on a deux méthodes, l’une dans la classe mère et l’autre

dans la classe fille, qui ont la même signature (même noms, même paramètres) mais que leur

contenu est différent. Le terme anglais pour redéfinition est “overriding” .

On utilise généralement la redéfinition quand la classe fille hérite des méthodes de la

classe mère mais qu’une de ces méthodes ne lui convient pas.

Page 41: Restructuration d applications Java Temps réel

JAVA Langage De L ’Avenir 4

39

V- Constructeur :

Un constructeur est un type particulier de méthode. La particularité de cette méthode

est qu’elle est appelée automatiquement à la création d’une instance de la classe. Il y a

plusieurs types de constructeurs, il y a le constructeur par défaut, le constructeur d’ instance et

le constructeur de copie (pour ne nommer que ceux-là). Lorsqu’ il vient le temps d’écrire un

constructeur, il faut se souvenir des quatre choses suivantes :

1. Le nom du constructeur doit être exactement le même que celui de la classe.

2. Le constructeur ne possède pas de type (void, int, ..etc.).

3. Le constructeur est toujours public.

4. Le constructeur ne retourne jamais rien (return).

Les constructeurs servent à initialiser les instances lors de leur déclaration. En effet, au lieu

d’avoir à chaque fois à donner des valeurs similaires à toutes les instances qu’on déclare, le

constructeur se charge de le faire à notre place. Le constructeur est appelé à l’aide de

l’opérateur “new” .

De plus, il est fréquent de voir un constructeur surchargé. Il est alors possible de créer de

nouvelles instances avec différents constructeurs.

V-1- Constructeur par défaut :

C’est le constructeur qui va être appelé si l’on ne passe pas de paramètres à l’ intérieur

des parenthèses. Il faut bien sûr qu’ il n’ y ait aucun argument de passé en paramètre au

moment de la définition du constructeur. Il ne peut pas y avoir plus d’un constructeur par

défaut.

V-2 Constructeur d’ instances :

C’est le nom donné aux constructeurs ayant un ou plusieurs arguments passés en

paramètre. Ils permettent de créer une instance avec une légère différence par rapport au

constructeur par défaut. Il peut y avoir plusieurs constructeurs d’ instances.

V-3- Constructeur de copie :

Un constructeur de copie, c’est un constructeur d’ instance où il n’ y a qu’un seul

argument passé en paramètre. Cet argument doit être une instance de la classe dans laquelle le

constructeur est défini.

Page 42: Restructuration d applications Java Temps réel

JAVA Langage De L ’Avenir 4

40

public Cheque(Cheque Copie)

Les constructeurs de copie, comme leur nom le laisse savoir, servant à faire une copie

d’une instance qui existe déjà. Cette copie n’a pas à être parfaite. Il peut y avoir certaines

modifications. Il peut être utile de rappeler qu’une méthode a accès à toutes les méthodes et

les attributs de la classe, même s’ il s’agit d’une instance de celle-ci. Par exemple, nous avons

déjà mentionné que les attributs déclarés “private” ne pouvait être utilisés à l’aide d’une

instance, mais nous pouvons tout de même le faire à l’ intérieur du constructeur de copie. La

raison pour laquelle c’est possible, c’est parce que le constructeur de copie est déclaré à

l’ intérieur de la même classe que l’ instance. Il en va de même pour toutes les méthodes.

Eléments importants à retenir :

• Un constructeur doit avoir le même nom que la classe.

• Il y a trois types de constructeur : par défaut, d’ instances et de copie.

• Un constructeur ne retourne jamais rien (return).

• Un constructeur n’a pas de type.

• Un constructeur doit être public.

• Les constructeurs sont appelés à l’aide de l’opérateur “new”

VI- Destructeur :

Les destructeurs sont des méthodes appelées automatiquement à la destruction d’une

instance de la classe. Dans Java, il n’y a pas de destructeur. La raison pour cela est que Java

possède un système de ramassage de déchets (garbage collection subsystem) qui se charge de

libérer la mémoire. Un tel système n’existe pas en C++, d’où l’utilité du destructeur.

Cependant, il existe une méthode, la méthode finalize(), qui est appelée lorsqu’une

instance est détruite.

VII - Les exceptions:

Le traitement des exceptions est très important dans Java. Mais avant de commencer à

expliquer comment utiliser les exceptions, il faut d’abord définir ce que c’est. Une exception,

c’est un problème qui se produit lors de l’exécution d’une application. Par exemple, une

division par zéro soulève une exception, ou encore, l’utilisation de l’ indice 10 d’un tableau de

Instance de la classe “Cheque” , classe dans

laquelle le constructeur est défini.

Page 43: Restructuration d applications Java Temps réel

JAVA Langage De L ’Avenir 4

41

10 éléments (de 0 à 9). En bref, le traitement des exceptions permet de réagir d’une façon

spécifique lorsqu’un problème survient.

VII -1- Le traitement des exceptions :

Dans Java, comme dans tous les langages, il est presque impossible de prévoir toutes les

erreurs. Toutefois, il est possible de réagir d’une façon spécifique lorsqu’une erreur se

produit. On pourrait, par exemple, vouloir afficher un message d’erreur convivial et ensuite

fermer l’application au lieu de tout faire planter.

VII -2- Gérer les exceptions une à une:

Maintenant, il peut être très utile de réagir différemment, en fonction du type d’erreur

rencontré. Par exemple, le message envoyé à l’usager ne sera pas le même pour une division

par zéro que pour un index hors limite dans un tableau. La convivialité de votre application

dépend de la façon que vous traitez les exceptions.

VII -3- Le try avec plusieurs catch

La meilleure façon de gérer les exceptions est bien souvent d’utiliser un try-catch,

avec plusieurs catch. En utilisant cette technique, vous serez en mesure de capter toutes les

exceptions possibles ayant un point en commun. Par exemple, toutes les erreurs arithmétiques,

que ce soit une division par zéro ou une extraction de la racine carrée d’un nombre négatif,

seront captées par le même catch.

Pour être en mesure d’utiliser la technique du try-catch de façon efficace, il faut bien

connaître les types d’exceptions. Les tableaux suivants vous aideront à mieux gérer les

exceptions.

Les exceptions suivantes ne sont pas vérifiées par le compilateur:

Exceptions Signification

ArithmeticException Erreurs arithmétiques, comme la division

par zéro.

ArrayIndexOutOfBoundsException L’ index d’un tableau est hors limites.

ArrayStoreException Assigner un élément d’un tableau à un type

incompatible.

ClassCastException Appel invalide.

IllegalArgumentException Argument illégal utilisé pour invoquer une

méthode.

IllegalMonitorStateException Opération illégale d’un moniteur, comme

Page 44: Restructuration d applications Java Temps réel

JAVA Langage De L ’Avenir 4

42

attendre après un “Thread unlocked” .

IllegalThreadStateException L’opération demandée n’est pas compatible

avec l’état du Thread.

IndexOutOfBoundsException Certains types d’ index sont hors limites.

NegativeArraySizeException Tableau créé avec une grandeur négative.

NullPointerException Utilisation invalide de la référence null.

NumberFormatException Conversion invalide d’une String vers un

format numérique.

SecurityException Violation de la sécurité.

� Les exceptions qui suivent sont vérifiées par le compilateur:

Exceptions Signification

ClassNotFoundException La classe est introuvable. CloneNotSupportedException Tentative de cloner un objet qui

n’ implémente pas l’ interface Cloneable. IllegalAccessException Accès à une classe est refusé. InstantiationException Tentative de créer un objet d’une classe

abstraite ou d’une interface. InterruptedException Un Thread a été interrompu par un autre

Thread. � Méthodes définies par Throwable: Méthodes Descr iption Throwable fillInStackTrace() Retourne un objet Throwable qui contient

la trace de la pile. Cet objet peut être redirigé.

String getMessage() Retourne la description d’une exception. void printStackTrace() Affiche la trace de la pile. void printStackTrace(PrintStream stream) Envoie la trace de la pile vers la stream

spécifiée. String toString() Retourne un objet String contenant la

description de l’exception.

Page 45: Restructuration d applications Java Temps réel

43

Modélisation Des Dépendances 5

43

Modèles de dépendances des programmes I -Introduction:

Les programmes sont représentés par un graphe orienté où les nœuds sont les entités du programme et les arcs représentent les types des dépendances existantes entre ces dernières. I I - Notion de dépendance:

Une relation de dépendance entre deux instructions d’un programme implique l’existence de contraintes entre leur ordre d’exécution. En compilation, on fait appel à ce concept afin d’étudier la possibilité de reformuler l’écriture du programme (ou une de ses parties), c’est à dire, changer la structure interne de ce programme sans altérer sa sémantique. C’est un concept fondamental dans l’analyse du comportement du programme et l’optimisation de son code (modification, alternance, suppression d’ instructions, … ).

La notion de dépendance définit un ordre d’exécution (total ou partiel) entre les instructions.

La relation de dépendance a été utilisée pour le parallélisme dans les programmes séquentiels, la compréhension de programme et l’ intégration de versions.

La relation d’ordre définie ainsi peut être explicitée par un organigramme ou un graphe représentants ainsi et respectivement la séquence d’opérations à exécuter et la relation de dépendance (positive ou négative), générant éventuellement un graphe partitionné, où chaque partie est un organigramme d’exécution d’un ensemble d’ instructions.

On doit signaler que la contrainte d’ordre n’est pas seulement la seule relation qui peut exister entre les relations, mais de plus, il y a un transfert d’ information entre les instructions, et ce qu’on appelle un flux de données, qui matérialise la dépendance de données entre les instructions, et encore l’existence d’ instructions qui confirment ou infirment l’exécution de d’autres instructions, matérialisant par conséquent le concept de la dépendance de contrôle. I I I - Types de dépendances:

Le parallélisme au sein d’un programme est limité par ses dépendances. Une dépendance entre deux instructions d’un programme provoque un conflit dans leur exécution concurrente.

On peut avoir trois types de dépendances: ressource, donnée et contrôle. Une dépendance de ressource, entre deux instructions, est une conséquence de la limite

du matériel disponible dans n’ importe quel système informatique physique. Ce type de dépendance se produit lorsque deux instructions différentes tentent simultanément d’utiliser la même ressource physique, tel les que deux opérations de multiplication entrant en compétition pour réquisitionner (occuper) un seul multiplicateur ou deux opérations de référence mémoire voulant accéder à une même cellule (port) mémoire.

Une dépendance de données existe dans le cas où deux instructions ne peuvent pas être exécutées simultanément à cause d’un partage de données, c’est à dire que ces deux instructions référencient la même location mémoire ou accèdent au même registre (bloc) physique. Il y a quatre formes de dépendances de données : dépendance de flux, anti-dépendance, dépendance de sortie et dépendance d’ itération.

Dans le cas où on a une dépendance de flux d’une instruction S1 à une instruction S2 (voir le fragment de programme ci-dessous), on constate que S2 a besoin de la valeur de A produite par S1avant qu’elle ne commence son exécution.

S1: A = B + C S2: D = A – E De ce fait, on dit que «S2 dépend par flux de S1» vu que S1 doit être exécutée avant S2,

car elle assigne une valeur à une variable A qui est utilisée par S2.

Page 46: Restructuration d applications Java Temps réel

44

Modélisation Des Dépendances 5

44

Deux instructions écrivant dans la même location (cellule) de stockage provoquent une dépendance de sortie. Autrement dit, une dépendance de sortie implique que deux instructions assignent des valeurs à une même variable, et entre ces deux instructions, il n’y a aucune utilisation de cette variable. Dans ce cas, la suppression de la première instruction n’altère pas le résultat final.

Soit le fragment de programme suivant : S1: X = Y + Z S2: C = X * 22 S3: X = A – B L’ instruction S1 doit s’exécuter avant S3 vu que l’ instruction intervenante S2 utilise le

résultat produit par S1, donc il y a une dépendance de flux de S1 à S2. Dans cet exemple, une anti-dépendance se produit entre S2 et S3 vu que S2 lit la valeur

de X qui sera écrasée par S3. Par conséquent, S2 doit s’exécuter avant S3. Autrement, S3 assigne une valeur à une variable qui a été utilisée par S2.

Les dépendances de flux sont les dépendances les plus fréquentes, dans lesquelles un résultat produit par une instruction, est utilisé par une autre.

Les anti-dépendances et les dépendances de sortie se produisent quand le programmeur ou le compilateur réutilisent les cellules de stockage afin de réduire les besoins en mémoire du programme.

On peut noter que la renominalisation de variables peut être utilisée pour éliminer ces deux types de dépendances. Par exemple, au lieu de réutiliser un seul tableau pour deux calculs indépendants dans de différents endroits du programme, le programmeur aurait pu allouer deux tableaux différents (séparés). Le tableau qu’on a rajouté va éliminer la dépendance de sortie et les anti-dépendances pour le premier tableau. Cela permet d’augmenter le degrés du parallélisme, mais ça vient à l’encontre du surcoût en espace mémoire pour le tableau additionnel.

En examinant les instructions de boucles (While, Repeat, …), chacune de ses instructions peut être exécutées plusieurs fois, ce qui peut engendrer des relations de dépendances entre les différentes itérations et c’est ce qu’on appelle les dépendances d’ itération. Soit le fragment de programme suivant :

S1: Do I = 2,n S2: a[I] = a[I] + c S3: b[I] = a[I - 1] * b[I] EndDo Dans cet exemple, il n’ y a pas de dépendance entre les instructions S2 et S3 au sein de

chaque itération, mais il y a une dépendance d’ itération entre les instructions S3 et S2 qui appartiennent respectivement à deux itérations successives.

En effet, quand I = k, l’ instruction S3 utilise la valeur de a[k-1] assignée par S2 durant l’ itération k – 1. De ce fait, on dit qu’ il y a une dépendance d’ itération si une variable est modifiée par une itération et utilisée par une autre.

Intuitivement, une dépendance de contrôle d’une instruction Si à une instruction Sj existe quand l’ instruction Sj doit être exécutée seulement si l’ instruction Si génère une certaine valeur. Ce type de dépendance se produit, par exemple, quand Si est une instruction conditionnelle et Sj ne sera exécutée que si la condition est satisfaite.

Les dépendances de contrôle peuvent limiter le parallélisme en s’attardant dans une boucle. Ferrant & al définissent formellement les dépendances de contrôle telles que: «les dépendances de contrôle sont un concept clé dans l’optimisation des programmes et le parallélisme. Une instruction w reçoit une dépendance de contrôle d’une instruction u si u est une condition qui affecte l’exécution de w».

Page 47: Restructuration d applications Java Temps réel

45

Modélisation Des Dépendances 5

45

Les tests symboliques de la dépendance de données peuvent déterminer s’ il existe des

dépendances ou non entre des instructions d’un programme qui accèdent à un tableau (variables indicées) avec des indices complexes. Par exemple, considérons la boucle suivante:

Do I = L,H M[a * I + b] = X[I] + Y[I] Z[I] = 2 * M[c * I + d] EndDo Les itérations de cette boucle peuvent être exécutées en parallèle en utilisant une

stratégie d’ordonnancement, s’ il n’y a pas des dépendances d’ itération croisées dû aux références dans le tableau M[]. Pour déterminer si une telle dépendance existe, l’analyseur symbolique de la dépendance de données doit résoudre l’équation de «Diophantine» aI1+b=cI2+d. Cette équation est sous la contrainte que: L <= I1 <= I2 <= H, où I1 et I2 sont deux valeurs spécifiques de l’ indice de la boucle, L et H sont les bornes inférieure et

Caractéristiques générales. Caractéristiques des programmes multiprocéduraux.

Programme

Extraction des dépendances

Dépendances de ressources

Dépendances de contrôle

Dépendances de données

Dépendances multiprocédurales

Dépendances d’ itération

Anti – dépendances Dépendances de flux

Dépendances de sor tie

Dépendances résumées

Dépendances d’appel

Fig. I I I -1: Schématisation des types de dépendances existantes au sein d’un programme

Page 48: Restructuration d applications Java Temps réel

46

Modélisation Des Dépendances 5

46

supérieure sur l’ indice de la boucle et a, b, c, et d sont des entiers. S’ il n’existe aucune solution alors il n’y a pas de dépendance entre les deux instructions dans cette boucle.

Des techniques pour résoudre ces équations ont été étendues pour analyser autres indices et qui sont plus complexes.

Dans le cas où le programme contient des appels de procédures (programme multiprocédural), on peut trouver deux autres formes de dépendances: dépendances d’appel et dépendances résumées. La première modélise l’ instruction d’appel et le passage de paramètres. La seconde représente l’ influence d’exécution des paramètres effectifs d’entée sur les paramètres effectifs de sortie, en faisant abstraction de la procédure. VI - Représentation des dépendances: Définition:

Un programme est dit monolitique s’ il ne contient pas de procédures, sinon il est dit multiprocédural.Pour un programme monolitique, les dépendances sont représentées par un graphe orienté appelé Graphe de Dépendance de Programme (GDP). Les nœuds de ce graphe sont les éléments de base du programme qui sont en général les instructions. Ces nœuds sont liés par des arcs représentant les dépendances extraites de ce programme. Un élément de base peut être une instruction d’affectation, d’écriture, d’alternance ou d’ itération. A chacun de ces éléments, on fait correspondre un nœud particulier. La racine du GDP est un nœud particulier appelé Entrée (ou Entry en anglais ) représentant l’entête du programme. Les arcs représentent les dépendances de données et de contrôle. L’extrémité initiale d’un arc de dépendance de contrôle est obligatoirement le nœud Entrée ou un nœud de contrôle. Les arcs issus du nœud Entrée sont toujours libellés à vrai, sachant que chaque arc est libellé soit par vrai ou faux. Pour un programme multiprocédural, les dépendances sont représentées par un Graphe de Dépendances de Système (GDS). Il est composé d’un ensemble de GDP reliés entre eux par des arcs. Chacun des GDP d’un GDS représente les dépendances entre les instructions d’une procédure donnée. Les arcs de connexion modélisent les dépendances d’appel et les dépendances résumées.

Une dépendance d’appel est représentée soit par un arc reliant un nœud d’appel à un nœud d’entrée (le nom de la procédure), soit par des arcs reliant des nœuds effectifs à des nœuds formels. Il y a un nœud effectif d’entée (de sortie) pour chaque paramètre formel d’entrée (de sortie). Les variables globales sont, en général, traitées comme étant des paramètres effectifs supplémentaires. Les dépendances résumées sont représentées par des arcs reliant les nœuds effectifs d’entrée à ceux de sortie.

Dans une approche proposée par Jackson et Rollins[Jackson 94], on représente, au sein de chaque GDP, les actions sur les variables par un nœud et les dépendances entre variables par les arcs. Les instructions d’appel sont modélisées par des arcs résumées.

Notez qu’un arc de dépendance de données d’un nœud v à un nœud u signifie que le comportement du système peut changer si l’ordre relatif des composants représentés par v et u est inversé. Cependant, un arc de dépendance de contrôle d’un nœud v à un nœud u signifie que durant l’exécution, en cas où le prédicat représenté par v est évalué et sa valeur relie le libellé de l’arc à u, donc la composante du programme représentée par u sera éventuellement exécutée et fournira au système une terminaison normale.

Une autre vision de nos arcs de dépendances de données partage ces derniers en deux types : les arcs de dépendances de flux et les arcs de dépendances def-ordre.

Un arc de dépendance de flux relie un nœud v, qui représente une affectation d’une variable x, au nœud u représentant l’ensemble des utilisations possibles de cette affectation.

Un arc def-ordre relie deux nœuds v et u qui représentent des affectations de la variable x et où ces deux affectations atteignent une utilisation commune et v précède lexicalement u.

Page 49: Restructuration d applications Java Temps réel

47

Modélisation Des Dépendances 5

47

Dans un GDS, les arcs résumés représentent une dépendance transitive dûe aux effets des appels de procédures. Une instruction d’appel est représentée en utilisant un nœud d’appel et quatre types de nœuds paramètres qui représentent le passage des paramètres.

Du point de vue appel, le passage de paramètres est représenté par les nœuds «Actual-in» et «Actual-out», ou tout court «A-in» et «A-out» respectivement, et qui sont un contrôle dépendant du nœud d’appel.

Dans la procédure appelée, le passage des paramètres est représenté par les nœuds «Formal-in» et «Formal-out», ou tout court «F-in» et «F-out» respectivement, et qui sont un contrôle qui dépend du nœud Entrée de la procédure.

Les nœuds «A-in» et «F-in» inclus pour tout paramètre et variable globale et qui peuvent être utilisés ou modifiés comme un résultat de l’appel.

Les nœuds «F-out» et «A-out» sont inclus pour tout paramètre et variable globale qui peuvent être modifiés comme un résultat de l’appel.

La difficulté majeure dans la troncature inter-procédurale est la prise en charge correcte du contexte d’appel de la procédure appelée.

Pour résoudre le problème du contexte d’appel, le GDS inclut les arcs résumés. Un arc résumé relie un nœud v «A-in» à un nœud u «A-out» s’ il y a une liaison dans le GDS de v à u et qui respecte le contexte d’appel en liant des retours aux appels.

Trois types d’arcs inter-procéduraux sont nécessaires: 1. Un arc d’appel reliant chaque nœud d’appel au nœud Entrée de la procédure

correspondante. 2. L’arc «Parameter-in» reliant chaque nœud «A-in» dans un endroit d’appel au nœud

«F-in» correspondant dans la procédure appelée. 3. L’arc «Parameter-out» reliant chaque nœud «F-out» au nœud «A-out»

correspondant dans chaque position d’appel dans le programme. Les variables globales sont généralement traitées comme des paramètres courants supplémentaires.

NB. Notre définition du GDS modélise un langage ayant les propriétés suivantes:

� Un système complet consiste en une seule procédure principale (main) et une collection de procédures auxiliaires.

� Les paramètres sont passés par valeur. � On n’admet pas des appels de la forme P(x,x) ou bien P(g) où g est une variable

globale, afin d’éviter les problèmes de conflits de copie-arrière et pour considérer les variables globales comme des paramètres additionnels pour chaque procédure.

V- Exemple d’extraction des dépendances d’un programme:

Soit le programme suivant: Procedure Main; Procedure A(x,y) Procedure Add(a,b) Procedure Increment(z) Sum:=0; Call Add(x,y); a:= a + b; Call Add(z,1); I:=1; Call Increment(y); return; return; While i < 11 do return; Call A(Sum,I); Od Output(Sum); End.

Page 50: Restructuration d applications Java Temps réel

48

Modélisation Des Dépendances 5

48

En voici le GDS correspondant : Clé des arcs: Contrôle Appel Résumé

a:=ain

Entrée main

Sum:=0 I :=1 While i < 11 Output (Sum)

Call A

xin:=Sum yin:=i Sum:=xout I :=yout

Entrée A

x:=xin y:=yin Call Add Call Inc xout :=x yout:=y

x:=aout bin:=y ain:=x zin:=y y:=zout

Entrée Inc

zout:=z Call Add

z:=zin

z:=aout bin:=1 ain:=z

Entrée Add

aout :=a

a:=a+b b:=bin

Page 51: Restructuration d applications Java Temps réel

49 C Concepts De l’Or ienté Objet 3

49

Concepts de l’approche objet:

I -Introduction:

L’approche objet est une méthodologie de programmation permettant la maîtrise de la

complexité des systèmes, ainsi que la possibilité et la souplesse dans la réutilisation des

composants d’un logiciel. C’est un moyen efficace dans la structuration de programme,

permettant ainsi la mise au point d’applications facilement testées, efficacement améliorées,

souplement réutilisées et simplement maintenues.

Elle est mise en œuvre afin de résoudre le problème de la séparation entre les structures

de données manipulées et les procédures définies là-dessus.

En définitive, l’approche objet est caractérisée par :

� La structuration de l’univers manipulé en terme d’entités.

� La modélisation du raisonnement humain.

� La conception et la maintenance de logiciels immenses.

I I - Notions et concepts de base:

I I -1-Objet:

L’objet représente l’entité de base dans la programmation orientée objet, regroupant

deux partie qui sont les données (partie statique de l’objet) et les procédures (appelées

méthodes, représentant la partie dynamique de l’objet ).

La communication avec l’objet se fait à travers une interface, masquant ainsi les détails

de son implémentation et organisation interne.

Un objet étant caractérisé par son comportement et non pas par sa structure, assurant

ainsi l’abstraction de données.

I I -2- Classe:

Une classe est la concrétisation d’une famille d’objets ayant même structure et

comportement. Elle regroupe un ensemble de données et procédures (et/ou fonctions).

Chaque classe possède une paire de composantes :

� Une première statique, les données, qui sont des champs nommés ayant une valeur

représentant l’état des objets pendant l’exécution du programme.

� Une deuxième dynamique, les procédures, appelés aussi méthodes, représentant le

comportement commun des objets d’une même classe. Elle définit l’ensemble des

manipulations possibles à produire sur les données.

Page 52: Restructuration d applications Java Temps réel

50 C Concepts De l’Or ienté Objet 3

50

Une classe permet de définir des instances d’objets qu’elle contient.

I I -3- Instanciation:

L’ instanciation consiste à définir un objet particulier en se référant à une classe donnée.

L’objet ainsi définit reçoit l’architecture que fournit la classe dont il est issu (champs de

données et méthodes). De ce fait, l’ instanciation et un moulage permettant la production

d’objets, avec autant d’exemplaires que nécessaires.

I I -4- Envoi de message:

L’envoi de message est le seul moyen permettant la communication entre les objets.

Tout message doit comporter :

� Le nom de l’objet destinataire.

� Le nom de la méthode à activer (Sélecteur).

� Les arguments des méthodes à appliquer.

Une fois le message est reçu, l’objet destinataire exécute la méthode désignée dans le

message, avec un éventuel traitement des erreurs qui peuvent survenir soit au niveau

transmission, ou bien concernant le passage des paramètres.

I I -5- Héritage:

Une propriété principale de l’approche objet est la possibilité d’étendre les propriétés

d’une classe et de construire des classes plus spécifiques à partir d’une ou de plusieurs autres

qui existent déjà.

L’héritage est une technique permettant la définition d’un nouveau type d’objet à partir

d’un type existant, auquel on adjoint de nouveaux champs de données et/ou de nouvelles

méthodes.

La conception d’un nouveau type d’objet (qui hérite ainsi des propriétés et des

aptitudes de l’ancien type ), peut alors s’appuyer sur des réalisations antérieurs que l’on

spécialise à son gré, c’est à dire qu’on définit des classes plus spécifiques à partir d’autres qui

sont générales qu’on appelle classes mères(ou classes parentes), en complétant les

connaissances de ces dernières.

Les connaissances les plus générales sont ainsi mises en commun dans des classes, qui

sont ensuite spécialisées par définition de sous-classes successives, de façon à aboutir à une

hiérarchie de classes liées par la relation d’héritage appelée graphe d’héritage, dans lequel

chaque sous-classe hérite des données et des méthodes de ses classes mères.

Page 53: Restructuration d applications Java Temps réel

51 C Concepts De l’Or ienté Objet 3

51

La génération de classes spécifiques peut se faire de deux manières:

� L’enrichissement: qui consiste à doter la sous-classe avec de nouvelles variables

et/ou nouvelles méthodes représentant les caractéristiques propres au sous-ensemble

d’objets ainsi décrits.

� La substitution: qui consiste à redéfinir une ou plusieurs méthodes héritées.

L’héritage peut être:

� Simple: une classe ne peut hériter que d’une seule autre classe. Par conséquent, la

relation d’héritage est représentée par une arborescence.

� Multiple: une classe peut hériter de plusieurs classes. Elle comprend alors l’union

des variables et des méthodes de toutes ses classes mères. La relation d’héritage se

bascule ainsi en un graphe orienté sans circuit.

Cette alternative permet la décomposition des systèmes et de les représenter avec un

minimum de symboles des structures complexes.

Cependant, l’héritage multiple pose de nombreux problèmes difficiles à résoudre,

surtout lorsqu’ il s’agit de l’héritage de propriétés homonymes.

Bien entendu, l’héritage facilite grandement la réutilisation de produits existants.

D’autre part, l’héritage s’avère très utile pour la structuration et le développement de logiciels,

car il s’agit d’une méthode efficace de partage de connaissances où il n’est plus nécessaire de

dupliquer le code pour une éventuelle réutilisation future, ce qui rend aisé la lisibilité et la

compréhensibilité des programmes.

I I -6-Polymorphisme:

Le polymorphisme définit la capacité, pour une entité, de prendre plusieurs formes, et

par conséquent, elle prend des valeurs de différents types durant l’exécution du programme où

elle est définie.

Ça revient à dire qu’un même identificateur peut désigner, en l’utilisant à plusieurs

reprises, une variable, une classe ou une méthode.

I I I - Caractér istiques pr incipales de l’approche objet:

La programmation orientée objet est basée sur les concepts suivants :

I I I -1- Abstraction des données:

Page 54: Restructuration d applications Java Temps réel

52 C Concepts De l’Or ienté Objet 3

52

Il n’est plus nécessaire de connaître l’ implantation physique et la représentation interne

d’un objet pour qu’on puisse communiquer avec ce dernier, en lui adressant un message.

C’est à l’objet de décider avec quel procédé il exécute l’opération demandée en fonction de

son implémentation physique.

Bien évidemment, l’accès à un objet se fait à travers une interface qui cache son

organisation interne assurant ainsi l’abstraction des données (manipulation loin de

l’organisation).

I I I -2- Encapsulation:

Le principe d’encapsulation consiste en l’abstraction de la définition des objets en vue

de leurs modifications.

Un objet étant un ensemble de données et de procédures qui les manipulent, qui sont

regroupées dans une seule entité.

L’ interface définie sur cet objet nous permet d’accéder à ses données mais en n’ayant

aucune information concernant son implémentation physique.

De ce fait, l’encapsulation facilite la production de programmes robustes, résistants aux

changements des représentations des objets, et elle représente un moyen de protection et de

maîtrise de la complexité des systèmes par leur décomposition en composants élémentaires.

I I I -3- Modularité:

L’héritage permet le partage du code entre différentes classes, sans avoir à le dupliquer,

assurant ainsi une modularité par différenciation permettant la description d’un nouvel objet,

en exprimant ce que le différencie de celui qu’ il spécialise, ce qui assure un minimum

d’ interaction avec les autres objets.

I I I -4- Réutilisation:

Une propriété importante de l’approche objet permet l’ introduction d’objets ou classes

dans une bibliothèque offrant à tout programmeur la possibilité de les utiliser afin de définir

des objets de même type, ou de construire des objets plus spécifiques par spécialisation ou

composition des objets existants, ou faire appel à l’héritage pour la fabrication de classes

spécifiques à partir de celles déjà fournies.

Page 55: Restructuration d applications Java Temps réel

Les Dépendances Or ientées Objets 6

46

Représentation des programmes orientés objets (les dépendances orientées objets): I -Introduction:

Les caractéristiques orientées objets, telles que les classes et les objets, l’héritage, le polymorphisme, la liaison dynamique et les portées, interviennent dans le développement d’une représentation efficace d’un programme orienté objet.

Une classe définit les attributs qu’une de ses instances va posséder. Les attributs d’une classe se composent de:

1. Instance de variables qui implémentent l’état de l’objet. 2. Méthodes qui implémentent les opérations sur l’état de l’objet. On a souvent conçu, implémenté et testé les classes sans connaître les environnements

d’appel. Par conséquent, une représentation graphique efficace, pour les logiciels orientés objets, doit se composer d’une représentation des classes qui peuvent être réutilisées dans la construction de d’autres classes et applications utilisant ces dernières.

Les classes dérivées sont définies à travers l’héritage, qui permet à la classe dérivée d’hériter des attributs à partir de leurs classes parentes, et étendre, restreindre, redéfinir ou de les remplacer en quelque sorte.

Le fait que l’héritage facilite la réutilisation de code, une représentation graphique efficace d’une classe dérivée doit permettre la réutilisation des informations d’analyse. La construction de la représentation d’une classe dérivée doit réutiliser les informations d’analyse calculées pour les classe de base, et ne détermine que les informations qui sont définies dans la classe dérivée.

Le polymorphisme est une caractéristique importante des langages orientés objets, qui permet à l’exécution (runtime) de choisir l’un des appels aux méthodes faisant partie de l’ensemble des destinations possibles.

Une représentation statique d’un choix dynamique exige que toutes les destinations possibles soient incluses, à moins que le type peut être déterminé statiquement.

Une représentation doit prendre en considération les dépendances des instances de variables entre les appels aux méthodes de l’objet par un programme d’appel, même si ces instances ne sont pas visibles à ce programme.

I I - Applications or ientées objets et leurs modèles de représentations:

Afin de pouvoir modéliser les caractéristiques orientées objets, on doit développer des GDS pour les applications orientées objets, sur lesquels un algorithme de troncature inter- procédurale [14,23] peut être appliqué. On construit ces GDS pour des classes uniques, groupes de classes interactives et des programmes orientés objets complets.

Pour chaque classe C dans le système, on construit un GDC (Graphe de Dépendances de la Classe), qu’on réutilise dans la construction des classes qui dérivent de C et celles qui l’ instancient.

Pour un Système Incomplet (SI ) se composant d’une seule classe ou un nombre de classes interactives, on construit un Graphe de Dépendance de Procédure (GDP), qui simule tous les appels possibles aux méthodes publiques dans la classe.

Pour un Système orienté objet Complet (SC), on construit un GDP à partir du programme principal dans le système.

L’approche adoptée dans la représentation s’ intéresse à l’efficacité dans la construction et le stockage pour réutilisation des composantes précédemment calculée dans une représentation.

Page 56: Restructuration d applications Java Temps réel

Les Dépendances Or ientées Objets 6

47

Un GDS [4] est une collection de GDP, un pour chaque procédure. Un GDP [10] représente une procédure comme un graphe, dans lequel les nœuds sont les instructions ou les expressions prédicatives. Les arcs de dépendances de données représentent un flux de données entre des instructions ou des expressions, et les arcs de dépendances de contrôle représentent des conditions de contrôle, sur lesquelles l’exécution d’une instruction ou une expression en dépend.

Chaque GDP contient un nœud Entrée qui représente l’entrée dans la procédure. Pour modéliser le passage des paramètres, un GDS associe, à chaque nœud d’entrée

d’une procédure, les nœuds «Formal-in» et «Formal-out». Un GDS comporte un nœud «Formal-in» pour chaque paramètre formel de la

procédure, et un nœud «Formal-out» pour chaque paramètre formel qui peut être modifié[17] par la procédure.

Un GDS associe, à chaque position d’appel dans la procédure, un nœud d’appel et un ensemble de nœuds «Actual-in» et «Actual-out».

Un GDS contient un nœud «Actual-in» pour chaque paramètre effectif à la position d’appel, et un nœud «Actual-out» pour chaque paramètre effectif qui peut être modifié par la procédure appelée.

A l’entrée de la procédure et aux positions des appels, les variables globales sont

traitées comme des paramètres. Par conséquent, il y a des nœuds «Actual-in»,«Actual-out», «Formal-in» et «Formal-out» pour ces variables globales.

Notons aussi que les GDS relient les GDP aux positions des appels. Un arc d’appel relie un nœud d’appel de la procédure au nœud Entrée du GDP de la

procédure appelée. Les arcs «Parameter-in» et «Parameter-out» représentent le passage des paramètres. Les

arcs «Parameter-in» relient «Actual-in» et «Formal-in», et les arcs «Parameter-out» relient les nœuds «Formal-out» et «Actual-out».

Pour faciliter le calcul d’une tranche interprocédurale qui considère le contexte d’appel, un GDS représente le flux des dépendances à travers des endroits d’appel.

Un flux transitif de dépendance se produit entre un nœud «Actual-in» et un nœud «Actual-out», si la valeur associée au nœud «Actual-in» affecte celle associée au nœud «Actual-out». Le flux transitif de dépendance peut être généré par des dépendances de données et/ou de contrôle. Un arc résumé modélise le flux transitif de dépendances à travers un appel de procédure. I I I -Les GDS des programmes or ientés objets: I I I -1-Graphe de Dépendances des Classes:

Cette section décrit la construction du GDC pour des classes singulières, des classes dérivées, et des classes en interaction. De plus, elle discutera la manière avec laquelle on représente le polymorphisme. I I I -1-1-Représentation des classes de base:

Pour faciliter l’analyse et la réutilisation, on représente chaque classe dans un système par un Graphe de Dépendances de la Classe (GDC).[25]

Un GDC capture les relations de dépendances de données et de contrôles qui peuvent être déterminées à propos d’une classe sans connaître les environnements d’appel.

Chaque méthode dans un GDC est représentée par un GDP. Chaque méthode a un nœud Entrée de la méthode représentant son entrée.

Un GDC contient aussi un nœud Entrée de la Classe qui est relié au nœud Entrée de la méthode, pour chaque méthode dans la classe par un arc membre de la classe.

Page 57: Restructuration d applications Java Temps réel

Les Dépendances Or ientées Objets 6

48

Les nœuds d’entrées et les arcs membres des classes nous permettent d’accéder rapidement aux informations des méthodes, quand une classe est combinée avec une autre classe ou système.

Notre construction du GDC étend chaque entrée de méthode par l’ajout de nœuds «Formal-in» et «Formal-out». On ajoute de nœuds «Formal-in» pour chaque paramètre formel dans la méthode, et les nœuds «Formal-out» pour chaque référence à un paramètre formel qui est modifié par la méthode. De plus, on ajoute les paramètres «Formal-in» et «Formal-out» pour les variables globales qui sont référencées dans la méthode.

Enfin, tant que les instances des variables d’une classe sont accessibles à toutes les méthodes dans la classe, on les traite comme globales aux méthodes dans la classe, et on ajoute des nœuds «Formal-in» et «Formal-out» pour toutes les instances des variables qui sont référencées dans la méthode.

L’exception dans cette représentation, pour les instances des variables, est que notre construction omet les nœuds «Formal-in» pour les instances des variables dans le constructeur de la classe, et les nœuds «Formal-out» pour les instances des variables dans le destructeur de la classe.

Vu que les méthodes dans une classe peuvent s’ interagir, un GDC doit inclure une représentation des effets d’appel de méthodes par le nœud d’appel. A chaque nœud d’appel, il y a des nœuds «Actual-in» et «Actual-out» à lier au nœuds «Formal-in» et «Formal-out» présents à l’entrée de la méthode appelée.

Un GDC doit représenter les effets des instructions de retours, qui signifient qu’une méthode retourne une valeur à son appelant. Dans un GDC, chaque instruction de retour est liée à son nœud d’appel correspondant en utilisant un arc «Parameter-out». De plus, pour tout paramètre «Formal-in» qui peut affecter la valeur de retour, les arcs résumés sont rajoutés entre les nœuds «Formal-in» et le nœud d’appel. Ces arcs résumés facilitent la troncature interprocédurale. I I I -1-2-Représentation des classes dérivées:

On construit un GDC pour une classe dérivée par construction d’une représentation pour chaque méthode définie par la classe dérivée, et réutilisation des représentations de toutes les méthodes qui sont héritées des classes de base.

On crée un nœud d’Entrée de Classe pour la classe dérivée, et on rajoute des arcs membres de classe, reliant ce nœud d’Entrée de classe au nœud d’Entrée de méthode de chaque méthode dans la définition de la classe dérivée. On crée aussi des arcs membres de classe pour relier le nœud d’Entrée de classe aux nœuds d’Entrée de méthode de n’ importe quelle des méthodes, définies dans la classe de base et qui sont héritées par la classe dérivée.

Les nœuds «Formal-in» pour une méthode, représentent les paramètres formels de la méthode, les instances de variables dans la classe dérivée ou les classes de base qui peuvent être référencées par un appel à cette méthode, et les variables globales qui peuvent être référencées par cette méthode.

De manière similaire, les nœuds «Formal-out» pour une méthode, représentent les paramètres formels de cette méthode, les instances des variables dans des classes de base ou dérivées, qui peuvent être modifiées par un appel à cette méthode, et les variables globales qui peuvent être modifiées par un appel à cette méthode. I I I -1-3-Représentation des classes en interaction:

Dans les logiciels orientés objets, une classe peut instancier une autre classe, soit à travers une déclaration, ou par utilisation d’un opérateur tel que new.

Quand une classe C1 instancie une classe C2, il y a un appel implicite au constructeur de C2. Pour représenter cet appel implicite au constructeur, notre construction du GDC rajoute un nœud d’appel dans C1 à la location de l’ instanciation.

Un arc d’appel relie ce nœud d’appel au constructeur de la méthode de C2.

Page 58: Restructuration d applications Java Temps réel

Les Dépendances Or ientées Objets 6

49

Notre construction du GDC rajoute aussi des nœuds « Actual-in » et « Actual-out » au nœud d’appel pour relier les nœuds «Formal-in» et «Formal-out» dans le constructeur de C2.

Quand il y a une position d’appel d’une méthode M1 de C1 à la méthode M2 appartenant à l’ interface publique de C2, notre construction rajoute un arc d’appel entre le nœud d’appel dans C1 et le nœud d’entrée de M2, sans oublier le rajout des arcs du paramétrage.

Le chaînage de ces deux GDC forme un nouveau GDC représentant un système partiel. I I I -1-4-Représentation du polymorphisme:

Un GDC doit représenter les appels polymorphiques de méthodes, qui se produisent quand un appel de méthode est lancé, et la destination de l’appel est inconnue au moment de la compilation.

Un GDC utilise un nœud Choix Polymorphique pour représenter le choix dynamique parmi les destinations possibles. Un nœud d’appel correspondant à un appel polymorphique possède un arc d’appel incidant à un nœud de choix polymorphique.

Un nœud de choix polymorphique a des arcs d’appel incidant aux sous-graphes représentant les appels pour chaque destination possible.

Le nœud de choix polymorphique représente la sélection dynamique d’une destination. Une analyse statique, à l’encontre, doit considérer toutes les possibilités. I I I -2-Systèmes Incomplets:

Les classes et ses bibliothèques sont souvent développées indépendamment des programmes d’application qui les utilisent.

Pour représenter ces systèmes incomplets pour analyse, on simule les environnements d’appels possibles en utilisant un frame.[12]

Un frame représente un pilote universel pour une classe, qui nous permet de simuler l’appel des méthodes publiques dans n’ importe quel ordre.

En premier lieu, un frame appelle le constructeur de la classe, et entre par la suite dans une boucle qui possède des appels à chaque méthode publique dans la classe. Pour chacune des itérations de cette boucle, le contrôle peut passer à n’ importe quelle méthode publique. A la fin de cette boucle, le frame appelle le destructeur de la classe.

Un frame est le programme main d’un GDS pour un système incomplet. Par conséquent, on l’utilise pour construire un GDP. L’appel au constructeur, la boucle du frame et l’appel au destructeur sont tous en dépendance de contrôle avec le nœud Entrée du frame. La boucle du frame est aussi en dépendance de contrôle avec elle même. Finalement, l’appel du frame est en dépendance de contrôle avec sa boucle.

L’appel du frame est remplacé par des appels aux méthodes publiques dans la classe, et les nœuds paramètres sont rajoutés aux endroits des appels.

Pour créer un GDP d’un frame d’une classe particulière, on remplace le nœud d’appel du frame par les nœuds d’appel pour chaque méthode publique dans la classe.

Notez que, vu que les variables gardent leurs valeurs entre les appels des méthodes, il peut y avoir des dépendances de données entre les endroits des appels, même si les variables ne sont pas visibles dans le programme d’appel. pour expliquer ces dépendances de données, notre construction rajoute des arcs de dépendances de données entre les nœuds « Actual-out » de chaque appel de méthode et les nœuds « Actual-in » correspondant à tout autre appel de méthode.

On doit signaler qu’on ne peut avoir un flux (propagation) de valeurs à travers le constructeur de la classe, à l’exception des paramètres formels, vu qu’ il n’existe aucune valeur des instances de variables précédemment utilisées. De même, on ne reçoit aucun flux

Page 59: Restructuration d applications Java Temps réel

Les Dépendances Or ientées Objets 6

50

de valeur à partir du destructeur, tant que les instances des variables ne sont pas disponibles pour longtemps. I I I -2-Systèmes Complets:

On construit un GDS pour un programme complet en connectant des appels, dans le GDS partiel, aux méthodes dans le GDC pour chaque classe.

Cette construction implique qu’on relie les nœuds d’appel aux nœuds d’entrées des méthodes, les nœuds «Actual-in» aux nœuds «Formal-in», et les nœuds «Formal-out» aux nœuds «Actual-out». Les arcs résumés des méthodes, d’une classe précédemment analysée, sont rajoutés entre les nœuds «Actual-in» et «Actual-out» aux endroits des appels.

Cette construction du GDS, pour un système orienté objet, maximise la réutilisation de portions des représentations précédemment construites.

L’ introduction de variables dans la portée du programme d’application, telle qu’une variable globale, n’affecte pas la représentation dans n’ importe quelle partie du GDC. N’ importe laquelle des variables globales, référencée ou modifiée par une classe, doit être déclarée extern dans la classe, donc cette information doit être incluse durant la construction du GDC de la classe. IV- Algor ithme de construction du GDS:

La procédure de construction du GDS reçoit en entrée le flux de contrôle pour chaque procédure ou méthode dans un programme, et fournit en sortie le GDS de ce denier. Cette procédure construit le GDP pour l’ensemble des méthodes dans chaque classe.

Pour calculer le GDP des méthodes d’une classe, la procédure de construction identifie en premier lieu les méthodes qui ont besoin de nouveaux GDP. Ensuite, pour chaque méthode M définie dans C, l’algorithme construit le GDP de M. Pour une méthode M définie dans une classe de base, si M appelle directement ou indirectement une méthode virtuelle redéfinie dans C, l’algorithme construit le GDP à partir de celui de M qui a été construit pour la classe de base. Si M n’appelle aucune méthode virtuelle redéfinie dans C, l’algorithme réutilise le GDP de M avec la classe de base.

Après construction du GDP pour chacune des méthodes, la procédure de construction appelle la procédure de connexion, avec des arcs de liaison, chaque site d’appel dans ces GDP avec l’entrée de la méthode appelée.

Page 60: Restructuration d applications Java Temps réel

Les Dépendances Or ientées Objets 6

51

Algor ithme ConstructGDS; Entrée: graphe du flux de contrôle du programme P; Sortie: GDS de P; Déclaration: Début ConstructGDS; 1. Pour chaque classe C 2. Identifier les méthodes qui ont besoin d’une nouvelle présentation; 3. Pour chaque méthode M déclarée dans C 4. Calculer les dépendances de contrôle de M; 5. Prétraitement de M avec l’analyse du flux de données; 6. Etendre les objets dans M; 7. Calculer les dépendances de données pour les objets; 8. Fin Pour; 9. Pour chaque méthode M dans les classes de base 10. Si M est marquée alors 11. Copier l’ancien GDP 12. Ajuster les sites d’appel; 13. Sinon 14. Réutiliser l’ancien GDP de M; 15. Fin Si;. 16. Fin Pour; 17. Fin Pour; 18. Connecter(); 19. Construct_Arcs_Résumés(); Fin ConstructGDS.

Page 61: Restructuration d applications Java Temps réel

Les Tranches – Concepts De Base 7

52

Les tranches – Concepts généraux- I -Introduction:

La troncature des programmes est une opération qu’on effectue sur les relations de dépendances et qui a plusieurs applications telles que le débogage, la compréhension de code, tests des programmes et l’analyse des métriques. Elle permet d’extraire des tranches dont le comportement est indiscernable du programme initial en respectant un critère de troncature composé d’un point p du programme et d’un sous-ensemble de variables V de ce programme. I I -Définition d’une tranche:

Les tranches sont des programmes exécutables qui sont construits par élimination (suppression) de zéro ou plusieurs instructions du programme initial.

Une tranche de programme, par rapport à un point p et une variable v, consiste en des instructions du programme et de ses prédicats qui peuvent affecter la valeur de v au point p. Son comportement est identique à celui du programme d’origine par rapport à un critère donné, c’est à dire qu’une tranche est un fragment du programme d’entrée, isolé par rapport à une instruction critique dans le programme.

La variable v et le point p définissent le critère de troncature noté C=<p,v>. En d’autres termes, une tranche de programme est un programme de taille réduite dont le comportement par rapport à un critère donné est identique à celui du programme source. I I I -Extraction des tranches de programmes – Procédés et Algor ithmes-:

Les algorithmes utilisés pour l’extraction des tranches se basent sur l’analyse du flux de données et de contrôle en déterminant ainsi les tranches inter et intra-procédurales.

Ottenstein et Ottenstein [ ] définissent un algorithme efficace utilisant une méthode de parcours de graphe sur GDP. Horwitz, Reps et Binkley utilisent aussi les graphes de dépendances et ils ont développé une représentation interprocédurale du programme qui est le GDS et un algorithme de parcours du graphe en deux passes exploitant ce GDS.

Notez que le type de parcours du GDS définit le type de la tranche, de ce fait, on a deux types de tranches:

1. Une tranche arrière [Weiser 84]: c’est une tranche composée de toutes les instructions et prédicats dont dépend le calcul de la valeur de v au point p.

2. Une tranche avant [Binkley95 – Jackson94 – Reps95]: c’est une tranche composée de toutes les instructions et prédicats qui peuvent dépendre de la valeur de v au point p. Autrement dit, la tranche avant est le dual de la tranche arrière.

D’après [Binkley93], une tranche interprocédurale d’un GDS par rapport à un nœud v

est calculée en utilisant deux passes sur le graphe. Les arcs résumés sont utilisés pour permettre de passer d’un nœud d’appel à un autre sans avoir à descendre vers la procédure appelée. Par conséquent, ceci n’a pas besoin de garder une trace explicite du contexte d’appel pour s’assurer que les liaisons d’une exécution légale se sont traversées.

Les deux passes opèrent sur le GDS, en traversant les arcs afin de trouver l’ensemble des instructions qui peuvent atteindre (affecter) un ensemble donné de nœuds, tout au long de certains types d’arcs.

Le parcours dans la première passe commence à partir de tout nœud v et va en marche arrière (depuis la cible jusqu’à la racine) à travers les arcs de flux, arcs de contrôle, arcs d’appel, arcs résumés et les arcs «Parameter-in» des paramètres d’entrée, mais non plus à travers les arcs «def-ordre» ou «Parameter-out» des paramètres de sortie.

Le parcours dans la deuxième passe commence à partir de tous les nœuds atteints dans la première passe et part en marche arrière à travers les arcs de flux, arcs de contrôle, arcs

Page 62: Restructuration d applications Java Temps réel

Les Tranches – Concepts De Base 7

53

résumés et les arcs «Parameter-out» des paramètres de sortie, mais non plus à travers les arcs «def-ordre» ou les arcs «Parameter-in» .

Le résultat d’une tranche interprocédurale se compose des ensembles de nœuds rencontrés (parcourus) durant les deux phases (c’est un sous-graphe du graphe de départ).

Pour la troncature intra-procédurale, la tranche d’un graphe de dépendances peut être utilisée pour produire un programme exécutable par restriction du système initial aux éléments dont les nœuds sont dans la tranche du graphe de dépendances.

Il est totalement faux de considérer le même raisonnement sur une tranche directement produite à partir d’un GDS vu qu’on peut trouver des instructions syntaxiquement illégales, parce qu’elles contiennent des paramètres incompatibles. Ça est dû au fait que deux instructions d’appel, représentant des appels d’une procédure, contiennent des sous-ensembles différents de paramètres de la procédure.

Il y a deux problèmes relatifs à l’ incompatibilité: 1. Deux endroits d’appel pour la même procédure peut inclure des nœuds «Actual-in»

différents. 2. Deux endroits d’appel pour la même procédure peut inclure des nœuds «Actual-out»

différents.

L’extraction de tranche (troncature) a grandement évolué depuis sa naissance dans Weiser[1984], et plusieurs nouveaux algorithmes destinés à résoudre ce problème ont vu le jours. Le plus connu est celui utilisant le concept des graphes de dépendances des programmes (GDP)[Ferrante et Ottenstein 1987, Horwitz et al 1990, Ottenstein et Ottenstein 1984].

Le GDP est une structure de données adéquate principalement pour la troncature, parce qu’ il intègre l’ensemble des flux de données et de contrôle en un seul graphe, et par conséquent, réduit la troncature de programme en un problème de parcours d’un graphe[Ottenstein et Ottenstein 1984].

Dans le contexte des application temps réel, on admet les hypothèses suivantes concernant la structure des programmes:

� Toute condition contient seulement une variable booléenne simple. � Les instructions de saut inconditionnel tel que Goto et break ne sont pas présentes

dans le code de la tâche. Algorithme de la troncature des programmes:

On va s’ intéresser à la troncature exécutable, arrière et statique des programmes, c’est à dire que:

� Chaque tranche est exécutable comme un programme propre. � Les tranches sont calculées selon des données statiques disponibles, données arrières

et les informations du flux de contrôle. Conceptuellement, une tranche arrière d’un programme P, par rapport à un point p et

une expression e, est composée des instructions de P et les prédicats de contrôle qui peuvent affecter la valeur de e au point p.

Le couple (p,e) est généralement appelé le critère de la troncature et la tranche associée est notée P/(p,e). L’ idée est que pour déterminer la valeur de e à p, on a besoin seulement d’exécuter la tranche P/(p,e).

L’algorithme d’extraction a besoin de considérer les trois types de dépendances de données, de flux, anti-dépendances et dépendances de sortie. Ça peut être effectué de manière directe par extension de la définition du GDP (ou GDS) pour avoir un GDPE (Graphe de Dépendances de Programme Etendu).

Page 63: Restructuration d applications Java Temps réel

Les Tranches – Concepts De Base 7

54

Les nœuds d’un GDPE représentent les instructions de la tâche, avec un nœud particulier Entrée, qui est la racine de la tâche.

Les arcs d’un GDPE sont de deux types: 1. N1 c N2 qui signifie une dépendance de contrôle entre N1 et N2, et on a:

� soit N1 est le nœud Entrée et N2 ne faisant pas de références dans une boucle ou condition. � ou bien N1 représente un prédicat de contrôle et N2 est immédiatement introduit dans une boucle ou une condition dont le prédicat est représenté par N1.

2. N1 d N2 dénotant soit une dépendance de flux, de sortie ou une anti-dépendance. De ce fait, un contrôle peut atteindre N2 après N1 à travers une liaison, sur laquelle il n’ y a aucune définition de variable v et : � N1 définit v et N2 l’utilise (dépendance de flux). � N2 définit v et N1 l’utilise (anti-dépendance). � N1 et N2 définissent v (dépendance de sortie).

On définit (p⇒*q) pour signifier que le nœud p peut atteindre le nœud q à travers zéro

ou plusieurs arcs de dépendances de contrôle et de données. Notez qu’on ne considère pas les dépendances d’ itération concernant les structures périodiques des tâches, vu qu’on ne passe pas entre deux instances de tâches successives.

Une tranche d’un programme P, en se référant à un point p de P et une expression e (c’est à dire P/(p,e)), qui peut être obtenue en parcourant le GDP de P.

Vu que p dénote un nœud du GDPE, l’association d’un nœud dans le GDPE à une seule ligne source simplifie énormément le processus d’ isolation d’une tranche d’un programme. Pour cela, le programme source subit un prétraitement afin que toutes les instructions d’affectation et les prédicats de contrôle se trouvent sur des lignes de texte séparées. Par conséquent, dans notre problème, le critère de troncature (p,e) n’a pas besoin d’ inclure l’expression e vu que e est complètement du côté droit dans p, ce qui revient à dire que le point du programme <p> seul peut servir comme un critère de troncature.

On peut étendre la définition d’une tranche de programme par un ensemble de critères de troncature C d’une manière générale et on la définit telle que : P/C=U<p>∈c P/<p>. Algorithme calculant la tranche P/<n> :

Etape1: calculer la tranche par un parcours arrière du GDPE tel que: P/<n>={ m/m⇒*n} .

Etape2: marquer tous les nœuds dans P/<n>. L’ensemble ainsi obtenu représente la tranche recherchée.

Un de nos objectifs essentiels est de fournir le critère de troncature le plus adéquat pour

l’algorithme de telle sorte que la tranche temporelle de la tâche couvre tous les comportements observables de la tâche en cours d’étude. IV- Considérations pratique:

La troncature des STR dépend des analyses imprécises et statiques des flux de données pour calculer les tranches de programme. En pratique, on suppose l’existence d’une relation de dépendance de données entre n’ importe quelles deux instructions, à moins qu’on puisse prouver statiquement qu’une n’a pas modifié des variables que d’autres accèdent pour les consulter.

Cela a un grand impact quand on est confronté aux appels de fonctions. Quand une fonction modifie les données des pointeurs, les analyseurs contemporains sont souvent forcés pour supposer que l’opération peut être sur n’ importe quelle variable globale dans le programme. Ceci va naturellement se tromper sur le côté conservatif et va supposer qu’un

Page 64: Restructuration d applications Java Temps réel

Les Tranches – Concepts De Base 7

55

appel de fonction provoque des relations de dépendances où ça n’existe pas. Au pire des cas, on va finir avec un code qui semble être intranchable, alors qu’on doit se ramener à la troncature.

Pour les dépendances de sortie et les anti-dépendances, notez qu’ ils sont introduites comme un résultat de la réutilisation de variables, et elles peuvent être éliminées par un prétraitement du code.

Par conséquent, chacun peut utiliser deux étapes de l’approche afin de s’adapter au constructions temporelles. Un analyseur de temps statique peut être utilisé pour une estimation initiale et grossière. Ensuite, après avoir compléter la troncature du programme, le résultat peut être vérifié avec une description plus sophistiquée qui exécute actuellement le programme.

L’amélioration des performances de telles temporisations est importante dans la structure des mémoires câches, où l’ordonnancement de code va toujours changer l’alignement des instructions.

Page 65: Restructuration d applications Java Temps réel

Les Tranches Or ientées Objets 8

56

Les tranches dans les Systèmes Orientés Objets: I -Introduction:

La troncature des programme a plusieurs applications telles que le déboggage, la compréhension de code, tests des programmes et analyses des métriques.

Weiser [20] définit une tranche en respectant un critère de troncature qui consiste en un point p et un sous-ensemble de variables V du programme. Ces tranches sont des programmes exécutables qui sont construits par suppression de zéro ou plusieurs instructions du programme original.

Son algorithme utilise l’analyse du flux de données et les graphes de flux de contrôle pour calculer les tranches inter et intra-procédurales.

Ottestein & Ottenstein [20]définissent un critère de troncature en se référant à un point p du programme et une variable v qui est définie ou utilisée au point p. Ils utilisent un algorithme de parcours de graphe sur le GDP pour calculer une tranche qui se compose de toutes les instructions et prédicats du programme qui peuvent affecter la valeur de v au point p.

Horwitz, Reps et Binkley [14] utilisent aussi les graphes de dépendances pour calculer les tranches. Ils ont développé la représentation interprocédurale du programme qui est le GDS et un algorithme de parcours du graphe en deux passes qui exploite ce GDS.

L’algorithme des deux phases calcule des tranches inter-procédurales plus précises parce qu’ il utilise les informations résumées aux endroits d’appels en considérant le contexte d’appel des procédures appelées. I I -Environnement de l’algor ithme et son application :

Pour dresser les caractéristiques orientées objets, on a développé des GDS pour les applications orientées objets sur lesquels un algorithme de troncature interprocédurale [14, 23] sera appliqué.

On doit noter que la technique adoptée permet le calcul de tranches pour des classes uniques (seules) ainsi que les tranches pour des systèmes complets.

Les GDS définis pour les programmes orientés objets sont adéquats pour l’application de l’algorithme d’atteinte du graphe de deux phases afin de calculer les tranches. Cet algorithme utilise un critère de troncature <p,x> dans lequel p est une instruction et x est une variable qui est définie ou utilisée au point p.

Les développeurs de logiciels orientés objets empêchent les utilisateurs d’une classe de manipuler de manière directe les instances des variables à l’ intérieur d’un objet (l’état de l’objet), en fournissant des méthodes comme une interface afin de situer et observer l’état de l’objet. Par conséquent, les systèmes orientés objets substituent plusieurs références de variables avec des appels de méthodes qui retournent simplement une valeur.

Pour nous permettre de tronquer sur les valeurs retournées par une méthode, on utilise un critère de troncature peu modifié. Notre critère de troncature <p,x> se compose d’une instruction et une variable ou un appel de méthode x.

Si x est une variable, elle doit être définie ou utilisée à p. Si x est un appel de méthode, cette dernière doit être appelée à p.

Tant que notre construction du GDS crée des arcs résumés, qui sont utilisés pour préserver le contexte de l’appel, on calcule les tranches qui satisfont notre critère sur nos GDS en utilisant l’algorithme des deux phases.

Durant la première phase de l’algorithme de troncature, les arcs résumés facilitent la troncature à travers les nœuds d’appel (de l’un à l’autre), qui ont des dépendances transitives sur des nœuds «Actual-in».

Page 66: Restructuration d applications Java Temps réel

Les Tranches Or ientées Objets 8

57

Durant la deuxième phase de l’algorithme, on descend dans les méthodes appelées (procédures) à travers les arcs «Parameter-out».

Vu qu’on calcule une tranche, comme si toutes les séquences possibles des appels aux méthodes publiques étaient possibles, le calcul peut inclure dans ses résultats plus d’ instructions par rapport à une même tranche prise à partir d’un programme d’application qui spécifie une séquence d’appels particulière de méthodes publiques.

Cependant, durant le développement, ce type de tranches peut être utile tant qu’elles indiquent les dépendances qui peuvent exister entre les instructions dans la classe, et peut aider dans la compréhension , le déboggage ou le test de la classe.

Notez bien que les notions de tranche avant et tranche arrière se conservent pour les applications orientées objets de même que pour une application classique simple. I I I - Extraction de tranche (Tranche Arr ière):

La première phase de l’algorithme de troncature interprocédurale traverse en marche arrière le long de tous les arcs du GDS à l’exception des arcs «Parameter-out» et marque les nœuds atteints.

La deuxième phase traverse en arrière, à partir de tous les nœuds marqués durant la première phase, le long de tous les arcs à l’exception de ceux d’appel et «Parameter-in», et marque les nœuds atteints.

La tranche est l’union des nœuds marqués durant les deux phases.

I I I - Troncature d’objet: Dans un programme orienté objet, quand un objet est instancié à partir d’une classe, les

membres de données et méthodes de la classe sont instanciés pour cet objet. Le fait qu’on utilise une seule représentation pour toutes les instances d’une méthode,

toutefois, l’ensemble des instructions dans une méthode identifié par un algorithme de troncature, tel que Horwitz & al[7], inclut les instructions dans des différentes instances de la méthode.

Pour l’étude des tâches, on doit s’accentuer sur un seul objet à la fois. Pour cela, on veut identifier l’ensemble des instructions dans les méthodes d’un objet particulier, qui peut affecter le critère de troncature. C’est la troncature d’objet.

L’extraction d’une tranche d’un objet O, par rapport à un critère (v,p), on doit en premier lieu avoir la tranche complète à partir du GDS par rapport à (v,p). Ensuite, on identifie les endroits d’appel (envoi de message), qui ont été marqués par l’algorithme de troncature. Les méthodes invoquées par ces sites d’appels sont les seules méthodes de O qui peuvent affecter (v,p). Par la suite, on identifie les instructions dans ces méthodes qui sont incluses dans la tranche vu l’ invocation des endroits d’appel sélectionnés. On appelle ces instructions la tranche de O.

Pour identifier les endroits d’appel et d’envoi de message, qui ont été marqués par l’algorithme de troncature, on examine les nœuds, le sous graphe de flux de l’objet O dans la méthode ou la procédure dans laquelle O est construit. Si O est passé comme un paramètre à une autre méthode ou procédure, on traverse l’arc de liaison à l’endroit d’appel , et on continue à examiner le sous graphe de flux de l’objet paramètre formel dans la méthode ou la procédure appelée. Le parcours se poursuit jusqu’à ce que tous les sites d’appel de l’objet soient examinés.

Une instruction S dans une méthode d’un objet peut affecter (v,p) de plusieurs manières. Premièrement, S peut affecter un paramètre «Actual-out» Aout dans un endroit d’appel (envoi de message) de l’objet O, qui appelle M, et Aout à son tour peut affecter (v,p). Ce cas se produit quand l’exécution de P doit se passer après le retour de l’appel. l’ensemble des Aout est l’ensemble des nœuds «Actual-out», qui sont marqués par les deux phases de l’algorithme

Page 67: Restructuration d applications Java Temps réel

Les Tranches Or ientées Objets 8

58

de troncature, lorsqu’on calcule la tranche pour le programme tout entier. Etant donné un Aout, S est une instruction qui peut atteindre Fout, le nœud « Formal-out » qui est contraint à Aout, à travers un chemin composé seulement de nœuds dans M. On identifie ce type d’ instruction en utilisant la marche arrière dans M, commençant par Fout.

En deuxième lieu, si p est aussi dans M, S peut affecter (v,p) à travers un chemin se composant des nœuds qui sont dans M seulement. On identifie ce type d’ instruction en utilisant la marche arrière dans M, commençant par p.

Troisièmement, S peut affecter (v,p) en affectant un paramètre «Actual-in» A in au site d’appel c dans M, dans le cas où A in peut atteindre p à travers des chemins qui ne traversent aucun arc «Parameter-out». Cela veut dire que p est exécutée avant le retour de l’appel c. Pour identifier ce type d’ instruction, on doit au départ marquer l’ensemble des A in. Ce marquage peut être fait à l’aide d’un parcours en arrière à partir de p, sans traverser aucun des arcs «Parameter-out». Le marquage peut aussi être accompli par le rajout d’une marque aux nœuds paramètres «Actual-in», à la fin de la première phase de l’algorithme de troncature. Dans ce cas, l’ensemble des A in va contenir, en plus de ses valeurs précédentes, les marques d’appel dans M. Après le marquage des A in, on identifie l’ensemble des S par un parcours arrière, en commençant par les nœuds paramètres «Actual-in» marqués.

Il est facile de voir que si une instruction dans une méthode d’un objet peut affecter (v,p), alors elle doit être marquée par l’un des trois cas. De ce fait, le processus ci-dessus peut être utilisé pour calculer la tranche de l’objet O.

Page 68: Restructuration d applications Java Temps réel

L ’ Instrumentation Des Programmes 9

59

Instrumentation des programmes–Méthodologies générales, application sur les systèmes orientés objets et implémentation: NB. Le compilateur du langage adopté doit être réalisé et l’ instrumentation est basée essentiellement su les résultats de ce compilateur. I -Définition:

L’ instrumentation consiste en la réécriture du programme source suivant une formalisation particulière.

Chaque ligne du programme instrumenté est définie par le couple <n°d’ instruction:,instruction>.

L’ instrumentation consiste à séparer les instructions du programme source et générer une autre écriture de ce programme dont chaque ligne de ce dernier correspond à une instruction simple.

L’ instrumentation étant une phase primordiale dans la compréhension du code source en facilitant la génération du graphe de dépendances. C’est une technique de séparation d’entités qui vont jouer le rôle de nœuds du GDS durant la phase de génération du graphe de dépendances. I I - Concepts de la mise en œuvre de l’ instrumentation:

On signale que dans le code instrumenté, on a: � Chaque ligne correspond à une instruction simple (instruction de calcul, appel de

procédure, d’affectation) ou un prédicat (boucle ou alternance). � Chaque ligne est étiquetée par un numéro de séquence initialisé à zéro. � Les délimiteurs d’ouverture des blocs d’ instructions sont considérés comme étant

des instructions vides et sont associées à leurs initiateurs. I I I - L ’ instrumentation d’un programme or ienté objet:

Le concept de l’ instrumentation se conserve pour les applications orientées objets. Malgré l’apparition de nouvelles constructions et formats d’ instruction (définition de classes, définition des méthodes et attributs, constructeur de classe, ..etc.), la manière d’extraction des entités et instructions élémentaires semble être inchangée. Cependant, on peut noter les points suivants:

� Chaque ligne du code instrumenté définit une instruction du programme d’origine écrite sous la forme d’un couple composé du numéro de l’ instruction et l’ instruction elle même.

� Une définition d’une classe est considérée comme étant une instruction, et donc fera partie du code instrumenté (on va lui faire correspondre une ligne dans le code instrumenté).

� Toute déclaration d’attributs, instruction de calcul, appel de méthode, constructeur de classe, ou autre à l’exception des instructions prédicatives, sont des instructions élémentaires qu’on va leur associer une ligne de code dans le code instrumenté.

� On ne fait aucun traitement particulier entre le corps d’une méthode et celui de la partie main de l’application en cours d’étude.

� Les instructions prédicatives (if, while, ..etc.) se traiteront d’une manière particulière. Le prédicat sera dans une seule ligne du code instrumenté vu qu’ il joueront le rôle de nœuds de contrôle dans le GDS. On appliquera par la suite les règles décrites ci-dessus sur la partie restante de l’ instruction en cours.

Page 69: Restructuration d applications Java Temps réel

L ’ Instrumentation Des Programmes 9

60

IV- Mise en œuvre du processus d’ instrumentation:

La réalisation d’un processus automatique de génération d’un programme instrumenté, à partir du code source, semble être une opération simple à implémenter. Elle est d’autant facile et sûre lorsqu’on introduit un programme correct (passé par la phase de compilation), afin de le décharger du rôle de vérification et correction des erreurs de programmation.

Le processus de génération du code instrumenté consiste en le parcours du programme d’entrée, et une fois il détecte un point virgule, accolade ouvrant, fermante, ou un prédicat, il génère la ligne du code instrumenté correspondante. Ce processus se poursuit jusqu’à arriver à la fin du programme traité.

Page 70: Restructuration d applications Java Temps réel

Restructuration Des Programmes Or ientés Objets (Java) 10

61

Restructuration des programmes Concepts de base – Application aux Programmes Orientés Objets: I -Introduction:

La restructuration de programmes est une méthodologie de transformation et modification de la structure interne de codes, tout en conservant leurs sémantiques. L’adoption de cette technique a grandement facilité la compréhension des programmes et la maintenance des logiciels, elle permet de plus d’avoir un code optimisé, améliorer l’ordonnançabilité, la décomposition, la conversion et la réutilisation de composantes de programmes. Elle est un moyen efficace pour l’étude comportementale des programmes.

Dans notre étude, cette technique sera appliquée aux programmes temps réels, où le facteur temps représente un paramètre essentiel pour l’analyse du comportement du système. L’évolution de tels systèmes peut importer des modifications sur les caractéristiques temps réels des tâches (échéances, temps d’exécution,…)[POS92], ou surcharger les ressources. De ce fait, la restructuration devient une nécessité devant le développement d'un programme d’une application temps réel qui tend à devenir peu structuré. De plus, la restructuration semble être le moyen adéquat et une option importante pour le contrôle des coûts de la maintenance des logiciels. Il existe d’autres raisons pour la restructuration telles que :

� Faciliter les tests. � Réduction potentielle de la complexité des programmes. � Etendre la durée de vie des programmes en maintenant une flexibilité à travers une

bonne structure. � Mise en place de standards pour les structures des programmes. � Préparer les programmes pour faire l’objet d’entrée à des outils (parallélisme,

test,..). � Préparer les programmes pour la conversion. � Préparer pour ajouter de nouvelles caractéristiques au logiciel. La restructuration est aussi appliquée en cours de développement des logiciels, surtout

en cas de non possession de méthodes de programmation rigoureuses, en ayant comme objectif l’amélioration des performances du logiciel. On en déduit que la restructuration n’est une fin d’autant qu’elle ne soit un moyen pour réaliser des objectifs fixés tels que :

� Rendre le code en cours d’étude plus facile à comprendre, sans altérer ses dépendances de données ou de contrôle.

� Formatage du code (restructuration textuelle). � Souplesse dans la détermination du flux de contrôle. Durant la phase de développement d’une application, on peut être amené à concevoir

des tâches non ordonnançables. Cela peut entraîner l’échec du système dans l’exécution à temps d’une tâche temps réel, causé par une violation d’échéance[STE97]. Pour palier à ce type de problème, les programmeurs procèdent manuellement, à d’ intenses activités de modifications, de déplacement de portions de codes, de prise de mesure et de restructuration. Un tel processus est lent, coûteux et non contrôlable[CHU95,GER97]. Il se pourrait que dans certains cas, que tout un système doit être reconçu. I I -Approche de restructuration:

Nous savons déjà que la restructuration est un moyen de changement de la structure interne d’un programme en gardant sa sémantique intacte.

En cas de l’application de ce concept pour améliorer l’ordonnançabilité, on obtient comme résultat, des échéances flexibles. Nous pouvons assurer la flexibilité en restructurant

Page 71: Restructuration d applications Java Temps réel

Restructuration Des Programmes Or ientés Objets (Java) 10

62

une tâche afin d’avoir deux fragments. Le premier est un fragment temps contraint (noté FT), qui doit satisfaire son échéance. Le second est un fragment non temps contraint (noté FnT), qui correspond à un calcul interne. Ce dernier fragment peut tolérer un certain retard. Ensuite, les fragments seront séquentiellement recomposés, pour constituer un nouveau programme de la tâche en question, qui est sémantiquement équivalent au programme initial.

La figure X-1 représente le comportement d’exécution d’une tâche périodique non restructurée. Les sections hachurées représentent les composants temps contraint du programme de la tâche. A la (K+1)ième période, l’exécution de cette tâche dépasse son échéance et devient par conséquent, non ordonnançable. Toutefois dans la figure X-2, les actions temps contraint s’effectuent à l’ intérieur de la fenêtre de temps prescrite, l’exécution de la tâche entière est acceptable, sans avoir à provoquer d’erreurs fatales.

FT FnT

I I I - Processus de restructuration:

Nous savons déjà que la restructuration d’une tâche temps réel consiste à reformuler son écriture, en extrayant son FT et FnT.

Cependant, le processus d’extraction des fragments doit répondre au critère disant que, dans le cas où une instruction de contrôle est incluse dans le premier fragment, et qui contrôle un ensemble non vide d’ instructions se trouvant dans le deuxième, alors on doit inclure ces instructions dans le premier, afin de préserver la sémantique du programme initial. Il est à

(K)ième (K+1)ième (K+2)ième

Fig. X-1:Exécution d’une tâche périodique non restructurée

(K)ième (K+1)ième (K+2)ième

Fig. X-2:Exécution d’une tâche périodique après restructuration

temporel Non temporel

Page 72: Restructuration d applications Java Temps réel

Restructuration Des Programmes Or ientés Objets (Java) 10

63

noter que la décomposition du programme de la tâche se fait d’une manière récursive, comme montré dans la figure X-3.

En voici en détail le processus de restructuration avec adaptation pour les application

orientées objets: Phase1: Elle consiste à générer le GDS entier du système en cours d’étude. Il va servir pour

l’étape suivante, et en appliquant l’algorithme de troncature, à extraire les tranches et par conséquent, l’obtention des fragments recherchés.

Phase2: Ayant comme objectif le calcul du premier fragment (temporel),et en se servant du

résultat de la première phase, elle se déroulera comme suit sur la partie main de notre programme:

� On efface dans le programme toutes les lignes (instructions) correspondantes aux nœuds non marqués. On obtient par conséquent l’ensemble des instructions temporelles.

� En cas d’une instruction d’appel à une méthode, on effectue sur le corps de cette méthode le même traitement décrit dans le premier point. Cela nous permettra d’obtenir deux sous méthodes, SM1qui représente la partie temporelle de la méthode M appelée, et sa partie restante forme la deuxième sous méthode SM2.

� Si SM1 n’est pas vide, on remplace chaque appel de M avec un appel de SM1. � Le résultat ainsi obtenu, constitue le fragment temporel noté FT. Phase 3 : Elle a pour rôle le calcul du deuxième fragment (non temporel), en appliquant les étapes

suivantes : � A partir du programme (forme instrumentée), on efface les lignes qui correspondent

aux nœuds marqués, sauf les instructions de contrôle (if, while,..) et les appels aux méthodes.

� On efface les lignes des instructions de contrôle ayant comme cible des ensembles vides d’ instructions.

Programme

Fragment I-1

Fragment I-2

Fragment II

Fig. X-3:Fragmentation de programme

Page 73: Restructuration d applications Java Temps réel

Restructuration Des Programmes Or ientés Objets (Java) 10

64

� Si le bloc de SM2 est vide, on efface les lignes d’appel de méthodes correspondantes aux nœuds marqués.

� On effectue les trois étapes précédentes à la méthode M afin d’obtenir la sous procédure SM2.

� Dans le programme principal, si le corps de SM2 n’est pas vide, on remplace tout appel de M marqué par un appel un appel de SM2, sinon on efface tout appel de M marqué.

� De même, si le corps de SM2 n’est pas vide, on remplace tout appel de M non marqué par un appel de SM1 suivi d’un appel de SM2, dans le but d’avoir seulement deux nouvelles déclarations obtenues à partir de M (SM1 et SM2), au lieu de trois déclarations (M, SM1 et SM2).

� Le résultat ainsi obtenu, constitue le fragment non temporel FnT. Remarques:

On peut résumer notre objectif dans l’utilisation de la technique de restructuration, par la possibilité de générer deux partie de code complémentaires et indépendantes, dont l’une dépend du facteur temps, et son exécution passera comme prioritaire devant la partie non temporelle, qui peut s’exécuter même en dehors de son échéance sans la moindre crainte.

Deux questions peuvent se poser : 1. Est ce qu’on est toujours contraint par la génération de deux et deux fragments

seulement ? 2. A quel point on est sûr d’avoir des fragments et qui sont totalement indépendants? On peut répondre disant que tout dépend de la complexité du système en cours, la

manière avec laquelle, il a été conçu et développé et la nature de l’application cible. De ce fait, on peut obtenir une séquence de fragments, dont le facteur d’ indépendance intervient pour la détermination de leurs nombres, c’est à dire que le nombre de fragment diminue jusqu’à atteindre la valeur deux, tant que le degré d’ indépendance entre les instructions temporelles et le calcul interne est important.

Page 74: Restructuration d applications Java Temps réel

Conception Du Système De Restructuration Des Programmes Or ientés Objets (Java) 11

65

Par tie I : Structure du Système de Restructuration des Programmes Orientés Objets Temps Réel:

Le système se compose des modules suivants: 1. Un compilateur:permettant:

� La détection des erreurs. � La réalisation de l’ instrumentation. � L’extraction des dépendances entre les différentes instructions. Ce module est aussi dit Analyseur.

2. Un générateur: il a comme tâche de générer le GDS du programme en entrée à partir de données fournies par le compilateur.

3. Un extracteur: il permet l’extraction de tranches du programme à partir de son GDS. 4. Un reconstructeur: il permet la génération du nouveau code du programme en entée de

telle sorte que ce programme soit restructuré.

Cette représentation architecturale du système de restructuration est universelle. Dans ce projet, ce processus sera appliqué sur les programmes temporels orientés objets développés avec le langage Java.

entrée

Sor tie

non

oui Programme

en entée

Compilateur : A.Léxicale

A.Syntaxique A.Sémantique

Erreurs de programmation

Instrumentation du

Programme source

Extraction des dépendances

Générateur : Génération du GDS

Extracteur : Extraction des

tranches

Fragment temporel

Fragment non temporel

Reconstructeur : Réorganisation des fragments extraits

Programme restructuré

Fig IX-1 : Processus de restructuration

Page 75: Restructuration d applications Java Temps réel

Conception Du Système De Restructuration Des Programmes Or ientés Objets (Java) 11

66

Ce module est basé sur les résultats offerts par l’extracteur. Ce dernier permet l’extraction du fragment temporel et du fragment non temporel du programme source. De ce fait, le reconstructeur va tenter de placer le fragment non temporel après celui du temporel. Par conséquent, le code produit représente un programme restructuré qui permet de respecter les échéances des tâches et assurant ainsi une exécution correcte et sûre. On peut schématiser le fonctionnement de ce système ainsi: Par tie I I :Approche De Restructuration

Modèle Basé Tranches pour la Restructuration d’Applications Temps Réel Objets I - Introduction:

Le monde du temps réel s’est élargi considérablement ces dernières années, ce qui a permis par conséquent d’améliorer les méthodes d’ ingénierie. Plus particulièrement, les méthodes orientées objets ont été étendues et couplées avec les propriétés temps réel, en fournissant des mécanismes au modèle d’activité temporel[Ishik92][Kim97].

On va considérer le domaine des applications temps réel, où les tâches sont accomplies régulièrement afin de contrôler des processus physiques ou un fonctionnement de moniteur. Il est extrêmement important de rencontrer des contraintes de temps dans de tels systèmes. Pour satisfaire leurs échéances, les tâches doivent être ordonnancées d’une manière appropriée. Les algorithmes d’ordonnancement des tâches dans les systèmes temps réel [Liu73][Klein94] permettent de s’assurer que toutes les tâches peuvent être accomplies au bout de leurs échéances de telle sorte qu’aucune d’elles ne dépasse son temps d’exécution dans le plus pire des cas. Une tâche qui dépasse son temps prévu, peut mener à la perte de l’échéance et l’échec de tout le système.

Notons qu’une violation d’une échéance rend les tâches non ordonnançables. Dans ce cas, on fait appel à des techniques manuelles et de force brute pour remettre les tâches dans une situation d’ordonnaçabilité. Les développeurs accomplissent des opérations intensives et manuelles telles que l’ instrumentation, prise de mesure, déplacement de fragments de programmes et éventuellement une reconception du système. Malgré ce que fournissent les caractéristiques du modèle orienté objet, telles que l’héritage et le polymorphisme, en terme de réutilisabilité et flexibilité, elles rendent le système plus difficile pour l’étude et un processus pénible et coûteux[Wilde92]. Les développeurs doivent extraire et comprendre l’ interdépendance du comportement temporel d’objet, dans le but d’analyser et réarranger son code interne. Dans plusieurs applications, les objets sont rassemblés dans des groupes pour donner le service du temps réel afin de répondre à quelques buts. Avec ce groupe, les objets forment les relations Client-Serveur. De plus, le nombre relativement important et la petite taille des méthodes dans des programmes orientés objets typiques augmentent le nombre de ces relations[Bihari92][Wilde92].

Dans la perspective de l’ordonnanceur rate-monotonic, Gerber et Hong[Gerber97] ont montré qu’ ils peuvent améliorer l’ordonnançabilité en divisant une tâche de programme en deux fragments. Le premier dépend d’un événement observable, et le deuxième concerne le calcul interne, qui peut être retardé. Cependant, la présente approche traite seulement les programmes monolitiques et procéduraux simples, indépendamment des contraintes de synchronisation introduites en augmentant le nombre de tâches.

Afin d’achever l’ordonnançabilité, on propose une approche semi-automatique qui est l’extension de solutions précédentes et qui est adaptée au modèle temps réel objet. D’une

Page 76: Restructuration d applications Java Temps réel

Conception Du Système De Restructuration Des Programmes Or ientés Objets (Java) 11

67

manière spécifique, quand on trouve un ensemble de tâches surchargé et non ordonnançable, un analyseur d’ordonnancement choisit les tâches appropriées pour les restructurer. On met en œuvre le module de restructuration en faisant appel au concept de l’analyse de dépendance du système orienté objet.

Par conséquent, notre approche de restructuration est basée sur deux concepts :les tranches de programme et la technique d’ordonnancement à priorité fixe. Les tranches de programme, définies en premier lieu par Weiser[Weiser84], sont basées sur l’analyse du flux de données statique sur le graphe de flux du programme. C’est une technique d’ isolation des Threads de calcul dans les programmes. Une tranche de programme consiste en les parties du programme qui affectent potentiellement les valeurs calculées par rapport à quelques points d’ intérêt. Un point d’ intérêt de tranche est généralement spécifié par une position dans le programme avec un sous ensemble de variables du programme. Par exemple, on peut isoler une tranche par rapport à une instruction critique ou une méthode dans un programme, une instruction qui émet une commande à un actionneur ou une instruction d’une alarme dans une tâche de contrôle. Les tranches statiques d’un programme ont été appliquées avec succès dans les outils de programmation pour les langages non orientés objets tels que Pascal[Horwitz90] [Ben97], pour le déboggage, le test, ou la maintenance des logiciels. Mais avec quelques extensions, elles sont toujours efficaces dans le domaine de l’orienté objet[Larsen96][Lang97][Hang98].

En utilisant le concept des tranches de programme, notre méthode de restructuration permet d’améliorer l’ordonnançabilité d’un ensemble de tâches de deux façons. D’abord, on respecte toujours les différentes dépendances dans le code d’une tâche non ordonnançable, on s’assure que les instructions qui affectent l’échéance (fragment temporel) soient exécutées en premier lieu. Le fragment de code qui correspond au calcul interne (fragment non temporel) peut être différé. De plus, elle permet la décomposition d’une ou plusieurs tâches en sous tâches, de telle sorte qu’on puisse utiliser des méthodes d’ordonnancement à priorité fixe généralisées[Härbour94], qui peuvent augmenter l’ordonnançabilité d’un ensemble de tâches, mieux qu’appliquer l’algorithme rate-monotonic. En restructurant une tâche choisie parmi l’ensemble de tâches d’origine, on peut augmenter l’ordonnançabilité totale.

On a appliqué notre solution sur les applications temps réel Java, vu qu’ il est actuellement le langage le plus utilisé et qui est purement objet, ressemblant au langage populaire C++, mais plus simple. En effet, en combinant les conventions spéciales du temps réel de la machine virtuelle de Java avec les facilités de ce dernier, Java autant qu’un langage objet pur, permet le traitement d’activités temps réel (ramasse miette, multithread, protection, simplicité et portabilité)[Hamilton96]. I I - Modèle Temps Réel Objet:

Le modèle de calcul uniforme du paradigme orienté objet permet d’avoir une bonne représentation des entités du temps réel, du point de vu physique ou logique[Bihari92]. Par exemple, dans un logiciel de contrôle d’un manipulateur, les objets du logiciel représentent le manipulateur soit même, les actionneurs et les entités conceptuelles du planificateur. Les contraintes de temps[Das85] peuvent être représentées dans le modèle du temps réel objet, qui offre des constructions au développeur permettant de spécifier les implémentations d’objets spécifiques et des messages d’efficience et de prévision acceptables[Bihari92][Ish92]. I I -1- Approches d’ordonnancement:

Le problème le plus fondamental et classique dans les systèmes temps réel est l’ordonnancement d’un ensemble de tâches périodiques, qui s’exécutent sur un seul CPU[Gerber97]. Ce modèle peut être décrit par : (1)une tâche est un programme ayant un seul Thread (bloc temporel), qui s’exécute indéfiniment avec une périodicité positive, où ce type

Page 77: Restructuration d applications Java Temps réel

Conception Du Système De Restructuration Des Programmes Or ientés Objets (Java) 11

68

de programme est la construction de bloc commune trouvée dans les applications temps réel, et (2) un ensemble de tâches est une collection de tâches périodiques.

Une tâche périodique, notée t, est une séquence infinie d’ instances de tâches demandée avec un taux fixe dans un environnement temps réel. Considérons un ensemble de n tâches périodiques t1, t2, …, tn. Chaque tâche est caractérisée par trois composantes (Ci, Ti, Di), 1<=i<=n. Ci est le temps d’exécution dans le plus pire des cas de la tâche ti (chacune des instances de tâche a le même taux de calcul). Ti est la période de la tâche. Di est l’échéance de la tâche ti, par lequel elle doit être complétée. Un ordonnanceur temps réel[Klein94] décide quand est ce que chaque tâche requisitionne le processeur. Un traitement théorique de l’ordonnancement avec priorité fixe, apparue en 1973, quand Liu et Layland[Liu73] ont introduit l’algorithme rate-monotonic pour des tâches périodiques et indépendantes.

Dans [Härbour94], Harbour et al, a considéré une classe de problèmes plus générale, et

fournit une structure pour l’analyse de l’ordonnançabilité dans le contexte de l’algorithme d’ordonnancement avec priorité fixe d’un ensemble de tâches composées de sous tâches, qui ont des niveaux de priorité différents. Comparé avec la technique rate-monotonic, il a été démontré que cette méthode offre une meilleure ordonnançabilité. I I -2- Application temps réel en Java:

Evidemment, les développeurs temps réel ont besoin de langages orientés objets simples supportant le développement rapide, la portabilité, la robustesse, la reconfiguration rapide, la sécurité et une haute performance. Java, comme étant un système orienté objet pur, possède des caractéristiques avancées telles qu’une efficace fonction de ramasse miettes, le multithreads et l’absence du type pointeur afin d’améliorer la sécurité[Hamilton96].

Quelques problèmes particuliers du domaine des systèmes temps réel embarqués sont adressés par la conception d’un environnement de programmation temps réel Java. Les implémentations temps réel Java sont devenues utiles pour la programmation des applications temps réel www distribuées (exemple : gestion de stock et commerce, animation interactive, les jeux, et la téléconférence), et pour l’ implémentation d’applications temps réel embarquées plus traditionnelles (exemple : dans les systèmes de navigation, interface de traitement vocal et graphique, contrôle du trafic aérien, environnement de la réalité virtuelle et les systèmes de défense à missile). I I I - Fragmentation de programmes or ientés objets:

Dans le but d’avoir des échéances de tâches flexibles, vu que l’ordonnançabilité est améliorée tant que la flexibilité des échéances augmente, on effectue une transformation sur le programme de la tâche, de telle sorte que cette dernière puisse aller au delà de son échéance. On peut procurer cette avantage en ramenant le fragment non temporel à s’exécuter après le fragment temporel. Ensuite, les fragments sont recomposés séquentiellement, afin de constituer un nouveau programme de la tâche en question, qui est sémantiquement équivalent à celui d’origine.

La figure 1.a représente le comportement d’exécution d’une tâche périodique. Les parties ombrées dans les figures 1.a et 1.b représentent les composants temporels du programme de la tâche. Dans la (k+1)ième période, l’exécution de cette tâche va au delà de son échéance et devient, par conséquent, non ordonnançable cas où les instructions temporelles devraient s’achever au bout de la période prescrite, l’exécution de la tâche entière est acceptable I I I -1- Représentation des dépendances:

Page 78: Restructuration d applications Java Temps réel

Conception Du Système De Restructuration Des Programmes Or ientés Objets (Java) 11

69

On calcule un fragment de programme en utilisant le concept de tranche de programme, basé sur la représentation du programme. Les chercheurs ont considéré plusieurs manières pour la représentation des programmes orientés objets[Larsen96][Lang97][Hang98]. Les caractéristiques orientées objets, telles que les classes et les objets, l’héritage, le polymorphisme et la liaison dynamique interviennent dans le développement d’une représentation efficace d’un programme orienté objet. Une classe définit les attributs qu’une instance d’une classe (objet) va posséder. Les attributs d’une classe consiste en l’ instance des variables qui implémentent l’état de l’objet, et des méthodes modélisant les opérations sur l’état de l’objet.

Un bon graphe de représentation d’une application orientée objets doit inclure la représentation de classes qui peuvent être réutilisées dans la construction de d’autres classes et applications utilisant ces dernières. Les classe dérivées sont définies à travers l’héritage, qui permet à la classe dérivée d’hériter des attributs provenant de ses classes parentes, de les étendre, restreindre, redéfinir ou les remplacer en quelque sorte. Tout comme ce que fournit l’héritage en facilitant la réutilisation de code, un bon graphe de représentation pour une classe dérivée doit faciliter la réutilisation des informations des classes. Le polymorphisme est une caractéristique importante pour les langages orientés objets qui permet durant l’exécution le choix d’une des destinations parmi celles de l’ensemble des appels de méthode.

Une représentation statique d’un choix dynamique exige que toutes les destinations possibles doivent être incluses, à moins que le type puisse être déterminé statiquement. Malgré la limite de la visibilité des variables d’une instance d’objet (état), ces variables d’ instance retiennent ses valeurs entre les appels de méthode à l’objet.

Une représentation doit compter pour les dépendances des variables des instances entre les appels aux méthodes de l’objet par un programme d’appel, même si les variables d’ instance ne sont pas visibles au programme d’appel. Pour pouvoir le réaliser, on construit un Graphe de Dépendance Etendu du Système (EGDS:Extended System Dependance Graph), basé sur la représentation des différents concepts orientés objets, principalement ceux proposés dans [Hang98], avec quelques adaptations qu’on introduit, et qui sont nécessaires pour notre processus de restructuration. Méthode d’Objet. Contrairement aux travaux décrits dans [Larsen96][Hang98], dans chacune des méthodes de l’objet, on a besoin de considérer tous les trois types de dépendances de données:flux, sortie et anti-dépendance, car les transformations modifient l’ordre des instructions. Cela peut être fait directement par un Graphe de Dépendance de Méthode (MDG:Method Dependance Graph): Le MDG est formé de (N,E) avec: � Les nœuds N représentent les instructions, i.e., assignation, prédicat de contrôle, appel de

méthode, ou une instruction temporisée (telle qu’une entrée ou une sortie). De plus, il y a un nœud particulier « Entry » qui représente la racine de la tâche.

� Les arcs E, qui sont de deux types: un arc v1 v2, qui indique une dépendance de contrôle entre v1 et v2. De ce fait, soit (1)v1 est un Entry, et v2 n’est pas lié ni à une boucle ou une condition, ou bien, (2) v1 représente un prédicat de contrôle, et v2 est immédiatement dans une boucle ou une condition dont le prédicat est représenté par v1. un arc v1 v2 dénote un flux, une sortie ou une anti-dépendance. Pour cela, un contrôle peut atteindre v2 après v1 via une trajectoire au long de laquelle il n’ y a aucune définition d’une variable m :

� v1 définit m, et v2 l’utilise (dépendance de flux). � v2 définit m, et v1 l’utilise (anti-dépendance). � v1 et v2 définissent tous les deux m (dépendance de sortie).

Page 79: Restructuration d applications Java Temps réel

Conception Du Système De Restructuration Des Programmes Or ientés Objets (Java) 11

70

En outre, on traite l’action de construction d’objet (new) comme une instruction d’appel. On la représente par la suite par un nœud Entry, relié par des arcs de dépendance de contrôle aux nœuds représentant ses membres de données.

Membres de Données d’Objet. On suppose de plus que les membres d’un objet peuvent être accédés seulement à travers une méthode. Enfin, on traite les membres de données statiques comme étant des variables globales et les méthodes statiques comme des méthodes globales, parce qu’elles ne s’associent à aucun objet particulier durant l’exécution. Pour pouvoir représenter un objet récepteur de message, on poursuit le schéma de Larsen et Horrold[Larsen98]. Un site d’appel contient des nœuds de membres de données «Actual-in» représentant les membres de données qui sont référencés, et des nœuds de membres de données «Actual-out» représentant les membres de données modifiables par une méthode appelée. Pour pouvoir supporter cette représentation, un nœud «Method Entry» contient les nœuds de membres de données «Formal-in» représentant les membres de données référencées dans la méthode, et les nœuds de membres de données «Formal-out» représentant les membres de données modifiables dans la méthode. Les nœuds de membres de données «Formal-in» sont libellés par des assignations qui copient la valeur des membres de données d’un objet dans la portée de la méthode au début de cette dernière, et les nœuds des membres de données «Formal-out» sont libellés avec des assignations qui copient la valeur des membres de données à partir de la portée de la méthode dans l’objet, à la fin de cette dernière encore. Suivant cette approche, les dépendances de données relatives aux membres de données de la classe dans une méthode sont calculées de la même manière que celles pour une procédure [Horwitz90][Hang98]. Objets Paramètres. Comme situé dans [Hang98], pour obtenir plus de précision quand un objet est utilisé comme étant un paramètre, un objet paramètre est représenté comme un arbre : la racine représente l’objet lui même, les fils de la racine représentent les membres de données de l’objet, et les branches de l’arbre représentent les dépendances de données entre l’objet et ses membres de données.

Afin de pouvoir calculer des dépendances de données, quand un arbre est utilisé dans la

représentation d’un objet, les utilisations ou les définitions sont associées aux nœuds des membres de données. Objet Polymorphique. Un objet polymorphique est représenté par un arbre[Hang94], dont la racine représente cet objet et les fils de la racine représentent les objets de tout type possible. Classe dans la Hiérarchie. Comme dans [Hang94], à travers une hiérarchie d’une classe, on garde une copie de la représentation pour une méthode, et cette représentation peut être partagée par différentes classes dans cette hiérarchie. Un nœud d’entrée de classe regroupe les méthodes appartenant à une classe et utilisant ensemble les arcs des relations membres. Pour identifier la classe d’origine, dans laquelle une méthode à été déclarée, on fait précéder le nom d’une méthode par le nom de la classe d’origine. Construction du ESDG. Comme dans Java, toute méthode ou variable fait partie d’une classe, notons que les méthodes et variables statiques sont en dépendance de contrôle au nœud d’entrée du programme P. Pour la construction du ESDG d’un programme, on poursuit les étapes suivantes: Etape 1- Construction des Graphes de Dépendance des Méthodes (MDG):

Page 80: Restructuration d applications Java Temps réel

Conception Du Système De Restructuration Des Programmes Or ientés Objets (Java) 11

71

On construit en premier lieu un MDG pour chaque méthode invoquées d’une manière directe ou indirecte dans le programme. La construction est faite d’une manière ascendante (figure 2), suivant la hiérarchie de la classe (une méthode statique va appartenir à la classe spéciale correspondante à P). Le constructeur de classe est représenté comme une méthode avec les variables formelles et effectives correspondantes seulement aux attributs de la classe qui sont référencées dans le programme de la tâche. Etape 2- Calcul des arcs résumés dans les endroits d’appel: L’endroit d’appel d’une méthode est représenté par (1)un nœud d’entrée, relié par un arc de contrôle au paramètre effectif, (2)les arcs résumés. Ensuite, on relie les MDG à leurs endroits d’appel correspondants. Etape 3- Construction des arcs de dépendances de données. I I I -2- Les tranches dans les Systèmes Objets:

Nous sommes concernés par les tranches arrières. Pour plus de clarification, et afin de permettre l’extraction de tranches par rapport à une valeur retournée par une méthode, on reformule la définition d’une tranche comme suit : « une tranche d’un programme P par rapport à un point p et une variable ou un appel de méthode m (si m est une variable, elle doit être définie ou utilisée au point p), consiste en les instructions et prédicats de P, qui peuvent affecter m au point d’exécution p ». Une paire <m,p>est généralement appelée le critère de la troncature, et la tranche associée est notée P/<m,p>.

Horwitz et al[Horwitz90] calculent les tranches interprocédurales en résolvant un problème d’atteinte de graphe sur le graphe de dépendance du système (SDG). Vu que le ESDG qu’on calcule pour un programme orienté objet appartient à une classe du SDG définie par Horwitz et al, on peut utiliser cette technique pour calculer une tranche, avec une petite modification. La première passe de l’algorithme de troncature traverse en marche arrière à travers tous les arcs, à l’exception des arcs «Parameter-out», et marque tous les nœuds atteints. La deuxième passe traverse en marche arrière à partir de tout les nœuds marqués durant la première passe, à travers tous les arcs, à l’exception des arcs d’appel et «Parameter-in», et marque les nœuds atteints. La tranche est l’union des nœuds marqués durant les deux passes.

La figure 3 schématise la tranche calculée par rapport au critère <<31>, <b>>, qui correspond à la ligne 31 dans le programme Java de l’exemple, et la variable b. En accomplissant les deux passes, la tranche est formée des nœuds ombrés dans le ESDG. La ligne de numéro 31 indique que l’ instruction qui émet (envoie) la variable b à l’actionneur. Suivant l’événement basé paradigme [Hang98], l’échéance de la tâche est placé sur cette action de sortie. Par conséquent, on détermine toutes les instructions qui influencent de telle action pour former le fragment temporel. Le reste des instructions forment le fragment non temporel, qui sera coller à la fin du temporel, afin d’obtenir un nouveau programme qui est sémantiquement équivalent à celui d’origine. IV- Processus de Restructuration:

Après la construction du ESDG suivant la procédure décrite précédemment, on détermine la tranche par un marquage arrière des nœuds atteints, commençant à partir des nœuds déterminés par le critère de troncature. De plus, on classe les méthodes en deux catégories : (1) les méthodes finales qui n’appellent aucune autre méthode, notée F, (2) les méthodes intermédiaires qui sont appelées par d’autres méthodes et appellent autres méthodes, notée I.

Le processus de restructuration consiste en:

Page 81: Restructuration d applications Java Temps réel

Conception Du Système De Restructuration Des Programmes Or ientés Objets (Java) 11

72

� Le calcul du fragment temporel et celui non temporel de chaque méthode. � Chaque corps de sous méthode calculé sera inséré dans la classe correspondante. � Le calcul du fragment temporel et celui du non temporel du programme P. � La disposition du fragment non temporel à la fin du fragment temporel dans le

programme P. Comme montré dans la figure 2, et d’une manière ascendante, on accomplit de tel

processus suivant les phases suivantes : Phase1 :Calcul du fragment temporel et non temporel des méthodes finales. Pour chaque méthode dans F : 1. A partir du corps de la méthode notée M, supprimer toutes les lignes correspondant aux

nœuds non marqués dans le ESDG. 2. Construire le corps de la méthode notée MT, qui inclut le reste des instructions. MT :M’s

Temporal fragment. 3. A partir du corps de la méthode M, supprimer toutes les lignes correspondant aux nœuds

marqués dans le ESDG, à l’exception des lignes conditionnelles ou de boucle. 4. Supprimer les lignes conditionnelles et de boucle contrôlant un ensemble vide

d’ instructions. 5. Construire le corps de la méthode notée MN, qui inclut le reste des instructions. MN:M’s

Non Temporal fragment. Phase2:Calcul des fragments temporel et non temporel des méthodes intermédiaires. Pour chaque méthode dans I, et d’une manière ascendante appliquée sur la hiérarchie de l’appel de méthode : 1. A partir du corps de la méthode M, supprimer toutes les lignes correspondant aux nœuds

non marqués dans le ESDG. 2. Si MNi-1 n’est pas vide, remplacer chaque appel de méthode M i-1 par l’appel de la

méthode MTi-1 (i est le numéro du niveau dans la hiérarchie de l’appel de méthode décrit dans la figure 2).

3. Construire le corps de la méthode MT, qui inclut le reste des instructions. 4. A partir du corps de la méthode M, supprimer toutes les lignes correspondant aux nœuds

marqués dans le ESDG, à l’exception des lignes d’appel, conditionnelles ou de boucle. 5. Si MNi-1 est vide, supprimer les lignes d’appel. 6. Supprimer les lignes d’appel et de condition qui contrôlent un ensemble vide

d’ instructions. 7. Remplacer chaque appel de méthode M i-1 par l’appel de la méthode MNi-1. 8. Construire le corps de méthode MN, contenant le reste des instructions.

La première phase calcule les fragments temporel et non temporel des méthodes finales. Elle introduit le schéma de l’appel de méthode (figure 2a), et produit pour chaque méthode M dans F, son fragment temporel (MT) et son fragment non temporel (MN). Une fois les sous méthodes MT et MN de la méthode M sont construites, on insert MT et MN dans leur classe afin de remplacer la méthode M. Quand la classe correspondante est une superclasse d’une autre classe, on insert les sous méthodes dans la classe de base sans suppression de la méthode d’origine. Phase3:Restructuration de classe. Pour chaque méthode M dans F et I : 1. Si MN n’est pas identique à M et est non vide, insérer le corps de MN dans la classe

d’origine de M.

Page 82: Restructuration d applications Java Temps réel

Conception Du Système De Restructuration Des Programmes Or ientés Objets (Java) 11

73

2. Si MT n’est pas identique à M et est non vide, insérer le corps de MT dans la classe d’origine de M.

Phase4:Restructuration de P (calcul des fragments temporel et non temporel de P). 1. A partir du corps du programme P, supprimer toutes les lignes correspondant aux nœuds

non marqués dans le ESDG. 2. Si MN n’est pas vide, remplacer chaque appel de méthode M par l’appel de la méthode

MT. 3. Le reste des instructions du fragment temporel de P est noté PT. 4. A partir du corps du programme P, supprimer toutes les lignes correspondant aux nœuds

marqués dans le ESDG, à l’exception des lignes de condition, boucle ou d’appel. 5. Supprimer les lignes d’appel et de condition qui contrôlent un ensemble vide

d’ instructions. 6. Si MN est vide, supprimer les lignes d’appel. 7. Remplacer tout appel de méthode M par l’appel de la méthode MN. 8. Le reste des instructions du fragment non temporel de P est noté PN. 9. Placer PN à la fin de PT. Enfin, après le calcul des deux fragments de P, on obtient notre tâche transformée, en plaçant le fragment non temporel à la fin du fragment temporel (figure 3), via une composition séquentielle. IV- Exemple d’application :

Soit le programme suivant écrit en Java :

Programme P Méthode M1 Méthode M2

a) Schéma d’appel de méthode avant restructuration

-- M1+

-- --

M1+ --

M1+

M2+ -- --

M2+ --

-- -- -- --

Programme P Méthode MT1 Méthode MT2 Méthode MN1 Méthode MN2

b) Schéma d’appel de méthode après restructuration

-- MN1+

-- MN1+

-- --

MN2+ --

MN2+

-- MT2+

-- MT2+

-- -- --

-- -- --

-- MT1+

-- MT1+

Figure 2 : Schéma de restructuration

Page 83: Restructuration d applications Java Temps réel

Conception Du Système De Restructuration Des Programmes Or ientés Objets (Java) 11

74

public class plan{ static float t, p ;//Temperat & Pression float a, b ; static void sense(){….}//(t, p)�(a, b) public void vm(){ a=a+b ;} public void mbi(int i){ b=b+i ; } public void mbvm(){ if(a>0){ vm() ;} b=b+1 ; } //envoi de commande à l’actionneur static void signal(float com){} //programme main dans le thread public class planMvt extends Thread{ int delay ; planMvt(int dealy){ this.dealy=delay ; start() ;} public void run(){ while (true){ new sense() ;//lecture à partir du capteur plan o = new plan() ; plan ba =new plan() ; ba.mbvm() ; o.mbi(1) ; ba.mbi(1) ; ba.signal(b) ;//émission à l’actionneur sleep(delay) ; }}}//création du thread new planMvt(60) ;//60 est la période de la tâche

Programme Temps Réel en Java

Page 84: Restructuration d applications Java Temps réel

Conception Du Système De Restructuration Des Programmes Or ientés Objets (Java) 11

75

Il s’agit d’un programme concernant une application temps réel développée sous Java. Nous sommes maintenant concernés par la restructuration de ce code et générer un autre

plus sûr en exécution (générer une tâche ordonnancée). Les étapes qu’on va suivre sont les suivantes, une fois qu’on est certain de la correction

du code en entrée: � Génération du code instrumenté. � Génération du GDS de notre système orienté objet. � Extraction de la tranche temporelle et par conséquent l’obtention du fragment du

code temporel. Le code restant est le fragment non temporel. Génération du code restructuré par composition des deux fragments obtenus de l’étape précédente, et en déplacement le fragment temps contraint au début du code à générer. Notez que la sémantique est préservée. Phase1:Génération du code instrumenté. En voici le programme instrumenté correspondant à celui présenté ci-dessus.

1 public class plan{ 2 static float t, p ;//Temperat & Pression 3 float a, b ; 4 static void sense(){….}//(t, p)����(a, b) 5 public void vm(){ 6 a=a+b ;} 7 public void mbi(int i){ 8 b=b+i ; 9 } 10 public void mbvm(){ 11 if(a>0){ 12 vm() ;} 13 b=b+1 ; 14 } 15 //envoi de commande à l’actionneur 16 static void signal(float com){} 17 //programme main dans le thread 18 public class planMvt extends Thread{ 19 int delay ; 20 planMvt(int dealy){ 21 this.dealy=delay ; 22 start() ;} 23 public void run(){ 24 while (true){ 25 new sense() ;//lecture à partir du capteur 26 plan o = new plan() ; 27 plan ba =new plan() ; 28 ba.mbvm() ; 29 o.mbi(1) ; 30 ba.mbi(1) ; 31 ba.signal(b) ;//émission à l’actionneur 32 sleep(delay) ; 33 } } } //création du thread 34 new planMvt(60) ;//60 est la période de la tâche

Code Instrumenté de la Tâche

Page 85: Restructuration d applications Java Temps réel

Conception Du Système De Restructuration Des Programmes Or ientés Objets (Java) 11

76

Phase2:Génération du GDS. En voici le GDS de notre application temps réel et orientée objet.

A3-in

planMvt

plan ba ba.mbvm sense() plan o

a F2-out t F1-out p

o.mbi(1)

ba.signal()

t p

ba.mbi(i)

a b b

b b

mbvm()()

A3-in

b b

b b

mbi(i)

a>0 F1-out b=b+1 F2-out

F2-out

b=b+i

F3-in F2-in

F1-in

F2-in

vm()

A1-out A2-in A1-in

vm()

a=a+b F1-in F2-in F1-out

Flux de contrôle Flux de données Arcs d’appel Arcs résumés

Génération du GDS

Page 86: Restructuration d applications Java Temps réel

Conception Du Système De Restructuration Des Programmes Or ientés Objets (Java) 11

77

Phase3: Extraction des tranches (Recherche du fragment temporel). En appliquant l’algorithme de troncature sur ce GDS orienté objet, par rapport à l’ instruction ba.signal(b) et en considérant la variable b, on trouve ce qui suit:

A3-in

planMvt

plan ba ba.mbvm sense() plan o

a F2-out t F1-out p

o.mbi(1)

ba.signal()

t p

ba.mbi(i)

a b b

b b

mbvm()

A3-in

b b

b b

mbi(i)

a>0 F1-out b=b+1 F2-out

F2-out

b=b+i

F3-in F2-in

F1-in

F2-in

vm()

A1-out A2-in A1-in

vm()

a=a+b F1-in F2-in F1-out

Extraction de Tranche

Page 87: Restructuration d applications Java Temps réel

Conception Du Système De Restructuration Des Programmes Or ientés Objets (Java) 11

78

Les nœuds hachurés représentent la tranche extraite à partir de ce GDS. A partir de cette tranche , on peut extraire le fragment temporel, qui doit être exécuté en premier lieu, et qui est indépendant du reste du programme.

On note, dans ce qui concerne l’extraction d’une tranche orientée objet, que � La tranche ne concerne que l’objet dans lequel il y avait l’ instruction du critère de troncature, même s’ il existe d’arcs reliant des objets différents appelant la même méthode. On peut expliquer ce résultat par la caractéristique d’encapsulation dans le concept de l’orienté objet. � Les concepts de l’extraction des tranches connues dans les programmes multiprocéduraux se conservent pour le cas de l’orienté objet (passage de paramètres, les appels …etc.). � Une instruction d’ instanciation dans le programme source implique l’existence d’un nœud d’ instanciation d’un objet , ayant des arcs de contrôle vers sa partie statique(attributs). Les éléments de cette partie ne feront partie que d’un flux de données ou d’une paramétrisation.

Phase4: Extraction du Fragment Temporel et du Fragment Non Temporel.

Le fragment temporel est constitué des instructions du programme source (partie main), qui s’est trouvée dans la tranche extraite. Le reste des instructions constitue le fragment non temporel.

Dans le code instrumenté, les instructions temporelles (éléments du fragment temporel) sont écrites en gras. Phase5: Génération du code restructuré plus sûr en exécution. On génère le nouveau code comme suit : � Conservation de la partie déclaration et de toute définition externe. � Dans la partie main, on met en premier lieu le fragment temporel, suivi du fragment non

temporel. Par cela, on parvient à produire un code restructuré d’une application temps réel orientée objet, dont la probabilité de commettre une erreur d’exécution, en cas de commutation, soit minimale, vu que la partie critique, qui dépend du facteur temps, va s’exécuter dès le lancement de notre thread. 1 public class plan{ 2 static float t, p ; 3 float a, b ; 4 static void sense(){….} 5 public void vm(){ 6 a=a+b ;} 7 public void mbi(int i){ 8 b=b+i ; 9 } 10 //mbvm est subdivisée en deux fragments 11 public void mbvmT(){//fragm temporel 12 b=b+1 ;} 13 public void mbvmN(){ //non temporel 14 if(a>0){ 15 vm() ;} } 16 static void signal(float com){} 17 public class planMvt extends Thread{ 18 int delay ;

19 planMvt(int dealy){ 20 this.dealy=delay ; 21 start() ;} 22 public void run(){ 23 while (true){ 24 new sense() ; 25 plan ba =new plan() ; 26 ba.mbvmT() ; 27 ba.mbi(1) ; 28 ba.signal(b) ; 29 plan o = new plan() ; 30 o.mbi(1) ; 31 ba.mbvmN() ; 32 sleep(delay) ; 33 } } } //création du thread 34 new planMvt(60) ;//60 est la période de la tâche

Programme Restructuré de la Tâche

Page 88: Restructuration d applications Java Temps réel

Conception Du Système De Restructuration Des Programmes Or ientés Objets (Java) 11

79

V- Conclusion: Dans notre modèle, on a présenté une approche étendue pour améliorer

l’ordonnançabilité des applications temps réel. Elle est basée sur deux concepts : la tranche d’objet et la théorie de l’ordonnancement avec priorité fixe. Par conséquent, on a montré qu’on peut augmenter l’ordonnançabilité à priorité fixe d’une tâche de deux manières : premièrement, on décompose le programme d’une tâche non ordonnançable en deux fragments, ensuite on placera le fragment non temporel après le fragment temporel dans le nouveau code de la tâche. Et en deuxième lieu, par décomposition d’une ou de plusieurs tâches en sous tâches qui sont exécutées à niveaux de priorités modifiables, on peut augmenter l’ordonnançabilité totale au delà de celle fournie par l’algorithme d’ordonnancement rate-monotonic simple.

Par conséquent, appliquée aux programmes temps réels orientés objets, la nature complémentaire de notre approche de restructuration pour l’analyse de l’ordonnançabilité, sera une base pour d’autres outils qui adoptent la prévision temporelle sans sacrifier de bonnes pratiques en ingénierie. Ces deux techniques constitue une partie du processus de développement de logiciels temps réel.

Pour terminer sur les systèmes temps réel, on a utilisé des constructions qui sont très utilisées dans les langages de programmation temps réel. A présent, nous sommes entrain d’ implémenter notre technique de restructuration pour Java, pour l’expérimenter avec des applications utiles dans le domaine du temps réel.