Search

Schedulability analysis aims at guaranteeing the absence of deadline misses in hard real-time systems. This property is crucial for systems used in safety-critical domains such as avionics and automotive because a single deadline miss may have catastrophic consequences such as loss of human lives. In this thesis, we use theorem proving and machine-checked proofs to provide the highest confidence in hard real-time systems schedulability analyses as well as related industrial tools.The main contributions of this thesis are:(i) A formal interface combining the schedulability analyses proven in the Prosalibrary with a formally verified OS kernel (RT-CertiKOS). This work demonstrated the adequacy of Prosa’s abstract model to a real system and showed that analyses proven over an abstract and analysis-convenient model can be also applied to a concrete system. This work also provided RT-CertiKOS with a modular, state-of-the-art schedulability analysis proof.(ii) CertiCAN, a formally verified result certifier for CAN (Controller Area Network) analyzers. This work showed that result certification is a flexible andlight-weight process suitable for industry practice. Indeed, it does not rely onthe source code and is not impacted by software updates. Our experiments show that CertiCAN is efficient enough to certify the results produced by the industrial tool RTaW-Pegase even for large systems.(iii) Gd, a very general task model and its corresponding response time analysisamenable to Coq formalization. The main benefit of this approach is to factorize and reduce the proof effort. After formally verifying a general schedulability analysis for Gd, proving the correctness of an analysis for a more specificmodel boils down to prove its instantiation to Gd.; L’analyse de l’ordonnancabilité vise à garantir le respect des échéances dans les systèmes temps réel durs. Cette propriété est cruciale pour les systèmes utilisés dans les domaines critiques tels que l’avionique et l’automobile, car une échéance manquée peut avoir des conséquences catastrophiques allant jusqu’à la perte de vies humaines. Dans cette thèse, nous utilisons la preuve et la vérification mécanique des démonstrations afin d’assurer la correction des analyses d’ordonnancabilité des systèmes temps réel durs et des outils industriels associés.Les principales contributions de cette thèse sont:(i) Une interface formelle combinant les analyses d’ordonnancabilité prouvées dans la bibliothèque Prosa avec un noyau de sytème d’exploitation concret vérifié formellement (RT-CertiKOS). Ce travail a permis de justifier l’adéquation du modèle abstrait de Prosa à un système réel. Il a montré que les analyses prouvées pour un modèle abstrait et dédié à l’analyse peuvent également être appliquées à un système concret. Ce travail a également fourni à RT-CertiKOS une preuve d’ordonnancabilité modulaire à la pointe de l’état de l’art.(ii) CertiCAN, un certificateur de résultats formellement vérifié pour les analyseurs de réseaux CAN (Controller Area Network). Ce travail a montré que la certification de résultats est un processus flexible et léger qui convient bien aux pratiques de l’industrie. En effet, CertiCAN n’a pas besoin d’avoir accès au code source et n’est pas affecté par les mises à jour logicielles. Nos expérimentations ont montré que CertiCAN est suffisamment efficace pour certifier les résultats produits par l’outil industriel RTaW-Pegase et ceci même pour de grands systèmes.(iii) Gd, un modèle de tâches très général et une analyse du temps de réponse associée se prêtant à sa formalisation en Coq. L’avantage de cette approche est de factoriser et de simplifier l’effort de preuve. Une fois l’analyse du temps de réponse pour Gd formellement vérifiés, prouver la correction d’une analys epour un modèle plus spécifique revient à prouver son instanciation à Gd.

The continuous integration of new functionality increases the complexity of embedded systems, while each functionality might impose precedence constraints between the programs fulfilling it. In addition, the prevalence of several processors may create the illusion of higher computation capacity easing the associated scheduling problem. However, this capacity is not exploitable in critical real time systems because of the increased variability of the execution times due to processor features designed to provide excellent average time behavior and not necessarily ensuring small worst case bounds. This difficulty is added to the existence of scheduling anomalies when the systems are built a top of multi-core processors.In this thesis, we consider partitioned scheduling of DAG tasks defining precedence constraints. The variability of execution times is described by probability distributions. We propose a Response Time Analysis (RTA) based on iterative equations and probabilistic operators for independent distributions. For dependent distributions, we model them using Bayesian network. We also use C-space representation combined with SVM classification to estimate the schedulability probability. Moreover, we provide techniques to define priority and sub-task partitioning in a way to increase parallelism. We also decrease analysis complexity by reducing size of graph without altering the precedence structures.; L'intégration de nouvelles fonctionnalités augmente la complexité des systèmes temps réel , alors que chaque fonctionnalité peut imposer des contraintes de précédences entre les tâches. De plus, la prévalence des multicœurs peut créer l'illusion d'une capacité de calcul élevée. Cependant, cette capacité n'est pas exploitable dans les systèmes critiques en raison de la variabilité des temps d'exécution causé par les nouvelles architecture matérielle qui améliorent le comportement moyen mais pas le pire cas. Cette difficulté s'ajoute à l'existence d'anomalies d'ordonnancement pour les systèmes multicœurs. Dans cette thèse, nous considérons l'ordonnancement partitionné des graphes de précédence. La variabilité des temps d'exécution est décrite par des distributions de probabilité. Nous proposons une Analyse des Temps de Réponse (ATR) basée sur des équations itératives et des opérateurs probabilistes pour des distributions indépendantes. Pour les distributions dépendantes, nous les modélisons par des réseau bayésien. Nous utilisons également la représentation de C-espace et la classification SVM pour estimer la probabilité d'ordonnancabilité. De plus, nous fournissons des techniques de partitionnement et définition des priorités de manière à augmenter le parallélisme. Nous réduisons aussi la complexité de l'analyse en réduisant la taille du graphe sans modifier sa structure.

The continuous integration of new functionality increases the complexity of embedded systems, while each functionality might impose precedence constraints between the programs fulfilling it. In addition, the prevalence of several processors may create the illusion of higher computation capacity easing the associated scheduling problem. However, this capacity is not exploitable in critical real time systems because of the increased variability of the execution times due to processor features designed to provide excellent average time behavior and not necessarily ensuring small worst case bounds. This difficulty is added to the existence of scheduling anomalies when the systems are built a top of multi-core processors. In this thesis, we consider partitioned scheduling of DAG tasks defining precedence constraints. The variability of execution times is described by probability distributions. We propose a Response Time Analysis (RTA) based on iterative equations and probabilistic operators for independent distributions. For dependent distributions, we model them using Bayesian network. We also use C-space representation combined with SVM classification to estimate the schedulability probability. Moreover, we provide techniques to define priority and sub-task partitioning in a way to increase parallelism. We also decrease analysis complexity by reducing size of graph without altering the precedence structures., L'intégration de nouvelles fonctionnalités augmente la complexité des systèmes temps réel , alors que chaque fonctionnalité peut imposer des contraintes de précédences entre les tâches. De plus, la prévalence des multicœurs peut créer l'illusion d'une capacité de calcul élevée. Cependant, cette capacité n'est pas exploitable dans les systèmes critiques en raison de la variabilité des temps d'exécution causé par les nouvelles architecture matérielle qui améliorent le comportement moyen mais pas le pire cas. Cette difficulté s'ajoute à l'existence d'anomalies d'ordonnancement pour les systèmes multicœurs. Dans cette thèse, nous considérons l'ordonnancement partitionné des graphes de précédence. La variabilité des temps d'exécution est décrite par des distributions de probabilité. Nous proposons une Analyse des Temps de Réponse (ATR) basée sur des équations itératives et des opérateurs probabilistes pour des distributions indépendantes. Pour les distributions dépendantes, nous les modélisons par des réseau bayésien. Nous utilisons également la représentation de C-espace et la classification SVM pour estimer la probabilité d'ordonnancabilité. De plus, nous fournissons des techniques de partitionnement et définition des priorités de manière à augmenter le parallélisme. Nous réduisons aussi la complexité de l'analyse en réduisant la taille du graphe sans modifier sa structure.

The goal of this research is to define a time-triggered language for modeling real-time systems and to provide the conditions for their schedulability under Earliest Deadline First (EDF). Time-triggered languages separate the functional part of applications from their timing definition. These languages permit to model the real-time system temporal behavior by assigning system activities to particular time instants. We propose a new time-triggered framework, Extended Timing Definition Language (E-TDL), that enhances the basic task model used in Giotto and TDL while keeping compositional and modular structure brought by the latter. An E-TDL task is characterized by: an offset, a worst case execution time, a Logical Execution Time (a time interval between task release and its termination) and a period.The schedulability analysis of the system based on this new task model should be, in particular for EDF, investigated. We develop, on the concept of the processor demand criterion, conditions for the feasibility of an E-TDL system running on a single CPU under EDF. A necessary and sufficient condition is obtained by considering the global schedules that are made up of execution traces occurring at the same time in distinct modules that are able to switch their modes at predefined instants. We estimate a maximal length of the interval on which the schedulability condition must be checked. A tool suite performing the schedulability analysis of the E-TDL systems is developed., Les travaux réalisés dans le cadre de cette thèse ont pour objectif de proposer un langage de description temporelle pour des systèmes temps-réel et d’établir les conditions de leur ordonnançabilité sous l’algorithme Earliest Deadline First (EDF). Les langages de description temporelle permettent de spécifier le comportement temporel d’une application indépendamment de son comportement fonctionnel. Le programmeur déclare dans ces langages à quels instants précis doivent être déclenchées et terminées les activités du système. Cette gestion du temps, précise et explicite, apporte au système son caractère déterministe. Le langage proposé, Extended Timing Definition Language (E-TDL), étend des langages dirigés par le temps existants, en particulier Giotto et TDL, en introduisant un nouveau modèle de tâche donné par quatre paramètres : phase, pire temps d’exécution, temps d’exécution logique TEL (intervalle de temps séparant le lancement de la tâche et sa terminaison) et période.L’introduction de ce nouveau modèle de tâche nécessite de revisiter en particulier le problème de l’ordonnançabilité des tâches pour EDF. Cette thèse propose et développe une analyse basée sur la fonction de demande pour des ensembles de tâches décrites en E-TDL et s’exécutant en contexte monoprocesseur. Une condition nécessaire et suffisante est obtenue au travers d’une analyse précise des intervalles séparant les activations de tâches au sein de différents modules s’exécutant indépendamment et pouvant changer de mode à des instants prédéfinis. Une borne de la longueur des intervalles sur lesquels doit s’opérer la vérification est déterminée. Un outil mettant en œuvre cette analyse a été développé.

Les travaux réalisés dans le cadre de cette thèse ont pour objectif de proposer un langage de description temporelle pour des systèmes temps-réel et d’établir les conditions de leur ordonnançabilité sous l’algorithme Earliest Deadline First (EDF). Les langages de description temporelle permettent de spécifier le comportement temporel d’une application indépendamment de son comportement fonctionnel. Le programmeur déclare dans ces langages à quels instants précis doivent être déclenchées et terminées les activités du système. Cette gestion du temps, précise et explicite, apporte au système son caractère déterministe. Le langage proposé, Extended Timing Definition Language (E-TDL), étend des langages dirigés par le temps existants, en particulier Giotto et TDL, en introduisant un nouveau modèle de tâche donné par quatre paramètres : phase, pire temps d’exécution, temps d’exécution logique TEL (intervalle de temps séparant le lancement de la tâche et sa terminaison) et période. L’introduction de ce nouveau modèle de tâche nécessite de revisiter en particulier le problème de l’ordonnançabilité des tâches pour EDF. Cette thèse propose et développe une analyse basée sur la fonction de demande pour des ensembles de tâches décrites en E-TDL et s’exécutant en contexte monoprocesseur. Une condition nécessaire et suffisante est obtenue au travers d’une analyse précise des intervalles séparant les activations de tâches au sein de différents modules s’exécutant indépendamment et pouvant changer de mode à des instants prédéfinis. Une borne de la longueur des intervalles sur lesquels doit s’opérer la vérification est déterminée. Un outil mettant en œuvre cette analyse a été développé. The goal of this research is to define a time-triggered language for modeling real-time systems and to provide the conditions for their schedulability under Earliest Deadline First (EDF). Time-triggered languages separate the functional part of applications from their timing definition. These languages permit to model the real-time system temporal behavior by assigning system activities to particular time instants. We propose a new time-triggered framework, Extended Timing Definition Language (E-TDL), that enhances the basic task model used in Giotto and TDL while keeping compositional and modular structure brought by the latter. An E-TDL task is characterized by: an offset, a worst case execution time, a Logical Execution Time (a time interval between task release and its termination) and a period. The schedulability analysis of the system based on this new task model should be, in particular for EDF, investigated. We develop, on the concept of the processor demand criterion, conditions for the feasibility of an E-TDL system running on a single CPU under EDF. A necessary and sufficient condition is obtained by considering the global schedules that are made up of execution traces occurring at the same time in distinct modules that are able to switch their modes at predefined instants. We estimate a maximal length of the interval on which the schedulability condition must be checked. A tool suite performing the schedulability analysis of the E-TDL systems is developed.

Real-time embedded systems need to be analyzed at an early stage in order to detect temporal vulnerabilities. Indeed,software development costs are sharply impacted by wrong design choices made in the early stages of development, inparticular during the design phase, but often detected after the implementation. The schedulability analysis is one of themain analyses required to ensure the timing correctness of a real-time system. Indeed, the real-time scheduling theoryhas been devoted to propose different models providing several levels of expressiveness, and different analytical methodswith different levels of accuracy. The utilization of the real-time scheduling theory in practical cases could be profitable.Unfortunately, it is not sufficiently applied and research results have been exploited in an industrial context only to amodest extent to date. Actually, a difficulty faced by the real-time designers is to find the appropriate analysis testshelping to validate properly the system and also to reduce the over-dimensioning. This thesis is interested in the chasmexisting between real-time design community and real-time analysis community. The purpose of our work is to fill thegap between the modeling of real-time systems and the scheduling analysis. Then, we propose a decision aiding solutionbased on model-driven engineering. Our solution is dedicated (i) to increase the usage of the real-time scheduling theory,(ii) to facilitate the scheduling analysis tests choice and (iii) to reduce the pessimism during the design phase of real-timesystems.Our proposal is embodied as a framework unifying the designers and analysts efforts. The framework called MoSaRToffers a design language very close to the taxonomy of real-time scheduling theory. Moreover, MoSaRT provides ananalysis repository concept to enhance the applicability of the scheduling theory and also to improve the way designerscheck their designs.; Les systèmes embarqués temps réel nécessitent une analyse temporelle pour valider leur comportement temporel.Afin de réduire le coût de développement, l’analyse doit être effectuée à une phase précoce au moment de la modélisationpour détecter les anomalies de conception. L’analyse d’ordonnançabilité est une des analyses temporelles qui permettentde s’assurer du bon fonctionnement du système conçu. Elle est issue de la théorie de l’ordonnancement temps réel.Plusieurs méthodes et tests analytiques ont été proposés par la communauté académique mais peu sont les tests adoptéspar les industriels. En effet, l’utilisation des tests d’analyse exige une large connaissance des travaux de recherches - misà jour régulièrement - afin de choisir la méthode la plus adaptée aux systèmes conçus pour les valider ou les dimensionnerpour le cas des systèmes qui sont en cours de conception.Cette thèse s’intéresse à cette utilisation minimaliste de la théorie de l’ordonnancement dans l’industrie, et propose dessolutions d’aide à la décision basées sur l’ingénierie dirigée par les modèles. Nos solutions visent à augmenter l’applicabilitéde la théorie de l’ordonnancement, à faciliter le choix des tests appropriés et à réduire le surdimensionnement qui peutêtre généré au moment de la conception. Ces solutions sont implémentées dans un Framework appelé MoSaRT offrantdes fonctionnalités pour les concepteurs (modeleurs et analystes) afin d’améliorer le processus de conception des systèmestemps réel en vue de leur ordonnançabilité.

Real-time embedded systems need to be analyzed at an early stage in order to detect temporal vulnerabilities. Indeed,software development costs are sharply impacted by wrong design choices made in the early stages of development, inparticular during the design phase, but often detected after the implementation. The schedulability analysis is one of themain analyses required to ensure the timing correctness of a real-time system. Indeed, the real-time scheduling theoryhas been devoted to propose different models providing several levels of expressiveness, and different analytical methodswith different levels of accuracy. The utilization of the real-time scheduling theory in practical cases could be profitable.Unfortunately, it is not sufficiently applied and research results have been exploited in an industrial context only to amodest extent to date. Actually, a difficulty faced by the real-time designers is to find the appropriate analysis testshelping to validate properly the system and also to reduce the over-dimensioning. This thesis is interested in the chasmexisting between real-time design community and real-time analysis community. The purpose of our work is to fill thegap between the modeling of real-time systems and the scheduling analysis. Then, we propose a decision aiding solutionbased on model-driven engineering. Our solution is dedicated (i) to increase the usage of the real-time scheduling theory,(ii) to facilitate the scheduling analysis tests choice and (iii) to reduce the pessimism during the design phase of real-timesystems.Our proposal is embodied as a framework unifying the designers and analysts efforts. The framework called MoSaRToffers a design language very close to the taxonomy of real-time scheduling theory. Moreover, MoSaRT provides ananalysis repository concept to enhance the applicability of the scheduling theory and also to improve the way designerscheck their designs.; Les systèmes embarqués temps réel nécessitent une analyse temporelle pour valider leur comportement temporel.Afin de réduire le coût de développement, l’analyse doit être effectuée à une phase précoce au moment de la modélisationpour détecter les anomalies de conception. L’analyse d’ordonnançabilité est une des analyses temporelles qui permettentde s’assurer du bon fonctionnement du système conçu. Elle est issue de la théorie de l’ordonnancement temps réel.Plusieurs méthodes et tests analytiques ont été proposés par la communauté académique mais peu sont les tests adoptéspar les industriels. En effet, l’utilisation des tests d’analyse exige une large connaissance des travaux de recherches - misà jour régulièrement - afin de choisir la méthode la plus adaptée aux systèmes conçus pour les valider ou les dimensionnerpour le cas des systèmes qui sont en cours de conception.Cette thèse s’intéresse à cette utilisation minimaliste de la théorie de l’ordonnancement dans l’industrie, et propose dessolutions d’aide à la décision basées sur l’ingénierie dirigée par les modèles. Nos solutions visent à augmenter l’applicabilitéde la théorie de l’ordonnancement, à faciliter le choix des tests appropriés et à réduire le surdimensionnement qui peutêtre généré au moment de la conception. Ces solutions sont implémentées dans un Framework appelé MoSaRT offrantdes fonctionnalités pour les concepteurs (modeleurs et analystes) afin d’améliorer le processus de conception des systèmestemps réel en vue de leur ordonnançabilité.

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.

Colloque sur invitation.; Le standard Posix 1003.1b, auquel se conforme la grande majorité des OS temps réel, définit les politiques d'ordonnancement FPP (Fixed Priority Preemptive) et Round Robin. Cet exposé fera une synthèse des résultats portant sur l'ordonnancement de tâches sous Posix1003.1b ; seront traités les points suivants : * complétude et non-ambiguïté des spécifications ? * comment analyser l'ordonnançabilité sous Posix 1003.1b ? * comment choisir les politiques et les priorités pour une application ? * quelles stratégies d'ordonnancement DVS (Dynamic Voltage Scaling) sous Posix 1003.1b ? Finalement, nous verrons comment ces résultats restent valables lorsque l'implémentation fait usage de threads, dont le comportement est défini par Posix1003.1c.

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.