Concurrent programs are pervasive owing to the increasing adoption of multi-core systems across the entire computing spectrum. However, the large set of possible program behaviors make it difficult to write correct and efficient con-current programs. This also makes the formal and automated analysis of such programs a hard problem. Thus, concurrent programs provide fertile grounds for a large class of insidious defects. Static analysis techniques infer semantic properties of programs without executing them. They are attractive because they are sound (they can guarantee the absence of bugs), can execute with a fair degree of automation, and do not depend on test cases. However, current static analyses techniques for concurrent programs are either precise and prohibitively slow, or fast but imprecise. In this thesis, we partially address this problem by designing efficient static analyses for concurrent programs. In the first part of the thesis, we provide a framework for designing and proving the correctness of data flow analysis for race free multi-threaded programs. The resulting analyses are in the same spirit as the \sync-CFG" analysis, originally proposed in De et al, 2011. Using novel thread-local semantics as starting points, we devise abstract analyses which treat a concurrent program as if it were sequential. We instantiate these abstractions to devise efficient relational analyses for race free programs, which we have implemented in a prototype tool called RATCOP. On the benchmarks, RATCOP was fairly precise and fast. In a comparative study with a recent concurrent static analyzer, RATCOP was up to 5 orders of magnitude faster. In the second part of the thesis, we propose a technique for detecting all high-level data races in a system library, like the kernel API of a real-time operating system (RTOS) that relies on ag-based scheduling and synchronization. Such races are good indicators of atomicity violations. Using our technique, a user is able to soundly disregard 99:8% of an estimated 41; 000 potential high-level races. Our tool detected 38 high-level data races in FreeRTOS (a popular OS in the embedded systems domain), out of which 16 were harmful.

Due to higher requirements of computational power and safety, or functional safety ofequipments intended for the use in the industrial domain, embedded systems containing areal-time operating system are still the active area of research. This thesis addresses thehardware-assisted control module that is based on the runtime model-based verificationof a target application. This subsystem is intended to increase the diagnostic coverage,particularly, the detection of the execution errors. After the specification of the architecture,the formal model is defined and implemented into hardware using FPGA technology.This thesis also discuss some other aspects and embodies new approaches in the area ofembedded flow control, e.g. the integration of the design patterns. Using the simulation,the created module was tested using the created scenarios, which follow the real programexecution record. The results suggest that the error detection time is lower than usingstandard techniques, such a watchdog.

This diploma thesis deals with control the Ball on the wheel system in real time. In the first part there is made mathematical model of system, which is described by state equations. Then the laboratory model of Ball on the wheel system and its parts are described. The laboratory model consists servo drive, servo amplifier, microcontroller with real-time operating system and distance sensors. In the practical part of the thesis there is designed control of system by linear quadratic regulator and its implementation with control peripherals into microcontroller with real-time operating system. Ball on the wheel system is controlled by microcontroller, which sends a commands to servo amplifier by CAN bus.

This thesis concerns of benchmarking $\mu$C/OS-II systems on different microcontroller architectures. The thesis describes COS-II microcontroller core and possible series of benchmark tests which can be used. Selected tests are implemented and measured properties of microcontrollers with different architecture are compared.

This thesis deals with extensions of uC/OS-II kernel services. These extensions are about advanced task scheduling mechanisms. Source code of this operating system is wide open and can be, in accordance with licence agreement, modified and extended with additional capabilities. Functionality of implemented scheduling algorithms is at the end verified using tools Cheddar and TimesTool.

Les systèmes embarqués sont de plus en plus présents dans notre quotidien, à l’instar des téléphones ou des équipements des voitures modernes. Les systèmes embarqués modernes utilisent des plates-formes de plus en plus complexes. Après avoir longtemps utilisé un seul processeur, les plates-formes modernes peuvent désormais contenir plusieurs processeurs. Depuis quelques années, afin de continuer à améliorer la performance de ces systèmes à moindre coût, certaines de ces plates-formes embarquent désormais plusieurs processeurs différents, parfois même capables de modifier rapidement leurs caractéristiques pendant l’exécution du système. C’est ce qu’on appelle des plates-formes hétérogènes.Cette thèse traite de l’ordonnancement d’applications temps réel strict pour des plates-formes hétérogènes reconfigurables. Établir une polituqe d’ordonnancement consiste à garantir l’exécution d’ensembles de tâches récurrentes, avec le respect des contraintes temporelles de chaque tâche. Dans un contexte de temps réel strict, une tâche doit nécessairement être pleinement exécutée avant son échéance. Tout retard pourrait compromettre la sécurité du système ou des utilisateurs.Produire un ordonnancement temps réel strict efficace pour de telles plates-formes hétérogènes est particulièrement difficile. En effet, la vitesse d’exécution d’un processeur d’une telle plates-forme dépend à la fois du type du processeur et de la tâche exécutée. Cela rend les tâches difficilement interchangeables et augmente ainsi considérablement la complexité des polituqes d’ordonnancement. De plus, le coût d’une migration – le déplacement d’une tâche en cours d’exécution – d’un processeur à un autre est élevé, ce qui peut rendre les polituqes d’ordonnancement peu efficaces en pratique.Dans cette thèse, deux voies sont explorées pour tirer parti des possibilités offertes par ces plates-formes hétérogènes. Tout d’abord, en proposant un ordonnanceur dit global, qui permet une utilisation théorique de l’entièreté de la plates-forme. Pour atteindre cet objectif, nous isolons différents sous-problèmes, en suivant un schéma établi par la littérature existante. Pour chaque sous-problème, nous proposons une amélioration significative par rapport à l’état de l’art. L’ensemble constitue un nouvel ordonnanceur. Une évaluation empirique montre que ses performances sont bien supérieures à celles des ordonnanceurs existants. De plus, la polituqe d’ordonnancement proposée a une meilleure applicabilité, car elle réduit le nombre de migrations d’un processeur à un autre.Une deuxième voie explorée est le paradigme d’application dite multimode. Nous proposons ici le premier modèle où le matériel comme le logiciel peuvent être modifiés pendant l’exécution de l’application, afin de s’adapter au contexte dans lequel elle se trouve. Enfin, deux nouveaux protocoles utilisant ce modèle sont proposés et évalués. Il est montré théoriquement et empiriquement que ces protocoles présentent une faible complexité et de bonnes performances, et correspondent donc au besoin d’applications réelles. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

This thesis introduces the reader into RespiHeart, which is a product under development. RespiHeart is an complement/alternative to the regular Pulse Oximeter and is intended to be used within the health care sector for combined measurements and communication on open inexpensive platforms. This thesis evaluates interaction between RespiHeart and a Raspberry Pi 3 Model B to evaluate if the computer is capable of handling the data from RespiHeart and make signal processing. Python is used throughout the whole project and is a suitable language for interaction and signal processing in real time. / Detta examensarbete introducerar läsaren till RespiHeart, en ny trådlös produkt som är under utveckling. RespiHeart är ett komplement/alternativ till den nuvarande Pulsoximetern och är tänkt att användas inom sjukvården för analys, kommuniakation och kombinerade mätningar på öppna billiga plattformar. Detta project utvärderar interaktionen mellan RespiHeart och en Raspberry Pi 3 Model B för att undersöka om datorn är kapabel till att hantera datan från RespiHeart samt göra signal processing i real tid. Programmeringsspråket Python användes under hela projektet och är ett lämpligt språk att använda för interation och signal processing i real tid.

Concevoir un système embarqué implique de trouver un compromis algorithme/architecture en fonction des contraintes temps-réel. Thèse : pour concevoir un MPSoC et plus particulièrement avec les circuits reconfigurables modifiant le support d'exécution en cours de fonctionnement, la nécessaire validation des comportements fluctuants d'un système réactif impose une évaluation préalable que l'on peut réaliser par simulation (de haut niveau) tout en permettant l'exploration de l'espace de conception architectural, matériel mais aussi logiciel, au plus tôt dans le flot de conception. Le point de vue du gestionnaire de la plateforme est adopté pour explorer à haut niveau les réactions du système aux choix de partitionnement impactés par l'algorithmique des services du système d'exploitation et leurs implémentations possibles. Pour cela un modèle modulaire de services d'OS simule fonctionnellement et conjointement en SystemC le matériel, les tâches logicielles et le système d'exploitation, répartis sur plusieurs noeuds d'exécution hétérogènes communicants. Ce modèle a permis d'évaluer l'architecture temps-réel idéale d'une application dynamique de vision robotique conjointement à l'exploration des services de gestion d'une zone reconfigurable modélisée. Ce modèle d'OS a aussi été intégré dans un simulateur de MPSoC hétérogène d'une puissance estimé à un Tera opérations par seconde.

Optimisation of Performance Metrics of Embedded Hard Real-Time Systems using Software/Hardware Parallelism. Nowadays, embedded systems are part of our daily lives.Some of these systems are called safetycritical and have strong requirements in terms of safety and reliability.Additionally, these systems must have a long autonomy, good performance and minimal costs.Finally, these systems must exhibit predictable behaviour and provide their results within firm deadlines.When these different constraints are combined in the requirement specifications of a modern product, classic design techniques making use of single core platforms are not sufficient.Academic research in the field of real-time embedded systems has produced numerous techniques to exploit the capabilities of modern hardware platforms.These techniques are often based on using parallelism inherently present in modern hardware to improve the system performance while reducing the platform power dissipation.However, very few systems existing on the market are using these state-of-the-art techniques.Moreover, few of these techniques have been validated in the context of practical experiments.In this thesis, we realise the study of operating system level techniques allowing to exploit hardware parallelism through the implementation of parallel software in order to boost the performance of target applications and to reduce the overall system energy consumption while satisfying strict application timing requirements.We detail the theoretical foundations of the ideas applied in the dissertation and validate these ideas through experimental work.To this aim, we use a new Real-Time Operating System kernel written in the context of the creation of a spin-off of the Université libre de Bruxelles.Our experiments are based on the execution of applications on the operating system which run on a real-world platform for embedded systems.Our results show that, compared to traditional design techniques, using parallel and power-aware scheduling techniques in order to exploit hardware and software parallelism allows to execute embedded applications with substantial savings in terms of energy consumption.We present future and ongoing research work that exploit the capabilities of recent embedded platforms.These platforms combine multi-core processors and reconfigurable hardware logic, allowing further improvements in performance and energy consumption. / Optimisation de Métriques de Performances de Systèmes Embarqués Temps Réel Durs par utilisation du Parallélisme Logiciel et Matériel. De nos jours, les systèmes embarqués font partie intégrante de notre quotidien.Certains de ces systèmes, appelés systèmes critiques, sont soumis à de fortes contraintes de fiabilité et de robustesse.De plus, des contraintes de coûts, d’autonomie et de performances s’additionnent à la fiabilité.Enfin, ces systèmes doivent très souvent respecter des délais très stricts de façon prédictible.Lorsque ces différentes contraintes sont combinées dans le cahier de charge d’un produit, les techniques classiques de conception consistant à utiliser un seul cœur d’un processeur ne suffisent plus.La recherche académique dans le domaine des systèmes embarqués temps réel a produit de nombreuses techniques pour exploiter les plate-formes modernes.Ces techniques sont souvent basées sur l’exploitation du parallélisme inhérent au matériel pour améliorer les performances du système et la puissance dissipée par la plate-forme.Cependant, peu de systèmes existant sur le marché exploitent ces techniques de la littérature et peu de ces techniques ont été validées dans le cadre d’expériences pratiques.Dans cette thèse, nous réalisons l’étude des techniques, au niveau du système d’exploitation, permettant l’exploitation du parallélisme matériel par l’implémentation de logiciels parallèles afin de maximiser les performances et réduire l’impact sur l’énergie consommée tout en satisfaisant les contraintes temporelles strictes du cahier de charge applicatif. Nous détaillons les fondements théoriques des idées qui sont appliquées dans la dissertation et nous les validons par des travaux expérimentaux.A ces fins, nous utilisons le nouveau noyau d’un système d’exploitation écrit dans le cadre de la création d’une spin-off de l’Université libre de Bruxelles.Nos expériences, basées sur l’exécution d’applications sur le système d’exploitation qui s’exécute lui-même sur une plate-forme embarquée réelle, montre que l’utilisation de techniques d’ordonnancement exploitant le parallélisme matériel et logiciel permet de larges économies d’énergie consommée lors de l’exécution d’applications embarquées.De futurs travaux en cours de réalisation sont présentés.Ceux-ci exploitent des plate-formes innovantes qui combinent processeurs multi-cœurs et matériel reconfigurable, permettant d’aller encore plus loin dans l’amélioration des performances et les gains énergétiques. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

This thesis is about techniques for proving the functional correctness of Abstract Data Type (ADT) implementations. We provide a framework for proving the functional correctness of imperative language implementations of ADTs, using a theory of refinement. We develop a theory of refinement to reason about both declarative and imperative language implementations of ADTs. Our theory facilitates compositional reasoning about complex implementations that may use several layers of sub-ADTs. Based on our theory of refinement, we propose a methodology for proving the functional correctness of an existing imperative language implementation of an ADT. We propose a mechanizable translation from an abstract model in the Z language to an abstract implementation in VCC’s ghost language. Then we present a technique to carry out the refinement checks completely within the VCC tool. We apply our proposed methodology to prove the functional correctness of the scheduling-related functionality of FreeRTOS, a popular open-source real-time operating system. We focused on the scheduler-related functionality, found major deviations from the intended behavior, and did a machine-checked proof of the correctness of the fixed code. We also present an efficient way to phrase the refinement conditions in VCC, which considerably improves VCC’s performance. We evaluated this technique on a simplified version of FreeRTOS which we constructed for this verification exercise. Using our efficient approach, VCC always terminates and leads to a reduction of over 90% in the total time taken by a naive check, when evaluated on this case-study.