Shared hardware resources in commodity multicore processors are subject to contention from co-running threads. The resultant interference can lead to highly-variable performance for individual applications. This is particularly problematic for real-time applications, which require predictable timing guarantees. It also leads to a pessimistic estimate of the Worst Case Execution Time (WCET) for every real-time application. More CPU time needs to be reserved, thus less applications can enter the system. As the average execution time is usually far less than the WCET, a significant amount of reserved CPU resource would be wasted. Previous works have attempted partitioning the shared resources, amongst either CPUs or processes, to improve performance isolation. However, they have not proven to be both efficient and effective. In this thesis, we propose several mechanisms and frameworks that manage the shared caches and memory buses on multicore platforms. Firstly, we introduce a multicore real-time scheduling framework with the foreground/background scheduling model. Combining real-time load balancing with background scheduling, CPU utilization is greatly improved. Besides, a memory bus management mechanism is implemented on top of the background scheduling, making sure bus contention is under control while utilizing unused CPU cycles. Also, cache partitioning is thoroughly studied in this thesis, with a cache-aware load balancing algorithm and a dynamic cache partitioning framework proposed. Lastly, we describe a system architecture to integrate the above solutions all together. It tackles one of the toughest problems in OS innovation, legacy support, by converting existing OSes into libraries in a virtualized environment. Thus, within a single multicore platform, we benefit from the fine-grained resource control of a real-time OS and the richness of functionality of a general-purpose OS.

Avec l'avènement du cloud computing, la virtualisation est devenue aujourd'hui incontournable. Elle offre isolation et flexibilité, en revanche elle implique une fragmentation des ressources, et notamment de la mémoire. Les performances des applications qui effectuent beaucoup d'entrées/sorties (E/S) en sont particulièrement impactées. En effet, celles-ci reposent en grande partie sur la présence de mémoire libre, utilisée par le système pour faire du cache et ainsi accélérer les E/S. Ajuster dynamiquement les ressources d'une machine virtuelle devient donc un enjeu majeur. Dans cette thèse nous nous intéressons à ce problème, et nous proposons Puma, un cache réparti permettant de mutualiser la mémoire inutilisée des machines virtuelles pour améliorer les performances des applications qui effectuent beaucoup d'E/S. Contrairement aux solutions existantes, notre approche noyau permet à Puma de fonctionner avec les applications sans adaptation ni système de fichiers spécifique. Nous proposons plusieurs métriques, reposant sur des mécanismes existants du noyau Linux, qui permettent de définir le niveau d'activité « cache » du système. Ces métriques sont utilisées par Puma pour automatiser le niveau de contribution d'un noeud au cache réparti. Nos évaluations de Puma montrent qu'il est capable d'améliorer significativement les performances d'applications qui effectuent beaucoup d'E/S et de s'adapter dynamiquement afin de ne pas dégrader leurs performances. / With the advent of cloud architectures, virtualization has become a key mechanism for ensuring isolation and flexibility. However, a drawback of using virtual machines (VMs) is the fragmentation of physical resources. As operating systems leverage free memory for I/O caching, memory fragmentation is particularly problematic for I/O-intensive applications, which suffer a significant performance drop. In this context, providing the ability to dynamically adjust the resources allocated among the VMs is a primary concern.To address this issue, this thesis proposes a distributed cache mechanism called Puma. Puma pools together the free memory left unused by VMs: it enables a VM to entrust clean page-cache pages to other VMs. Puma extends the Linux kernel page cache, and thus remains transparent, to both applications and the rest of the operating system. Puma adjusts itself dynamically to the caching activity of a VM, which Puma evaluates by means of metrics derived from existing Linux kernel memory management mechanisms. Our experiments show that Puma significantly improves the performance of I/O-intensive applications and that it adapts well to dynamically changing conditions.

The project is aimed at testing the kernels of real-time OS within the HC08 platform. The RM, EDF and polled loop mechanisms are being compared as well as freely available FreeRSTOS and QP systems. The project also incorporates descriptions of techniques used in the development, obtaining and the implementation of test environments. The evaluation is based on the tests made within the HC08 platform and the knowledge gained from the programming for every individual type of real-time OS.

No description available.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Despite the increasing attention to the topic of computer security, the amount of vulnerable software services is still high. The exploitation of a common vulnerability like memory management bugs brought to the development of an attack known as Return Oriented Programming (ROP). Such technique employs malicious memory injections to hijack the control flow of the targeted application and execute an arbitrary series of instructions. This thesis explores the design and implementation of a static binary rewriting tool able to instrument applications compiled for the Linux operating system in order to offer protection against ROP exploitation on x86 and ARM platforms. The instrumentation is achieved by extracting re-compilable assembler code from executable binary files which is then processed and modified. The effectiveness of such solution is tested with a selection of benchmarking utilities in order to evaluate the cost in terms of performance caused by its employment. The results obtained from these experiments show that on average the added overheads are acceptably low and, consequently, the proposed tool is a valid solution to improve the security of vulnerable applications when the original source code is not available. / Trots den ökande uppmärksamheten på ämnet datasäkerhet är mängden sårbara mjukvarutjänster fortfarande stor. Utnyttjandet av en vanlig sårbarhet som minneshanteringsfel har lett till utvecklingen av en attack som kallas Return Oriented Programming (ROP). Denna teknik utnyttjar skadliga minnesinjektioner för att ändra kontrollflödet för den riktade applikationen och utföra en godtycklig serie instruktioner. Detta exjobb undersöker utformningen och genomförandet av ett verktyg för statisk binär omskrivning som kan användas för att instrumentera applikationer för Linux-operativsystemet för att erbjuda skydd mot ROP-exploatering på x86- och ARM-plattformar. Instrumentering uppnås genom att extrahera återkompilerbar assemblerkod från exekverbara binära filer som sedan behandlas och modifieras. Effektiviteten av sådan lösning testas med ett urval av benchmarkingverktyg för att utvärdera kostnaden när det gäller prestanda som orsakas av dess användning. Resultaten från dessa experiment visar att de extra kostnaderna i genomsnitt är acceptabelt låga och, följaktligen, är det föreslagna verktyget en giltig lösning för att förbättra säkerheten för sårbara applikationer när den ursprungliga källkoden inte är tillgänglig.

Understanding the background activity of a computer and its operating system when running an arbitrary application can lead to important performance discoveries. This is especially interesting in cases where the same task of an application is run over and over again and there is an expected run time, such as in testing. If a major deviation in the run time occurs, it can be crucial to know the reason to prevent it from happening again. Additionally, finding the relevant measurements to explain the performance in a compact way such as a score can further help both the readability and understanding of the performance. For this project, a tool was developed that, using existing tools, measures various parts of a computer and its operating system and presents their activity during the run time of a selected application over multiple iterations, as well as calculates the relevance of the different measurements with the purpose of finding one that can consistently rate the overall performance. Using the results, no single measurement was found that could rate the overall performance on a consistent level, only for specific scenarios. Possible causes for performance deviations could be found, however. The results show that although there is some activity in the background, most background operating system noise does not have a major effect on performance and that major deviations in the run time are rare. However, inflicting manual noise in either the form of CPU usage or memory usage can cause major performance penalties, sometimes reaching up to the double average run time.

Cyber-physical systems are computers equipped with sensors and actuators that enable them to interact with their surrounding environments. Ground vehicles, drones, and manufacturing robots are examples of such systems that require timing guarantees in addition to functional correctness to achieve their mission objectives. These systems often use multiple microcontroller boards for workload distribution and physical redundancy. The emergence of PC-class embedded systems featuring high processing capabilities and abundant resources presents an opportunity to consolidate separate microcontroller boards as software-defined functions into fewer computer systems. For instance, current automotive systems utilize upwards of 100 electronic control units (ECUs) for chassis, body, power-train, infotainment, and vehicle control services. Consolidation saves manufacturing costs, reduces wiring, simplifies packaging in space-limited situations, and streamlines software update delivery to end-users. However, consolidating functions on PC-class hardware does not address the real-time I/O challenges. A fundamental problem in such real-time solutions is the handling of device input and output in a timely manner. For example, a control system might require input data from a sensor to be sampled and processed regularly so that output signals to actuators occur within specific delay bounds. Input/output (I/O) devices connect to the host computer using different types of bus interfaces not necessarily supported by PC-class hardware natively. Examples of such interfaces include Controller Area Network (CAN) and FlexRay, which are prominent in the automotive world, but are not found in PC-class embedded systems. Universal Serial Bus (USB) is now ubiquitous in the PC-class domain, in part due to its support for many classes of devices with simplified hardware needed to connect to the host, and can be utilized to bridge this gap. USB provides the throughput and delay capabilities for next-generation high bandwidth sensors to be integrated with actuators in control area networks. However, typical USB host controller drivers suffer from potential timing delays that affect the delivery of data between tasks and devices. This Ph.D. thesis examines the use of Universal Serial Bus (USB) as the physical fabric for host-to-device and host-to-host communication, without special switching hardware or protocol translation logic, and through a unified programming interface. Combined with the real-time scheduling framework of the Quest RTOS, this work investigates how to form networks of I/O devices and computing nodes over USB with end-to-end timing guarantees. The main contribution of this thesis is a USB-centric design solution for real-time cyber-physical systems with distributed computing nodes.

Personal computer desktops, and other standardized computer architectures are optimized to provide the best performance for frequently occurring conditions. Real-time systems designed using worst-case analysis for such architectures under-utilize the hardware. This shortcoming provides the motivation for scheduling algorithms that can improve overall utilization by accounting for inherent uncertainty in task execution duration. A real-time task dispatcher must perform its function with constant scheduling overhead. Given the NP-hard nature of the problem of scheduling non-preemptible tasks, dispatch decisions for such systems cannot be made in real-time. This argues for a hybrid architecture that includes an offline policy generator, and an online dispatcher. This dissertation proposes, and demonstrates a hybrid operating system architecture that enables cost-optimal task dispatch on Commercial-Off-The-Shelf (COTS) systems. This is achieved by explicitly accounting for the stochastic nature of each task?s execution time, and dynamically learning the system behavior. Decision Theoretic Scheduling (DTS) provides the framework for scheduling under uncertainty. The real-time scheduling problem is cast as a Markov Decision Process (MDP). An offline policy generator discovers an epsilon-optimal policy using value iteration with model learning. For the selected representation of state, action, model, and rewards, the policydiscovered using value iteration is proved to have a probability of failure that is less than any arbitrarily small user-specified value. The PromisQoS operating system architecture demonstrates a practical implementation of the proposed approach. PromisQoS is a Linux based platform that supports concurrent execution of time-based (preemptible and non-preemptible) real-time tasks, and best-effort processes on an interactive workstation. Several examples demonstrate that model learning, and scheduling under uncertainty enables PromisQoS to achieve better CPU utilization than other scheduling methods. Real-time task sets that solve practical problems, such as a Laplace solver, matrix multiplication, and transpose, demonstrate the robustness and correctness of PromisQoS design and implementation. This pioneering application demonstrates the feasibility of MDP based scheduling for real-time tasks in practical systems. It also opens avenues for further research into the use of such DTS techniques in real-time system design.