This thesis presents the design and evaluation of an operating system kernel specially designed for dataflow software. Dataflow is a style of software architecture that is well suited for control and "signal flow" applications. This architecture involves many small processes and lots of inter-process communication, which impose too much overhead on traditional RTOSes. This thesis describes design and implementation of the Dataflow Architecture Real-time Kernel (DARK). DARK is a reconfigurable, multithreaded and preemptive operating system kernel that introduces a special data-driven scheduling strategy for dataflow applications. It uses the underlying hardware for high-speed context switching between the kernel and applications, which is five times faster than the ordinary context switch. The features of the kernel can be configured according to performance requirements without change to the applications. Along with the performance evaluation of DARK, the performance comparison results of DARK with two commercial RTOSes: MicroC/OS-II and Analog Devices VDK++ are also provided. / Master of Science

Den tekniska utvecklingen driver fram allt mer avancerade datorsystem. Samtidigt ställs allt större krav på stabilitet och flexibilitet i de operativsystem som ska användas på dessa system. De senaste årtiondena har micro kernel arkitekturen varit föremål för intensiv forskning och det finns idag ett flertal operativsystem på marknaden som använder denna arkitektur. Traditionella monolitiska operativsystem är relativt resurskrävande system som ofta anklagats för att sakna struktur. Micro kernel baserade system är en lösning på detta problem där man bantat ner kernel till så lite som ett tiotal kilobyte och flyttar ut tjänster som normalt ligger i kernel till user space. Solaris och Linux bygger på en utveckling av monolitisk kernel där man byggt operativsystemet i ett antal sinsemellan beroende lager vilket bidrar till ökad struktur i systemet. Flexibilitet uppnås i dessa system genom att man lägger till funktionalitet för att under exekvering länka in ny kod i kernel. Windows NT och Mac OS X är baserade på micro kernel arkitektur. De använder en relativt liten kernel och flyttar övriga tjänster till user space. På grund av prestandaproblem med t.ex. grafik och nätverk har dock vissa tjänster flyttats tillbaka till kernel space, vilket har lett till att kritiker hävdar att de inte är rena micro kernel system.

Populaere Betriebssysteme (Windows XP, UNIX) sind in heutiger Zeit meist monolithisch aufgebaut. Durch immer neue nachgewiesene Sicherheitslücken in Kern und Anwendungen wird eindrucksvoll belegt, dass monolithische Architekturen den heutigen Sicherheitsanforderungen nicht mehr gewachsen sind. Dennoch kann man auf die reichhaltige Basis an Anwendungen heutiger Betriebssysteme nicht verzichten. Als Ausweg werden herkoemmliche Betriebssysteme isoliert in einer vertrauenswuerdigen Umgebung ausgeführt. Eine in letzter Zeit immer populaerere Methode zur Kapselung besteht in der Virtualisierung mit verschiedenen Auspraegungen. Mit L4Linux wurde 1997 erstmals nachgewiesen, dass die Ausfuehrung eines Standard-Betriebssystems auf einem Mikrokern (manchmal auch Para-Virtualisierung genannt) nicht zwangslaeufig zu inakzeptablen Mehrkosten an Laufzeit fuehren muss. Bei Einsatz von gebraeuchlicher Standardhardware muessen allerdings eine Reihe von Problemen geloest werden, unter anderem der uneingeschraenkte Zugriff von Geraeten auf den physischen Adressraum mittels DMA. Im Rahmen der Arbeit wird ein allgemeines Modell von IO-Adressraeumen als Erweiterung der virtuellen Adressraeume der CPU eingefuehrt und gezeigt, wie mittels Teil-Virtualisierung von Geraeten IO-Adressraeume in Software emuliert werden koennen. Weiterhin werden anhand von L4Linux Moeglichkeiten eroertert und implementiert, wie Betriebssystem-Kerne vollstaendig gezaehmt und insbesondere ohne IO-Privilegien ausgefuehrt werden koennen. Im Kapitel "Leistungsbewertung" erfolgt eine umfangreiche Evaluation der Implementierung anhand von L4Linux 2.2.

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

Populaere Betriebssysteme (Windows XP, UNIX) sind in heutiger Zeit meist monolithisch aufgebaut. Durch immer neue nachgewiesene Sicherheitslücken in Kern und Anwendungen wird eindrucksvoll belegt, dass monolithische Architekturen den heutigen Sicherheitsanforderungen nicht mehr gewachsen sind. Dennoch kann man auf die reichhaltige Basis an Anwendungen heutiger Betriebssysteme nicht verzichten. Als Ausweg werden herkoemmliche Betriebssysteme isoliert in einer vertrauenswuerdigen Umgebung ausgeführt. Eine in letzter Zeit immer populaerere Methode zur Kapselung besteht in der Virtualisierung mit verschiedenen Auspraegungen. Mit L4Linux wurde 1997 erstmals nachgewiesen, dass die Ausfuehrung eines Standard-Betriebssystems auf einem Mikrokern (manchmal auch Para-Virtualisierung genannt) nicht zwangslaeufig zu inakzeptablen Mehrkosten an Laufzeit fuehren muss. Bei Einsatz von gebraeuchlicher Standardhardware muessen allerdings eine Reihe von Problemen geloest werden, unter anderem der uneingeschraenkte Zugriff von Geraeten auf den physischen Adressraum mittels DMA. Im Rahmen der Arbeit wird ein allgemeines Modell von IO-Adressraeumen als Erweiterung der virtuellen Adressraeume der CPU eingefuehrt und gezeigt, wie mittels Teil-Virtualisierung von Geraeten IO-Adressraeume in Software emuliert werden koennen. Weiterhin werden anhand von L4Linux Moeglichkeiten eroertert und implementiert, wie Betriebssystem-Kerne vollstaendig gezaehmt und insbesondere ohne IO-Privilegien ausgefuehrt werden koennen. Im Kapitel "Leistungsbewertung" erfolgt eine umfangreiche Evaluation der Implementierung anhand von L4Linux 2.2.

Research into modular approaches for constructing power electronics control systems has provided a number of benefits, as well as new opportunities. Control systems composed of an interconnected collection of standardized parts makes distributed processing a realistic possibility. Unfortunately, current strategies to supporting software on such systems have a number of critical drawbacks. Many existing approaches rely on centralized control strategies, fail to support fault tolerance in the face of failures among processing nodes or communications links, and fail to robustly support live addition or removal of nodes from a running network. In this context, failure of a single element means failure of the entire system. This thesis describes research to extend the Dataflow Architecture Real-time Kernel (DARK) to support distributed, fault-tolerant execution of control algorithms for power electronics control systems. An appropriate scheme for fault-tolerant scheduling of processes on distributed processing nodes is described, added to DARK, and evaluated. Literature indicates that fault-tolerant multiprocessor scheduling for hard real-time tasks with task precedence constraints is an NP-hard problem. The new system is based on an off-line fault-tolerant scheduling strategy that generates a static schedule of tasks for each processing unit to follow. This algorithm handles both the task precedence constraints and the constraints imposed by the underlying network protocol(DRPESNET). Modifications to the underlying daisy-chained, packet-switched, time-triggered ring network protocol to support communications fault tolerance and plug-and-play addition or removal of live nodes from an existing control system are also described. / Master of Science

L'objectif de cette thèse est l'étude d'un environnement d'exécution pour machines parallèles sans mémoire commune. Elle comprend la définition d'un modèle de programme parallèle, basé sur l'échange de message offrant une forme restreinte de mémoire partagée. La communication est indirecte, via des portes; les processus utilisent les barrières pour la synchronisation. Les entités du système. processus, portes et barrières, sont créées dynamiquement, et placées sur un processeur quelconque du réseau de processeurs de façon explicite. Nous proposons une implantation de ce modèle comme la mise en oeuvre systématique d'une architecture client/serveur. Cette implantation a été efféctuée sur une machine Supemode. La base est un Micro Noyau Parallèle, où le composant principal est un mécanisme d'appel de procédure à distance minimal. / This thesis describes an execution environment for parallel machines without shared memory. A parallel programming model based on message passing, with a special shared memory. In this model, process communication occurs indirectly, via ports, and the processes use barriers for synchronization. All the entities of the system, such as processes, ports and barriers, are created dynamically and loaded on any processor of the network of processors. The implementation architecture of our model is a systematic realization of the client/server model. An implementation is proposed in a Supernode parallel machine as a parallel micro kernel. The principal parallel micro kernel component is a minimal remote procedure call mechanism.

L'objectif de cette thèse est l'étude d'un environnement d'exécution pour machines parallèles sans mémoire commune. Elle comprend la définition d'un modèle de programme parallèle, basé sur l'échange de message offrant une forme restreinte de mémoire partagée. La communication est indirecte, via des portes; les processus utilisent les barrières pour la synchronisation. Les entités du système. processus, portes et barrières, sont créées dynamiquement, et placées sur un processeur quelconque du réseau de processeurs de façon explicite. Nous proposons une implantation de ce modèle comme la mise en oeuvre systématique d'une architecture client/serveur. Cette implantation a été efféctuée sur une machine Supemode. La base est un Micro Noyau Parallèle, où le composant principal est un mécanisme d'appel de procédure à distance minimal. / This thesis describes an execution environment for parallel machines without shared memory. A parallel programming model based on message passing, with a special shared memory. In this model, process communication occurs indirectly, via ports, and the processes use barriers for synchronization. All the entities of the system, such as processes, ports and barriers, are created dynamically and loaded on any processor of the network of processors. The implementation architecture of our model is a systematic realization of the client/server model. An implementation is proposed in a Supernode parallel machine as a parallel micro kernel. The principal parallel micro kernel component is a minimal remote procedure call mechanism.

L'objectif de cette thèse est l'étude d'un environnement d'exécution pour machines parallèles sans mémoire commune. Elle comprend la définition d'un modèle de programme parallèle, basé sur l'échange de message offrant une forme restreinte de mémoire partagée. La communication est indirecte, via des portes; les processus utilisent les barrières pour la synchronisation. Les entités du système. processus, portes et barrières, sont créées dynamiquement, et placées sur un processeur quelconque du réseau de processeurs de façon explicite. Nous proposons une implantation de ce modèle comme la mise en oeuvre systématique d'une architecture client/serveur. Cette implantation a été efféctuée sur une machine Supemode. La base est un Micro Noyau Parallèle, où le composant principal est un mécanisme d'appel de procédure à distance minimal. / This thesis describes an execution environment for parallel machines without shared memory. A parallel programming model based on message passing, with a special shared memory. In this model, process communication occurs indirectly, via ports, and the processes use barriers for synchronization. All the entities of the system, such as processes, ports and barriers, are created dynamically and loaded on any processor of the network of processors. The implementation architecture of our model is a systematic realization of the client/server model. An implementation is proposed in a Supernode parallel machine as a parallel micro kernel. The principal parallel micro kernel component is a minimal remote procedure call mechanism.