This thesis is concerned with the modeling and the analysis of distributedreal-time systems. In distributed systems, components evolve partlyindependently: concurrent actions may be performed in any order, withoutinfluencing each other and the state reached after these actions does notdepends on the order of execution. The time constraints in distributed real-timesystems create complex dependencies between the components and the events thatoccur. So far, distributed real-time systems have not been deeply studied, andin particular the distributed aspect of these systems is often left aside. Thisthesis explores distributed real-time systems. Our work on distributed real-timesystems is based on two formalisms: time Petri nets and networks of timedautomata, and is divided into two parts.In the first part, we highlight the differences between centralized anddistributed timed systems. We compare the main formalisms and their extensions,with a novel approach that focuses on the preservation of concurrency. Inparticular, we show how to translate a time Petri net into a network of timedautomata with the same distributed behavior. We then study a concurrency relatedproblem: shared clocks in networks of timed automata can be problematic when oneconsiders the implementation of a model on a multi-core architecture. We showhow to avoid shared clocks while preserving the distributed behavior, when thisis possible.In the second part, we focus on formalizing the dependencies between events inpartial order representations of the executions of Petri nets and time Petrinets. Occurrence nets is one of these partial order representations, and theirstructure directly provides the causality, conflict and concurrency relationsbetween events. However, we show that, even in the untimed case, some logicaldependencies between event occurrences are not directly described by thesestructural relations. After having formalized these logical dependencies, wesolve the following synthesis problem: from a formula that describes a set ofruns, we build an associated occurrence net. Then we study the logicalrelations in a simplified timed setting and show that time creates complexdependencies between event occurrences. These dependencies can be used to definea canonical unfolding, for this particular timed setting.

Les architectures pluri-coeurs sont plus intéressantes pour concevoir des systèmes en temps réel que les systèmes multi-coeurs car il est possible de les maîtriser plus facilement et d’intégrer un plus grand nombre d’applications, potentiellement de différents niveau de criticité. Dans les systèmes temps réel embarqués, ces architectures peuvent être utilisées comme des éléments de traitement au sein d’un réseau fédérateur car ils fournissent un grand nombre d’interfaces Entrées/Sorties telles que les contrôleurs Ethernet et les interfaces de la mémoire DDR-SDRAM. Aussi, il est possible d’y allouer des applications ayant différents niveaux de criticités. Ces applications communiquent entre elles à travers le réseau sur puce (NoC) du pluri coeur et avec des capteurs et des actionneurs via l’interface Ethernet. Afin de garantir les contraintes temps réel de ces applications, les délais de transmission pire cas (WCTT) doivent être calculés pour les flux entre les coeurs ("inter-core") et les flux entre les coeurs et les interfaces entrées/sorties ("core-to-I/O"). Plusieurs réseaux sur puce (NoCs) ciblant les systèmes en temps réel dur ont été conçus en s’appuyant sur des extensions matérielles spécifiques. Cependant, aucune de ces extensions ne sont actuellement disponibles dans les architectures de réseaux sur puce commercialisés, qui se basent sur la commutation wormhole avec la stratégie d’arbitrage par tourniquet. En utilisant cette stratégie de commutation, différents types d’interférences peuvent se produire sur le réseau sur puce entre les flux. De plus, le placement de tâches des applications critiques et non critiques a un impact sur les contentions que peut subir les flux "core-to-I/O". Ces flux "core-to-I/O" parcourent deux réseaux de vitesses différentes: le NoC et Ethernet. Sur le NoC, la taille des paquets autorisés est beaucoup plus petite que la taille des trames Ethernet. Ainsi, lorsque la trame Ethernet est transmise sur le NoC, elle est divisée en plusieurs paquets. La trame sera supprimée de la mémoire tampon de l’interface Ethernet uniquement lorsque la totalité des données aura été transmise. Malheureusement, la congestion du NoC ajoute des délais supplémentaires à la transmission des paquets et la taille de la mémoire tampon de l’interface Ethernet est limitée. En conséquence, ce comportement peut aboutir au rejet des trames Ethernet. L’idée donc est de pouvoir analyser les délais de transmission pire cas sur les NoC et de réduire leurs délais afin d’éviter ce problème de rejet. Dans cette thèse, nous montrons que le pessimisme de méthodes existantes de calcul de WCTT et les stratégies de placements existantes conduisent à rejeter des trames Ethernet en raison d’une congestion interne sur le NoC. Des propriétés des réseaux utilisant la commutation "wormhole" ont été définies et validées afin de mieux prendre en compte les conflits entre les flux. Une stratégie de placement de tâches qui prend en compte les communications avec les I/O a été ensuite proposée. Cette stratégie vise à diminuer les contentions des flux qui proviennent de l’I/O et donc de réduire leurs WCTTs. Les résultats obtenus par la méthode de calcul définie au cours de cette thèse montrent que les valeurs du WCTT des flux peuvent être réduites jusqu’à 50% par rapport aux valeurs de WCTT obtenues par les méthodes de calcul existantes. En outre, les résultats expérimentaux sur des applications avioniques réelles montrent des améliorations significatives des délais de transmission des flux "core-to-I/O", jusqu’à 94%, sans impact significatif sur ceux des flux "intercore". Ces améliorations sont dues à la stratégie d’allocation définie qui place les applications de manière à réduire l’impact des flux non critiques sur les flux critiques. Ces réductions de WCTT des flux "core-to-I/O" évitent le rejet des trames Ethernet. / Many-core architectures are more promising hardware to design real-time systems than multi-core systems as they should enable an easier mastered integration of a higher number of applications, potentially of different level of criticalities. In embedded real-time systems, these architectures will be integrated within backbone Ethernet networks, as they mostly provide Ethernet controllers as Input/Output(I/O) interfaces. Thus, a number of applications of different level of criticalities could be allocated on the Network-on-Chip (NoC) and required to communicate with sensors and actuators. However, the worst-case behavior of NoC for both inter-core and core-to-I/O communications must be established. Several NoCs targeting hard real-time systems, made of specific hardware extensions, have been designed. However, none of these extensions are currently available in commercially available NoC-based many-core architectures, that instead rely on wormhole switching with round-robin arbitration. Using this switching strategy, interference patterns can occur between direct and indirect flows on many-cores. Besides, the mapping over the NoC of both critical and non-critical applications has an impact on the network contention these core-to-I/O communications exhibit. These core-to-I/O flows (coming from the Ethernet interface of the NoC) cross two networks of different speeds: NoC and Ethernet. On the NoC, the size of allowed packets is much smaller than the size of Ethernet frames. Thus, once an Ethernet frame is transmitted over the NoC, it will be divided into many packets. When all the data corresponding to this frame are received by the DDR-SDRAM memory on the NoC, the frame is removed from the buffer of the Ethernet interface. In addition, the congestion on the NoC, due to wormhole switching, can delay these flows. Besides, the buffer in the Ethernet interface has a limited capacity. Then, this behavior may lead to a problem of dropping Ethernet frames. The idea is therefore to analyze the worst case transmission delays on the NoC and reduce the delays of the core-to-I/O flows. In this thesis, we show that the pessimism of the existing Worst-Case Traversal Time (WCTT) computing methods and the existing mapping strategies lead to drop Ethernet frames due to an internal congestion in the NoC. Thus, we demonstrate properties of such NoC-based wormhole networks to reduce the pessimism when modeling flows in contentions. Then, we propose a mapping strategy that minimizes the contention of core-to-I/O flows in order to solve this problem. We show that the WCTT values can be reduced up to 50% compared to current state-of-the-art real-time packet schedulability analysis. These results are due to the modeling of the real impact of the flows in contention in our proposed computing method. Besides, experimental results on real avionics applications show significant improvements of core-to-I/O flows transmission delays, up to 94%, without significantly impacting transmission delays of core-to-core flows. These improvements are due to our mapping strategy that allocates the applications in such a way to reduce the impact of non-critical flows on critical flows. These reductions on the WCTT of the core-to-I/O flows avoid the drop of Ethernet frames.

Despiste the fact that many scheduling models teoretically capable of high system resource utilization were proposed with the development of the real-time system, the industry still uses the first scheduling model proposed for multi-processor real-time systems, the partitioned scheduling model. This scheduling model can guarantee scheduling of task sets up to around 69% processor utilization, which falls pale in comparison to recent scheduling models that can guarantee scheduling up to 97% processor utilization. The motive behind the utilization of the partitioned scheduling as industrial model is the amount of studies made on this model and the development of scheduling analysis capable of providing temporal guarantees for this model on a real system environment. Recent scheduling models, like semi-partitioned scheduling, offer the possibility of a higher system resource utilization, it still lack studies and scheduling analysis capable of provide temporal guarantees under a real environment. The current scheduling analysis for most of the more recent models take advantage of a series of abstractions, failing to provide guarantees under real circumstances. This papers primary objective is to produce a new scheduling analysis for semi-partitioned scheduling, capable of achieving temporal guarantees taking some of the previously abstracted factors, like task communication and the impact f task migration on its communications flows, approximating the scheduling model to real environmental conditions. With the development of such analysis preliminary studies were made on heuristic task mapping algorithms for semipartitioned systems. / Com a popularização de sistemas multi-processador, surgiu uma série de propostas de modelos de escalonamento, na área de sistemas de tempo real que, teoricamente, são capazes de obter um alto aproveitamento dos recursos do sistema. Entretanto, o modelo de escalonamento mais adotado continua sendo um dos primeiros modelos de escalonamento propostos na área, o modelo de escalonamento particionado. O modelo de escalonamento particionado só pode garantir o escalonamento de conjuntos com até cerca de 69% de utilização de processador, sendo limitado se comparado com garantias de escalonamento de até 97% de utilização de modelos mais recentes. O motivo pelo qual o escalonamento particionado continua sendo utilizado é a grande concentração de estudos a respeito do modelo e o desenvolvimento de análises de escalonamento capazes de garantir o escalonamento do modelo em condições reais do sistema. Modelos mais recentes, como o escalonamento semi-particionado, apresentam uma possibilidade de um maior aproveitamento do sistema, porém, ainda possuem estudos limitados e não dispõe de análises de escalonamento capazes de prover garantias temporais para o sistema em condições reais, devido à presença de diversas abstrações no modelo. Neste sentido, este trabalho foca em arquiteturas Network-on-Chip que apresentam comunicação explícita, abstraída nos trabalhos encontrados na literatura. Este trabalho tem como objetivo primário o desenvolvimento de uma análise de escalonamento capaz de prover garantias temporais para o modelo de escalonamento semi-particionado levando em consideração fatores previamente abstraídos, como a necessidade de comunicação entre tarefas e o impacto da migração das tarefas nos seus fluxos de comunicação, aproximando o modelo da realidade. O desenvolvimento de tal análise possibilita o estudo preliminar de algoritmos heurísticos de mapeamento de tarefas, capazes de mapear conjuntos de tarefas levando em consideração migrações de tarefas e comunicação entre tarefas em um modelo de escalonamento semi-particionado.

La prédictibilité est un aspect important des systèmes temps-réel critiques. Garantir la fonctionnalité de ces systèmespasse par la prise en compte des contraintes temporelles. Les architectures mono-cœurs traditionnelles ne sont plussuffisantes pour répondre aux besoins croissants en performance de ces systèmes. De nouvelles architectures multi-cœurssont conçues pour offrir plus de performance mais introduisent d'autres défis. Dans cette thèse, nous nous intéressonsau problème d’accès aux ressources partagées dans un environnement multi-cœur.La première partie de ce travail propose une approche qui considère la modélisation de programme avec des formules desatisfiabilité modulo des théories (SMT). On utilise un solveur SMT pour trouverun chemin d’exécution qui maximise le temps d’exécution. On considère comme ressource partagée un bus utilisant unepolitique d’accès multiple à répartition dans le temps (TDMA). On explique comment la sémantique du programme analyséet le bus partagé peuvent être modélisés en SMT. Les résultats expérimentaux montrent une meilleure précision encomparaison à des approches simples et pessimistes.Dans la deuxième partie, nous proposons une analyse de temps de réponse de programmes à flot de données synchroness'exécutant sur un processeur pluri-cœur. Notre approche calcule l'ensemble des dates de début d'exécution et des tempsde réponse en respectant la contrainte de dépendance entre les tâches. Ce travail est appliqué au processeur pluri-cœurindustriel Kalray MPPA-256. Nous proposons un modèle mathématique de l'arbitre de bus implémenté sur le processeur. Deplus, l'analyse de l'interférence sur le bus est raffinée en prenant en compte : (i) les temps de réponseet les dates de début des tâches concurrentes, (ii) le modèle d'exécution, (iii) les bancsmémoires, (iv) le pipeline des accès à la mémoire. L'évaluation expérimentale est réalisé sur desexemples générés aléatoirement et sur un cas d'étude d'un contrôleur de vol. / Predictability is of paramount importance in real-time and safety-critical systems, where non-functional properties --such as the timing behavior -- have high impact on the system's correctness. As many safety-critical systems have agrowing performance demand, classical architectures, such as single-cores, are not sufficient anymore. One increasinglypopular solution is the use of multi-core systems, even in the real-time domain. Recent many-core architectures, such asthe Kalray MPPA, were designed to take advantage of the performance benefits of a multi-core architecture whileoffering certain predictability. It is still hard, however, to predict the execution time due to interferences on sharedresources (e.g., bus, memory, etc.).To tackle this challenge, Time Division Multiple Access (TDMA) buses are often advocated. In the first part of thisthesis, we are interested in the timing analysis of accesses to shared resources in such environments. Our approach usesSatisfiability Modulo Theory (SMT) to encode the semantics and the execution time of the analyzed program. To estimatethe delays of shared resource accesses, we propose an SMT model of a shared TDMA bus. An SMT-solver is used to find asolution that corresponds to the execution path with the maximal execution time. Using examples, we show how theworst-case execution time estimation is enhanced by combining the semantics and the shared bus analysis in SMT.In the second part, we introduce a response time analysis technique for Synchronous Data Flow programs. These are mappedto multiple parallel dependent tasks running on a compute cluster of the Kalray MPPA-256 many-core processor. Theanalysis we devise computes a set of response times and release dates that respect the constraints in the taskdependency graph. We derive a mathematical model of the multi-level bus arbitration policy used by the MPPA. Further,we refine the analysis to account for (i) release dates and response times of co-runners, (ii)task execution models, (iii) use of memory banks, (iv) memory accesses pipelining. Furtherimprovements to the precision of the analysis were achieved by considering only accesses that block the emitting core inthe interference analysis. Our experimental evaluation focuses on randomly generated benchmarks and an avionics casestudy.

Submitted by Lucienne Costa (lucienneferreira@ufcg.edu.br) on 2018-05-02T20:48:28Z No. of bitstreams: 1 ALAN KELON OLIVEIRA DE MORAES – TESE (PPGCC) 2017.pdf: 2206784 bytes, checksum: 9e05994ae273d28b9871d8d16769dac8 (MD5) / Made available in DSpace on 2018-05-02T20:48:28Z (GMT). No. of bitstreams: 1 ALAN KELON OLIVEIRA DE MORAES – TESE (PPGCC) 2017.pdf: 2206784 bytes, checksum: 9e05994ae273d28b9871d8d16769dac8 (MD5) Previous issue date: 2017-08-31 / O teste baseado em modelos é uma abordagem de teste de software que usa modelos abstratos de uma aplicação para gerar, executar e avaliar os testes. A geração de casos de testes exerce um papel importante no teste baseado em modelos. Como essa geração consiste na busca sistemática por casos de testes que possam ser extraídos dos modelos, o teste baseado em modelos geralmente produz suítes de testes que são caras demais para serem executadas completamente. Técnicas de redução de suítes de testes têm sido propostas para abordar este problema. O objetivo dessas técnicas é obter suítes de testes reduzidas que são mais baratas de serem executadas e tão efetivas na detecção de faltas quanto as suítes completas, dado que as suítes reduzidas mantém o mesmo nível de cobertura, definido por um critério de adequação de testes, da suíte completa. Esses critérios definem que partes do sistema serão testados, com que frequência e sob quais circunstâncias. Entretanto, pouca atenção tem sido dada ao impacto que a escolha do critério tem na redução de suítes de testes. Por outro lado, sistemas de tempo-real são sistemas reativos cujos comportamentos são restringidos pelo tempo. Consequentemente, faltas relacionadas ao tempo são específicas desses sistemas. Para lidar com isso, modelos para sistemas de tempo real devem trabalhar com tempo e, consequentemente, há critérios de adequação de testes específicos para eles. Contudo, a pesquisa sobre redução de suítes de testes não tem focado em sistemas de tempo-real, portanto o impacto de critérios de adequação de testes na redução de suítes é desconhecido. Nesta pesquisa de doutorado objetivamos investigar a influência de critérios de adequação de testes nos resultados da redução de suítes de testes no contexto de teste baseado em modelos de sistemas de tempo-real. Em particular, nós estamos interessados no modelo Timed Input-Output Symbolic Transition Systems (TIOSTS), porque ele é um modelo de sistema de transições no qual dados e tempo são definidos simbolicamente, já que sistemas de transição são a base para o teste de conformidade de sistemas de tempo real. Para alcançar o objetivo da pesquisa, primeiramente, nós definimos 19 critérios de adequação de testes para o modelo TIOSTS. Os critérios definidos incluem critérios baseados em transições, fluxo de dados e tempo. Depois nós formalizamos uma hierarquia com esses critérios, onde eles estão parcialmente ordenados pela relação de inclusão estrita. Segundamente, nós avaliamos empiricamente o custo-benefício de doze dos critérios definidos e cinco técnicas de redução de suítes de testes. Nós avaliamos o tamanho, o tempo de execução e a detecção de faltas das suítes de testes reduzidas de cada uma das 60 combinações de critério e técnica. No experimento, nós usamos modelos de especificação, em TIOSTS, de uma máquina de recarga de cartão do metrô, de um sistema de alarme anti-roubo e de um limitador automático de velocidade de carros. Além disso, usamos simulações das implementações, que geram rastros corretos para os modelos. Por fim, o teste de mutação foi usado para gerar mutantes dos modelos de especificação, que, por sua vez, foram traduzidos para simulações com a finalidade de simular modelos de implementações defeituosas. As evidências empíricas sugerem que os critérios de adequação de testes mais próximos do topo da hierarquia produziram suítes reduzidas com melhor custo-benefício com relação à detecção de faltas e tempo de execução. Com relação às técnicas de redução, a técnica aleatória obteve melhor custo-benefício dentre as técnicas avaliadas. Os resultados apontam que os critérios explicam mais a variação nos resultados do que as técnicas. / Model-based testing is a testing approach that relies on the existence of abstract models of an application to generate, execute and evaluate tests. Test case generation plays an important role in model-based testing. Since it consists of a systematic search for test cases that can be extracted from models, model-based testing usually generates large test suites which are too expensive to execute in full. Test suite reduction techniques have been proposed to address this problem. The goal of the techniques is to obtain reduced test suites that are both cheaper to execute and as effective at detecting faults as the original suite, given that the reduced test suites maintain the same coverage level of the complete test suite required by a test adequacy criterion. These criteria define which parts of the system are going to be tested, how often and under what circumstances. Nevertheless, little attention has been paid to the impact of the criterion choice in test suite reduction research. On the other hand, real-time systems are reactive systems whose behavior is constrained by time. Consequently, time-related faults are specific to these systems. In order to cope with this issue, models for real-time systems must deal with time and, consequently, there are specific test adequacy criteria for them. However, test suite reduction research has not focused on real-time systems, therefore the impact of test adequacy criteria for models of real-time systems on test suite reduction is unknown. In this doctoral research, we aim at investigating the influence of test adequacy criteria on the outcomes of test suite reduction techniques in the context of model-based testing of real-time systems. In particular, we are interested in the Timed Input-Output Symbolic Transition Systems (TIOSTS) model because it is an expressive transition system in which data and time are symbolically defined, and transition systems are the basis for conformance testing of real-time systems. In order to achieve the research objective, first, we defined 19 test adequacy criteria for TIOSTS models. The defined criteria include transition-based criteria, data-flow-oriented criteria and real-time systems criteria. Next, we formalized a hierarchy with these criteria which is partially ordered by the strict inclusion relation. Second, we evaluated the cost-effectiveness of twelve criteria and five test suite reduction techniques in empirical studies of test suite reduction. We evaluated the size, execution time and fault detection of reduced test suites obtained from each combination of criterion and technique. In the experiment, we used TIOSTS specification models of a refilling machine for charging the subway card, a burglar alarm system, and an automated car speed limiter; simulations of the implementations, which generate correct traces for the models; and mutation testing to generate mutants of the specification models, which were also translated to simulations in order to simulate faulty model implementations. Empirical evidence suggests that test adequacy criteria closer to the top of the family obtained reduced test suites with better costeffectiveness regarding fault detection and execution time. With respect to the test suite reduction techniques, the Random technique obtained better cost-effectiveness among the evaluated criteria. Results also suggests that the criteria explain more the variation in fault detection and execution time of reduced test suites than the techniques.

Real-time systems do not only require that the logical operations are correct. Equally important is that the specified time constraints always are complied. This has successfully been studied before for mono-processor systems. However, as the hardware in the systems gets more complex, the previous approaches become invalidated. For example, multi-processor systems-on-chip (MPSoC) get more and more common every day, and together with a shared memory, the bus access time is unpredictable in nature. This has recently been resolved, but a safe and not too pessimistic cache analysis approach for MPSoC has not been investigated before. This thesis has resulted in designed and implemented algorithms for cache analysis on real-time MPSoC with a shared communication infrastructure. An additional advantage is that the algorithms include improvements compared to previous approaches for mono-processor systems. The verification of these algorithms has been performed with the help of data flow analysis theory. Furthermore, it is not known how different types of cache miss characteristic of a task influence the worst case execution time on MPSoC. Therefore, a program that generates randomized tasks, according to different parameters, has been constructed. The parameters can, for example, influence the complexity of the control flow graph and average distance between the cache misses.

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.

No description available.

This Master's project deals with implementation of uC/OS-II real-time operating system on FITkit 3 platform, its testing and proving its functionality with simple examples. Describes an example of uC/OS-II application for displaying images on a E-ink display and application of ECCA method for increasing fault tolerance of the system.

Unmanned, as well as manned space missions have seen a high failure rate in the early era of space technology. However, this decreased a lot since technology advanced and engineers learnt from previous experiences and improved critical real time systems with fault detection mechanisms. Fault detection, isolation and recovery, nowadays, is generally available in every flying device. However, the cost of hardware can bottleneck the process of creating such a system that is both robust and responsive. This thesis analyses the possibility of implementing a fault detection, isolation and recovery system inside of a single-threaded, cooperative scheduling operating system. The thesis suggests a cooperative implementation of such a system, where every task is responsible for parts of the fault detection. The analysis is done from both the integration layer, across the operating system and its tasks, as well as from the inside of the detection system, where two key components are implemented and analyzed: debug telemetry and operation modes. Results show that it is possible to implement a fault detection system that is spread across all the components of the satellite and acts cooperatively. Furthermore, the comparison with a traditional, dedicated fault detection system proves that errors can be caught faster with a cooperative mechanism. / Obemannade såväl som bemannade rymduppdrag har sett ett högt misslyckande i rymdteknikens tidiga era. Detta har dock förbättrats mycket sedan ingenjörer började lära sig av sina tidigare erfarenheter och utrustade kritiska realtidssystem med feldetekteringsmekanismer. Idag är alla flygande enheter utrustade med feldetekterings-, isolerings- och återställningsmekanismer. Däremot kan kostnaden för hårdvara vara ett problem för processen att skapa ett sådant system som är både robust och mottagligt. Denna uppsats analyserar möjligheten att implementera ett feldetekterings-, isolerings- och återställningssystem inuti ett enkelgängat samarbetsplaneringssystem. Denna uppsats föreslår ett samarbete för implementering av ett sådant system, där varje uppgift ansvarar för delar av feldetekteringen. Analysen görs från både integrationsskiktet, över operativsystemet och dess uppgifter, samt från insidan av detekteringssystemet, där två nyckelkomponenter implementeras och analyseras. Resultaten visar att det är möjligt att implementera ett feldetekteringssystem som täcker alla satellitkomponenter och som är mottaglig. Dessutom visar jämförelsen med ett traditionellt, dedikerat feldetekteringssystem att fel kan fångas snabbare med en mottagligmekanism. / Misiunile spat,iale cu oameni, atât cât s, i fara oameni, au avut o rata a es, ecurilor destul de ridicata în perioada init,iala a erei tehnologiei spat,iale. În schimb, aceasta a scazut semnificativ odata cu dezvoltarea tehnologiei, dar s, i datorita faptului ca inginerii au învat,at din experient,ele precendente s, i au îmbunatat, it sistemele critice în timp real cu mecanisme de detect,ie a erorilor. Sisteme de detect,ie, izolare s, i recuperare din erori sunt disponibile astazi în aproape toate sistemele spat,iale. Însa, costul echipamentelor poate împiedica crearea unor astfel de sisteme de detect,ie, care sa fie robuste s, i responsive. Aceasta teza analizeaza posibilitatea implementarii unui sistem de detect,ie, izolare s, i recuperare de la erori într-un satelit care este echipat cu un procesor cu un singur fir de execut,ie, care are un sistem de planificare cooperativ în sistemul de operare. Aceasta teza sugereaza o implementare cooperativa a unui astfel de sistem, unde fiecare proces este responsabil de câte o parte din detectarea erorilor. Analiza este realizata atât din perspectiva integrarii în sistemul de operare s, i procesele acestuia, cât s, i din interiorul acestui sistem de detect,ie, unde doua elemente importante sunt implementate s, i analizate: telemetria de depanare s, i modurile de operare. Rezultatele arata faptul ca este posibila implementarea unui sistem de detect,ie care este împart, it în toate componentele sistemului unui satelit s, i se comporta cooperativ. Mai departe, comparat,ia cu un sistem tradit,ional, dedicat, de detect,ie a erorilor arata ca erorile pot fi detectate mai rapid cu un sistem cooperativ.