Notre objectif est la conception d'algorithmes d'ordonnancement temps réel en-ligne faisables (i.e., garantissant le respect des contraintes temporelles imposées au systèmes) optimisant 1) l'utilisation de la plate-forme d'exécution (i.e., utiliser au mieux le potentiel de la plate-forme d'exécution tout en garantissant le respect des contraintes temporelles imposées au système) et/ou 2) optimisant des critères de performances<br />propres à l'application.<br /> <br />Deux cas ont été analysés : le cas de tâches indépendantes périodiques s'exécutant sur un processeur et le cas de flux de messages indépendants périodiques sur un réseau de terrain avec accès au médium priorisé.<br /><br />Nous avons donc proposé pour traiter les deux problèmatiques abordées :<br />1) des méthodes de configurations permettant d'optimiser l'utilisation de la plate-forme d'exécution en fixant d'une manière appropriée les paramètres : des politiques ou des activités du système considéré. Deux études ont été conduites dans ce cadre~: l'allocation des ``offsets'' dans les systèmes ``offset free'' et l'allocation de priorités, de politiques et de quantum dans<br />les systèmes conformes au standard Posix~1003.1b,<br />2) une nouvelle classe de politiques d'ordonnancement permettant<br />d'optimiser des critères de performances propres à l'application.

Cette thèse porte sur la vérification formelle de systèmes temps réel et procède par transformation de modèle entre l'algèbre de processus temporisée RT-LOTOS et les réseaux de Petri temporels étendus par des chronomètres et des données. Des schémas de traduction de RT-LOTOS vers ces réseaux de Petri étendus sont proposés et formellement prouvés. L'approche transformationnelle développée pour la partie " contrôle " de RT-LOTOS est étendue à la partie " données ". Le langage RT-LOTOS est lui même enrichi d'un opérateur de suspension reprise qui permet de modéliser et vérifier une classe plus large de systèmes temps réel Plusieurs études de cas attestent de l'efficacité des schémas de traduction proposés par rapport à des outils LOTOS ou RT-LOTOS développés antérieurement. L'approche proposée s'avère transposable à d'autres langages de modélisation en particulier le profil UML temps réel TURTLE (Timed UML and RT-LOTOS Environment).

Cette thèse se focalise sur le développement des algorithmes d'ordonnancement sous contrainte (m, k)-firm, ainsi que leurs applications pour la gestion de la qualité de service (QdS) dans les réseaux et systèmes temps réel distribués. L'objectif recherché est la ga-rantie déterministe de la QdS tout en maintenant un fort taux d'utilisation des ressources.<br />Les contributions sont (1) l'établissement d'une condition suffisante d'ordonnançabilité d'un ensemble de tâches sous l'algorithme « distance based priority »; (2) la définition de R-(m, k)-firm, un nouveau modèle qui relâche la contrainte (m, k)-firm et qui permet de modéliser de façon plus juste des exigences du temps réel souple; (3) le développement d'un algorithme efficace de dimensionnement de ressources sous contrainte (m, k)-firm relâchée; (4) la proposition de « Double Leaks Bucket » pour la gestion active de files d'attente permettant de maintenir une QdS en cas de surcharge des réseaux.

Ce mémoire présente des travaux concernant la spécification, la modélisation et l'analyse de systèmes de contrôle-commande temps réel répartis sur un réseau de terrain. La problématique de modélisation de tels systèmes, qui doivent satisfaire des contraintes temporelles, réside dans la maîtrise de la taille et de la complexité des modèles. Pour cela, une méthodologie de modélisation est proposée ; elle repose sur les concepts de structuration, de modélisation et de validation modulaires au moyen du modèle formel Réseaux de Petri Temporisés Stochastiques. La structuration consiste en une décomposition hiérarchisée en blocs fonctionnels élémentaires. Une structure est proposée pour des entités de communication d'un réseau local temps réel, ainsi que pour un système temps réel de commande et surveillance réparties. La modélisation repose sur la construction et la composition de modèles de modules élémentaires. Les principes énoncés concernent la définition de règles de composition. Des modèles d'assertions logiques sont également proposés pour faciliter le passage des descriptions de comportements exprimées en langage naturel, à une modélisation en Réseaux de Petri Temporisés Stochastiques. La validation repose sur des étapes de composition partielle qui utilisent la modularité pour effectuer des vérifications ascendantes du comportement. Cette méthodologie est appliquée au réseau de terrain FIP, ainsi qu'au futur système de contrôle-commande de poste de transformation d'énergie électrique d'EDF. L'étude du réseau FIP porte plus particulièrement sur les services et mécanismes périodiques de couche application pour les échanges temps réel. Les analyses (qualitatives et quantitatives) effectuées sur l'application de EDF répartie sur le réseau FIP portent sur la vérification des propriétés fonctionnelles et des contraintes temporelles du système.

Construire des modèles qui représentent fidèlement les systèmes temps réels complexes est indispensable pour l'analyse de leurs propriétés fonctionnelles et temporelles. Ce travail présente une méthodologie de modélisation pour les systèmes temps réels dans le contexte de la technologie Java. Le modèle est obtenu par la restriction du modèle fonctionnel du logiciel avec les informations temporelles appropriées. Nous établissons un sous ensemble du langage Java qui réglemente la structure concurrente de l'application, la communication et les pratiques de programmation au niveau des threads, des objets et du flot de contrôle. Le modèle fonctionnel est construit à partir de règles de réécriture basées sur la sémantique du langage. Les modèles non temporisés sont ensuite décorés par les informations relatives à la plate forme d'exécution, la dynamique de l'environnement et les échéances temps réel. La méthodologie de modélisation à été implémentée dans l'outil JediTool.

Cette thèse s'inscrit dans le cadre général de l'utilisation des techniques formelles lors de la phase conceptuelle des systèmes distribués temps-réel, et concerne plus précisément l'extension des pouvoirs d'expression et d'analyse du modèle Réseaux de Petri Temporisés Stochastiques. Ce modèle, qui appartient à la classe des Réseaux de Petri Stochastiques, associe à chaque transition un intervalle de temps, et une distribution de probabilité sur cet intervalle (ceci permet de représenter des caractéristiques temporelles variées et en particulier des contraintes) En ce qui concerne le pouvoir d'expression, nous avons introduit, d'une part, la notion de mémoire temporelle de toutes les sensibilisations (ceci est important pour l'étude des phénomènes de préemption que l'on rencontre dans des algorithmes d'ordonnancement et dans des problèmes de sûreté de fonctionnement) et, d'autre part, plusieurs règles de tir de transitions (en particulier les règles MIN et MAX qui permettent des études des cas pires, aspect important dans les systèmes temps-réels). Les graphes ainsi obtenus ont été également situés par rapport à la référence comportementale que constitue le graphe des classes d'états (obtenu à partir des Réseaux de Petri Temporels). En ce qui concerne le pouvoir d'analyse, nous avons défini le concept d'automate quotient quantifié (concept basé, à la fois, sur la relation d'équivalence de Milner et les règles de réduction de Beizer), qui a deux qualités importantes : il permet, d'une part, d'obtenir des modèles, à la fois qualitatifs et quantitatifs de services de communication ; et, d'autre part, de contrôler les dimensions des modèles à traiter lors de la modélisation d'architectures de communication multicouches. Ce modèle a été appliqué à un exemple industriel, le protocole embarqué temps-réel ARINC 629 CP. L'étude faite a mis en évidence les propriétés temps-réel et de tolérance aux pannes de ce protocole.

Les travaux de cette thèse, menés dans le cadre du projet RNRT A3S, intègrent la notion de composants au sein d'une méthodologie de conception de plates-formes SoC (System on Chip), basée sur le langage de modélisation UML (Unified Modeling Language). Cette méthodologie propose un environnement de conception haut-niveau, basé sur le profil UML A3S, développé pour apporter la sémantique du domaine des systèmes temps réel embarqués et en particulier celle relative aux applications Radio Logicielle. Elle repose sur une approche MDA ou l'architecture est dirigée par les modèles où chaque modèle correspond à un niveau d'abstraction, à un niveau de raffinement particulier.<br /><br />Une chaîne UMTS a permis la validation de l'outil réalisé, en confrontant les résultats estimés de l'outil, à ceux mesurés sur une plate-forme temps réel hétérogène (multi-DSP, multi-FPGA). Une partie du travail s'est concentré sur l'identification des composants utiles à la conception des systèmes SoC, et de leurs caractéristiques, en adéquation avec le niveau d'abstraction considéré. Une autre partie des travaux a porté sur la définition des modèles UML, et donc du profil, qui définissent la sémantique des différents composants identifiés en fonction de la configuration (PIM, PSM), ainsi que leurs relations. Une réflexion a été nécessaire afin d'élaborer les diverses règles de vérification et modèles d'exécution qui permettent d'informer le concepteur de ses erreurs et de la faisabilité du système modélisé. Un modèle de système d'exploitation a également été inclus, enrichissant la liste des éléments (composants) déjà définis et démontrant l'extensibilité du profil.

Cette thèse traite de la modélisation des systèmes temps-réel à l'aide<br />de réseaux de Petri. Nous considérons séparément la question de<br />représentation du temps et celle de la préemption (interruption des<br />processus d'un système) qui est d'un usage courant pour les<br />applications temps-réel.<br /><br />Nous utilisons des réseaux de Petri sans extension par des<br />informations concernant le temps. Notre approche consiste alors à<br />introduire le temps par des sous-réseaux spécifiques représentant les<br />horloges du système modélisé. Le résultat est appelé temps<br />causal puisque seule la causalité définit la relation de précédence<br />entre les occurrences des événements. Afin d'obtenir une formulation<br />élégante de l'approche causale du temps, nous utilisons le modèle des<br />M-nets, une classe de réseaux de Petri colorés composables à la<br />manière des algèbres de processus. Nous étendons ce modèle de façon à<br />permettre la représentation efficace des communications asynchrones<br />entre processus et les bases théoriques liées à cette extension sont<br />revisitées et mises à jour. Nous utilisons les M-nets ainsi étendus<br />pour modéliser plusieurs horloges aux fonctionnalités différentes.<br />Nous montrons comment des systèmes à plusieurs horloges, synchronisées<br />ou non, peuvent être assez simplement obtenus. La pertinence de notre<br />approche est évaluée par une étude de cas et appliquée à la sémantique<br />d'une extension d'un langage de programmation parallèle, appelé<br />B(PN)², par des instructions liées au temps.<br /><br />Pour introduire la préemption nous proposons une nouvelle extension<br />des M-nets avec des opérations permettant la suspension/reprise et<br />l'avortement. Le modèle obtenu est étudié sur le plan théorique et<br />appliqué à l'extension de la sémantique de B(PN)² par des exceptions<br />et un système de tâches.

Les charges réelles d'applications sont souvent dynamiques. Ainsi, le dimensionnement statique de ressources est voué soit au gaspillage, s'il est basé sur une estimation du pire scénario, soit à la dégradation de performance, s'il est basé sur la charge moyenne. Grâce au modèle du cloud computing, les ressources peuvent être allouées à la demande et le dimensionnement adapté à la variation de la charge. Cependant, après avoir exploré les travaux existants, nous avons trouvé que la plupart des outils d'élasticité sont trop génériques et ne parviennent pas à répondre aux besoins spécifiques d'applications particulières. Dans le cadre de ce travail, nous utilisons des boucles autonomiques et diverses techniques d'élasticité afin de rendre élastiques différents types d'applications, à savoir un service de consolidation, un intergiciel de messagerie et une plateforme de traitement de données en temps-réel. Ces solutions élastiques ont été réalisées à partir d'applications libres et leur évaluation montre qu'ils permettent d'économiser les ressources utilisées avec un surcoût minimal. / Real world workloads are often dynamic. This makes the static scaling of resourcesfatally result in either the waste of resources, if it is based on the estimatedworst case scenario, or the degradation of performance if it is based on the averageworkload. Thanks to the cloud computing model, resources can be provisioned ondemand and scaling can be adapted to the variations of the workload thus achievingelasticity. However, after exploring the existing works, we find that most elasticityframeworks are too generic and fail to meet the specific needs of particularapplications. In this work, we use autonomic loops along with various elasticitytechniques in order to render different types of applications elastic, namelya consolidation service, message-oriented middleware and a stream processingplatform. These elastic solutions have been implemented based on open-sourceapplications and their evaluation shows that they enable resources’ economy withminimal overhead.

L'implémenation distribuée des systèmes temps-réel a été toujous une tâche non-triviale. La coordination des composants s'exécutant sur une plate-forme distribuée doit être assurée par des protocoles de communication complexes en tenant compte de leurs contraintes de temps. Dans cette thèse, nous proposons un flot de conception rigoureux à partir d'un modèle de haut niveau d'un logiciel d'application décrit en BIP (Behavior, Interaction, Priority) et conduisant à une implémenation distribuée. Le flot de conception implique l'utilisation de transformations de modèles tout en conservant les propriétés fonctionnelles des modèles originaux de BIP. Un modèle BIP se compose d'un ensemble de composants qui se synchronisent à travers les interactions et les priorités. Notre méthode transforme les modèles BIP en un modéle Send/Receive qui fonctionnent en utilisant le passage de messages asynchrones. Les modèles obtenus sont directement implémenté sur une plate-forme donnée. Nous présentons trois solutions pour obtenir un modéle Send/Receive. Dans la première solution, nous proposons des modéles Send/Receive qui fonctionnent avec un engin centralisé qui implémente les interactions et les priorités. Les composants atomiques des modèles originaux sont transformés en composants Send/Receive qui communiquent avec l'engin centralisé via des interactions Send/Receive. L'engin centralisé exécute les interactions sous certaines conditions définies par les modèles à états partiels. Ces modèles représentent une déscription haut niveau de l'exécution parallèle de modèles BIP. Dans la deuxième solution, nous proposons de décentraliser l'engin. Les modéles Send/Receive obtenus sont structurées en trois couches: (1) les composants Send/Receive (2) un ensemble d'engin, chacun exécutant un sous-ensemble d'interactions, et (3) un ensemble de composants implémentant un protocole de résolution des conflits. Avec les solutions décrites ci-dessus, nous supposons que les latences de communication sont négligeables. Ceci est du au fait que les modéles Send/Receive sont concu de telle sorte qu'il n'y ait pas retard entre la décision d'exécuter une interaction dans un engin et son exécution dans les composants participant. Dans la troisième solution, nous proposons des modéles Send/ Receive qui exécutent correctement même en présence de latences de communication. Cette solution est basée sur le fait que les engin planifient l'exécution des interactions et notifient les composants à l'avance. Afin de planifier correctement les interactions, nous montrons que les engins sont tenus à observer des composants supplémentaires, en plus de ceux qui participent aux interactions. Nous présentons également une méthode pour optimiser le nombre de composants observés, en se basant sur l'utilisation de techniques d'analyse statique. A partir d'un modéle Send/Receive donné, nous générons une application distribuée où les interactions Send/Receive sont implémentées par les sockets TCP. Les résultats expérimentaux sur des exemples non triviaux et des études de cas montrent l'efficacité de notre méthode. / Correct distributed implementation of real-time systems has always been a challenging task. The coordination of components executing on a distributed platform has to be ensured by complex communication protocols taking into account their timing constraints. In this thesis, we propose rigorous design flow starting from a high-level model of an application software in BIP (Behavior, Interaction, Priority) and leading to a distributed implementation. The design flow involves the use of model transformations while preserving the functional properties of the original BIP models. A BIP model consists of a set of components synchronizing through multiparty interactions and priorities. Our method transforms high-level BIP models into Send/Receive models that operate using asynchronous message passing. The obtained models are directly implementable on a given platform. We present three solutions for obtaining Send/Receive BIP models. -In the first solution, we propose Send/Receive models with a centralized scheduler that implements interactions and priorities. Atomic components of the original models are transformed into Send/Receive components that communicate with the centralized scheduler via Send/Receive interactions. The centralized scheduler is required to schedule interactions under some conditions defined by partial state models. Those models represent high-level representation of parallel execution of BIP models. - In the second solution, we propose to decentralize the scheduler. The obtained Send/Receive models are structured in 3 layers: (1) Send/Receive atomic components, (2) a set of schedulers each one handling a subset of interactions, and (3) a set of components implementing a conflict resolution protocol. With the above solutions, we assume that the obtained Send/Receive models are implemented on platforms that provide fast communications (e.g. multi-process platforms) to meet perfect synchronization in components. This is because the obtained schedulers are modeled such that interactions scheduling corresponds exactly to execution in components. - In the third solution, we propose Send/Receive models that execute correctly even if communications are not fast enough. This solution is based on the fact that schedulers plan interactions execution and notify components in advance. In order to plan correctly the interactions, we show that the schedulers are required to observe additional components, in addition to the ones participating in the interactions. We present also a method to optimize the number of observed components, based on the use of static analysis techniques. From a given Send/Receive model, we generate a distributed implementation where Send/Receive interactions are implemented by TCP sockets. The experimental results on non trivial examples and case studies show the efficiency of our design flow.