This article provides an overview of the Quest real-time operating system (RTOS) and the Quest-V partitioning hypervisor. We summarize the system features and requirements to use the Quest software development kit (SDK). The SDK is capable of prototyping systems combining one or more instances of Quest with legacy services from a Yocto Linux guest. Secure shared memory channels provide the means to build secure and predictable systems of systems.

Other

Device interrupts have long been a problem in real-time systems. Handling an interrupt in the context of a critical task potentially leads to a missed deadline. While modern systems have proposed techniques to schedule interrupts, the challenge is to determine the correct priority based on the task that triggers their occurrence. One approach is to assign an interrupt with the highest priority among all tasks waiting on a corresponding device. However, this does not fully eliminate priority inversion, as the interrupt may be handled at a much higher priority than the task with which it is associated. To solve this problem, we present a solution for devices con-nected to a Universal Serial Bus (USB). USB has properties that make it potentially suitable for tackling high bandwidth sensor data processing and low-latency input/output (I/O) control. We describe the implementation of an xHCI (USB 3.x) driver in the Quest RTOS, which guarantees throughput and delay require-ments for USB devices and their I/O requests using time-budgeted interrupt handling servers. Our paper is the first to introduce differentiated USB interrupt servicing. Experiments show how our approach outperforms a Linux xHCI driver running on a PREEMPT_RT-patched system with SCHED_DEADLINE tasks. Differentiated USB interrupt handling is shown to improve the performance of Quest's default xHCI driver, which is purposely designed to provide real-time I/O guarantees.

Multicore PC-class embedded systems present an opportunity to consolidate separate microcontrollers as software-defined functions. For instance, an automotive system with more than 100 electronic control units (ECUs) could be replaced with one or, at most, several multicore PCs running software tasks for chassis, body, powertrain, infotainment, and advanced driver assistance system (ADAS) services. However, a key challenge is how to handle real-time device input and output (I/O) and host-level networking as part of sensor data processing and control. A traditional microcontroller would commonly feature one or more Controller Area Network (CAN) buses for real-time I/O. CAN buses are usually absent in PCs, which instead feature higher bandwidth Universal Serial Bus (USB) interfaces. This article shows how to achieve real-time device I/O and host-to-host communication over USB, using suitably written device drivers and a time-aware POSIX-like “tuned pipe” abstraction. This allows developers to establish task pipelines spanning one or more hosts, with end-to-end latency and throughput guarantees for sensor data processing, control, and actuation.

This paper presents ModelMap, a model-based multi-domain application development framework for DriveOS, our in-house centralized vehicle management software system. DriveOS runs on multicore x86 machines and uses hardware virtualization to host isolated RTOS and Linux guest OS sandboxes. In this work, we design Simulink interfaces for model-based vehicle control function development across multiple sandboxed domains in DriveOS. ModelMap provides abstractions to: (1) automatically generate periodic tasks bound to threads in different OS domains, (2) establish cross-domain synchronous and asynchronous communication interfaces, and (3) handle USB-based CAN I/O in Simulink. We introduce the concept of a nested binary, for the deployment of ELF binary executable code in different sandboxed domains. We demonstrate ModelMap using a combination of synthetic benchmarks, and experiments with Simulink models of a CAN Gateway and HVAC service running on an electric car. ModelMap eases the development of applications, which are shown to achieve industry-target performance using a multicore hardware platform in DriveOS.

Autonomous multicopters often feature federated architectures, which incur relatively high communication costs between separate hardware components. These costs limit the ability to react quickly to new mission objectives. Additionally, federated architectures are not easily upgraded without introducing new hardware that impacts size, weight, power and cost (SWaP-C) constraints. In turn, such constraints restrict the use of redundant hardware to handle faults. In response to these challenges, we propose FlyOS, an Integrated Modular Avionics (IMA) approach to consolidate mixed-criticality flight functions in software on heterogeneous multicore aerial platforms. FlyOS is based on a separation kernel that statically partitions resources among virtualized sandboxed OSes. We present a dual-sandbox prototype configuration, where timing-and safety-critical flight control tasks execute in a real-time OS alongside mission-critical vision-based navigation tasks in a Linux sandbox. Low latency shared memory communication allows flight commands and data to be relayed in real-time between sandboxes. A hypervisor-based fault-tolerance mechanism is also deployed to ensure failover flight control in case of critical function or timing failures. We validate FlyOS’s performance and showcase its benefits when compared against traditional architectures in terms of predictable, extensible and efficient flight control.

Complex embedded systems are now supporting the co-existence of multiple OSes to manage services once assigned to separate embedded microcontrollers. Automotive systems, for example, now use multiple OSes to consolidate electronic control unit (ECU) functions on a centralized embedded computing platform. Such platforms have the complexity of an industrial embedded PC, with multiple cores and hardware virtualization capabilities. This enables a partitioning hypervisor to spatially and temporally share the physical machine with separate guest OSes, which manage services of different criticality levels. However, PC-class hardware incurs a large latency to bootstrap an OS and associated application-level services. A firmware BIOS performs a power-on-self-test, and then loads OS images into memory from a bootable storage device. This latency is unacceptable in time-critical embedded systems, where important services must be operational within milliseconds of starting the system. In this paper, we present Jumpstart, a PC-class power management approach that minimizes the wakeup delay of a partitioning hypervisor for use in embedded systems. We show how Jumpstart resumes critical OS services and tasks from a low power suspended state in approximately 600 milliseconds, and reduces full system startup delay by a factor of 23. Additionally, Jumpstart consumes minimal power compared to approaches requiring a system boot from a previously powered-off state. By comparison, an alternative firmware-optimized bootloader, called Slim, reduces boot latency by a factor of 1.8.

Modern solid-state disks achieve high data transfer rates due to their massive internal parallelism. However, out-of-place updates for flash memory incur garbage collection costs when valid data needs to be copied during space reclamation. The root cause of this extra cost is that solid-state disks are not always able to accurately determine data lifetime and group together data that expires before the space needs to be reclaimed. Real-time systems found in autonomous vehicles, industrial control systems, and assembly-line robots store data from hundreds of sensors and often have predictable data lifetimes. These systems require guaranteed high storage bandwidth for read and write operations by mission-critical real-time tasks. In this article, we depart from the traditional block device interface to guarantee the high throughput needed to process large volumes of data. Using data lifetime information from the application layer, our proposed real-time design, called Telomere , is able to intelligently lay out data in NAND flash memory and eliminate valid page copies during garbage collection. Telomere’s real-time admission control is able to guarantee tasks their required read and write operations within their periods. Under randomly generated tasksets containing 500 tasks, Telomere achieves 30% higher throughput with a 5% storage cost compared to pre-existing techniques.

Modern automotive systems feature dozens of electronic control units (ECUs) for chassis, body and powertrain functions. These systems are costly and inflexible to upgrade, requiring ever increasing numbers of ECUs to support new features such as advanced driver assistance (ADAS), autonomous technologies, and infotainment. To counter these challenges, we propose DriveOS, a safe, secure, extensible, and timing-predictable system for modern vehicle management in a centralized platform. DriveOS is based on a separation kernel, where timing and safety-critical ECU functions are implemented in a real-time OS (RTOS) alongside non-critical software in Linux or Android. The system enforces the separation, or partitioning, of both software and hardware among different OSes. DriveOS runs on a relatively low-cost embedded PC-class platform, supporting multiple cores and hardware virtualization capabilities. Instrument cluster, in-vehicle infotainment and advanced driver assistance system services are implemented in a Yocto Linux guest, which communicates with critical real-time services via secure shared memory. The RTOS manages a real-time controller area network (CAN) interface that is inaccessible to Linux services except via well-defined and legitimate communication channels. In this work, we integrate three Qt-based services written for Yocto Linux, running in parallel with a real-time longitudinal controller task and multiple CAN bus concentrators, for vehicular sensor data processing and actuation. We demonstrate the benefits and performance of DriveOS with a hardware-in-the-loop CARLA simulation using a real car dataset.

Multi-rotor drones require real-time sensor data processing and control to maintain flight stability, which is made more challenging by external disturbances such as wind. In this paper we introduce smARTflight: an environmentally-aware adaptive real-time flight management system. smARTflight adapts the execution frequencies of flight control tasks according to timing and safety-critical constraints, in response to transient fluctuations of a drone’s attitude. In contrast to current state-of-the-art methods, smARTflight’s criticality-aware scheduler reduces the latency to return to a steady-state target attitude. The system also improves the overall control accuracy and lowers the frequency of adjustments to motor speeds to conserve power. A comparative case-study with a well-known autopilot shows that smARTflight reduces unnecessary control loop executions under stable conditions, while reducing response time latency by as much as 60% in a given axis of rotation when subjected to a 15° step attitude disturbance.

Over-estimation of worst-case execution times (WCETs) of real-time tasks leads to poor resource utilization. In a mixed-criticality system (MCS), the over-provisioning of CPU time to accommodate the WCETs of highly critical tasks may lead to degraded service for less critical tasks. In this paper we present PAStime, a novel approach to monitor and adapt the runtime progress of highly time-critical applications, to allow for improved service to lower criticality tasks. In PAStime, CPU time is allocated to time-critical tasks according to the delays they experience as they progress through their control flow graphs. This ensures that as much time as possible is made available to improve the Quality-of-Service of less critical tasks, while high-criticality tasks are compensated after their delays. This paper describes the integration of PAStime with Adaptive Mixed-criticality (AMC) scheduling. The LO-mode budget of a high-criticality task is adjusted according to the delay observed at execution checkpoints. This is the first implementation of AMC in the scheduling framework of LITMUS^RT, which is extended with our PAStime runtime policy and tested with real-time Linux applications such as object classification and detection. We observe in our experimental evaluation that AMC-PAStime significantly improves the utilization of the low-criticality tasks while guaranteeing service to high-criticality tasks.

This paper presents Boomerang, an I/O system that integrates a legacy non-real-time OS with one that is customized for timing-sensitive tasks. A relatively small RTOS benefits from the pre-existing libraries, drivers and services of the legacy system. Additionally, timing-critical tasks are isolated from less critical tasks by securely partitioning machine resources among the separate OSes. Boomerang guarantees end-to-end processing delays on input data that requires outputs to be generated within specific time bounds.We show how to construct composable task pipelines in Boomerang that combine functionality spanning a custom RTOS and a legacy Linux system. By dedicating time-critical I/O to the RTOS, we ensure that complementary services provided by Linux are sufficiently predictable to meet end-to-end service guarantees. While Boomerang benefits from spatial isolation, it also outperforms a standalone Linux system using deadline-based CPU reservations for pipeline tasks. We also show how Boomerang outperforms a virtualized system called ACRN, designed for automotive systems.

Autopilot systems are typically composed of an “inner loop” providing stability and control, whereas an “outer loop” is responsible for mission-level objectives, such as way-point navigation. Autopilot systems for unmanned aerial vehicles are predominately implemented using Proportional-Integral-Derivative (PID) control systems, which have demonstrated exceptional performance in stable environments. However, more sophisticated control is required to operate in unpredictable and harsh environments. Intelligent flight control systems is an active area of research addressing limitations of PID control most recently through the use of reinforcement learning (RL), which has had success in other applications, such as robotics. Yet previous work has focused primarily on using RL at the mission-level controller. In this work, we investigate the performance and accuracy of the inner control loop providing attitude control when using intelligent flight control systems trained with state-of-the-art RL algorithms—Deep Deterministic Policy Gradient, Trust Region Policy Optimization, and Proximal Policy Optimization. To investigate these unknowns, we first developed an open source high-fidelity simulation environment to train a flight controller attitude control of a quadrotor through RL. We then used our environment to compare their performance to that of a PID controller to identify if using RL is appropriate in high-precision, time-critical flight control.

A fundamental problem in real-time computing is handling 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 at a regular rate 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. One of the most popular interfaces in use today is the universal serial bus (USB). USB is now ubiquitous, in part due to its support for many classes of devices with simplified hardware needed to connect to the host. However, typical USB host controller drivers suffer from potential timing delays that affect the delivery of data between tasks and devices. Consequently, this paper introduces tuned pipes, a host controller driver and system framework that guarantees end-to-end latency and throughput requirements for I/O transfers. We expand on our earlier work involving USB 2.0 to support higher bandwidth USB 3.x communication. As a case study, we show how a USB-Controller Area Network (CAN) guarantees temporal isolation and end-to-end guarantees on communication between a set of peripheral devices and host tasks. A comparable USB-CAN bus setup using Linux is not able to achieve the same level of temporal guarantees, even when using SCHED_DEADLINE.

This paper addresses the problem of guaranteeing performance and predictability of NAND flash memory in a real-time storage system. Our approach implements a new flash translation layer scheme that exploits internal parallelism within solid state storage devices. We describe the Partitioned Real-Time Flash Translation Layer (PaRT-FTL), which splits a set of flash chips into separate read and write sets. This ensures reads and writes to separate chips proceed in parallel. However, PaRT-FTL is also able to rebuild the data for a read request from a flash chip that is busy servicing a write request or performing garbage collection. Consequently, reads are never blocked by writes or storage space reclamation. PaRT-FTL is compared to previous real-time approaches including scheduling, over-provisioning and partial garbage collection. We show that by isolating read and write requests using encoding techniques, PaRT-FTL provides better latency guarantees for real-time applications.

Timing guarantees are crucial to embedded and cyber-physical applications that must bound the end-to-end delay between sensing, processing and actuation. For example, in a flight controller for a multirotor drone, the data from a gyro or inertial sensor must be gathered and processed to determine the attitude of the aircraft. Sensor data fusion is followed by control outputs that alter rotor speeds to adjust the drone's flight. If the processing pipeline between sensor input and actuation is not bounded, the drone will lose control and possibly fail to maintain flight. This paper describes a composable pipe model for sensor data processing and actuation tasks. The pipe model is used to analyze two end-to-end semantics: 1) freshness and 2) reaction time. We provide a mathematical framework to derive feasible task periods and budgets that satisfy both schedulability and end-to-end timing requirements. We demonstrate the applicability of our design approach by using it to port the Cleanflight flight controller firmware to our in-house real-time operating system called Quest. Experiments show that Cleanflight ported to Quest is able to achieve end-to-end latencies within the predicted time bounds derived by analysis.

Single Board Computers (SBCs) are now emerging with multiple cores, ADCs, GPIOs, PWM channels, integrated graphics, and several serial bus interfaces. The low power consumption, small form factor and I/O interface capabilities of SBCs with sensors and actuators makes them ideal in embedded and real-time applications. However, most SBCs run non-realtime operating systems based on Linux and Windows, and do not provide a user-friendly API for application development. This paper presents QduinoMC, a multicore extension to the popular Arduino programming environment, which runs on the Quest real-time operating system. QduinoMC is an extension of our earlier single-core, real-time, multithreaded Qduino API. We show the utility of QduinoMC by applying it to a specific application: a web-connected 3D printer. This differs from existing 3D printers, which run relatively simple firmware and lack operating system support to spool multiple jobs, or interoperate with other devices (e.g., in a print farm). We show how QduinoMC empowers devices with the capabilities to run new services without impacting their timing guarantees. While it is possible to modify existing operating systems to provide suitable timing guarantees, the effort to do so is cumbersome and does not provide the ease of programming afforded by QduinoMC.

This paper addresses the problem of scheduling tasks with differentcriticality levels in the presence of I/O requests. In mixed-criticalityscheduling, higher criticality tasks are given precedence over those of lowercriticality when it is impossible to guarantee the schedulability of alltasks. While mixed-criticality scheduling has gained attention in recentyears, most approaches typically assume a periodic task model. Thisassumption does not always hold in practice, especially for real-time andembedded systems that perform I/O. In prior work, we developed ascheduling technique in the Quest real-time operating system, which integratesthe time-budgeted management of I/O operations with Sporadic Server schedulingof tasks. This paper extends our previous scheduling approach with support formixed-criticality tasks and I/O requests on the same processing core. Resultsshow that in a real implementation the mixed-criticality scheduling methodintroduced in this paper outperforms a scheduling approach consisting of onlySporadic Servers.

This paper describes a multicore scheduling and load-balancing framework called MARACAS, to address shared cache and memory bus contention. It builds upon prior work centered around the concept of virtual CPU (VCPU) scheduling. Threads are associated with VCPUs that have periodically replenished time budgets. VCPUs are guaranteed to receive their periodic budgets even if they are migrated between cores. A load balancing algorithm ensures VCPUs are mapped to cores to fairly distribute surplus CPU cycles, after ensuring VCPU timing guarantees. MARACAS uses surplus cycles to throttle the execution of threads running on specific cores when memory contention exceeds a certain threshold. This enables threads on other cores to make better progress without interference from co-runners. Our scheduling framework features a novel memory-aware scheduling approach that uses performance counters to derive an average memory request latency. We show that latency-based memory throttling is more effective than rate-based memory access control in reducing bus contention. MARACAS also supports cache-aware scheduling and migration using page recoloring to improve performance isolation amongst VCPUs. Experiments show how MARACAS reduces multicore resource contention, leading to improved task progress.

Multi- and many-core processors are becoming increasingly popular in embedded systems. Many of these processors now feature hardware virtualization capabilities, as found on the ARM Cortex A15 and x86 architectures with Intel VT-x or AMD-V support. Hardware virtualization provides a way to partition physical resources, including processor cores, memory, and I/O devices, among guest virtual machines (VMs). Each VM is then able to host tasks of a specific criticality level, as part of a mixed-criticality system with different timing and safety requirements. However, traditional virtual machine systems are inappropriate for mixed-criticality computing. They use hypervisors to schedule separate VMs on physical processor cores. The costs of trapping into hypervisors to multiplex and manage machine physical resources on behalf of separate guests are too expensive for many time-critical tasks. Additionally, traditional hypervisors have memory footprints that are often too large for many embedded computing systems. In this article, we discuss the design of the Quest-V separation kernel, which partitions services of different criticality levels across separate VMs, or sandboxes . Each sandbox encapsulates a subset of machine physical resources that it manages without requiring intervention from a hypervisor. In Quest-V, a hypervisor is only needed to bootstrap the system, recover from certain faults, and establish communication channels between sandboxes. This not only reduces the memory footprint of the most privileged protection domain but also removes it from the control path during normal system operation, thereby heightening security.

Arduino [1] is an open source platform that offers a clear and simple environment for physical computing. It is now widely used in modern robotics and Internet-of-Things (IoT) applications, due in part to its low-cost, ease of programming, and rapid prototyping capabilities. Sensors and actuators can easily be connected to the analog and digital I/O pins of an Arduino device, which features an on-board microcontroller programmed using the Arduino API. We present Qduino, a system developed for Arduino compatible boards. It is built upon our Quest realtime operating system kernel [4] and new Arduino-compatible boards.

Arduino is an open source platform that offers a clear and simple environment for physical computing. It is now widely used in modern robotics and Internet of Things (IoT) applications, due in part to its low-cost, ease of programming, and rapid prototyping capabilities. Sensors and actuators can easily be connected to the analog and digital I/O pins of an Arduino device, which features an on-board microcontroller programmed using the Arduino API. The increasing complexity of physical computing applications has now led to a series of Arduino-compatible devices with faster processors, increased flash storage, larger memories and more complicated I/O architectures. The Intel Galileo, for example, is designed to support the Arduino API on top of a Linux system, code-named Clanton. However, the standard API is restricted to the capabilities found on less powerful devices, lacking support for multithreaded programs, or specification of real-time requirements. In this paper, we present Qduino, a system developed for Arduino compatible boards. Qduino provides an extended Arduino API which, while backward-compatible with the original API, supports real-time multithreaded sketches and event handling. Experiments show the performance gains of Qduino compared to Clanton Linux.

Shared caches in 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, requiring predictable timing guarantees. Previous work has applied page coloring techniques to partition a shared cache, so that conflict misses are minimized amongst co-running workloads. However, prior page coloring techniques have not addressed the problem of partitioning a cache on over-committed processors where there are more executable threads than cores. Similarly, page coloring techniques have not proven efficient at adapting the cache partition sizes for threads with varying memory demands.

On behalf of the IEEE Technical Committee on Real-Time Systems, it is our pleasure to welcome you to the 20th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2014), held in Berlin, Germany, as part of the Cyber-Physical Systems Week!

Quest-V is a separation kernel, which partitions a system into a collection of sandboxes. Each sandbox encapsulates one or more processing cores, a region of machine physical memory, and a subset of I/O devices. Quest-V behaves like a distributed system on a chip, using explicit communication channels to exchange data and migrate addresses spaces between sandboxes, which operate like traditional hosts. This design has benefits in safety-critical systems, which require continued availability in the presence of failures. Additionally, online faults can be recovered without rebooting an entire system. However, the programming model for such a system is more complicated. Each sandbox has its own local scheduler, and threads must communicate using message passing with those in remote sandboxes. Similarly, address spaces may need to be migrated between sandboxes, to ensure newly forked processes do not violate the feasibility of existing local task schedules. Migration may also be needed to move a thread closer to its required resources, such as I/O devices that are not directly available in the local sandbox. This paper describes how Quest-V performs real-time communication and migration without violating service guarantees for existing threads.

Multi- and many-core processors are becoming increasingly popular in embedded systems. Many of these processors now feature hardware virtualization capabilities, such as the ARM Cortex A15, and x86 processors with Intel VT-x or AMD-V support. Hardware virtualization offers opportunities to partition physical resources, including processor cores, memory and I/O devices amongst guest virtual machines. Mixed criticality systems and services can then co-exist on the same platform in separate virtual machines. However, traditional virtual machine systems are too expensive because of the costs of trapping into hypervisors to multiplex and manage machine physical resources on behalf of separate guests. For example, hypervisors are needed to schedule separate VMs on physical processor cores. In this paper, we discuss the design of the Quest-V separation kernel, which partitions services of different criticalities in separate virtual machines, or sandboxes. Each sandbox encapsulates a subset of machine physical resources that it manages without requiring intervention of a hypervisor. Moreover, a hypervisor is not needed for normal operation, except to bootstrap the system and establish communication channels between sandboxes.

This paper describes a real-time USB 2 subsystem for the Quest operating system. Quest is designed for real-time embedded systems. Such systems need to interact with their environment using sensors and actuators. On many embedded platforms today there is support for basic serial, USB 2.0 and 100 Mbps Ethernet. Of these, USB 2.0 supports the highest throughput, while also supporting real-time communication. We show how the Quest USB 2.0 sub-system improves upon some of the deficiencies in USB software stacks in systems such as Linux through experimental evaluation. We demonstrate that the Quest USB sub-system is capable of predictable bandwidth allocation and increased overall performance. By dynamically reordering transaction requests, Quest's USB sub-system is able to avoid unnecessary admission control rejections. Additionally, we are able to provide real-time guarantees for asynchronous USB transactions such as bulk transfers, which are typically treated in a best-effort manner. Real-time guarantees for bulk transactions are necessary for any system interacting with devices that implement bulk endpoints such as in a real-time file system. The paper also introduces an algorithm for USB scheduling that accepts more requests and provides bulk transfer guarantees, for cases where Linux fails.

This article presents the design of user-level scheduling hierarchies in the C omposite component-based system. The motivation for this is centered around the design of a system that is both dependable and predictable, and which is configurable to the needs of specific applications. Untrusted application developers can safely develop services and policies, that are isolated in protection domains outside the kernel. To ensure predictability, C omposite enforces timing control over user-space services. Moreover, it must provide a means by which asynchronous events, such as interrupts, are handled in a timely manner without jeopardizing the system. Towards this end, we describe the features of C omposite that allow user-defined scheduling policies to be composed for the purposes of combined interrupt and task management. A significant challenge arises from the need to synchronize access to shared data structures (e.g., scheduling queues), without allowing untrusted code to disable interrupts. Additionally, efficient upcall mechanisms are needed to deliver asynchronous event notifications in accordance with policy-specific priorities, without undue recourse to schedulers. We show how these issues are addressed in C omposite , by comparing several hierarchies of scheduling polices, to manage both tasks and the interrupts on which they depend. Studies show how it is possible to implement guaranteed differentiated services as part of the handling of I/O requests from a network device while diminishing livelock. Microbenchmarks indicate that the costs of implementing and invoking user-level schedulers in C omposite are on par with, or less than, those in other systems, with thread switches more than twice as fast as in Linux.

As software systems are becoming increasingly complex, the likelihood of faults and unexpected behaviors will naturally increase. Today, mobile devices to large-scale servers feature many millions of lines of code. Compile-time checks and offline verification methods are unlikely to capture all system states and control flow interactions of a running system. For this reason, many researchers have developed methods to contain faults at runtime by using software and hardware-based techniques to define protection domains. However, these approaches tend to impose isolation boundaries on software components that are static, and thus remain intact while the system is running. An unfortunate consequence of statically structured protection domains is that they may impose undue overhead on the communication between separate components. This paper proposes a new runtime technique that trades communication cost for fault isolation. We describe Mutable Protection Domains (MPDs) in the context of our Composite operating system. MPD dynamically adapts hardware isolation between interacting software components, depending on observed communication “hot-paths,” with the purpose of maximizing fault isolation where possible. In this sense, MPD naturally tends toward a system of maximal component isolation, while collapsing protection domains where costs are prohibitive. By increasing isolation for low-cost interacting components, MPD limits the scope of impact of future unexpected faults. We demonstrate the utility of MPD using a webserver, and identify different hot-paths for different workloads that dictate adaptations to system structure. Experiments show up to 40 percent improvement in throughput compared to a statically organized system, while maintaining high-fault isolation.

This paper describes the scheduling framework for a new operating system called "Quest". The three main goals of Quest are to ensure safety, predictability and efficiency of software execution. For this paper, we focus on one aspect of predictability, involving the integrated management of tasks and I/O events such as interrupts. Quest's scheduling infrastructure is based around the concept of a virtual CPU (VCPU). Using both Main and I/O VCPUs, we are able to separate the CPU bandwidth consumed by tasks from that used to complete I/O processing. We introduce a priority-inheritance bandwidth-preserving server policy for I/O management, called PIBS. We show how PIBS operates with lower cost and higher throughput than a comparable Sporadic Server for managing I/O transfers that require small bursts of CPU time. Using a hybrid system of Sporadic Servers for Main VCPUs, and PIBS for I/O VCPUs, we show how to maintain temporal isolation between multiple tasks and I/O transfers from different devices. We believe Quest's VCPU scheduling infrastructure is scalable enough to operate on systems supporting large numbers of threads. For a system of 24 Main VCPUs, we observe a CPU scheduling overhead of approximately 0.3% when VCPU budget is managed in 1ms units.

This paper presents HiRes, a system structured around predictable, hierarchical resource management (HRM). Applications and different subsystems use customized resource managers that control the allocation and usage of memory, CPU, and I/O. This increased resource management flexibility enables subsystems with different timing constraints to specialize resource management around meeting these requirements. In HiRes, subsystems delegate the management of resources to other subsystems, thus creating the resource management hierarchy. In delegating the control of resources, the subsystem focuses on providing isolation between competing subsystems. To make HRM both predictable and efficient, HiRes ensures that regardless of a subsystem's depth in the hierarchy, the overheads of resource usage and control remain constant. In doing so, HiRes encourages HRM as a fundamental system design technique. Results show that HiRes has competitive performance with existing systems, and that HRM naturally provides both strong isolation guarantees, and flexible and efficient subsystem control over resources.

In order to eliminate the costs of proprietary systems and special purpose hardware, many real-time and embedded computing platforms are being built on commodity operating systems and generic hardware. Unfortunately, many such systems are ill-suited to the low-latency and predictable timing requirements of real-time applications. This article, therefore, focuses on application-specific service technologies for low-cost commodity operating systems and hardware, so that real-time service guarantees can be met. We describe contrasting methods to deploy first-class services on commodity systems that are dispatched with low latency and execute asynchronously according to bounds on CPU, memory, and I/O device usage. Specifically, we present a “user-level sandboxing” (ULS) mechanism that relies on hardware protection to isolate application-specific services from the core kernel. This approach is compared with a hybrid language and runtime protection scheme, called SafeX , that allows untrusted services to be dynamically linked and loaded into a base kernel. SafeX and ULS have been implemented on commodity Linux systems. Experimental results have shown—that both approaches are capable of reducing service violations (and, hence, better qualities of service) for real-time tasks, compared to traditional user-level methods of service deployment in process-private address spaces. ULS imposes minimal additional overheads on service dispatch latency compared to SafeX, with the advantage that it does not require application-specific services to execute in the trusted kernel domain. As evidence of the potential capabilities of ULS, we show how a user-level networking stack can be implemented to avoid data copying via the kernel and allow packet processing without explicit process scheduling. This improves throughput and reduces jitter.

Modern chip-level multiprocessors (CMPs) contain multiple processor cores sharing a common last-level cache, memory interconnects, and other hardware resources. Workloads running on separate cores compete for these resources, often resulting in highly-variable performance. To improve fairness and performance, it is helpful to co-schedule workloads having minimal cache and other forms of resource contention. In this work, we develop several cache modeling techniques to help make informed resource management decisions.

This paper presents the design of user-level scheduling hierarchies in the composite component-based system. The motivation for this is centered around the design of a system that is both dependable and predictable, and which is configurable to the needs of specific applications. Untrusted application developers can safely develop services and policies, that are isolated in protection domains outside the kernel. To ensure predictability, composite needs to enforce timing control over user-space services. Moreover, it must provide a means by which asynchronous events, such as interrupts, are handled in a timely manner without jeopardizing the system. Towards this end, we describe the features of composite that allow user-defined scheduling policies to be composed for the purposes of combined interrupt and task management. A significant challenge arises from the need to synchronize access to shared data structures (e.g., scheduling queues), without allowing untrusted code to disable interrupts or use atomic instructions that lock the memory bus. Additionally, efficient upcall mechanisms are needed to deliver asynchronous event notifications in accordance with policy-specific priorities, without undue recourse to schedulers. We show how these issues are addressed in Composite, by comparing several hierarchies of scheduling polices, to manage both tasks and the interrupts on which they depend. Studies show how it is possible to implement guaranteed differentiated services as part of the handling of I/O requests from a network device while avoiding livelock. Microbenchmarks indicate that the costs of implementing and invoking user-level schedulers in composite are on par with, or less than, those in other systems, with thread switches more than twice as fast as in Linux.

This paper focuses on a technique to empower commercial-off-the-shelf (COTS) systems with an execution environment, and corresponding services, to support real-time and embedded applications. By leveraging COTS systems, we are able to reduce the potentially expensive maintenance and development costs of proprietary solutions. We describe a system called "Hijack" that enables user-level services to take control of features such as CPU scheduling, interrupt handling and synchronization. In contrast to other approaches that support real-time tasks within the kernel of commodity systems such as Linux, Hijack provides the basis for predictable thread execution at user-level. No changes to the kernel source code are required to support this approach. Instead, Hijack works by using a combination of kernel module support and an interposed execution environment between traditional process address spaces and the kernel. This technique enables system calls and hardware interrupts to be intercepted with bounded latencies via the kernel module, that passes control to a user-level real-time executive. From within the executive, system-wide services and policies can be deployed to over-ride certain features of the underlying kernel, while still leveraging base kernel services where appropriate. Using this technique, we show how a vanilla Linux system can be hijacked to support predictable service execution using a series of user-defined policies. In particular, we show how to deliver and process asynchronous events with bounded latency, using interposition agents within a Hijack execution environment. Results show that for realtime streaming applications, Hijack is able to receive and process packets with significantly lower loss rates and jitter compared to using alternative application-level processes for the same task

The increasing complexity of software poses significant challenges for real-time and embedded systems beyond those based purely on timeliness. With embedded systems and applications running on everything from mobile phones, PDAs, to automobiles, aircraft and beyond, an emerging challenge is to ensure both the functional and timing correctness of complex software. We argue that static analysis of software is insufficient to verify the safety of all possible control flow interactions. Likewise, a static system structure upon which software can be isolated in separate protection domains, thereby defining immutable boundaries between system and application-level code, is too inflexible to the challenges faced by real-time applications with explicit timing requirements. This paper, therefore, investigates a concept called "mutable protection domains" that supports the notion of hardware-adaptable isolation boundaries between software components. In this way, a system can be dynamically reconfigured to maximize software fault isolation, increasing dependability, while guaranteeing various tasks are executed according to specific time constraints. Using a series of simulations on multidimensional, multiple-choice knapsack problems, we show how various heuristics compare in their ability to rapidly reorganize the fault isolation boundaries of a component- based system, to ensure resource constraints while simultaneously maximizing isolation benefit. Our ssh oneshot algorithm offers a promising approach to address system dynamics, including changing component invocation patterns, changing execution times, and mispredictions in isolation costs due to factors such as caching.

For original paper see R. West et al., ibid., vol.53, no.6, p.744-759, (2004). This short report clarifies the behavior of DWCS with respect to Theorem 3 in our previously published paper and describes an alternative approach to make guarantees for arbitrary window-constraints

In most operating systems, the handling of interrupts is typically performed within the address space of the kernel. Moreover, interrupt handlers are invoked asynchronously during the execution of arbitrary processes. Unfortunately, this allows for a process's time quantum to be consumed by arbitrary interrupt handling. To avoid significant impact to process execution and also to respond quickly enough to interrupts, interrupt servicing is usually split into two parts: a "top" and "bottom" half. The top half executes at interrupt time and is meant to be short enough to complete all necessary actions at the time of the interrupt. In contrast, the bottom half can be deferred to a more suitable point in time to complete servicing of a prior interrupt. Systems such as Linux may defer bottom half handling to a schedulable thread that may be arbitrarily delayed until there are no other processes to execute. A better approach would be to schedule bottom halves in accordance with the priorities of processes that are affected by their execution. Likewise, bottom half processing should be charged to the CPU-time usage of the affected process, or processes, where possible, to ensure fairer and more predictable resource management. This paper describes some of our approaches, both algorithmically and in terms of implementation on a Linux system, to combine interrupt scheduling and accountability. We show significant improvements in predictability of a Linux system by modifying the kernel to more accurately account for interrupt servicing costs and more precisely control when and to what extent interrupts can be serviced

With the increased use of Virtual Machines (VMs) as vehicles that isolate applications running on the same host, it is necessary to devise techniques that enable multiple VMs to share underlying resources both fairly and efficiently. To that end, one common approach is to deploy complex resource management techniques in the hosting infrastructure. Alternately, in this paper, we advocate the use of self-adaptation in the VMs themselves based on feedback about resource usage and availability. Consequently, we define Friendly VM (FVM) to be a virtual machine that adjusts its demand for system resources, so that they are both efficiently and fairly allocated to competing FVMs. Such properties are ensured using one of many provably convergent control rules, such as Additive-Increase/Multiplicative-Decrease (AIMD). By adopting this distributed application-based approach to resource management, it is not necessary to make assumptions about the underlying resources nor about the requirements of FVMs competing for these resources. To demonstrate the elegance and simplicity of our approach, we present a prototype implementation of our FVM framework in User-Mode Linux (UML)---an implementation that consists of less than 500 lines of code changes to UML. We present an analytic, control-theoretic model of FVM adaptation, which establishes convergence and fairness properties. These properties are also backed up with experimental results using our prototype FVM implementation.

Cluster computing environments built from commodity hardware have provided a cost-effective solution for many scientific and high-performance applications. Likewise, middleware techniques have provided the basis for large-scale applications to communicate and exchange data across the various end-hosts in a distributed system. Unfortunately, middleware services are typically encapsulated in user-level address spaces that suffer from scheduling delays and communication overheads induced by the host kernel. For various high performance distributed computing applications such overheads are unacceptable. This work therefore addresses the problem of providing an efficient end-host architecture to support application-specific communication services at user-level, without the need to explicitly schedule such services or copy data via the kernel. We briefly describe a sandboxing mechanism that allows applications to configure and deploy services at user-level that may execute in the context of any address space. Using Linux as the basis for our approach, we focus specifically on the implementation of a user-space network protocol stack that avoids copying data via the kernel when communicating with the network interface. Our approach enables services to efficiently process and forward data via proxies, or intermediate hosts, in the communication path of high performance data streams. Unlike other user-level networking implementations, our method makes no special hardware requirements. Results show that we achieve a substantial increase in throughput, and a reduction in jitter, over comparable user-space communication methods.

ShareStreams (scalable hardware architectures for stream schedulers) is a unified hardware architecture for realizing a range of wire-speed packet scheduling disciplines for output link scheduling. This paper presents opportunities to exploit parallelism, design issues, tradeoffs and evaluation of the FPGA hardware architecture for use in switch network interfaces. The architecture uses processor resources for queuing and data movement and FPGA hardware resources for accelerating decisions and priority updates. The hardware architecture stores state in register base blocks, stream service attributes are compared using single-cycle decision blocks arranged in a novel single-stage recirculating network. The architecture provides effective mechanisms to trade hardware complexity for lower execution-time in a predictable manner. The hardware realized in a Virtex-I and Virtex-II FPGA can meet the packet-time requirements of 10 Gbps links for 256 stream queues with window-constrained scheduling disciplines. The hardware can schedule 1536 stream queues with priority-class/fair-queuing scheduling disciplines using 16 service-classes to meet 10 Gbps packet-times.

Current research on Internet-based distributed systems emphasizes the scalability of overlay topologies for efficient search and retrieval of data items, as well as routing amongst peers. However, most existing approaches fail to address the transport of data across these logical networks in accordance with quality of service (QoS) constraints. Consequently, we investigate the use of scalable overlay topologies for routing real-time media streams between publishers and potentially many thousands of subscribers. Specifically, we analyze the costs of using k-ary n-cubes for QoS-constrained routing. Given a number of nodes in a distributed system, we calculate the optimal k-ary n-cube structure for minimizing the average distance between any pair of nodes. Using this structure, we describe a greedy algorithm that selects paths between nodes in accordance with the real-time delays along physical links. We show this method improves the routing latencies by as much as 40%, compared to approaches that do not consider physical link costs. Additionally, we discuss an approach that dynamically repositions nodes in logical space, to improve the likelihood of meeting service requirements on data routed between publishers and subscribers.

This paper presents an approach to window-constrained scheduling, that is suitable for multimedia and weakly-hard real-time systems. Our algorithm called virtual deadline scheduling (VDS) attempts to service m out of k job instances by their virtual deadlines, that may be some finite time after the corresponding real-time deadlines. By carefully deriving virtual deadlines, VDS outperforms our earlier dynamic window-constrained scheduling (DWCS) algorithm when servicing jobs with different request periods. Additionally, VDS is able to limit the extent to which a fraction of all job instances are serviced late, while maximizing resource utilization. Simulations show that VDS can provide better window-constrained service guarantees than other related algorithms, while having as good or better delay bounds for all scheduled jobs. Finally, an implementation of VDS in the Linux kernel compares favorably against DWCS for a range of scheduling loads.

We describe an algorithm for scheduling packets in real-time multimedia data streams. Common to these classes of data streams are service constraints in terms of bandwidth and delay. However, it is typical for real-time multimedia streams to tolerate bounded delay variations and, in some cases, finite losses of packets. We have therefore developed a scheduling algorithm that assumes streams have window-constraints on groups of consecutive packet deadlines. A window-constraint defines the number of packet deadlines that can be missed (or, equivalently, 'must be met) in a window of deadlines for consecutive packets in a stream. Our algorithm, called dynamic window-constrained scheduling (DWCS), attempts to guarantee no more than re out of a window of y deadlines are missed for consecutive packets in real-time and multimedia streams. Using DWCS, the delay of service to real-time streams is bounded, even when the scheduler is overloaded. Moreover, DWCS is capable of ensuring independent delay bounds on streams, while, at the same time, guaranteeing minimum bandwidth utilizations over tunable and finite windows of time. We show the conditions under which the total demand for bandwidth by a set of window-constrained streams can exceed 100 percent and still ensure all window-constraints are met. In fact, we show how it is possible to strategically skip certain deadlines in overload conditions, yet fully utilize all available link capacity and guarantee worst-case per-stream bandwidth and delay constraints. Finally, we compare DWCS to the "distance-based" priority (DBP) algorithm, emphasizing the trade-offs of both approaches.

This paper presents the embedded realization and experimental evaluation of a media stream scheduler on network interface (NI) CoProcessor boards. When using media frames as scheduling units, the scheduler is able to operate in real-time on streams traversing the CoProcessor, resulting in its ability to stream video to remote clients at real-time rates. This paper presents a detailed evaluation of the effects of placing application or kernel-level functionality, like packet scheduling on NIs, rather than the host machines to which they are attached. The main benefits of such placement are: 1) that traffic is eliminated from the host bus and memory subsystem, thereby allowing increased host CPU utilization for other tasks, and 2) that NI-based scheduling is immune to host-CPU loading, unlike host-based media schedulers that are easily affected even by transient load conditions. An outcome of this work is a proposed cluster architecture for building scalable media servers by distributing schedulers and media stream producers across the multiple NIs used by a single server and by clustering a number of such servers using commodity network hardware and software.

General-purpose operating systems are ill-equipped to meet the quality of service (QoS) requirements of complex real-time applications. Consequently, many classes of realtime applications have either been carefully developed to compensate for inadequate system support, or they have been developed to run on special purpose systems. This paper focuses on a safe extension architecture for general purpose systems, to allow applications to customize the behavior of the system for their individual needs. Using Linux as the basis for our work, we describe how application programmers can safely incorporate `service extensions´ into the kernel, so that application-specific QoS guarantees can be provided. We introduce the notion of `QoS safety´, which is concerned with meeting the QoS constraints of applications while maintaining system integrity. Our safe extension architecture supports the dynamiclinking of code into the address space of the kernel, to affect service management decisions. Extensions are written in a type-safe language, to monitor and adapt resource usage on behalf of specific applications. Experimental results show that safe kernel extensions can lead to fewer service violations (and, hence, better qualities of service) for realtime tasks, compared to user-level methods that monitor and adapt system resources.

Distributed multimedia applications require support from the underlying operating system to achieve and maintain their desired Quality of Service (QoS). This has led to the creation of novel task and message schedulers and to the development of QoS mechanisms that allow applications to explicitly interact with relevant operating system services. However, the task scheduling techniques developed to date are not well equipped to take advantage of such interactions. As a result, important events such as position update messages in virtual environments may be ignored. If a CPU scheduler ignores these events, players will experience a lack of responsiveness or even inconsistencies in the virtual world. This paper argues that real-time and multimedia applications can benefit from coordinatedel event delivery mechanism, termed ECalls, that supports such coordination. We then show ECalls's ability to reduce variations in inter-frame times for media streams.

Operating system enhancements to support real-time and multimedia appl ications often include specializations and extensions of kernel functionality, as with the kernel HTTP daemon (khttpd) in Linux, for instance. To enable efficient and flexible interactions of such extensions with user-level functionality, we have developed ECalls, a lightweight, bidirectional kernel/user event delivery facility, which not only supports the timely delivery of events, but it also reduces the cost and frequency of kernel/user boundary crossings. ECalls is a communication tool that allows (a) kernel extensions to register their offered services and (b) applications to register their interest in these services. Using ECalls, applications use lightweight system calls to generate events, while kernel extensions raise real-time signals or invoke handler functions (residing in either user or kernel space), or they may use kernel threads to handle events on behalf of applications. ECalls can also influence the CPU scheduler such that a process with pending events is given preference over other processes. To demonstrate its utility, this paper implements an I/O event delivery mechanism using ECalls. This mechanism is shown to improve the performance of two applications: a distributed video player and a web server.

This paper presents the embedded construction and experimental results for a media scheduler on i960 RD equipped I20 Network Interfaces (NI) used for streaming. We utilize the Distributed Virtual Communication Machine (DVCM) infrastructure developed by us which allows run-time extensions to provide scheduling for streams that may require it. The scheduling overhead of such a scheduler is /spl ap/65 /spl mu/s with the ability to stream MPEG video to remote clients at requested rates. Moreover, placement of scheduler action 'close' to the network on the Network Interface (NI) allows tighter coupling of computation and communication, eliminating traffic from the host bus and memory subsystem, allowing increased host CPU utilization for other tasks without being affected by host-CPU loading. Architectures to build scalable media scheduling servers are explored-by distributing media schedulers and media stream producers among NIs within a server and clustering a number of such servers using commodity hardware and software.

Describes how dynamic window-constrained scheduling (DWCS) can guarantee real-time service to packets from multiple streams with different performance objectives. We show that: (1) DWCS can guarantee that no more than x packets miss their deadlines for every y consecutive packets requiring service, as long as the minimum aggregate bandwidth requirement of all real-time packet streams does not exceed the available bandwidth; (2) using DWCS, the delay of service to real-time packer streams is bounded even when the scheduler is overloaded; (3) DWCS can ensure that the delay bound of any given stream is independent of other streams; and (4) a fast response time for best-effort packet streams, in the presence of real-time packet streams, is possible. Furthermore, if a feasible schedule exists, each stream is guaranteed a minimum fraction of available bandwidth over a finite window of time.

Gigabit network technologies have made it possible to combine workstations into a distributed, massively-parallel computer system. Middleware, such as distributed shared objects (DSO), attempts to improve programmability of such systems, by providing globally accessible 'object' abstractions. Researchers have developed consistency protocols for replicated 'memory' objects. These protocols are well suited to scientific applications but less suited to multimedia or groupware applications. We address the state sharing needs of complex distributed applications with: high-frequency symmetric accesses to shared objects; unpredictable and limited locality of accesses; dynamically changing sharing behavior; and potential data races. We show that a DSO system exploiting application-level temporal and spatial constraints on shared objects can outperform shared object protocols which do not exploit application-level constraints. We compare our S(emantic) DSO against entry consistency using a sample application having the four properties mentioned above.

The monograph, Improving the Maintainability of Software, has the objective of providing practical guidance on the maintainability of software: maintainability definitions, factors, building and improvement suggestions, and an assessment method. The first part of this review provides an introduction to the monograph and discusses the general software maintainability guidance it provides. The second part provides a more in-depth review of the maintainability assessment method. This monograph is easy to read and understand. The guidance provided appeals to common sense and reflects an understanding of many software maintenance concerns. Although the scope of the monograph is primarily business information systems, the guidance is basically sound for many other types of applications in business, industry, government and military organizations. The defined framework of maintainability factors, features, and measures provides interesting guidance for discovering potential areas of concern. Identifying these areas of concern can be a basis for directing action and resources to the more critical maintenance activities. The maintainability assessment method provided by this monograph is not adequately supported by references or detailed information. Definitely read this monograph for its practical guidance. But be careful when applying the maintainability assessment method and analysing the results.