Search

Interference on the memory system can cause significant slowdowns to applications running in parallel on COTS multi-core processors. They are caused by concurrent accesses to shared hardware resources in the memory system. The magnitude of the delays caused by this phenomenon is difficult to predict, making interference a major obstacle to the adoption of COTS multi-core processors in real-time systems.This thesis is devoted to the characterization of the sensitivity of an application to memory interferences based on a characterization of its behavior in isolation. The goal is to determine a priori if an application is sensitive to this problem or not. Using a set of microbenchmarks that we have previously introduced, we show that a purely quantitative characterization of memory access behavior characterizes the sensitivity to interference in a very imprecise way.In order to allow a more precise characterization of sensitivity, we introduce different metrics to quantify quantitative and qualitative aspects of memory use. In order to measure these metrics, we implement a profiler prototype based on dynamic binary instrumentation approaches.In addition to allowing the measurement of qualitative aspects, this tool produces high-resolution profiles that clearly distinguish the different phases in application behaviors. Finally, we use data from our microbenchmarks to train a machine learning algorithm according to several characterizations.Experimental results show significant reductions in error reduction for the prediction of the delay undergone by applications of the MiBench and PARSEC suites.; Les interférences du système mémoire peuvent entraîner d’importants ralentisse- ments aux applications s’exécutant en parallèle sur les processeurs multi-cœurs COTS. Elles ont pour origine les accès concurrents aux ressources matérielles partagées du sys- tème mémoire. L’ampleur des retards causés par ce phénomène s’avère difficile à prédire, faisant des interférences un obstacle majeur à l’adoption des processeurs multi-cœur COTS dans les systèmes temps-réels. Cette thèse est consacrée à la caractérisation de la sensibilité d’une application aux interférences mémoires à partir d’une caractérisation de son comportement exécutée seule. Le but étant de pouvoir déterminer à priori si une ap- plication est sensible à ce problème ou non. À l’aide d’un ensemble de microbenchmarks que nous avons préalablement introduit, nous montrons qu’une caractérisation pure- ment quantitative du comportement d’accès à la mémoire caractérise la sensibilité aux interférences de façon très imprécise. Afin de permettre une caractérisation plus précise de la sensibilité, nous introduisons différentes métriques permettant de quantifier des aspects quantitatifs de l’utilisation de la mémoire. Afin de mesurer ces métriques, nous implémentons un prototype de profileur reposant sur des approches d’instrumentation binaire dynamique. En plus de permettre la mesure des aspects qualitatifs, cet outil produit des profils haute résolution permettant de distinguer clairement les différentes phases dans les comportements applicatifs. Enfin, nous utilisons les données issues de nos microbenchmarks pour entraîner un algorithme d’apprentissage automatique selon plusieurs caractérisations. Les résultats expérimentaux montrent des réductions significatives de réduction d’erreur pour la prédiction du retard subi par des applications des suites MIBENCH et PARSEC.

Interference on the memory system can cause significant slowdowns to applications running in parallel on COTS multi-core processors. They are caused by concurrent accesses to shared hardware resources in the memory system. The magnitude of the delays caused by this phenomenon is difficult to predict, making interference a major obstacle to the adoption of COTS multi-core processors in real-time systems.This thesis is devoted to the characterization of the sensitivity of an application to memory interferences based on a characterization of its behavior in isolation. The goal is to determine a priori if an application is sensitive to this problem or not. Using a set of microbenchmarks that we have previously introduced, we show that a purely quantitative characterization of memory access behavior characterizes the sensitivity to interference in a very imprecise way.In order to allow a more precise characterization of sensitivity, we introduce different metrics to quantify quantitative and qualitative aspects of memory use. In order to measure these metrics, we implement a profiler prototype based on dynamic binary instrumentation approaches.In addition to allowing the measurement of qualitative aspects, this tool produces high-resolution profiles that clearly distinguish the different phases in application behaviors. Finally, we use data from our microbenchmarks to train a machine learning algorithm according to several characterizations.Experimental results show significant reductions in error reduction for the prediction of the delay undergone by applications of the MiBench and PARSEC suites.; Les interférences du système mémoire peuvent entraîner d’importants ralentisse- ments aux applications s’exécutant en parallèle sur les processeurs multi-cœurs COTS. Elles ont pour origine les accès concurrents aux ressources matérielles partagées du sys- tème mémoire. L’ampleur des retards causés par ce phénomène s’avère difficile à prédire, faisant des interférences un obstacle majeur à l’adoption des processeurs multi-cœur COTS dans les systèmes temps-réels. Cette thèse est consacrée à la caractérisation de la sensibilité d’une application aux interférences mémoires à partir d’une caractérisation de son comportement exécutée seule. Le but étant de pouvoir déterminer à priori si une ap- plication est sensible à ce problème ou non. À l’aide d’un ensemble de microbenchmarks que nous avons préalablement introduit, nous montrons qu’une caractérisation pure- ment quantitative du comportement d’accès à la mémoire caractérise la sensibilité aux interférences de façon très imprécise. Afin de permettre une caractérisation plus précise de la sensibilité, nous introduisons différentes métriques permettant de quantifier des aspects quantitatifs de l’utilisation de la mémoire. Afin de mesurer ces métriques, nous implémentons un prototype de profileur reposant sur des approches d’instrumentation binaire dynamique. En plus de permettre la mesure des aspects qualitatifs, cet outil produit des profils haute résolution permettant de distinguer clairement les différentes phases dans les comportements applicatifs. Enfin, nous utilisons les données issues de nos microbenchmarks pour entraîner un algorithme d’apprentissage automatique selon plusieurs caractérisations. Les résultats expérimentaux montrent des réductions significatives de réduction d’erreur pour la prédiction du retard subi par des applications des suites MIBENCH et PARSEC.

The search for an upper bound of the execution time of a program is an essential part of the verification of real-time critical systems. The execution times of the programs of such systems generally vary a lot, and it is difficult, or impossible, to predict the range of the possible times. Instead, it is better to look for an approximation of the Worst-Case Execution Time (WCET). A crucial requirement of this estimate is that it must be safe, that is, it must be guaranteed above the real WCET. Because we are looking to prove that the system in question terminates reasonably quickly, an overapproximation is the only acceptable form of approximation. The guarantee of such a safety property could not sensibly be done without static analysis, as a result based on a battery of tests could not be safe without an exhaustive handling of test cases. Furthermore, in the absence of a certified compiler (and tech- nique for the safe transfer of properties to the binaries), the extraction of properties must be done directly on binary code to warrant their soundness. However, this approximation comes with a cost : an important pessimism, the gap between the estimated WCET and the real WCET, would lead to superfluous extra costs in hardware in order for the system to respect the imposed timing requirements. It is therefore important to improve the precision of the WCET by reducing this gap, while maintaining the safety property, as such that it is low enough to not lead to immoderate costs. A major cause of overestimation is the inclusion of semantically impossible paths, said infeasible paths, in the WCET computation. This is due to the use of the Implicit Path Enumeration Technique (IPET), which works on an superset of the possible execution paths. When the Worst-Case Execution Path (WCEP), corresponding to the estimated WCET, is infeasible, the precision of that estimation is negatively affected. In order to deal with this loss of precision, this thesis proposes an infeasible paths detection technique, enabling the improvement of the precision of static analyses (namely for WCET estimation) by notifying them of the infeasibility of some paths of the program. This information is then passed as data flow properties, formatted in the FFX portable annotation language, and allowing the communication of the results of our infeasible path analysis to other analyses., La recherche d'une borne supérieure au temps d'exécution d'un programme est une partie essentielle du processus de vérification de systèmes temps-réel critiques. Les programmes de tels systèmes ont généralement des temps d'exécution variables et il est difficile, voire impossible, de prédire l'ensemble de ces temps possibles. Au lieu de cela, il est préférable de rechercher une approximation du temps d'exécution pire-cas ou Worst-Case Execution Time (WCET). Une propriété cruciale de cette approximation est qu'elle doit être sûre, c'est-à-dire qu'elle doit être garantie de majorer le WCET. Parce que nous cherchons à prouver que le système en question se termine en un temps raisonnable, une surapproximation est le seul type d'approximation acceptable. La garantie de cette propriété de sûreté ne saurait raisonnablement se faire sans analyse statique, un résultat se basant sur une série de tests ne pouvant être sûr sans un traitement exhaustif des cas d'exécution. De plus, en l'absence de certification du processus de compilation (et de transfert des propriétés vers le binaire), l'extraction de propriétés doit se faire directement sur le code binaire pour garantir leur fiabilité. Toutefois, cette approximation a un coût : un pessimisme - écart entre le WCET estimé et le WCET réel - important entraîne des surcoûts superflus de matériel pour que le système respecte les contraintes temporelles qui lui sont imposées. Il s'agit donc ensuite, tout en maintenant la garantie de sécurité de l'estimation du WCET, d'améliorer sa précision en réduisant cet écart de telle sorte qu'il soit suffisamment faible pour ne pas entraîner des coûts supplémentaires démesurés. Un des principaux facteurs de surestimation est la prise en compte de chemins d'exécution sémantiquement impossibles, dits infaisables, dans le calcul du WCET. Ceci est dû à l'analyse par énumération implicite des chemins ou Implicit Path Enumeration Technique (IPET) qui raisonne sur un surensemble des chemins d'exécution. Lorsque le chemin d'exécution pire-cas ou Worst-Case Execution Path (WCEP), correspondant au WCET estimé, porte sur un chemin infaisable, la précision de cette estimation est négativement affectée. Afin de parer à cette perte de précision, cette thèse propose une technique de détection de chemins infaisables, permettant l'amélioration de la précision des analyses statiques (dont celles pour le WCET) en les informant de l'infaisabilité de certains chemins du programme. Cette information est passée sous la forme de propriétés de flot de données formatées dans un langage d'annotation portable, FFX, permettant la communication des résultats de notre analyse de chemins infaisables vers d'autres analyses. Les méthodes présentées dans cette thèse sont inclues dans le framework OTAWA, développé au sein de l'équipe TRACES à l'IRIT. Elles usent elles-mêmes d'approximations pour représenter les états possibles de la machine en différents points du programme.

The search for an upper bound of the execution time of a program is an essential part of the verification of real-time critical systems. The execution times of the programs of such systems generally vary a lot, and it is difficult, or impossible, to predict the range of the possible times. Instead, it is better to look for an approximation of the Worst-Case Execution Time (WCET). A crucial requirement of this estimate is that it must be safe, that is, it must be guaranteed above the real WCET. Because we are looking to prove that the system in question terminates reasonably quickly, an overapproximation is the only acceptable form of approximation. The guarantee of such a safety property could not sensibly be done without static analysis, as a result based on a battery of tests could not be safe without an exhaustive handling of test cases. Furthermore, in the absence of a certified compiler (and tech- nique for the safe transfer of properties to the binaries), the extraction of properties must be done directly on binary code to warrant their soundness. However, this approximation comes with a cost : an important pessimism, the gap between the estimated WCET and the real WCET, would lead to superfluous extra costs in hardware in order for the system to respect the imposed timing requirements. It is therefore important to improve the precision of the WCET by reducing this gap, while maintaining the safety property, as such that it is low enough to not lead to immoderate costs. A major cause of overestimation is the inclusion of semantically impossible paths, said infeasible paths, in the WCET computation. This is due to the use of the Implicit Path Enumeration Technique (IPET), which works on an superset of the possible execution paths. When the Worst-Case Execution Path (WCEP), corresponding to the estimated WCET, is infeasible, the precision of that estimation is negatively affected. In order to deal with this loss of precision, this thesis proposes an infeasible paths detection technique, enabling the improvement of the precision of static analyses (namely for WCET estimation) by notifying them of the infeasibility of some paths of the program. This information is then passed as data flow properties, formatted in the FFX portable annotation language, and allowing the communication of the results of our infeasible path analysis to other analyses.; La recherche d'une borne supérieure au temps d'exécution d'un programme est une partie essentielle du processus de vérification de systèmes temps-réel critiques. Les programmes de tels systèmes ont généralement des temps d'exécution variables et il est difficile, voire impossible, de prédire l'ensemble de ces temps possibles. Au lieu de cela, il est préférable de rechercher une approximation du temps d'exécution pire-cas ou Worst-Case Execution Time (WCET). Une propriété cruciale de cette approximation est qu'elle doit être sûre, c'est-à-dire qu'elle doit être garantie de majorer le WCET. Parce que nous cherchons à prouver que le système en question se termine en un temps raisonnable, une surapproximation est le seul type d'approximation acceptable. La garantie de cette propriété de sûreté ne saurait raisonnablement se faire sans analyse statique, un résultat se basant sur une série de tests ne pouvant être sûr sans un traitement exhaustif des cas d'exécution. De plus, en l'absence de certification du processus de compilation (et de transfert des propriétés vers le binaire), l'extraction de propriétés doit se faire directement sur le code binaire pour garantir leur fiabilité. Toutefois, cette approximation a un coût : un pessimisme - écart entre le WCET estimé et le WCET réel - important entraîne des surcoûts superflus de matériel pour que le système respecte les contraintes temporelles qui lui sont imposées. Il s'agit donc ensuite, tout en maintenant la garantie de sécurité de l'estimation du WCET, d'améliorer sa précision en réduisant cet écart de telle sorte qu'il soit suffisamment faible pour ne pas entraîner des coûts supplémentaires démesurés. Un des principaux facteurs de surestimation est la prise en compte de chemins d'exécution sémantiquement impossibles, dits infaisables, dans le calcul du WCET. Ceci est dû à l'analyse par énumération implicite des chemins ou Implicit Path Enumeration Technique (IPET) qui raisonne sur un surensemble des chemins d'exécution. Lorsque le chemin d'exécution pire-cas ou Worst-Case Execution Path (WCEP), correspondant au WCET estimé, porte sur un chemin infaisable, la précision de cette estimation est négativement affectée. Afin de parer à cette perte de précision, cette thèse propose une technique de détection de chemins infaisables, permettant l'amélioration de la précision des analyses statiques (dont celles pour le WCET) en les informant de l'infaisabilité de certains chemins du programme. Cette information est passée sous la forme de propriétés de flot de données formatées dans un langage d'annotation portable, FFX, permettant la communication des résultats de notre analyse de chemins infaisables vers d'autres analyses. Les méthodes présentées dans cette thèse sont inclues dans le framework OTAWA, développé au sein de l'équipe TRACES à l'IRIT. Elles usent elles-mêmes d'approximations pour représenter les états possibles de la machine en différents points du programme.

Real-time and embedded systems are becoming increasingly complex due to hardware evolution led by Moore's law. New development approaches are needed to master this complexity. The aspect-oriented approach allows separating functional and non-functional mechanisms when implementing a computer system. This makes it easier to implement and maintain these applications. It is within this setting that the research of this thesis takes place. We proposed a new approach, called AOM-RTSys, for the design of real-time systems. Indeed, a real-time system can be seen as a composition of functional and nonfunctional requirements. These include time, scheduling and synchronization constraints. From this point of view, any standard application can be transformed into a real-time application by "weaving" non-functional constraints. This approach has been applied in the field of object-oriented design of real-time systems, with UML and its profile MARTE. AOM-RTSys allows integrating real-time constraints, modeled with MARTE, into an initial model. The integration of the constraints is ensured by a weaving operation which consists in adding these constraints in well-defined locations by the designer using a weaving plane constituted by instances of weaving rules. A weaver called NOLE carries out the weaving operation. The Weaver inputs an initial model and a set of constraints in the form of one or more weaving planes in order to generate a target, real-time model. To ensure the proper functioning of the weaving process provided by the weaver NOLE, we opted for the integration of a process of verification and validation in the latter. Validation and verification of rule instances involve four main steps: Lexical, syntactic, semantic and aspect checking. These checks aim to detect and predict potential conflicts., Les systèmes temps réel et embarqués ne cessent de gagner en complexité grâce à l'évolution du matériel menée par la loi de Moore. Des nouvelles approches de développement sont nécessaires afin de maîtriser cette complexité. L'approche orientée aspect permet de séparer les mécanismes fonctionnels de ceux non-fonctionnels lors de l'implémentation d'un système informatique. Ceci facilite la mise en œuvre et la maintenance de ces applications. C'est dans ce contexte général que s'inscrivent les travaux de recherche de cette thèse. Nous avons proposé une nouvelle approche, appelée AOM-RTSys, pour la conception des systèmes temps réel. En effet, un système temps réel peut être vu comme une composition des besoins fonctionnels et ceux non fonctionnels. Ces derniers, regroupent des contraintes de temps, d'ordonnancement et de synchronisation. Partant de ce point de vue, toute application standard peut se transformer en une application temps réel par <> de contraintes non fonctionnelles. Cette approche a été appliquée dans le domaine de la conception orientée objet, des systèmes temps réel, avec UML et son profil MARTE. AOM-RTSys permet d'intégrer des contraintes temps réel, modélisées avec MARTE, dans un modèle initiale. L'intégration des contraintes est assurée par une opération de tissage qui consiste à ajouter ces contraintes dans des emplacements bien déterminés par le concepteur en utilisant un Plan de tissage constitué par des instances de règles de tissages. L'opération de tissage est assurée par un tisseur que nous avons appelé NOLE. Le tisseur prend en entrée un modèle initial et un ensemble de contraintes sous forme d'un ou plusieurs plans de tissages afin de générer un modèle temps réel cible. Afin d'assurer le bon fonctionnement du processus de tissage assuré par le tisseur NOLE, nous avons opté pour l'intégration d'un processus de vérification et de validation dans ce dernier. La validation et la vérification des instances de règles comporte quatre étapes principale ; la vérification lexicale, syntaxique, sémantique et d'aspect. Ces vérifications visent à détecter et prévoir les conflits possibles.

Real-time and embedded systems are becoming increasingly complex due to hardware evolution led by Moore's law. New development approaches are needed to master this complexity. The aspect-oriented approach allows separating functional and non-functional mechanisms when implementing a computer system. This makes it easier to implement and maintain these applications. It is within this setting that the research of this thesis takes place. We proposed a new approach, called AOM-RTSys, for the design of real-time systems. Indeed, a real-time system can be seen as a composition of functional and nonfunctional requirements. These include time, scheduling and synchronization constraints. From this point of view, any standard application can be transformed into a real-time application by "weaving" non-functional constraints. This approach has been applied in the field of object-oriented design of real-time systems, with UML and its profile MARTE. AOM-RTSys allows integrating real-time constraints, modeled with MARTE, into an initial model. The integration of the constraints is ensured by a weaving operation which consists in adding these constraints in well-defined locations by the designer using a weaving plane constituted by instances of weaving rules. A weaver called NOLE carries out the weaving operation. The Weaver inputs an initial model and a set of constraints in the form of one or more weaving planes in order to generate a target, real-time model. To ensure the proper functioning of the weaving process provided by the weaver NOLE, we opted for the integration of a process of verification and validation in the latter. Validation and verification of rule instances involve four main steps: Lexical, syntactic, semantic and aspect checking. These checks aim to detect and predict potential conflicts., Les systèmes temps réel et embarqués ne cessent de gagner en complexité grâce à l'évolution du matériel menée par la loi de Moore. Des nouvelles approches de développement sont nécessaires afin de maîtriser cette complexité. L'approche orientée aspect permet de séparer les mécanismes fonctionnels de ceux non-fonctionnels lors de l'implémentation d'un système informatique. Ceci facilite la mise en œuvre et la maintenance de ces applications. C'est dans ce contexte général que s'inscrivent les travaux de recherche de cette thèse. Nous avons proposé une nouvelle approche, appelée AOM-RTSys, pour la conception des systèmes temps réel. En effet, un système temps réel peut être vu comme une composition des besoins fonctionnels et ceux non fonctionnels. Ces derniers, regroupent des contraintes de temps, d'ordonnancement et de synchronisation. Partant de ce point de vue, toute application standard peut se transformer en une application temps réel par <> de contraintes non fonctionnelles. Cette approche a été appliquée dans le domaine de la conception orientée objet, des systèmes temps réel, avec UML et son profil MARTE. AOM-RTSys permet d'intégrer des contraintes temps réel, modélisées avec MARTE, dans un modèle initiale. L'intégration des contraintes est assurée par une opération de tissage qui consiste à ajouter ces contraintes dans des emplacements bien déterminés par le concepteur en utilisant un Plan de tissage constitué par des instances de règles de tissages. L'opération de tissage est assurée par un tisseur que nous avons appelé NOLE. Le tisseur prend en entrée un modèle initial et un ensemble de contraintes sous forme d'un ou plusieurs plans de tissages afin de générer un modèle temps réel cible. Afin d'assurer le bon fonctionnement du processus de tissage assuré par le tisseur NOLE, nous avons opté pour l'intégration d'un processus de vérification et de validation dans ce dernier. La validation et la vérification des instances de règles comporte quatre étapes principale ; la vérification lexicale, syntaxique, sémantique et d'aspect. Ces vérifications visent à détecter et prévoir les conflits possibles.

Real-time systems must conform to requirements of correctness and safety, which requires testing them. In this thesis, we propose a method that allows to force an execution of a real-time system so as to reach a chosen state. This technique can be used to test real-time systems in situations where the chosen state could be hard to reach when dealing with the input sequence of the system alone. One example of an application could be that of a state that triggers a redundancy mechanism when reached, the execution of which would be infrequent, but that still requires testing. In this use case, it is effectively fault injection in the system. This solution is based on an offline analysis of a set of behavioral models of the system, using the formalism of durational Kripke structures. The models of the system are obtained through a Model Driven Engineering approach, and present the behaviors of the tasks from the point of view of the real-time operating system. Using a parametrization, transformation and composition of the models, we perform a parametric analysis of the resulting Time Petri net. Thanks to the result of this analysis, we establish a set of delays to be added to the execution of the system so as to reach the chosen state. With the help of an embedded model of the different tasks of the system, and through the means of a controller embedded in the real-time operating system, we perform the runtime enforcement of the system so as to make it reach the chosen state, and possibly allow for testing the execution starting from this state. This thesis details the formalisms used to model the application, the way in which the models are modified and analyzed to obtain the execution delays, as well as the implementation in a real-time operating system: TrampolineRTOS.; Les systèmes temps réel doivent répondre à des contraintes d’exactitude et de sureté de fonctionnement, ce qui nécessite de pouvoir les tester. Dans ces travaux de thèse, nous proposons une méthode permettant de forcer une exécution d’un système temps réel de manière à atteindre un état choisi. Cette technique peut permettre le test de systèmes temps réel dans des situations où l’état choisi pourrait être compliqué à atteindre en ne manipulant que les données d’entrée du système. Un exemple d’application pourrait être celui d’un état déclenchant un redondant, et dont l’exécution serait peu fréquente, mais que l’on souhaite néanmoins tester. Dans ce cas d’utilisation, il s’agit effectivement de l’injection de fautes dans le système. Cette solution est basée sur une analyse hors-ligne d’un ensemble de modèles comportementaux du système, utilisant le formalisme des structures de Kripke à durée. Les modèles du système sont issu d’une démarche IDM, et présentent le comportement des tâches du point de vue du système d’exploitation temps réel. À l’aide d’une paramétrisation, transformation et composition des modèles, nous effectuons une analyse paramétrée du réseau de Petri temporel résultant. Grâce au résultat de cette analyse, nous déterminons un ensemble de délais à ajouter à l’exécution du système afin de forcer le système à atteindre l’état choisi. En utilisant un modèle embarqué des différentes tâches, et par le biais d’un contrôleur intégré au système d’exploitation temps réel, nous effectuons le forçage en ligne du système afin de permettre l’atteinte de l’état choisi, et éventuellement le test de l’exécution découlant de cet état. Ce travail de thèse détaille les formalismes utilisés pour modéliser l’application, la manière dont ils sont modifiés et analysés pour obtenir les délais d’exécution, ainsi que l’implémentation dans un système d’exploitation temps réel : TrampolineRTOS.

Real-time systems must conform to requirements of correctness and safety, which requires testing them. In this thesis, we propose a method that allows to force an execution of a real-time system so as to reach a chosen state. This technique can be used to test real-time systems in situations where the chosen state could be hard to reach when dealing with the input sequence of the system alone. One example of an application could be that of a state that triggers a redundancy mechanism when reached, the execution of which would be infrequent, but that still requires testing. In this use case, it is effectively fault injection in the system. This solution is based on an offline analysis of a set of behavioral models of the system, using the formalism of durational Kripke structures. The models of the system are obtained through a Model Driven Engineering approach, and present the behaviors of the tasks from the point of view of the real-time operating system. Using a parametrization, transformation and composition of the models, we perform a parametric analysis of the resulting Time Petri net. Thanks to the result of this analysis, we establish a set of delays to be added to the execution of the system so as to reach the chosen state. With the help of an embedded model of the different tasks of the system, and through the means of a controller embedded in the real-time operating system, we perform the runtime enforcement of the system so as to make it reach the chosen state, and possibly allow for testing the execution starting from this state. This thesis details the formalisms used to model the application, the way in which the models are modified and analyzed to obtain the execution delays, as well as the implementation in a real-time operating system: TrampolineRTOS.; Les systèmes temps réel doivent répondre à des contraintes d’exactitude et de sureté de fonctionnement, ce qui nécessite de pouvoir les tester. Dans ces travaux de thèse, nous proposons une méthode permettant de forcer une exécution d’un système temps réel de manière à atteindre un état choisi. Cette technique peut permettre le test de systèmes temps réel dans des situations où l’état choisi pourrait être compliqué à atteindre en ne manipulant que les données d’entrée du système. Un exemple d’application pourrait être celui d’un état déclenchant un redondant, et dont l’exécution serait peu fréquente, mais que l’on souhaite néanmoins tester. Dans ce cas d’utilisation, il s’agit effectivement de l’injection de fautes dans le système. Cette solution est basée sur une analyse hors-ligne d’un ensemble de modèles comportementaux du système, utilisant le formalisme des structures de Kripke à durée. Les modèles du système sont issu d’une démarche IDM, et présentent le comportement des tâches du point de vue du système d’exploitation temps réel. À l’aide d’une paramétrisation, transformation et composition des modèles, nous effectuons une analyse paramétrée du réseau de Petri temporel résultant. Grâce au résultat de cette analyse, nous déterminons un ensemble de délais à ajouter à l’exécution du système afin de forcer le système à atteindre l’état choisi. En utilisant un modèle embarqué des différentes tâches, et par le biais d’un contrôleur intégré au système d’exploitation temps réel, nous effectuons le forçage en ligne du système afin de permettre l’atteinte de l’état choisi, et éventuellement le test de l’exécution découlant de cet état. Ce travail de thèse détaille les formalismes utilisés pour modéliser l’application, la manière dont ils sont modifiés et analysés pour obtenir les délais d’exécution, ainsi que l’implémentation dans un système d’exploitation temps réel : TrampolineRTOS.

Embedded systems dedicated to aeronautics or automotive interact permanently with their environment. They get information from their sensors, process the data and react with their actuators. Such systems have to execute the functionalities correctly, but also to process them within the allocated time. This feature classifies those systems in the category of real-time systems. In the cited domains, those functionalities are originally defined accordingly to the dynamics of the system and their number can reach several thousand. The real-time operating systems, software which handles the processing of those functionalities on the hardware, generally limit the number of functionalities, due to the overhead caused by their management. In this work, we are interested in techniques that reduce the number of those functionalities so to overstep those restrictions. We propose clustering algorithms that ensure that timing constraints are respected. These methods are applied to monoprocessor and multiprocessor architecture with communicating processes.; Les systèmes embarqués des domaines de l'aéronautique ou de l'automobile sont en interaction permanente avec leur environnement. Ils récupèrent de l'information depuis leurs capteurs, traitent les données et réagissent par le biais de leurs actionneurs. Ces systèmes critiques se doivent non seulement de produire des résultats corrects du point de vue logique mais aussi de les réaliser dans le temps imparti. Cette particularité les classe dans la famille des systèmes temps réel. Dans les domaines cités, les fonctionnalités sont à l'origine définies au regard de la dynamique du système et leur nombre peut atteindre plusieurs milliers. Les systèmes d'exploitation temps réel, logiciels responsables du traitement de ces fonctionnalités sur le matériel, limitent généralement le nombre de traitements implantables, en raison des surcoûts engendrés par leur gestion. Dans ce travail, nous nous intéressons donc à des techniques de réduction du nombre de ces traitements, de manière à passer outre les limitations des systèmes d'exploitation temps réel. Nous proposons des algorithmes de regroupement qui assurent que les contraintes de temps soient respectées. Ces méthodes visent des architectures monoprocesseurs et multiprocesseurs pour des traitements communicants.

The work of this thesis lies in the context of real-time embedded systems. These systems require significant effort for validation and verification. As part of this thesis, we are particularly interested in validation through simulation. This can be done at many levels of abstraction, from high-level model of the application to binary code. We are in the latter case, only able to give accurate results close to the processor cycle.Harmless is a Hardware Architecture Description Language (HADL). It generates a functional simulator (ISS) and a temporal simulator cycle-accurate (CAS). As part of real-time systems, it is this second type of simulators that interests us. With respect to the ISS, CAS has the major drawback to be very slow at runtime.One way to improve the speed of execution is to use the compiled simulation. There are two main types of implementation of the simulation: interpreted simulation and compiled simulation. If interpreted simulator behaves as an interpreter for the program to run, a compiled simulator requires a compilation phase of the program. It allows a better execution speed to the detriment of flexibility in the development chain.It is this technique that we introduce in the context of CAS. Coupled with a technique of abstraction of the program, we will show that we can improve the simulation speed by more than 50% compared to the interpreted CAS.; Le travail de cette thèse s'inscrit dans le contexte des systèmes embarqués temps réel. Ces systèmes exigent d'importants efforts pour leur validation et leur vérification. Dans le cadre de cette thèse, nous nous intéressons plus particulièrement à la validation par simulation. Celle-ci peut se faire à de nombreux niveaux d'abstraction, depuis le haut niveau du modèle de l'application jusqu'au code binaire. Nous nous situons dans ce dernier cas, seul capable de donner des résultats précis au cycle près.Harmless est un langage de description d'architectures. Il permet de générer un simulateur fonctionnel (ISS) et un simulateur temporel précis au cycle près (CAS). Dans le cadre des systèmes temps réel, c'est ce deuxième type de simulateurs qui nous intéresse. Relativement à l'ISS, un CAS présente l'inconvénient majeur de se montrer très lent à l'exécution.Un moyen d'améliorer la rapidité d'exécution est d'utiliser la simulation compilée. On distingue deux grands types d'implantation de la simulation : la simulation interprétée et la simulation compilée. Si un simulateur interprété se comporte comme un interpréteur du programme à exécuter, un simulateur compilé nécessite une phase de compilation du programme. Il permet une meilleure vitesse d'exécution, au détriment de la souplesse dans la chaîne de développement.C'est cette technique que nous introduirons dans le cadre des CAS. Couplé à une technique d'abstraction du programme, nous montrerons que l'on peut améliorer la vitesse de simulation de plus de 50% en comparaison du CAS interprété.

National audience; Current systems are becoming every day more and more complex, being both distributed and real-timed. Conventional methods responsible for guaranteeing dependability, such as testing, fault injection or formal methods are no longer sufficient. In order to process any errors when they appear in a given distributed system, we want to implement a software monitoring it and capable of launching an alert when the system does not respect anymore its specification. Such a program is called monitor. A monitor interpret information received from the system as messages (these messages are called events) and propose a diagnosis. The objective of this thesis is to set in place a monitor for a distributed real-time verification of temporal properties. In particular we want our monitor to be able to check up a maximum of properties with a minimum of information. Thus, our tools are designed to work perfectly even if the observation is imperfect, that is to say, even if some events are late or never received. We have also managed to achieve this goal through a highly distributed protocol. To verify the feasibility and effectiveness of our approach, we have established an implementation called Minotor who was found to have very good performance. Finally, we detailed a set of properties, expressed in our formalism, to show it’s expressiveness.; Les systèmes actuels deviennent chaque jour de plus en plus complexe; à la distribution s’ajoutent les contraintes temps réel. Les méthodes classiques en charge de garantir la sûreté de fonctionnement, comme le test, l’injection de fautes ou les méthodes formelles ne sont plus suffisantes à elles seules. Afin de pouvoir traiter les éventuelles erreurs lors de leur apparition dans un système distribué donné, nous désirons mettre en place un programme, surveillant ce système, capable de lancer une alerte lorsque ce dernier s’éloigne de ses spécifications ; un tel programme est appelé superviseur (ou moniteur). Le fonctionnement d’un superviseur consiste simplement à interpréter un ensemble d’informations provenant du système sous forme de message, que l’on qualifiera d’évènement, et d’en déduire un diagnostic. L’objectif de cette thèse est de mettre un place un superviseur distribué permettant de vérifier en temps réel des propriétés temporelles. En particulier nous souhaitons que notre moniteur soit capable de vérifier un maximum de propriétés avec un minimum d’information. Ainsi notre outil est spécialement conçu pour fonctionner parfaitement même si l’observation est imparfaite, c’est-à-dire, même si certains évènements arrivent en retard ou s’ils ne sont jamais reçus. Nous avons de plus cherché à atteindre cet objectif de manière distribuée pour des raisons évidentes de performance et de tolérance aux fautes. Nous avons ainsi proposé un protocole distribuable fondé sur l’exécution répartie d’un réseau de Petri temporisé. Pour vérifier la faisabilité et l’efficacité de notre approche, nous avons mis en place une implémentation appelée Minotor qui s’est révélée avoir de très bonnes performances. Enfin, pour montrer l’expressivité du formalisme utilisé pour exprimer les spécifications que l’on désire vérifier, nous avons détaillé un ensemble de propriétés sous forme de réseaux de Petri à double sémantique introduite dans cette thèse (l’ensemble des transitions étant partitionné en deux catégories de transitions, chacune de ces parties ayant sa propre sémantique)

This Work deals with te defintion of a new methodology called DRIM for the development of real-time embedded systems following the Model-Driven development paradigm., Les travaux présentés dans cette thèse s’inscrivent dans le cadre du développement logiciel des systèmes temps réel embarqués. Nous définissons dans ce travail une méthodologie nommée DRIM (Design Refinement toward Implementation Methodology). Cetteméthodologie permet de guider le déploiement des applications temps réel sur différentssystèmes d’exploitation temps réel (RTOS) en suivant la ligne de l’Ingénierie Dirigée parles Modèles (IDM) et en assurant le respect des contraintes de temps après le déploiement.L’automatisation de la méthodologie DRIM montre sa capacité à détecter les descriptionsnon-implémentables de l’application, réalisées au niveau conception, pour un RTOS donné,ce qui présente l’avantage de réduire le temps de mise sur le marché (time-to-market) d’unepart et de guider l’utilisateur pour un choix approprié du RTOS cible d’autre part.

The work of this thesis lies in the context of real-time embedded systems. These systems require significant effort for validation and verification. As part of this thesis, we are particularly interested in validation through simulation. This can be done at many levels of abstraction, from high-level model of the application to binary code. We are in the latter case, only able to give accurate results close to the processor cycle.Harmless is a Hardware Architecture Description Language (HADL). It generates a functional simulator (ISS) and a temporal simulator cycle-accurate (CAS). As part of real-time systems, it is this second type of simulators that interests us. With respect to the ISS, CAS has the major drawback to be very slow at runtime.One way to improve the speed of execution is to use the compiled simulation. There are two main types of implementation of the simulation: interpreted simulation and compiled simulation. If interpreted simulator behaves as an interpreter for the program to run, a compiled simulator requires a compilation phase of the program. It allows a better execution speed to the detriment of flexibility in the development chain.It is this technique that we introduce in the context of CAS. Coupled with a technique of abstraction of the program, we will show that we can improve the simulation speed by more than 50% compared to the interpreted CAS., Le travail de cette thèse s'inscrit dans le contexte des systèmes embarqués temps réel. Ces systèmes exigent d'importants efforts pour leur validation et leur vérification. Dans le cadre de cette thèse, nous nous intéressons plus particulièrement à la validation par simulation. Celle-ci peut se faire à de nombreux niveaux d'abstraction, depuis le haut niveau du modèle de l'application jusqu'au code binaire. Nous nous situons dans ce dernier cas, seul capable de donner des résultats précis au cycle près.Harmless est un langage de description d'architectures. Il permet de générer un simulateur fonctionnel (ISS) et un simulateur temporel précis au cycle près (CAS). Dans le cadre des systèmes temps réel, c'est ce deuxième type de simulateurs qui nous intéresse. Relativement à l'ISS, un CAS présente l'inconvénient majeur de se montrer très lent à l'exécution.Un moyen d'améliorer la rapidité d'exécution est d'utiliser la simulation compilée. On distingue deux grands types d'implantation de la simulation : la simulation interprétée et la simulation compilée. Si un simulateur interprété se comporte comme un interpréteur du programme à exécuter, un simulateur compilé nécessite une phase de compilation du programme. Il permet une meilleure vitesse d'exécution, au détriment de la souplesse dans la chaîne de développement.C'est cette technique que nous introduirons dans le cadre des CAS. Couplé à une technique d'abstraction du programme, nous montrerons que l'on peut améliorer la vitesse de simulation de plus de 50% en comparaison du CAS interprété.

The feature content of new cars is increasing dramatically, which involves more demanding requirements. AUTOSAR (AUTomotive Open System ARchi- tecture) - an open and standardized automotive soft- ware architecture jointly developed by vehicle makers, suppliers and tool developers - enables to benefit from new hardware technology by considering multicore architectures. Despite their undeniable advantages in terms of performance, multicore architectures bring a set of problems that may jeopardize the dependability of embedded applications (ISO 26262 is the dependability standard for automotive). For example, multicore scheduling requires to cope with task dependencies constraints, and data consistency must be ensured for inter core communication. First, to meet the task dependencies, safety requirements on data flows are used to generate monitors. The tool Enforcer has been built in order to do that. A service based on runtime verification uses these monitors (injected in the kernel of the operating system) checks if the system behaves as expected. Finally, we propose an alternative locking mechanism for inter core data sharing. The wait-free protocol STM- HRT (Software Transactional Memory for Hard Real- Time systems), based on transactional memory, aims at increasing the robustness of multicore applications.; Les besoins en ressources CPU dans l'automobile sont en constante augmentation. Le standard de développement logiciel AUTOSAR (AUTomotive Open System ARchitecture) - développé au sein d'un consortium regroupant des fabricants de véhicules et des sous-traitants - offre désormais la possibilité de s'orienter vers de nouvelles architectures : les microcontrôleurs multicœur. Leur introduction au sein des systèmes embarqués critiques apporte un lot de problèmes allant à l'encontre des objectifs de sûreté de fonctionnement ISO 26262. Par exemple, le parallélisme des cœurs impose de maîtriser l'ordonnancement pour respecter les contraintes de dépendance entre les tâches, et le partage des données intercœur doit être effectué en assurant leur cohérence. Notre approche s'articule en deux volets. Pour vérifier les contraintes de dépendance entre les tâches, les exigences sur les flots de données sont utilisées pour synthétiser des moniteurs à l'aide de l'outil Enforcer. Un service de vérification en ligne utilise ces moniteurs (injectés dans le noyau du système d'exploitation) pour vérifier le comportement du système. Enfin, pour maîtriser le partage des données intercœur, nous proposons une alternative aux protocoles bloquants. Le protocole wait-free STM-HRT (Software Transactional Memory for Hard Real-Time systems), est conçu sur les principes des mémoires transactionnelles afin d'améliorer la robustesse des systèmes.

Critical tasks in the context of real-time systems submit to both timing and correctness constraints. Whence, the validation of a real-time system rely on the estimation of its tasks’ Worst case execution times. Resource sharing, as it occurs on multicore architectures, hinders the computation of such estimates. The timing behaviour of a task is impacted by its concurrents, whether because of resource access arbitration or concurrent modifications of a resource state. This study focuses on estimating the contribution of the memory hierarchy to tasks’ worst case execution time. Existing analysis methods, defined for instruction caches, are extended to support private and shared data caches, hence allowing for the analysis of rich memory hierarchies. Cache bypass is then used to reduce the pressure laid by concurrent tasks on shared caches levels. We propose different bypass heuristics, based on the capture of cache blocks’ reuse between memory accesses. Our second proposal is the Preti partitioning scheme which allows for the allocation to tasks of a cache space, free from inter-task conflicts. Preti offers the added benefit of providing for average-case performance to non-critical tasks concurrent to real-time ones on hybrid criticality systems.; Les tâches critiques en systèmes temps-réel sont soumises à des contraintes temporelles et de correction. La validation d'un tel système repose sur l'estimation du comportement temporel au pire cas de ses tâches. Le partage de ressources, inhérent aux architectures multi-cœurs, entrave le calcul de ces estimations. Le comportement temporel d'une tâche dépend de ses rivales du fait de l'arbitrage de l'accès aux ressources ou de modifications concurrentes de leur état. Cette étude vise à l'estimation de la contribution temporelle de la hiérarchie mémoire au pire temps d'exécution de tâches critiques. Les méthodes existantes, pour caches d'instructions, sont étendues afin de supporter caches de données privés et partagés, et permettre l'analyse de hiérarchies mémoires riches. Le court-circuitage de cache est ensuite utilisé pour réduire la pression sur les caches partagés. Nous proposons à cette fin différentes heuristiques basées sur la capture de la réutilisation de blocs de cache entre différents accès mémoire. Notre seconde proposition est la politique de partitionnement Preti qui permet l'allocation d'un espace sans conflits à une tâche. Preti favorise aussi les performances de tâches non critiques concurrentes aux temps-réel dans les systèmes de criticité hybride.

Thèse confidentielle jusqu’au 23 octobre 2022; Current space launchers, and particularly Ariane 5, use the deterministic network MIL-STD-1553B. According to the new objectives of cost and system mass reduction and of multimedia traffic support, this technology is not optimal anymore. Among the potential candidates, this thesis highlights the fact that such objectives can be achieved through the use of Ethernet standard based on components-on-the-shelf. The first contribution focuses on time performance evaluation of switched architectures. The gain and limits related to the communication mode (from master/slaves to producers/consummers) and future avionic distribution are studied. This study relies on a deterministic evaluation of the end-to-end delay by using network calculus, simulations and experiments. These results are validated with two switched architectures by using a scenario considered as representative of current flights. The second contribution is the network availability improvement. A real-time path reconfiguration strategy is proposed through active network supervision. Based on critical requirements, it is also suggested to use multiple spanning-trees for anticipating network element failures. The last contribution deals with the issue that in switched and segmented architectures it is not possible to collect all the traffic as in a bus. In order to do so, this thesis introduces the configurations under which a clock synchronization protocol could contribute to generate a single network trace from many collecting points. This work will enable to identify the tests for a future Ethernet standard validation in the framework of space launchers; Les lanceurs spatiaux actuels, et en particulier Ariane 5, utilisent le réseau déterministe MIL-STD-1553B. Compte tenu des nouveaux objectifs de réduction des coûts et de la masse du système global ainsi que du support de trafic de télémesure multimédia, cette technologie n'est plus forcément optimale. Parmi les différents candidats de remplacement, cette thèse met en évidence les capacités du standard Ethernet à répondre à ces nouveaux objectifs tout en s'appuyant sur une utilisation de composants matériels et d'outils de développement existants à moindre coût (COTS). La première contribution porte sur l'évaluation de performances temporelles des architectures commutées. Les travaux mettent ainsi en évidence les gains et limites liés au choix d'une part du mode de communication (de maître/esclaves à producteurs/consommateur) et d'autre part à une future distribution de l'avionique. Pour cela, cette étude s'appuie sur une évaluation déterministe des délais de bout en bout par calcul réseau, simulations et expérimentations. Ces résultats ont été validés pour deux architectures commutées pour un scénario représentatif des vols actuels. La seconde contribution concerne l'amélioration de la disponibilité du système de communication. Il est proposé une stratégie de reconfiguration "temps réel" des chemins par supervision active du réseau. Dans le cadre d'exigences critiques, il est également proposé l'utilisation d'arbres couvrants multiples permettant d'anticiper la défaillance d'éléments d'interconnexion. Enfin, le choix d'architectures commutées et segmentées ne permet plus d'observer en tout point le réseau comme sur un bus. Pour cela, cette thèse met en avant les conditions et performances dans lesquelles un protocole de synchronisation d'horloges pourra contribuer à générer à partir de plusieurs points de captures une trace unique des échanges sur le réseau. Ce travail permettra d'identifier les tests pour une future validation du standard Ethernet pour les lanceurs spatiaux

In this thesis, we studied the fault-tolerant multiprocessor hard real-time scheduling of non-preemptive strict periodic tasks which could be combined with preemptive tasks. We proposed solutions that we implemented into the SynDEx software, then we tested these solutions on an electric vehicle following. First, we present a state of the art on real-time embedded systems and more specificaly on the classical uniprocesseur and multiprocessor scheduling of preemptive periodic tasks. Since we were interested in critical real-time control applications, sensor/actuators computations and processes control must not have jitter. For these reasons, we also presented a state of the art of the scheduling of non-preemptive strict periodic tasks. Also, we presented a state of the art on fault-tolerance. As we were interested in hardware faults, we presented two types of redundancies: software and hardware. Presently, existing schedulability analyses of non-preemptive strict periodic tasks have low schedulability success ratios, thus we proposed a new schedulability analysis. We first presented a scheduling strategy which consists in scheduling a candidate task whereas a task set is already scheduled. We used this strategy to solve the problem of scheduling harmonic and non-harmonic tasks, and we proposed new schedulability conditions. In order to improve the scheduling success ratio of non-preemptive strict periodic tasks, we proposed to keep some non preemptive strict periodic tasks and to add preemptive periodic tasks which are neither dedicated to input/output nor to control. Then, we studied the multiprocessor scheduling problem using the partitioned approach. In order to solve this problem we proposed three algorithms. The first algorithm performs a uniprocessor schedulability analysis and assigns each task according to a schedulability condition to possibly several processors. The second algorithm transforms the dependent task graph into an unrolled graph where each task is repeated a number of times equal to the ratio between the LCM of all tasks periods and its period. The third algorithm exploits the two precedent algorithms to choose, with a cost function, on which processor it will schedule a task previously assigned to several processors, and it computes the first start times of each task. Then, we extended the multiprocessor schedulability analysis to be tolerant to processor and bus media faults. We proposed an algorithm which transforms the dependent task graph by adding redundant tasks, redundant dependencies, and selecting tasks. The latter allow to choose the redundant task allocated to non faulty processors. We studied separately the processor fault-tolerance problem, the bus fault-tolerant problem, and finally both processor and bus fault-tolerant problem. Finally, we extended the schedulability analysis algorithms, the unrolling algorithm and the scheduling algorithm to be fault-tolerant. Then, we presented the improvements provided to the SynDEx software for the schedulability analysis algorithm, the scheduling algorithm and the fault-tolerance algorithm. Finally, we conducted some experiments on the electric vehicle following called CyCab. We modified the hardware architecture of the CyCab to integrate dsPICs microcontrolers, and we tested dsPICs and CAN buses fault-tolerant on the CyCabs following.; Nous nous sommes intéressés dans cette thèse au problème d'ordonnancement temps réel dur multiprocesseur tolérant aux fautes pour des tâches non préemptives périodiques strictes pouvant être combinées avec des tâches préemptives. Nous avons proposé des solutions à ce problème et les avons implantées dans le logiciel SynDEx puis nous les avons testées sur une application de suivi de véhicules électriques CyCabs. Nous avons d'abord présenté un état de l'art sur les systèmes temps réel embarqués et plus précisément sur l'ordonnancement classique monoprocesseur et multiprocesseur de tâches préemptives périodiques. Comme nous nous intéressons aux applications de contrôle/commande temps réel critiques, les traitements de capteurs/actionneurs et les traitements de commande de procédés ne doivent pas avoir de gigue. Pour ces raisons nous avons aussi présenté un état de l'art sur l'ordonnancement des tâches non-préemptives périodiques strictes. Par ailleurs nous avons présenté un état de l'art sur la tolérance aux fautes. Comme nous nous sommes intéressés aux fautes matérielles, nous avons présenté les deux types de redondances : logicielle et matérielle. Les analyses d'ordonnançabilité existantes de tâches non préemptives périodiques strictes dans le cas monoprocesseur ayant de faibles taux de succès d'ordonnancement, nous avons proposé une nouvelle analyse d'ordonnançabilité. Nous avons présenté une stratégie d'ordonnancement qui consiste à ordonnancer une tâche candidate avec un ensemble de tâches déjà ordonnancée. Nous avons utilisé cette stratégie pour ordonnancer des tâches harmoniques et non harmoniques, et nous avons proposé des nouvelles conditions d'ordonnançabilité. Afin d'améliorer le taux de succès d'ordonnancement de tâches non préemptives périodiques strictes, nous avons proposé de garder certaines tâches non préemptives périodiques strictes et d'y ajouter des tâches préemptives périodiques non strictes ne traitant ni les entrées/sorties ni le contrôle/commande. Nous avons ensuite étudié le problème d'ordonnancement multiprocesseur selon une approche partitionnée. Ce problème est résolu en utilisant trois algorithmes. Le premier algorithme effectue une analyse d'ordonnançabilité monoprocesseur et assigne chaque tâche sur éventuellement plusieurs processeurs. Le deuxième algorithme transforme le graphe de tâches dépendantes en un graphe déroulé où chaque tâche est répétée un nombre de fois égal au rapport entre le PPCM des autres périodes et sa période. Le troisième algorithme exploite les résultats des deux algorithmes précédents pour choisir sur quel processeur ordonnancer une tâche et calculer sa date de début d'exécution. Nous avons ensuite proposé d'étendre l'étude d'ordonnançabilité temps réel multiprocesseur précédente pour qu'elle soit tolérante aux fautes de processeurs et de bus de communication. Nous avons proposé un algorithme qui permet de transformer le graphe de tâches dépendantes en y ajoutant des tâches et des dépendances de données répliques et des tâches de sélection permettant de choisir la réplique de tâches allouée à un processeur non fautif. Nous avons étudié séparément les problèmes de tolérance aux fautes pour des processeurs, des bus de communication, et enfin des processeur et des bus de communication. Finalement nous avons étendu les trois algorithmes vus précédemment d'analyse d'ordonnançabilité, de déroulement et d'ordonnancement afin qu'ils soient tolérants aux fautes. Nous avons ensuite présenté les améliorations apportées au logiciel SynDEx tant sur le plan de l'analyse d'ordonnançabilité et l'algorithme d'ordonnancement, que sur le plan de la tolérance aux fautes. Finalement nous avons présenté les travaux expérimentaux concernant l'application de suivi de CyCabs. Nous avons modifié l'architecture des CyCabs en y intégrant des microcontrôleurs dsPICs et nous avons testé la tolérance aux fautes de dsPICs et du bus CAN sur une application de suivi de CyCab.

In this thesis, we studied the fault-tolerant multiprocessor hard real-time scheduling of non-preemptive strict periodic tasks which could be combined with preemptive tasks. We proposed solutions that we implemented into the SynDEx software, then we tested these solutions on an electric vehicle following. First, we present a state of the art on real-time embedded systems and more specificaly on the classical uniprocesseur and multiprocessor scheduling of preemptive periodic tasks. Since we were interested in critical real-time control applications, sensor/actuators computations and processes control must not have jitter. For these reasons, we also presented a state of the art of the scheduling of non-preemptive strict periodic tasks. Also, we presented a state of the art on fault-tolerance. As we were interested in hardware faults, we presented two types of redundancies: software and hardware. Presently, existing schedulability analyses of non-preemptive strict periodic tasks have low schedulability success ratios, thus we proposed a new schedulability analysis. We first presented a scheduling strategy which consists in scheduling a candidate task whereas a task set is already scheduled. We used this strategy to solve the problem of scheduling harmonic and non-harmonic tasks, and we proposed new schedulability conditions. In order to improve the scheduling success ratio of non-preemptive strict periodic tasks, we proposed to keep some non preemptive strict periodic tasks and to add preemptive periodic tasks which are neither dedicated to input/output nor to control. Then, we studied the multiprocessor scheduling problem using the partitioned approach. In order to solve this problem we proposed three algorithms. The first algorithm performs a uniprocessor schedulability analysis and assigns each task according to a schedulability condition to possibly several processors. The second algorithm transforms the dependent task graph into an unrolled graph where each task is repeated a number of times equal to the ratio between the LCM of all tasks periods and its period. The third algorithm exploits the two precedent algorithms to choose, with a cost function, on which processor it will schedule a task previously assigned to several processors, and it computes the first start times of each task. Then, we extended the multiprocessor schedulability analysis to be tolerant to processor and bus media faults. We proposed an algorithm which transforms the dependent task graph by adding redundant tasks, redundant dependencies, and selecting tasks. The latter allow to choose the redundant task allocated to non faulty processors. We studied separately the processor fault-tolerance problem, the bus fault-tolerant problem, and finally both processor and bus fault-tolerant problem. Finally, we extended the schedulability analysis algorithms, the unrolling algorithm and the scheduling algorithm to be fault-tolerant. Then, we presented the improvements provided to the SynDEx software for the schedulability analysis algorithm, the scheduling algorithm and the fault-tolerance algorithm. Finally, we conducted some experiments on the electric vehicle following called CyCab. We modified the hardware architecture of the CyCab to integrate dsPICs microcontrolers, and we tested dsPICs and CAN buses fault-tolerant on the CyCabs following.; Nous nous sommes intéressés dans cette thèse au problème d'ordonnancement temps réel dur multiprocesseur tolérant aux fautes pour des tâches non préemptives périodiques strictes pouvant être combinées avec des tâches préemptives. Nous avons proposé des solutions à ce problème et les avons implantées dans le logiciel SynDEx puis nous les avons testées sur une application de suivi de véhicules électriques CyCabs. Nous avons d'abord présenté un état de l'art sur les systèmes temps réel embarqués et plus précisément sur l'ordonnancement classique monoprocesseur et multiprocesseur de tâches préemptives périodiques. Comme nous nous intéressons aux applications de contrôle/commande temps réel critiques, les traitements de capteurs/actionneurs et les traitements de commande de procédés ne doivent pas avoir de gigue. Pour ces raisons nous avons aussi présenté un état de l'art sur l'ordonnancement des tâches non-préemptives périodiques strictes. Par ailleurs nous avons présenté un état de l'art sur la tolérance aux fautes. Comme nous nous sommes intéressés aux fautes matérielles, nous avons présenté les deux types de redondances : logicielle et matérielle. Les analyses d'ordonnançabilité existantes de tâches non préemptives périodiques strictes dans le cas monoprocesseur ayant de faibles taux de succès d'ordonnancement, nous avons proposé une nouvelle analyse d'ordonnançabilité. Nous avons présenté une stratégie d'ordonnancement qui consiste à ordonnancer une tâche candidate avec un ensemble de tâches déjà ordonnancée. Nous avons utilisé cette stratégie pour ordonnancer des tâches harmoniques et non harmoniques, et nous avons proposé des nouvelles conditions d'ordonnançabilité. Afin d'améliorer le taux de succès d'ordonnancement de tâches non préemptives périodiques strictes, nous avons proposé de garder certaines tâches non préemptives périodiques strictes et d'y ajouter des tâches préemptives périodiques non strictes ne traitant ni les entrées/sorties ni le contrôle/commande. Nous avons ensuite étudié le problème d'ordonnancement multiprocesseur selon une approche partitionnée. Ce problème est résolu en utilisant trois algorithmes. Le premier algorithme effectue une analyse d'ordonnançabilité monoprocesseur et assigne chaque tâche sur éventuellement plusieurs processeurs. Le deuxième algorithme transforme le graphe de tâches dépendantes en un graphe déroulé où chaque tâche est répétée un nombre de fois égal au rapport entre le PPCM des autres périodes et sa période. Le troisième algorithme exploite les résultats des deux algorithmes précédents pour choisir sur quel processeur ordonnancer une tâche et calculer sa date de début d'exécution. Nous avons ensuite proposé d'étendre l'étude d'ordonnançabilité temps réel multiprocesseur précédente pour qu'elle soit tolérante aux fautes de processeurs et de bus de communication. Nous avons proposé un algorithme qui permet de transformer le graphe de tâches dépendantes en y ajoutant des tâches et des dépendances de données répliques et des tâches de sélection permettant de choisir la réplique de tâches allouée à un processeur non fautif. Nous avons étudié séparément les problèmes de tolérance aux fautes pour des processeurs, des bus de communication, et enfin des processeur et des bus de communication. Finalement nous avons étendu les trois algorithmes vus précédemment d'analyse d'ordonnançabilité, de déroulement et d'ordonnancement afin qu'ils soient tolérants aux fautes. Nous avons ensuite présenté les améliorations apportées au logiciel SynDEx tant sur le plan de l'analyse d'ordonnançabilité et l'algorithme d'ordonnancement, que sur le plan de la tolérance aux fautes. Finalement nous avons présenté les travaux expérimentaux concernant l'application de suivi de CyCabs. Nous avons modifié l'architecture des CyCabs en y intégrant des microcontrôleurs dsPICs et nous avons testé la tolérance aux fautes de dsPICs et du bus CAN sur une application de suivi de CyCab.

/, Actuellement, les méthodes formelles sont de plus en plus utilisées dans le but d’analyser le comportement les systèmes dits temps-réel. Ces méthodes utilisent des modèles formels de spécification dotés de sémantiques bien définies et des techniques de vérification formelle. D'autre part, les sémantiques de vrai parallélisme, comme la sémantique de maximalité peuvent être utilisées à bon escient si on veut échapper à l’hypothèse de l’atomicité temporelle et structurelle des actions. Des travaux antérieurs ont montré l’aptitude de modèles basés sur la maximalité, à l’image des systèmes de transitions étiquetés maximales, à supporter l’expression du parallélisme d’exécution d’actions.Notre travail qui s’inscrit dans le cadre de la spécification et la vérification formelle des systèmes temps-réel consiste à tirer profit des avantages offerts par la sémantique de maximalité en l’appliquant à quelques modèles temporels et/ou temporisés. Ainsi, nous proposons trois méthodes de géenération de structures basés sur la maximalité (systèmes de transitions étiquetées maximales, DATA et DATA*) à partir de modèles de haut niveau à savoir le langages Basic LOTOS avec durées d’actions, la langage D-LOTOS et les réseaux de Petri place/transition.

Nowadays, more and more industrial systems rely on distributed real-time embedded software (DRES) applications. Implementing such applications requires answering to an important set of heterogeneous, or even conflicting, constraints. To satisfy these constraints, it is sometimes necessary to equip DRES with adaptation capabilities. Moreover, real-time applications often control systems of which failures can have dramatic economical - or worst human - consequences. In order to design such application, named critical applications, it is necessary to rely on rigorous methodologies, of which certain have already been used in industry. However, growth complexity of critical DRES applications requires proposing always new methodologies in order to answer to all of these stakes. Yet, as far as we know, existing design processes do not tackle the issue of adaptation mechanisms that require to modify deeply the software configuration. This PhD thesis work presents a new methodology that answers this problem by relying on the notion of operational mode : each possible behaviour of the system is represented by an operational mode, and a software configuration is associated to this mode. Modeling transition rules betwen these modes, it becomes possible to generate and analyze the reconfigurations of the software architecture that implement the system adaptations. The generated code respects the implementation requirements of critical systems, and relies on safe and analyzable adaptation mechanisms. To achieve this objective, we define a new architecture description language (COAL : Component Oriented Architecture Language), specific to this domain, that enables to profit from advantages of component-based software engineering (based on Lightweight CCM), and analysis, static deployment and configuration techniques that provides architecture description languages (and in particular AADL : Architecture Analysis and Design Language). This methodology also relies on a new component framework, MyCCM-HI (Make your Component Container Model - High Integrity), that exploits COAL constructs so as to (i) generate AADL models enabling static deployment and configuration of DRES applications, (ii) generate code to deploy and configure Lightweight CCM components, (iii) generate code implementing the system adaptation mechanisms, and (iv) formally analyse the behaviour of the system, including during adaptation. The adopted approach thus reduces complexity of development of adaptative and critical DRES by automating production of adaptation mechanisms while easing their analysis. These two steps, analysis and production, are then part of the automatic production tool chain pro- vided by MyCC-HI. This component framework is availabe under (L)GPL license at address http ://myccm-hi.sourceforge.net.; Aujourd'hui, de plus en plus de systèmes industriels s'appuient sur des applications logicielles temps-réel réparties embarquées (TR2E). La réalisation de ces applications demande de répondre à un ensemble important de contraintes très hétérogènes, voire contradictoires. Pour satisfaire ces contraintes, il est presque toujours nécessaire de fournir à ces systèmes des capacités d'adaptation. Par ailleurs, certaines de ces applications pilotent des systèmes dont la défection peut avoir des conséquences financières - voire humaines - dramatiques. Pour concevoir de telles applications, appelées applications critiques, il faut s'appuyer sur des processus de développpement rigoureux capables de repérer et d'éliminer les erreurs de conception potentielles. Malheureusement, il n'existe pas à notre connaissance de processus de développement capable de traiter ce problème dans le cas où l'adaptation du système à son environnement conduit à modifier sa configuration logicielle. Ce travail de thèse présente une nouvelle méthodologie qui répond à cette problématique en s'appuyant sur la notion de mode de fonctionnement : chacun des comportements possibles du système est représenté par le biais d'un mode de fonctionnement auquel est associé une configuration logicielle. La spécification des règles de transition entre ces modes de fonctionnement permet alors de générer l'implantation des mécanismes de changement de mode, ainsi que des reconfigurations logicielles associées. Le code ainsi produit respecte les contraintes de réalisation des systèmes critiques et implante des mécanismes de reconfiguration sûrs et analysables. Pour ce faire, nous avons défini un nouveau langage de description d'architecture (COAL : Component Oriented Architecture Language) qui permet de bénéficier à la fois des avantages du génie logiciel à base de composants (de type Lightweight CCM), et des techniques d'analyse, de déploiement et de configuration statique, qu'apporte l'utilisation des langages de description d'architecture (et en particulier AADL : Architecture Analysis and Description Language). Nous avons alors réalisé un nouveau framework à composant, MyCCM-HI (Make your Component Container Model - High Integrity), qui exploite les constructions de COAL pour (i) générer le modèle AADL permettant de réaliser le déploiement et la configuration statique de l'application TR2E, (ii) générer le code de déploiement et de configuration des composants logiciels de type Lightweight CCM, (iii) générer le code correspondant aux mécanismes d'adaptation du système, et (iv) analyser formellement le comportement du système, y compris en cours d'adaptation. Ce framework à composant est disponible au téléchargement à l'adresse http ://myccm-hi.sourceforge.net.

Nowadays, more and more industrial systems rely on distributed real-time embedded software (DRES) applications. Implementing such applications requires answering to an important set of heterogeneous, or even conflicting, constraints. To satisfy these constraints, it is sometimes necessary to equip DRES with adaptation capabilities. Moreover, real-time applications often control systems of which failures can have dramatic economical - or worst human - consequences. In order to design such application, named critical applications, it is necessary to rely on rigorous methodologies, of which certain have already been used in industry. However, growth complexity of critical DRES applications requires proposing always new methodologies in order to answer to all of these stakes. Yet, as far as we know, existing design processes do not tackle the issue of adaptation mechanisms that require to modify deeply the software configuration. This PhD thesis work presents a new methodology that answers this problem by relying on the notion of operational mode : each possible behaviour of the system is represented by an operational mode, and a software configuration is associated to this mode. Modeling transition rules betwen these modes, it becomes possible to generate and analyze the reconfigurations of the software architecture that implement the system adaptations. The generated code respects the implementation requirements of critical systems, and relies on safe and analyzable adaptation mechanisms. To achieve this objective, we define a new architecture description language (COAL : Component Oriented Architecture Language), specific to this domain, that enables to profit from advantages of component-based software engineering (based on Lightweight CCM), and analysis, static deployment and configuration techniques that provides architecture description languages (and in particular AADL : Architecture Analysis and Design Language). This methodology also relies on a new component framework, MyCCM-HI (Make your Component Container Model - High Integrity), that exploits COAL constructs so as to (i) generate AADL models enabling static deployment and configuration of DRES applications, (ii) generate code to deploy and configure Lightweight CCM components, (iii) generate code implementing the system adaptation mechanisms, and (iv) formally analyse the behaviour of the system, including during adaptation. The adopted approach thus reduces complexity of development of adaptative and critical DRES by automating production of adaptation mechanisms while easing their analysis. These two steps, analysis and production, are then part of the automatic production tool chain pro- vided by MyCC-HI. This component framework is availabe under (L)GPL license at address http ://myccm-hi.sourceforge.net., Aujourd'hui, de plus en plus de systèmes industriels s'appuient sur des applications logicielles temps-réel réparties embarquées (TR2E). La réalisation de ces applications demande de répondre à un ensemble important de contraintes très hétérogènes, voire contradictoires. Pour satisfaire ces contraintes, il est presque toujours nécessaire de fournir à ces systèmes des capacités d'adaptation. Par ailleurs, certaines de ces applications pilotent des systèmes dont la défection peut avoir des conséquences financières - voire humaines - dramatiques. Pour concevoir de telles applications, appelées applications critiques, il faut s'appuyer sur des processus de développpement rigoureux capables de repérer et d'éliminer les erreurs de conception potentielles. Malheureusement, il n'existe pas à notre connaissance de processus de développement capable de traiter ce problème dans le cas où l'adaptation du système à son environnement conduit à modifier sa configuration logicielle. Ce travail de thèse présente une nouvelle méthodologie qui répond à cette problématique en s'appuyant sur la notion de mode de fonctionnement : chacun des comportements possibles du système est représenté par le biais d'un mode de fonctionnement auquel est associé une configuration logicielle. La spécification des règles de transition entre ces modes de fonctionnement permet alors de générer l'implantation des mécanismes de changement de mode, ainsi que des reconfigurations logicielles associées. Le code ainsi produit respecte les contraintes de réalisation des systèmes critiques et implante des mécanismes de reconfiguration sûrs et analysables. Pour ce faire, nous avons défini un nouveau langage de description d'architecture (COAL : Component Oriented Architecture Language) qui permet de bénéficier à la fois des avantages du génie logiciel à base de composants (de type Lightweight CCM), et des techniques d'analyse, de déploiement et de configuration statique, qu'apporte l'utilisation des langages de description d'architecture (et en particulier AADL : Architecture Analysis and Description Language). Nous avons alors réalisé un nouveau framework à composant, MyCCM-HI (Make your Component Container Model - High Integrity), qui exploite les constructions de COAL pour (i) générer le modèle AADL permettant de réaliser le déploiement et la configuration statique de l'application TR2E, (ii) générer le code de déploiement et de configuration des composants logiciels de type Lightweight CCM, (iii) générer le code correspondant aux mécanismes d'adaptation du système, et (iv) analyser formellement le comportement du système, y compris en cours d'adaptation. Ce framework à composant est disponible au téléchargement à l'adresse http ://myccm-hi.sourceforge.net.

The validation process is an important step in the development of a real-time application. It consists in proving that, whatever happens, the scheduling policy guarantees that all the temporal constraints are met. In this thesis we study the schedulability test of tasks with offsets, on uniprocessor system, with fixed and dynamic priority assignments. The exact tests has an exponential complexity and only a sufficient (pessimistic) feasibility test with a pseudo-polynomial complexity has been proposed. Note that all existing tests are based on the response time analysis (RTA) technique. In the fixed priority context, we propose a new pseudo-polynomial RTA method, less pessimistic than the existing methods. We present some properties (accumulatively monotonic transactions, dominated tasks) that make exact the approximate methods, for certain cases, and optimize the run time computation. In the dynamic priority context, we provide a pseudo-polynomial exact schedulability test, based on the processor demand analysis. We provide experimental evaluations of the proposed tests and their optimization.; Un système temps réel critique nécessite une validation temporelle utilisant un test d'ordonnançabilité avant sa mise en œuvre. Cette thèse traite le problème d'ordonnancement des taches à offset (transactions) sur une architecture monoprocesseur, en priorités fixes et en priorités dynamiques. Les méthodes existantes pour un test exact ont une complexité exponentielle et seules existent des méthodes approchées, donc pessimistes, qui sont pseudo-polynomiales. En priorités fixes nous proposons des méthodes pseudo-polynomiales, basées sur l'analyse de temps de réponse qui sont moins pessimistes que les méthodes existantes. Nous présentons quelques propriétés (accumulativité monotonique, dominance de tâches) rendant exacte les méthodes d'analyse approchées pour certains cas de systèmes, et optimisant le temps de calcul. En priorités dynamiques, nous proposons un test d'ordonnançabilité exact avec une complexité pseudo-polynomiale. Ce test est basé sur l'analyse de la demande processeur. Les qualités des résultats de nos méthodes sont confirmées par des évaluations expérimentales.

In this thesis, we address the problem of dynamic memory management in real-time embedded Java systems. When programming in C or C++, all memory management is done explicitly by the programmer, inducing numerous execution faults because of hazardous use of memory operations. This greatly increases software development costs, because such errors are very hard to debug. The Java language tackles this problem by offering automatic memory management, thanks to the use of a garbage collector. However, garbage collection is often deemed to be unsuited to a real-time embedded context, because of its unpredictable execution times. This problem hinders the spread of modern languages like Java in the world of real-time embedded systems.To settle the problem of execution times, we propose to use a region-based memory manager. The idea is to group objects of similar lifetimes into memory regions, which are deallocated as a whole. This paradigm offers predictable execution times for all memory operations. We propose a static analysis algorithm that predicts connections between objects, so that every data structure is grouped into one region. The analysis also produces results describing the memory behaviour of the program, helping the developer to write his code in a style suitable for region-based memory management. We implemented an automatic region allocator in the virtual machine of the JITS project, dedicated to bringing full Java support to resource-constrained embedded devices. Experiments show that for most programming patterns, our system behaves as efficiently as a garbage collector, while retaining predictable execution times. Our analysis tool is furthermore able to provide useful feedback to the programmer to pinpoint problematic constructs., La problématique abordée dans ce travail est celle de la gestion mémoire automatique pour des programmes Java temps-réel embarqués. Dans des langages comme le C ou le C++, la mémoire est typiquement gérée explicitement par le programmeur, ce qui est la source de nombreuses erreurs d'exécution causées par des manipulations hasardeuses. Le coût de correction de telles erreurs est très important car ces erreurs sont rarement reproductibles et donc difficiles à appréhender. En Java la gestion mémoire est entièrement automatique, ce qui facilite considérablement le développement. Cependant, les techniques classiques de recyclage de la mémoire, typiquement basées sur l'utilisation d'un ramasse-miettes, sont souvent considérées comme inapplicables dans le contexte des applications temps-réel embarquées, car il est très difficile de prédire leur temps de réponse. Cette incompatibilité est un frein important à l'adoption de langages de haut niveau comme Java dans ce domaine.Pour résoudre le problème de la prévisibilité du temps d'exécution des opérations mémoire, nous proposons une approche fondée sur l'utilisation d'un modèle mémoire en régions. Cette technique, en groupant physiquement les objets de durées de vie similaires dans des zones gérées d'un seul bloc, offre en effet un comportement temporel prévisible. Afin de décider du placement des objets dans les différentes régions, nous proposons un algorithme d'analyse statique qui calcule une approximation des relations de connexion entre les objets. Chaque structure de données est ainsi placée dans une région distincte. L'analyse renvoie également au programmeur des informations sur le comportement mémoire du programme, de façon à le guider vers un style de programmation propice à la gestion mémoire en régions, tout en pesant le moins possible sur le développement. Nous avons implanté un gestionnaire mémoire automatique en régions dans la machine virtuelle JITS destinée aux systèmes embarqués à faibles ressources. Les résultats expérimentaux ont montré que notre approche permet dans la plupart des cas de recycler la mémoire de façon satisfaisante, tout en présentant un comportement temporel prévisible. Le cas échéant, l'analyse statique indique au développeur quels sont les points problématiques dans le code, afin de l'aider à améliorer son programme.

The validation process is an important step in the development of a real-time application. It consists in proving that, whatever happens, the scheduling policy guarantees that all the temporal constraints are met. In this thesis we study the schedulability test of tasks with offsets, on uniprocessor system, with fixed and dynamic priority assignments. The exact tests has an exponential complexity and only a sufficient (pessimistic) feasibility test with a pseudo-polynomial complexity has been proposed. Note that all existing tests are based on the response time analysis (RTA) technique. In the fixed priority context, we propose a new pseudo-polynomial RTA method, less pessimistic than the existing methods. We present some properties (accumulatively monotonic transactions, dominated tasks) that make exact the approximate methods, for certain cases, and optimize the run time computation. In the dynamic priority context, we provide a pseudo-polynomial exact schedulability test, based on the processor demand analysis. We provide experimental evaluations of the proposed tests and their optimization., Un système temps réel critique nécessite une validation temporelle utilisant un test d'ordonnançabilité avant sa mise en œuvre. Cette thèse traite le problème d'ordonnancement des taches à offset (transactions) sur une architecture monoprocesseur, en priorités fixes et en priorités dynamiques. Les méthodes existantes pour un test exact ont une complexité exponentielle et seules existent des méthodes approchées, donc pessimistes, qui sont pseudo-polynomiales. En priorités fixes nous proposons des méthodes pseudo-polynomiales, basées sur l'analyse de temps de réponse qui sont moins pessimistes que les méthodes existantes. Nous présentons quelques propriétés (accumulativité monotonique, dominance de tâches) rendant exacte les méthodes d'analyse approchées pour certains cas de systèmes, et optimisant le temps de calcul. En priorités dynamiques, nous proposons un test d'ordonnançabilité exact avec une complexité pseudo-polynomiale. Ce test est basé sur l'analyse de la demande processeur. Les qualités des résultats de nos méthodes sont confirmées par des évaluations expérimentales.

We present a method of fine grain QoS control for multimedia applications. The method allows the control of application software whose actions are parameterized by a quality level parameter and whose execution times are unknown. The method allows the construction of a Controller which computes adequate action schedules and corresponding quality levels, so as to meet safety and optimality for a given platform. In other words, we want to have a maximal utilization of the available time budget without exceed it. The Controller uses a quality management policy for choosing, for each action, a schedule and quality levels meeting the QoS requirements. We extend and improve results of previous into two directions. We propose a symbolic quality management method using speed diagrams, a representation of the controlled system's dynamics. From this representation we propose a method allowing relaxing the number of call to the Controller with respect to the QOS requirements. In a second time, we developed a stochastic approach based on probability distribution functions for the execution time of actions. Our method is parameterized according to the importance attributed to deadline misses. This means that the user is given the possibility to express how hard the real time constraints are. Besides, given a value of the parameter, we can compute the expected deadline miss ratio for the controlled application. We present experimental results including the implementation of the method and benchmarks for a video MPEG4 encoder running on a bare machine., Ce manuscrit présente une méthode de contrôle de qualité de service à grain fin d'applications multimédia. Celle-ci permet le contrôle d'applications dont les actions sont paramétrées par des niveaux de qualité et dont les durées d'exécution ne sont pas connues. Le contrôle consiste en la construction d'un ordonnancement et le choix des niveaux de qualité respectant des propriétés de sûreté et d'optimalité. C'est-à-dire que l'on cherche à maximiser l'utilisation du budget de temps sans pour autant le dépasser tout en ayant un choix de qualité régulier. Le contrôleur utilise une politique de gestion de qualité permettant de choisir pour chaque action l'ordonnancement et le niveau de qualité respectant les contraintes de qualité de service. Nous étendons et améliorons les résultats précédents dans deux directions. La première propose une approche symbolique de la politique de gestion de qualité. Celle-ci utilise un diagramme de vitesses qui est une représentation graphique du comportement de l'application contrôlée. À partir de cette représentation, nous avons proposé une technique de contrôle permettant de relâcher le nombre d'appels au contrôleur tout en respectant les propriétés de sûreté et d'optimalité. Nous avons ensuite proposé une approche stochastique du problème basée sur des fonctions de distribution de probabilités pour les durées d'exécution des actions. Notre méthode donne la possibilité à l'utilisateur de fixer la criticité des contraintes temps-réel. Elle permet aussi de calculer à priori le taux attendu de dépassement des échéances. Ces résultats théoriques ont été appuyés par des expériences réalisées sur un encodeur vidéo s'exécutant sur machine nue.

This thesis adresses real-time systems, usinga transformational approach. The timed process algebra RT-LOTOS serves as source language. Extended Petri nets with stopwatches and data serve as target language. Rt-LOTOS to extended Petri nets translation patterns are proposed and formally proved. The transformational approach developed for the control part is extended to the data part. The RT-LOTOS language is enhanced with a suspend /resume operator, thus extending the class of real-time systems that can be modeld and verified . The efficiency of the new approach is demonstrated on various case studies that include comparisons with LOTOS and RT-LOTOS tools that had been developed before. The proposed approach may be applied and extended to other modelling languages, in particular the real-time UML profile TURTLE (Timed UML and RT-LOTOS Environment).; 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).

In the field of networked control systems, researches have considerably evolved since Ethernet is more and more used to substitute the traditional industrial local area networks. Even if this choice of Ethernet is justified regarding its intrinsic ability to support all the communications of the enterprise (from office to workshop), it is not suitable to assume the time constraints of distributed control applications. Contrary to the fieldbuses, the non-determinism of the medium access method used by Ethernet does not enable to guarantee strict time constraints.The contribution of this thesis is to define an analytical approach to upper-bound the end-to-end delays in networked control systems which are based on switched Ethernet architectures. Work has focused on the adaptation of the network calculus theory to these specifics environments. Within this framework, this thesis presents the modeling of an IEEE 802.1D switch as well as a computation method of the end-to-end delays based on the increasing of the traffic burstiness. Several real experiments validate the tightness of the computed bounds.In addition to the performance evaluation, the work has also considered the Classification of Service (IEEE 802.1D/p) and the optimization of the frames scheduling on Ethernet. Finally, this thesis shows how such a performances evaluation method can be used to scale and optimize the design of switched Ethernet architectures., La recherche dans le domaine des systèmes contrôlés en réseau a considérablement évolué depuis qu'Ethernet est de plus en plus utilisé en remplacement des traditionnels réseaux locaux industriels. Si ce choix d'Ethernet se justifie par sa faculté intrinsèque à supporter toutes les communications de l'entreprise (du bureau à l'atelier), il s'accorde difficilement avec les contraintes temporelles des applications de contrôle / commande distribuées. Contrairement aux réseaux de terrain, l'indéterminisme de l'accès à la voie d'Ethernet ne permet pas de garantir le respect des contraintes temporelles strictes.La contribution de cette thèse est la définition d'une approche analytique permettant de majorer les délais de communication de bout en bout dans les systèmes contrôlés en réseau lorsqu'ils reposent sur une architecture Ethernet commutée. Les travaux se sont focalisés sur l'adaptation de la théorie du calcul réseau à ce type d'environnement. Dans ce cadre, cette thèse développe la modélisation d'un commutateur IEEE 802.1D ainsi qu'une méthode de calcul des délais de bout en bout basée sur l'augmentation du volume des rafales. Plusieurs expérimentations réelles ont permis de valider l'efficacité des bornes obtenues par calcul.Outre l'évaluation de performances, ces travaux s'intéressent également à la Classification de Service (IEEE 802.1D/p) et à l'optimisation de l'ordonnancement des trames sur Ethernet. Cette thèse montre enfin comment une méthode d'évaluation de performances peut être utilisée pour dimensionner et optimiser la conception d'architectures Ethernet commutées.

Real-time and distributed systems capture complex problems in terms of architecture design and behavior description. Because of their life-criticality and prototyping costs, these systems have stimulated research work on formal modeling language and model-based validation techniques that enable early detection of design errors. Nevertheless, formal modeling languages have incompletely succeeded in industry. The advent of the OMG-based Unified Modeling Language (UML) has open new avenues for an integration of formal modeling languages into a design methodology that might receive greater acceptance among practitioners. Relying on former experience with the formal description technique Estelle and timed extensions of Petri Nets, the main output of our research activity over the last five years is a real-time UML profile named TURTLE (Timed UML and RT-LOTOS Environment). TURTLE supersedes UML 2.0 by its extension of UML analysis and design diagrams, its formal semantics expressed in RT-LOTOS, and its toolkit (diagram editor and formal validation tool combining simulation capabilities and verification based on reachability analysis). The TURTLE methodology typically applies to real-time system design and communication architecture validation. This approach has been successfully applied on space-based systems and authentication protocols.; Les systèmes temps réel et distribués posent des problèmes complexes en termes de conception d'architecture et de description de comportements. De par leur criticité en vies humaines et leurs coûts de prototypage, ces systèmes ont motivé le développement d'une activité de recherche sur les langages de modélisation formelle et les techniques de validation basées modèle qui contribuent à la détection au plus tôt des erreurs de conception. Néanmoins, les langages formels ont eu un succès plus que limité dans l'industrie. L'arrivée du langage UML (Unified Modeling Language) a ouvert de nouveaux horizons pour l'intégration de langages de modélisation formelle dans une méthodologie de conception susceptible d'être mieux acceptée par les praticiens du domaine. En s'appuyant sur une expérience antérieure de la technique de description formelle Estelle et des extensions temporelles des réseaux de Petri, notre activité de recherche sur les cinq dernières années a débouché sur la production d'un profil UML nommé TURTLE (Timed UML and RT-LOTOS Environment). TURTLE surpasse UML 2.0 par ses extensions aux diagrammes d'analyse et de conception UML, sa sémantique formelle exprimée en RT-LOTOS, et ses outils de support (éditeur de diagrammes et outil de validation formelle combinant simulation et vérification basée sur une analyse daccessibilité). La méthodologie TURTLE trouve son champ d'application naturel dans la conception de systèmes temps réel et la validation d'architectures de communication en particulier. L'approche proposée a été appliquée avec succès à des systèmes satellitaires et des protocoles d'authentification.

Real-time systems are devices consisting of hardware and software with functional and timing constraints for the interaction with their environment. Telecommunication, nuclear power plants, avionics, and medical technology are typical domains where such systems are encountered. These systems are often critical because of the high human and economic stakes. Therefore, the development of these systems requires highly reliable methods. The synchronous approach has been proposed in order to answer this demand. Its mathematical basis provides a formal framework that favors the description and validation of real-time systems. The multi clock or polychronous model stands out from other synchronous speci cation models by the fact that it allows the description of systems where each component can have its own activation clock. Besides formal validation, it favors component-based approaches and modular development of large-scale systems. This document suggests a methodology for the design of real-time systems that uses as formalism the synchronous language Signal which relies on the polychronous model. It uses the formal tools and techniques based on this model in order to verify both behavioral and non functional properties. This facilitates design space exploration. The methodology presented here allows to design systems that contain asynchronous mechanisms using the synchronous approach. It illustrates the characterization of real-time behaviors in the polychronous model. Avionics is considered as privileged application domain in the current document. This work has been supported by the european project SafeAir (Advanced Design Tools for Aircraft Systems and Airborne Software) in which many industrials are involved. We especially are interested in the design of applications following the Integrated Modular Avionics (IMA) architecture model that is based on the avionic standard ARINC. This leads to the implementation of a library in Signal containing real-time executive services de fined by ARINC.; Les systemes temps reel sont des dispositifs constitues de materiels et de logiciels soumis a des contraintes a la fois fonctionnelles et temporelles pour realiser des traitements, et agir sur leur environnement. Des exemples de domaines o u on rencontre de tels systemes sont les telecommunications, le nucl eaire, l'avionique ou le medical. Ces systemes sont souvent critiques a cause d'enjeux humains et economiques importants. Leur developpement exige donc des methodes tres ables. L'approche synchrone a et e proposee dans le but de repondre a cette attente. Ses fondements mathematiques o rent un cadre formel propice a la description et la validation des systemes temps reel. Parmi les modeles de specification synchrone, le modele multi-horloge ou polychrone se distingue par le fait qu'il permet de decrire des systemes o u chaque composant peut avoir sa propre horloge d'activation. Outre la validation formelle, il favorise des approches orientees composants et le d eveloppement modulaire de systemes a grande echelle. Cette these propose une m ethodologie de conception de syst emes temps reel en utilisant comme formalisme de description le langage synchrone Signal fond e sur le mod ele polychrone. Elle utilise les outils et techniques formels bas es sur ce modele pour verifier des proprietes comportementales portant sur des aspects tant fonctionnels que non fonctionnels. Cette demarche facilite l' evaluation des choix de conception. La methodologie propos ee permet de concevoir des systemes comportant des m ecanismes asynchrones a l'aide de l'approche synchrone. Elle illustre la caracterisation de comportements temps r eel dans le modele polychrone. L'avionique est le domaine d'application privilegie par la these. Cette derniere s'inscrit dans le cadre du projet europ een IST SafeAir (Advanced Design Tools for Aircraft Systems and Airborne Software), regroupant plusieurs industriels. Nous nous sommes particulierement interesses a la conception d'applications suivant le mod ele d'architecture IMA (Integrated Modular Avionics) sur lequel repose la norme avionique ARINC. Cela a conduit a la r ealisation d'une bibliotheque Signal de composants, constituee en majeure partie de services d'un ex ecutif temps reel d e nis par ARINC.

Colloque sur invitation.; La consommation en énergie est devenue un problème crucial pour de nombreux équipements électroniques dont l'alimentation en énergie est assurée par des batteries. Des stratégies d'ordonnancement adaptées permettent de réduire considérablement la consommation énergétique. Nous proposons un tour d'horizon des techniques d'ordonnancement visant à minimiser la consommation d'énergie tout en garantissant le respect de contraintes d'échéances. Ces contraintes de temps peuvent peser explicitement sur certaines activités du système ou peuvent provenir de contraintes de performances minimales si l'on sort du cadre classique des systèmes temps réel. Le problème d'ordonnancement à résoudre consiste non seulement à déterminer l'ordre dans lequel exécuter les activités du système mais également à fixer la fréquence de fonctionnement du processeur au cours du temps. Comme souligné dans [Gruian02], l'ordonnancement sous contrainte d'énergie acquiert une nouvelle dimension qui est la vitesse du processeur.

Colloque avec actes et comité de lecture. internationale.; International audience; Energy consumption is becoming a crucial issue in the design of digital systems especially when considering portable and embedded systems due to their operational dependency on batteries. The processor being an important source of energy consumption, energy-aware scheduling strategies that decrease the CPU speed when possible enable to achieve significant energy savings. In this paper, we study the low-power scheduling under the Round-Robin policy which is widely available since it is part of the Posix1003.1b standard. An algorithm that computes the minimum processor speed for scheduling a job set under Round-Robin is provided. It relies on an efficient feasibility test that is also a contribution of this paper. Finally, we present mechanisms that are necessary for ensuring schedulability at run-time and that reduces consumption when jobs do not require their worst-case execution time. A counter-intuitive result shown in this study is that a job set might not be feasible at maximum frequency while being feasible with a lower frequency. This implies that even without interests in energy saving, lower frequencies have to be considered for feasibility.

Colloque sur invitation. nationale.; National audience; TTP/C (Time Triggered Protocol) est un réseau dont l'utilisation est envisagée dans les applications automobiles dites "X-By-Wire" c'est à dire des applications dans lesquelles des liaisons mécaniques ou hydrauliques sont remplacées par des réseaux de communication. Les deux principales fonctions relevant du X-by-Wire sont la direction et le freinage. Une certaine tolérance aux fautes étant indispensable, il existe des ensembles de stations, appelés FTU (Fault Tolerant Unit), qui effectuent les mêmes calculs et qui communiquent leurs résultats par l'intermédiaire du protocole de communication (on appelle "répliques" les différents messages provenant d'une même FTU). Les applications embarquées dans les véhicules étant soumises à de fortes perturbations électromagnétiques, il arrive que certaines trames soient corrompues avec des erreurs fortement corrélées (on observe des "rafales d'erreurs"). Dans cette étude, nous montrons, pour un modèle d'erreurs général, comment configurer de façon optimale un réseau TTP/C (et plus généralement des réseaux basés sur TDMA) de façon 1) à minimiser la probabilité que toutes les répliques soient corrompues ou 2) à minimiser la probabilité que au moins une réplique soit corrompue. Ces deux objectifs correspondent à des situations bien définies en sûreté de fonctionnement qui sont identifiées relativement au concept de "fail-silence". Les stratégies optimales pour les objectifs 1 et 2 sont antagonistes, pour l'objectif 1) il faut "répartir uniformément" dans le temps les répliques alors que pour 2) il faut grouper la transmission des répliques.

Colloque sur invitation. nationale.; National audience; Le modèle d'ordonnancement dit trajectoriel est le modèle mathématique d'une ressource utilisée par des activités récurrentes. Ce modèle permet d'exprimer dans un cadre commun les résultats d'ordonnancement existants et se révèle souvent bien adapté pour prouver certaines propriétés sur l'ordonnancement. Dans cette étude, nous montrons comment, à l'aide du modèle trajectoriel, il est possible d'envisager des analyses d'ordonnançabilité génériques, c'est à dire valable pour certaines classes de politiques.

Contribution à un ouvrage.; La consommation en énergie est devenu un problème crucial pour de nombreux équipements électroniques dont l'alimentation en énergie est assurée par des batteries. Des stratégies d'ordonnancement adaptées permettent de réduire considérablement la consommation énergétique. Nous proposons un tour d'horizon des techniques d'ordonnancement visant à minimiser la consommation d'énergie tout en garantissant le respect de contraintes d'échéances. Ces contraintes de temps peuvent peser explicitement sur certaines activités du système ou peuvent provenir de contraintes de performances minimales si l'on sort du cadre classique des systèmes temps réel. Le problème d'ordonnancement à résoudre consiste non seulement à déterminer l'ordre dans lequel exécuter les activités du système mais également à fixer la fréquence de fonctionnement du processeur au cours du temps. Comme souligné dans [Gruian02], l'ordonnancement sous contrainte d'énergie acquiert une nouvelle dimension qui est la vitesse du processeur.

Colloque sur invitation. nationale.; National audience; Nous montrons comment utiliser de façon optimale des unités tolèrantes aux fautes (Fault-Tolerant Units - FTU) pour se prémunir contre des perturbations en rafales sur un réseau TDMA. Deux objectifs sont étudiés. Si l'on veut minimiser la probabilité de perdre toutes les répliques d'un même message, la politique optimale est de répartir la transmission des répliques dans le temps. La preuve utilise des propriétés de convexité de la probabilité de perte. Au contraire, si l'on veut minimiser la probabilité de perdre une réplique ou plus, alors la solution optimale est de transmettre les répliques regroupées dans le temps. La preuve est basée sur une technique de majoration. Finalement, nous adaptons ces résultats au cas particulier du protocole TTP/C.

Colloque avec actes et comité de lecture. nationale.; National audience; In this paper we present a linear time algorithm to compute a schedule of tasks with real-time constraints that minimizes the total energy consumption on a dynamically variable voltage processor. This result, which is a significant improvement over the classical algorithm, comes as a by-product of a more general continuous optimization problem. We also provide an optimal algorithm when the processor can only take a limited number of clock frequencies.

Rapporteurs : Richard Castanet Elie Najm Examinateurs : Michel Diaz Hubert Garavel Patrick Sallé François Vernadat; This thesis deals with the design of real-time systems based on the RT-Lotos formal method, a timed extension to the Lotos process algebra. It addresses several issues related to the specification, validation and scheduling of concurrent systems subject to logical and temporal constraints. The first part of the work proposes a review of formal methods for the specification and validation of real-time systems. It also presents the RT-Lotos language and the associated formal verification technique based on reachability analysis. Finally, it details some works based on the timed automaton (called a DTA) derived from an RT-Lotos specification in order to carry out fast simulations, and to interface with model-checking tools. The second part presents a study on the concept of temporal consistency and proposes both a technique and a formal model to exploit in a new way the information resulting from the formal reachability analysis. This approach proposes to refine the regions graph, to remove paths considered to be nondesirable, to extract the firing instants of the actions, and to present this information in a new model of timed automaton (called a TLSA) which is able to schedule the execution of the actions of a system. Finally, the third part considers the possible relations between formal and nonformal methods. Within this framework, we propose a formal semantics for UML diagrams, after having defined a real-time extension to UML (called TURTLE). Thus, we define a methodology, which takes place inside traditional industrial development techniques and which allows a formal analysis of real-time systems.; Ce mémoire de thèse s'intéresse à la conception de systèmes temps-réel en s'appuyant sur la méthode formelle RT-Lotos, extension temporelle à l'algèbre de processus Lotos. Il aborde plusieurs points relatifs à la spécification, la validation et l'ordonnancement de systèmes concurrents sujets à des contraintes logiques et temporelles. La première partie propose un éventail de méthodes formelles pour la spécification et la validation de systèmes temps-réel. Elle présente également le langage RT-Lotos et la technique de vérification formelle associée basée sur une analyse d'accessibilité. Elle détaille finalement un ensemble de travaux concernant l'automate temporisé (appelé un DTA) dérivé d'une spécification RT-Lotos, avec comme objectifs d'exécuter des simulations rapides, et de s'interfacer avec des outils de vérification de type model-checker. La deuxième partie présente une étude sur la notion de cohérence temporelle et propose une technique ainsi qu'un modèle formel pour exploiter sous un nouvel angle des informations issues de la vérification formelle par analyse d'accessibilité. Cette approche propose de raffiner le graphe des régions, d'en élaguer certaines branches jugées non souhaitables, d'extraire les dates de tir possible des actions, et de présenter ces informations sous la forme d'un nouveau type d'automate temporisé (appelé un TLSA) ayant pour vocation l'ordonnancement dans le temps des actions d'un système. Enfin, la troisième partie se penche sur les liens possibles entre méthodes formelles et semi-formelles. Dans ce cadre, nous proposons une sémantique formelle pour les diagrammes UML s'appuyant sur RT-Lotos, après avoir défini une extension temps-réel à UML (appelée TURTLE). Ainsi, nous définissons une méthodologie qui s'inscrit dans les techniques de développement industriel classiques et qui permet une vérification formelle de systèmes temps-réel.

Article dans une revue de vulgarisation.; Ordonnancer c'est définir un ordre sur l'exécution des différentes activités d'un système. Lorsqu'il s'agit d'un système informatique ces différentes activités se décomposent en l'exécution de tâches sur un ou plusieurs processeurs et éventuellement en la transmission de messages sur un réseau de communication. Tout le problème consiste à trouver le bon ordonnancement vis-à-vis des contraintes pesant sur le système, contraintes qui sont issues de la dynamique du processus physique contrôlé. Généralement il s'agira de respecter des contraintes de date au plus tard sur les fins d'exécution (ou contraintes d'échéances) mais il existe bien d'autres contraintes comme celle de date au plus tôt ou de simultanéité sur l'occurrence d'événements comme le déclenchement d'actions. Dans le contexte de l'ordonnancement, un système est dit faisable si toutes les invocations successives des activités qui le composent (les différentes instances) sont assurées de respecter leurs contraintes d'échéances.

Decision Support Systems (DSS) should help users to take the best decisions as earlier as possible. In this thesis, we are interested in such DSS which are based on the multiagent paradigm. Indeed, multiagent systems are often the best way used to build computer systems that need multicriteria queries because they permit to design complex computerized systems. Moreover, in DSS, temporal constraints are very strong and in a lot of cases partial or incomplete results obtained early are preferred and more useful than complete and accurate results obtained too late. Anytime techniques seem to be a good solution in order to deal with these situations, that is to take into account real-time aspects in this framework. In this document, we present a method and a model to design a real-time multiagent system is based on anytime techniques. Furthermore, we have taken into account the inherent distributed aspect of current DSS in our model.; Les systèmes d'aide à la décision (SAD) doivent permettre aux utilisateurs (décideurs) de prendre les meilleures décisions dans les meilleurs délais. Dans cette thèse, nous nous sommes intéressés aux systèmes qui reposent sur une architecture multi-agents. En effet, les systèmes multi-agents (SMA) permettent de construire des systèmes informatiques ayant recours à l'interrogation multi-critères, souvent utilisée dans les SAD. De façon plus générale, les SMA permettent de concevoir des systèmes qui sont de nature complexe. Cependant, ils n'intègrent pas la notion de contraintes temporelles qui sont souvent très fortes dans les SAD. De plus, dans ces systèmes, des résultats même partiels ou incomplets obtenus dans les temps sont souvent préférés car plus utiles pour la prise de décision que des résultats complets et précis obtenus en retard. Pour cela, les techniques ``anytime'' (raisonnement progressif) semblent une excellente solution. Dans cette thèse, nous présentons une méthode de conception d'un système multi-agent temps réel basé sur l'exploitation des techniques ``anytime''. De plus, nous prenons en compte dans notre modèle l'aspect souvent distribué des SAD.

Decision Support Systems (DSS) should help users to take the best decisions as earlier as possible. In this thesis, we are interested in such DSS which are based on the multiagent paradigm. Indeed, multiagent systems are often the best way used to build computer systems that need multicriteria queries because they permit to design complex computerized systems. Moreover, in DSS, temporal constraints are very strong and in a lot of cases partial or incomplete results obtained early are preferred and more useful than complete and accurate results obtained too late. Anytime techniques seem to be a good solution in order to deal with these situations, that is to take into account real-time aspects in this framework. In this document, we present a method and a model to design a real-time multiagent system is based on anytime techniques. Furthermore, we have taken into account the inherent distributed aspect of current DSS in our model., Les systèmes d'aide à la décision (SAD) doivent permettre aux utilisateurs (décideurs) de prendre les meilleures décisions dans les meilleurs délais. Dans cette thèse, nous nous sommes intéressés aux systèmes qui reposent sur une architecture multi-agents. En effet, les systèmes multi-agents (SMA) permettent de construire des systèmes informatiques ayant recours à l'interrogation multi-critères, souvent utilisée dans les SAD. De façon plus générale, les SMA permettent de concevoir des systèmes qui sont de nature complexe. Cependant, ils n'intègrent pas la notion de contraintes temporelles qui sont souvent très fortes dans les SAD. De plus, dans ces systèmes, des résultats même partiels ou incomplets obtenus dans les temps sont souvent préférés car plus utiles pour la prise de décision que des résultats complets et précis obtenus en retard. Pour cela, les techniques ``anytime'' (raisonnement progressif) semblent une excellente solution. Dans cette thèse, nous présentons une méthode de conception d'un système multi-agent temps réel basé sur l'exploitation des techniques ``anytime''. De plus, nous prenons en compte dans notre modèle l'aspect souvent distribué des SAD.

Within the framework of telecommunication, the companies develop protocols performing the data transfer between machines. These protocols work on the principle of sending of messages between two parts via unreliable channels. To make sure that all the messages were received, the techniques employed consist in re-emitting the lost messages and/or awaiting a lapse of time determined before deciding of the failure from the transmission. Moreover, the systems are often modelled according to parameters. We worked on a mathematical model allowing the verification of specifications (awaited behaviors of the systems) for protocols handling at the same time counters, queues or clocks, as well as parameters. The goal of the analysis is to calculate the set of the behaviors possible for the system then to check that none them violates an awaited specification. The problem here is that this set is infinite. Indeed, a behavior is a function of the values taken by the variables of the system during the execution and some are defined on an infinite field. It is then necessary to be able to represent these behaviors in a finished way and to also find methods to calculate in a finished time an infinite set. More formally, we placed ourselves within the framework of the automatic analysis of the systems (model-checking). The selected representation for the models with counters and clocks parameterized is an extension of the bounded matrices for which we have an exact method of acceleration (calculation in a finished time of sets of infinite behaviors). Practical side, we established these methods in a tool TReX which is, to our knowledge, only being able to handle in an exact way of the counters, the clocks and the queues. We could check consequent examples such as the bounded retransmission protocol., Dans le cadre de la télécommunication, les entreprises développent des protocoles gérant le transfert de données entre machines. Ces protocoles fonctionnent sur le principe d'envoi de messages entre deux parties par l'intermédiaire de canaux non fiables. Pour s'assurer que tous les messages ont bien été reçus, les techniques employées consistent à réémettre les messages perdus et/ou à attendre un laps de temps déterminé avant de conclure à l'échec de la transmission. De plus, les systèmes sont souvent modélisés en fonction de paramètres. Nous avons travaillé sur un modèle mathématique permettant la vérification de spécifications (comportements attendus des systèmes) pour des protocoles manipulant à la fois des compteurs, des files d'attente ou des horloges, ainsi que des paramètres. Le but de l'analyse est de calculer l'ensemble des comportements possibles du système puis de vérifier qu'aucun d'eux ne viole une spécification attendue. Le problème ici est que cet ensemble est infini. En effet, un comportement est fonction des valeurs prises par les variables du système au cours de l'exécution et certaines sont définies sur un domaine infini. Il faut alors pouvoir représenter ces comportements de façon finie et aussi trouver des méthodes pour calculer en un temps fini un ensemble infini. Plus formellement, nous nous sommes placés dans le cadre de l'analyse automatique des systèmes (model-checking). La représentation choisie pour les modèles à compteurs et horloges paramétrés est une extension des matrices de bornes pour laquelle nous avons une méthode exacte d'accélération (calcul en un temps fini d'ensembles de comportements infinis). Du côté pratique, nous avons implanté ces méthodes dans un outil TReX qui est, à notre connaissance, le seul pouvant manipuler de manière exacte des compteurs, des horloges et des files d'attente. Nous avons pu vérifier des exemples conséquents tels que le protocole de retransmission bornée.

Colloque avec actes et comité de lecture.; La politique d'ordonnancement dite à changement de priorité ("dual-priority") donne des garanties sur le temps de réponse de tâches à contraintes strictes tout en diminuant le temps de réponse de tâches à contraintes souples. Dans \cite{Tin:95b}, les auteurs ont proposé d'appliquer cette politique à l'ordonnancement de messages, nous montrerons par simulation que ses performances sont excellentes sur une application typique de multiplexage véhicule utilisant CAN (Controller Area Network). Néanmoins, dans un environnement bruité, l'utilisation de cette politique a la fâcheuse conséquence de rendre le trafic à contraintes strictes particulièrement exposé à des dépassements d'échéances causés par les erreurs de transmission. Nous expliquerons pourquoi le trafic temps réel est hautement sensible aux erreurs de transmission, évaluerons le risque et proposerons un mécanisme simple pour donner des garanties probabilistes sur le respect des échéances des messages. Le mécanisme proposé sera comparé en termes de performance à la politique initiale. Enfin, nous proposerons une méthode de fixation "en-ligne" des paramètres du modèle d'erreurs, implantable sur des microcontrôleurs de puissance modérée.Parue || The dual-priority is a scheduling policy providing the guarantees needed by hard real-time tasks while decreasing the response time for soft real-time tasks. This scheduling policy can be applied to message scheduling \cite{Tin:95b} and its performance on

In this thesis we propose a complete formal framework for the analysis of timed systems, with the emphasis given on the practicality of the approach. We describe timed systems in the formal model of timed automata, finite-discrete-state automata equipped with clocks in a dense-time domain. Properties of such systems are expressed in the linear-time formalism of timed Büchi automata (timed automata with acceptance conditions), or in one of the branching-time logics CTL, TCTL or \etctl. These formalisms cover a large spectrum of properties on the order of events and the timing constraints on the delays between events. We also examine other interesting properties such as deadlock and timelock freedom or reachability. We consider two types of analysis. Verification : given a system and a property, check whether the system satisfies the property. Controller synthesis : given a system and a property, find a restriction of the system which satisfies the property. These problems have been proven decidable in previous works, however, with a high (exponential) complexity, basically due to the fact that the state space is extremely large (state explosion) and has to be entirely generated and explored. To respond to the challenge of making the approach tractable, we propose methods which are efficient in practice, despite of the high worst-case theoretical complexity. Our approach is based on two key elements. First, on abstractions which reduce the concrete state space to a much smaller abstract state space, while preserving all properties of interest. Second, on efficient techniques to compute and explore the abstract state space. We define two sets of abstractions and study the properties they preserve. Time-abstracting bisimulations are equivalences which hide the quantitative aspect of time : we know that some time passes, but not how much. The stronger of these bisimulations preserves all properties of interest. Time-abstracting simulations are abstractions derived by a forward reachability analysis on the system. These abstractions preserve only linear properties. The analysis methods differ depending on the underlying abstraction(s) used. In the case of bisimulations, the approach consists in two steps : first, generate the time-abstracting quotient of the state space, then apply classical (untimed) analysis techniques to the quotient to prove properties of the concrete system. In the case of simulations, the generation of the abstract state space and the analysis are performed at the same time. This technique is called on-the-fly and can often provide fast answers without having to generate the entire (abstract) state space. We develop on-the-fly verification techniques for TBA and ETCTL. To make the verification task easier for the user, we develop techniques for extracting concrete diagnostic sequences (both finite and infinite) from the abstract sequences usually returned by the algorithms. The concrete diagnostics contain information both about the discrete state changes as well as the exact time delays during the execution. For the problem of controller synthesis, we develop an on-the-fly algorithm for untimed systems and use on the time-abstracting quotient to solve the problem in the timed setting. To put our methods to the test, we have implemented the algorithms developed in the thesis, on top of Kronos, the real-time tool-suite of Verimag. We have extended Kronos with a number of functionalities, including time-abstracting quotient generation, on-the-fly parallel composition of TA, on-the-fly TBA verification, concrete diagnostic generation and controller synthesis. We have also connected Kronos to the verification programming environment Open-Caesar, developed at INRIA and Verimag. Using Kronos, we have treated a number of non-trivial case studies, including two industrial communication protocols by CNET and Bang&Olufsen, the asynchronous electronic circuit Stari, a multimedia document authoring language developed at INRIA, a real-time scheduling example and a benchmark example for timed verification tools. The analysis results have been interesting. Sometimes we found errors in the systems and in the case of multimedia documents we managed to solve a scheduling problem using controller synthesis techniques. The performance results have been encouraging. Most of the times we managed to improve the results of previous versions of Kronos and other similar verification tools by many orders of magnitude., Dans cette thèse nous proposons un cadre formel complet pour l'analyse des systèmes temporisés, avec l'accent mis sur la valeur pratique de l'approche. Nous décrivons des systèmes comme des automates temporisés et nous exprimons les propriétés en logiques temps-réel. Nous considérons deux types d'analyse. Vérification : étant donnés un système et une propriété, vérifier que le système satisfait la propriété. Synthèse de contrôleurs : étant donnés un système et une propriété, restreindre le système pour qu'il satisfasse la propriété. Pour rendre l'approche possible malgré la difficulté théorique des problèmes, nous proposons : Des abstractions pour réduire l'espace d'états concret en un espace abstrait beaucoup plus petit qui, pourtant, préserve toutes les propriétés qui nous intéressent. Des techniques efficaces pour calculer et explorer l'espace d'états abstrait. Nous définissons des bisimulations et simulations faisant abstraction du temps et nous étudions les propriétés qu'elles préservent. Pour les bisimulations, l'analyse consiste à générer d'abord l'espace abstrait, et ensuite l'utiliser pour vérifier des propriétés sur l'espace concret. Pour les simulations, la génération et la vérification se font en même temps (à-la-volée). Un algorithme à-la-volée est aussi développé pour la synthèse de contrôleurs. Pour aider l'utilisateur à sa compréhension du système, nous produisons des séquences diagnostiques concrètes. Nous avons implanté nos méthodes dans Kronos, l'outil d'analyse temps-réel de Verimag, et nous avons traité un nombre d'études de cas réalistes parmi lesquelles le protocole FRP-DT de réservation rapide de débit pour les réseaux ATM (dans le cadre d'une coopération scientifique avec le CNET), le protocole de détection de collisions dans un réseaux à accès multiple de Band&Olufsen, l'ordonnancement de tâches temps-réel périodiques, la cohérence et l'ordonnancement des documents multimédia, ainsi qu'un nombre d'études de cas benchmarks, telles que le protocole d'exclusion mutuelle de Fischer, les protocoles de communication CSMA/CD et FDDI.

The work presented deals with the analysis and design of real-time systems. We present an original technique for the translation of structured specifications to object-oriented specifications. The need for such a technique and related literature are first presented. Then, are presented the different steps of the proposed technique. Its originality comes from the use of Petri nets as a translation medium. First, structured specifications (SA-RT formalism) are described by means of Petri nets. Then, resulting Petri nets are decomposed by using S-invariants to identify and define objects. Resulting objects are specified according to HOOD/PNO formalism. The proposed technique can be based on the static view of the specifications, the dynamic view or can be balanced between both of them. Several examples illustrate the different steps and possible approaches. Limits of the proposed technique, possibilities to use it jointly with others and to systematise it are also studied. Moreover, we investigate the possibility to use the obtained results to evaluate structured specifications. Some time extensions of Petri nets are investigated for this goal.; Les travaux développés dans ce mémoire se situent dans le cadre de l'analyse et de la conception des systèmes temps réel. Nous proposons une approche d'aide à la translation entre analyse fonctionnelle et analyse orientée objet. L'utilité d'une telle démarche ainsi que les différents travaux effectués dans ce domaine sont d'abord étudiés. Ensuite, nous exposons les différentes étapes de la démarche. Son originalité découle de l'utilisation des réseaux de Petri comme moyen de translation. D'abord, les spécifications fonctionnelles (de type SA-RT) sont décrites par réseaux de Petri. Les composantes conservatives de ces derniers sont alors utilisées pour identifier et définir les objets. Le formalisme HOOD/PNO est adopté pour la spécification des objets. L'approche proposée peut s'appuyer sur l'aspect statique des spécifications ou sur l'aspect dynamique. Il est également possible d'adopter une approche mixte. Les différentes étapes de la démarche et les approches possibles sont illustrées par des exemples significatifs. Nous étudions également les limites de la démarche proposée, ses parties automatisables et la possibilité de l'utiliser avec d'autres techniques. Par ailleurs, nous nous intéressons à la possibilité d'exploiter les résultats obtenus dans des objectifs d'évaluation des spécifications fonctionnelles. L'apport de certaines extensions temporelles des réseaux de Petri est mis en évidence.

The work presented in the thesis deals with problems concerning the execution control of autonomous mobile robots. The first part of the work presents the global control architecture and compares it to other approaches. We describe the hierarchical levels which it is composed of and each of their roles in the system's functioning. The lower level, composed of several modules, combines the perception, modelisation and action functions of the system. The second part presents the executive level. The executive must follow the execution of the functions, resolve the conflicts between modules, carry out certain reflex actions and maintain information concerning the use of the robot resources that cannot be shared. It can be seen as a group of automatons, that interact and change states according to the requests arriving from the higher level and the answers coming from the modules. The implementation of the executive uses the rule-based KHEOPS system. KHEOPS' compilation, using a set of in-going and out-going variables and the rules that bind them, produces an equivalent decision tree whose depth is known, which guarantees that the execution of the executive will be bounded in time. The compilation also guarantees certain logical characteristics of the automatons used. The third part presents the relations between the functional level (modules and executive) and the the level just above: the task level. This level is based on the PRS system, which transforms high abstraction-level tasks into action procedures that are recognised by the functional level, and supervises their execution. The thesis presents an equivalence between a PRS subset and coloured Petri nets, which enables checking at the task level, when the equivalence exists. To conclude, we present some results regarding the experimental implementation of this work with the Hilare 2 robot.; Le travail présenté dans le mémoire traite des problèmes liés au contrôle d'exécution des actions des robots mobiles autonomes. Une première partie présente l'architecture de contrôle globale et la compare à d'autres approches. On décrit les niveaux hiérarchiques qui la constituent et leurs rôles dans le fonctionnement du système. Le niveau inférieur, composé d'un ensemble de modules, rassemble les fonctions de perception, de modélisation et d'action du système. La seconde partie présente le niveau exécutif. L'exécutif doit suivre l'exécution des fonctions, résoudre les conflits entre modules, accomplir certaines actions réflexes et maintenir une information sur l'utilisation des ressources non partageables du robot. Il peut être vu comme un ensemble d'automates, qui interagissent et changent d'état selon les requêtes qui arrivent du niveau supérieur et les répliques qui proviennent des modules. La mise en oeuvre de l'exécutif utilise le système à base de règles KHEOPS. La compilation faite par KHEOPS permet, à partir d'un ensemble de variables d'entrée et de sortie et des règles qui les relient, d'obtenir un arbre de décision équivalent et de profondeur connue, ce qui garantit un temps d'exécution borné pour l'exécutif. La compilation permet aussi de garantir certaines propriétés logiques des automates mis en place. La troisième partie présente les relations entre le niveau fonctionnel (modules et exécutif) et la couche immédiatement supérieure, le niveau tache. Ce niveau est basé sur le système PRS, qui transforme des taches de haut niveau d'abstraction en procédures d'actions reconnues par le niveau fonctionnel et surveille leur exécution. Le mémoire présente une équivalence entre un sous-ensemble de PRS et les réseaux de Pétri colorés, ce qui permet de faire une vérification du niveau tache quand l'équivalence existe. Enfin, on présente quelques rés ultats de la mise en oeuvre expérimentale de ces travaux avec le robot Hilare 2.

This work proposes a method for the analysis of real-time systems. The method is based on the compilation of specifications into timed graphs, from which it is possible to verify real-timeproperties and to generate executable code.Timed graphs are automata extended with a set of variables,called clocks, which are used to express timing constraints. An algorithm for constructing a finite timed graph froman ATP program is developed. ATP is an algebra of timedprocesses with built-in timed operators such as timeoutsand watchdogs. The main interest of the algorithm is thatthe size of the graph is independent of the values oftime parameters. Real-time properties are specified as formulas of thelogic TCTL. It is shown that temporal constructs can beexpressed as fixed points in terms of an appropriatenext-state operator. Furthermore, this work proposesa symbolic model-checking algorithm for TCTL. Thecharacteristic set of a formula is computed as adisjunction of linear constraints over the set of clocks.Both algorithms have been implemented within the KRONOS tool, which has been used to verify several non-trivial real-time applications. The results obtained show the practical interest of this approach., Ce travail propose une méthode pour l'analyse de systèmes temps-reél. Cette méthode est basée sur la compilation des spécificationsvers des graphes temporisés, à partir desquels il est possiblede vérifier des propriétés et de générer du code exécutable.Les graphes temporisés sont des automates étendus avec desvariables, appelées horloges, qui permettent de décrire lescontraintes temporelles. Un algorithme de compilation est développé pour l'algèbrede processus temporisés ATP, qui est une extension des algèbres de processus avec des opérateurs temporels comme le ``timeout'' et le ``watchdog''. L'intérêt de l'algorithme est que la taille du graphe obtenu est indépendante des valeurs des paramètres des opérateurs temporels.Les propriétés temps-reél sur les graphes temporisés sont décrites par des formules de la logique TCTL. Il est montré que les opérateurs temporelsde TCTL s'expriment en termes de points fixes à l'aide d'un opérateur ``d'état suivant'' défini de façon appropriée.De plus, ce travail propose un algorithme de vérification quiconsiste à évaluer symboliquement l'ensemble caractéristiqued'une formule comme une disjonction de contraintes linéairessur les horloges.Les algorithmes de compilation et de vérification développés ont été implémentés dans l'outil KRONOS, utilisé pour analyser des applications temps-reél significatives. Les résultats obtenus confirment l'intérêtpratique de l'approche proposée.