Les systèmes temps-réel critiques sont de plus en plus complexes, et les exigences fonctionnelles et non-fonctionnelles ne cessent plus de croître. Le flot de conception de tels systèmes doit assurer, parmi d’autres propriétés, le déterminisme fonctionnel et la prévisibilité temporelle. Le déterminisme fonctionnel est inhérent aux modèles de calcul flot de données (ex. KPN, SDF, etc.) ; c’est pour cela qu’ils sont largement utilisés pour modéliser les systèmes embarqués de traitement de flux. Un effort considérable a été accompli pour résoudre le problème d’ordonnancement statique périodique et à mémoire de communication bornée des graphes flot de données. Cependant, les systèmes embarqués temps-réel optent de plus en plus pour l’utilisation de systèmes d’exploitation temps-réel et de stratégies d’ordonnancement dynamique pour gérer les tâches et les ressources critiques. Cette thèse aborde le problème d’ordonnancement temps-réel dynamique des graphes flot de données ; ce problème consiste à assigner chaque acteur dans un graphe à une tâche temps-réel périodique (i.e. calcul des périodes, des phases, etc.) de façon à : (1) assurer l’ordonnançabilité des tâches sur une architecture et pour une stratégie d’ordonnancement (ex. RM, EDF) données ; (2) exclure statiquement les exceptions d’overflow et d’underflow sur les buffers de communication ; et (3) optimiser les performances du système (ex. maximisation du débit, minimisation des tailles des buffers). / The ever-increasing functional and nonfunctional requirements in real-time safety-critical embedded systems call for new design flows that solve the specification, validation, and synthesis problems. Ensuring key properties, such as functional determinism and temporal predictability, has been the main objective of many embedded system design models. Dataflow models of computation (such as KPN, SDF, CSDF, etc.) are widely used to model stream-based embedded systems due to their inherent functional determinism. Since the introduction of the (C)SDF model, a considerable effort has been made to solve the static-periodic scheduling problem. Ensuring boundedness and liveness is the essence of the proposed algorithms in addition to optimizing some nonfunctional performance metrics (e.g. buffer minimization, throughput maximization, etc.). However, nowadays real-time embedded systems are so complex that real-time operating systems are used to manage hardware resources and host real-time tasks. Most of real-time operating systems rely on priority-driven scheduling algorithms (e.g. RM, EDF, etc.) instead of static schedules which are inflexible and difficult to maintain. This thesis addresses the real-time scheduling problem of dataflow graph specifications; i.e. transformation of the dataflow specification to a set of independent real-time tasks w.r.t. a given priority-driven scheduling policy such that the following properties are satisfied: (1) channels are bounded and overflow/underflow-free; (2) the task set is schedulable on a given uniprocessor (or multiprocessor) architecture. This problem requires the synthesis of scheduling parameters (e.g. periods, priorities, processor allocation, etc.) and channel capacities. Furthermore, the thesis considers two performance optimization problems: buffer minimization and throughput maximization.

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.

El objetivo de este trabajo es la definición de una metodología para la representación y análisis del comportamiento de tiempo real de sistemas que han sido diseñados utilizando el paradigma de orientación a objetos. La metodología que se propone, denominada UML-MAST, concilia las diferencias entre la visión del diseñador de sistemas de tiempo real y la del de sistemas orientados a objetos. A tal fin define un nivel de abstracción adecuado para los elementos de modelado del comportamiento de tiempo real, que permite formularlos con una estructura paralela a la arquitectura lógica del sistema, y vincularlos a esta. La semántica de modelado sigue el perfil UML para planificabilidad, rendimiento y tiempo (SPT) estandarizado por el OMG, del que UML-MAST puede considerase una implementación. La propuesta se integra con las herramientas de análisis y diseño de sistemas de tiempo real MAST (Modeling and Analysis Suite for Real-Time Applications), que analiza los modelos y retorna los resultados al modelo inicial para su interpretación por el diseñador. Asimismo, se han definido criterios para la extensión de esta metodología a otros niveles de abstracción tales como sistemas basados en componentes y sistemas implementados utilizando Ada 95. Parte de los resultados de este trabajo han sido incorporados por el OMG a su perfil SPT. / The main objective of this work has been the definition of a methodology for the representation and analysis of the timing behaviour of real-time distributed systems designed following the object oriented paradigm. The methodology proposed is called UML-MAST, and reconciles the mismatch between the visions of the object oriented designer and the real-time systems designer. To get this, it has been developed a particular level of abstraction that holds all the modelling elements needed to represent real-time behaviour, structuring the models following the logical architecture of the system. The semantics of the modelling elements follows the "UML Profile for Schedulability, Performance and Time" (SPT), a standard of the Object Management Group (OMG) to which this thesis has reported a number of contributions. UML-MAST can also be considered a particular specialization of its schedulability analysis sub-profile. UML-MAST is integrated in the framework of the Modeling and Analysis Suite for Real-Time Applications (MAST), a modelling environment with a set of tools that enable the analysis of a model and the recovery of its results in it. Criteria for the extension of the methodology to higher levels of abstraction have been defined. As examples, its extension to the modelling of component-based systems as well as to distributed systems developed with Ada95 have been explored and formulated.

El objetivo de la tesis es definir una metodología de desarrollo de aplicaciones de tiempo real basadas en componentes, orientada a aplicaciones cuyos requisitos temporales se especifican utilizando un modelo reactivo de comportamiento temporal. La metodología se construye en base a extensiones que incorporan a las especificaciones, modelos de referencia y procesos estándares propios de la ingeniería de componentes convencionales, esto es, sin requisitos temporales, los datos y los procesos necesarios para la especificación, diseño y análisis de los aspectos relativos al comportamiento temporal. La metodología se sustenta en cuatro contribuciones principales:- Se propone la metodología de modelado modular del comportamiento temporal Mod-MAST, que permite construir el modelo de una aplicación basada en componentes por composición de los modelos de los componentes que la forman. - Se propone la extensión RT-D&C de la especificación Deployment and Configuration of Component-based Distributed Applications de OMG, que permite incluir metadatos relativos a comportamiento temporal en los descriptores de componentes, plataformas de ejecución y aplicaciones. - Se especifica la tecnología de componentes RT-CCM como una extensión de la especificación estándar Lightweight CCM de OMG, que añade los mecanismos necesarios para desarrollar aplicaciones con comportamiento temporal predecible.- Se propone la tecnología de componentes Ada-CCM como implementación concreta de RT-CCM basada en el lenguaje de programación Ada 2005.Todos estos elementos se integran en un proceso completo de diseño de tiempo real de aplicaciones basadas en componentes. / The objective of this work is to define a methodology for the development of real-time component-based applications, focused on applications whose timing requirements are specified according to a reactive model of the timing behaviour. The methodology is built through a set of extensions that incorporate to the standard specifications, reference models and processes typical from the conventional components engineering, i.e. components without timing requirements, the data structures and the processes required for the specification, design and analysis of the aspects related to timing behaviour. The methodology relies on four main contributions:- The Mod-MAST modular modelling methodology, which allows building the real-time model of a component-based application by composing the models of the components that form it.- The RT-D&C extension of the Deployment and Configuration of Component-based Distributed Applications Specification of the OMG, which allows including metadata related to timing behaviour in the descriptors of components, execution platforms and applications.- The RT-CCM components technology, which is an extension of the standard Lightweight CCM Specification of the OMG that incorporates mechanisms to develop applications with predictable timing behaviour.- The Ada-CCM components technology has been developed. It is an implementation of the RT-CCM technology based on the Ada 2005 programming language.All these elements have been integrated in a complete real-time design process for component-based applications.

This project deals with given safeguard possibilities, both mechanical and electronic. A row house with garden was chosen for being secured. Subsequently, were elaborated two`s proposals of securing and guarding of this object. First, was based on camera`s system and second on common system ESS. Later on they were evaluated and the most considerable benefits were emphasized. A system based on control panel with connected detectors was selected upon specification. Subsequently was created a model of the chosen system, at which the required behaviour was simulated and verified. An outline of an implementation was created in the C language.