A lightweight, predictable and dependable kernel for multicore processors
Frequently Asked Questions
Why another RTOS?
Many existing real-time OSes are either very simplistic, lacking features such as process address spaces, threads and separation of kernel and user-space protection domains, or they are overly complicated and cumbersome for many application domains. Quest sits between relatively simplistic RTOSes such as µC-OS II/III and FreeRTOS, and more complicated systems such as Linux that lack the same level of real-time control. Quest supports memory protection and process management that is missing in RTOSes such as RTEMS.
Quest supports threads and address spaces, a separation of kernel and user-space protection domains, and operates as a single system image on symmetric multiprocessing (SMP) architectures. More significantly, it features a virtual CPU (VCPU) scheduler that integrates the management of tasks and device interrupts. Quest is arguably the first system built entirely on a collection of bandwidth-preserving servers for predictable and efficient management of tasks and interrupts. Whereas other research systems might claim to manage interrupts in a time-predictable manner, none of them feature the same budget management scheme as in Quest. For example, those built on Sporadic Servers suffer from the fragmentation of budget replenishments caused by short-lived interrupt handlers that ultimately degrade the effective bandwidth and, hence, CPU utilization.
There are lots of existing OSes. Why should I use Quest?
Quest is designed to be like a stripped down dual-mode system with a separation of kernel- and user-level protection domains. However, its memory footprint is far smaller than many other dual-mode systems, making it suitable for many embedded computing applications with limited resources. For example, Arduino-compatible devices with a hardware MMU (e.g., Intel Galileo and Edison) would make an ideal target for systems such as Quest. With its integrated I/O and CPU resource management, it is best suited for applications where timing guarantees on GPIOs are critical.
Is Quest built on Linux?
No. Quest is a completely standalone operating system, built from scratch and is entirely independent of any pre-existing OS.
Does Quest provide a POSIX API?
Yes. It supports a lightweight C library based on newlib. A basic set of system calls and library routines are provided but, as with many RTOSes, you may need to implement your own functionality if a specific API function is missing.
What platforms does Quest run on?
Quest currently runs on IA-32 (x86) processors, with optional support for PAE to address greater than 4GB memory. We hope to port to other architectures in the future, such as ARM. The current focus is on multicore x86 architectures, both PC-class and single board computers (SBCs). For SBCs, Quest runs on the the Intel Galileo, Edison, Minnowboard Max, Joule, Up, Up Squared, and Aero Compute Board (and, possibly, other untested boards). Unlike PCs, these SBCs feature support for general purpose I/Os (GPIOs) to interact with sensors and actuators. Quest is a good choice of system for SBCs with sufficient power to run an RTOS and which require high precision timed management of I/O events and tasks.
What timing guarantees does Quest provide?
Quest uses the local APIC timers on each processor core to manage time events. The local APIC timers are programmed in one-shot mode, to expire at the next earliest event on the corresponding core. Quest performs time accounting at the accuracy of the hardware timestamp counter, and charges CPU usage to the virtual CPU associated with the current thread of control. All flows of control are associated with VCPUs in Quest, including interrupts and kernel control paths that are not associated with application threads. This means Quest accurately tracks time and charges its usage to the correct entity.
LAPIC timers in one-shot mode run at the speed of the system bus rather than the timestamp counter. Although we account for time using timestamp counters, we post events by reprogramming the LAPIC one-shot timer. As a reference, on a 1.33GHz Minnowboard Max, the system bus speed is about 133MHz (approximately 1/10 of the processor/timestamp counter speed). This means Quest is limited to an event timing resolution of about 7.5nS and a time accounting resolution of about 0.75nS on a 1.33GHz Minnowboard Max. We plan to switch to TSC-deadline mode for LAPIC event timing in the future, which is cycle accurate. We caution, however, that other timing issues such as the overhead of reprogramming the LAPIC timers, kernel locks, the cost of reading the timestamp counter, scheduling/context switching and so forth, affect the overall timing precision of the system. Notwithstanding, Quest aims to be highly precise with its event timing and accounting, with accuracy down to the smallest number of clock cycles possible.
What exactly are VCPUs in Quest? I thought these were really a concept in virtual machine systems.
The term "Virtual CPU" (VCPU) is often used in virtual machine systems for a software entity that presents itself to a guest OS as a physical CPU (PCPU). For example, a guest OS might think it is running on a quad-core processor, when in fact it is assigned four VCPUs. In reality, the physical machine might have a totally different number of CPUs (or processor cores) than VCPUs. It is up to a hypervisor to map VCPUs to PCPUs.
In Quest, the term VCPU has often caused confusion. Simply put, a Quest VCPU is a resource container that is associated with one or more software threads. Each thread exists in a process address space and is bound to a VCPU, similar to how user-space threads bind to lightweight processes (LWPs) in systems such as Solaris. A VCPU in Quest has two parameters: a budget (C) and a period (T). The two parameters are measured in time (e.g., processor clock cycles, nano-/micro-/milli-seconds). A VCPU will be guaranteed at least C time units every T time units of a PCPU, when it is runnable. A runnable VCPU has a non-zero budget and is associated with a thread that is ready to execute.
VCPUs are mapped to physical CPUs, which can be hardware threads or processor cores. When a thread executes, its time spent running on a PCPU is charged to its corresponding VCPU. Quest supports two classes of VCPUs: (1) main VCPUs for conventional tasks, and (2) I/O VCPUs for interrupt handlers. This ensures that interrupt processing does not consume CPU time at the cost of some arbitrarily preempted (potentially time-critical) process as in systems such as Linux. Instead, all processing is properly charged to the correct VCPU. The distinction between main and I/O VCPUs allows for fine-grained budget management and accounting for potentially short-lived interrupt handlers.
How does Quest compare to a micro-kernel?
Quest is a dual-mode system, with a monolithic kernel separated from user-space applications. This structure is similar to systems such as UNIX. There are lots of benefits to micro-kernels, most notably the idea that services run in the least privileged protection domain necessary. Micro-kernels provide a clean separation of policy and mechanism and allow for easy extensibility of services that are isolated in their own logical protection domains. As the Quest kernel is fairly small (around 10,000 lines of C and a few hundred lines of assembly -- discounting drivers, lwIP, ACPICA, and regression tests, which take the codebase to several hundred thousand lines) it is possible to restructure it as a micro-kernel. Right now, the focus is more on timing predictability than a reinvention of micro-kernel design. Moreover, micro-kernels only answer part of the problem when it comes to timing guarantees. While a micro-kernel might have an observable worst-case delay it is not clear what the end-to-end delay is between application level services. Applications require user-space services that must be scheduled and so the true timing costs of a micro-kernel must factor in the policy used for scheduling. Quest, by comparison, is centered around a unique high-resolution real-time scheduler that integrates task and I/O management.
What exactly is the difference between Quest and Quest-V?
Quest is a real-time operating system for uni- and multi-core processors. Quest-V is a separation kernel. A separation kernel is a collection of distributed components assigned to domains, which appear indistinguishable from separate private machines for each component. Communication between domains is via explicit channels -- ideally, there should be no implicit channels for information flow.
Quest-V uses hardware virtualization technologies to isolate guest domains in separate sandboxes. A sandbox is an encapsulation of a subset of CPU cores or hardware threads, I/O devices, and regions of machine physical memory. The software environment within a sandbox includes a minimal monitor and a collection of operating system services and applications. It is possible for Quest-V to run separate instances of the Quest OS in different sandboxes, or a mix of Quest and other OSes such as Linux.
Quest-V defines a chip-level distributed system, with the possibility of different sandboxes running library OSes, or different services within their guest domains. What makes Quest-V different from other hypervisor technologies is that once a sandbox is bootstrapped, it runs directly on the hardware within its domain, without ever involving the hypervisor under normal operation. There is no need for a hypervisor to multiplex hardware resources between different guests sharing the same physical machine. There is no need for a hypervisor to do scheduling, I/O, or memory management. Instead, I/O-passthrough allows interrupts to be delivered directly to guests, and DMA devices transfer directly to or from guest memory without copying or passing through the hypervisor.
Quest-V does not need a complicated hypervisor. Each sandbox monitor runs within a 4KB page, because there is no need to provide complete machine virtualization. Instead, Quest-V uses sandbox monitors to establish secure communication channels between sandboxes using shared memory. Additionally, Quest-V supports real-time communication between sandboxes making the whole distributed system highly time-predictable. The sandboxes provide an extra level of security because the code used to isolate guests is removed from the normal execution path of the system.
Quest-V is intended for highly secure and predictable computing environments. It is extremely lightweight, making it suitable for embedded devices with multicore, hardware virtualization capabilities. It provides a way to integrate real-time systems such as Quest with legacy non-real-time systems such as Linux. This way, the drivers, libraries and existing code base for systems such as Linux can be combined with new time-critical components written for Quest. This eases the porting of code to a real-time system, without having to make wholesale changes to existing applications.
Quest-V is the world's first real-time chip-level separation kernel, which uses hardware virtualization for time and space isolation of guest services without the overheads of a hypervisor.
Does Quest-V require KVM, Xen or Linux to boot?
No. Quest-V is completely standalone. By configuring Quest with the -DUSE_VMX option, you enable support for virtual machine extensions for sandbox isolation on architectures with the necessary capabilities. For example, on Intel VT-x processors, cpuid flags should include vmx and ept. To host Linux you will also need a processor with unrestricted guest support (typically anything from Westmere onwards).
Quest-V initially follows the normal Quest bootup sequence on an SMP platform. The bootstrap processor (BSP) sends an INIT-SIPI-SIPI sequence to all the application processors (APs). Then, the BSP launches the first (guest) sandbox environment. APs follow by "VM forking" their sandboxes from the BSP copy. This leaves the system with a collection of Quest instances running on the available cores. A Quest sandbox can then act as a bootloader for Linux or some other OS in the target sandbox. Currently, we support a Linux frontend in one sandbox and multiple Quest instances in others.
How does Quest-V compare to a hypervisor?
See above. Quest-V is not a hypervisor. It does not perform machine virtualization. Instead it uses hardware virtualization for safe and secure resource partitioning. Using Quest real-time services in separate sandboxes, it is possible to build a real-time chip-level distributed system.
I don't see why anyone would want to use machine virtualization in a real-time system. Why, then, should I ever want to use Quest-V?
Machine virtualization adds overheads and potential areas of timing unpredictability that make it ill-suited to real-time systems. A major problem is the overhead of VM exits and re-entries on some architectures. Performing scheduling, I/O and memory management in a hypervisor add an extra level of overhead beyond that of single-OS systems. Virtual machine systems were originally designed to consolidate multiple guests onto the same host, thereby increasing resource utilization without the need for multiple under-utilized physical machines. This proved to be a boon for server-based computing, where a single machine is essentially over-committed with more guest OSes than physical cores. However, in Quest-V, a real-time separation kernel partitions resources so that a physical machine is never over-committed (at best, fully-committed).
In a nutshell, Quest-V is a separation kernel that uses hardware virtualization features to implement resource partitioning rather than resource multiplexing.
What are the main advantages and disadvantages of Quest-V over other systems?Advantages:
Mostly security, safety, predictability and efficiency. Using replicated sandboxes, it is possible to support real-time fault detection and recovery: one sandbox might fail and others can take over (using primary-backup services, or Triple Modular Redundancy, for example). Software faults, hardware transient errors (e.g., bit-flips in memory due to radiation), and timing errors can all be isolated and recovered using Quest-V sandboxing support. From a security perspective, untrusted services can be isolated from those that are more trusted, by placing them in separate hardware-enforced sandboxes.
It is possible to support mixed-criticality services. For example, a Linux sandbox might support legacy non-real-time services, while a Quest sandbox might support higher-criticality real-time services. This could make sense in applications such as automotive and avionics systems, healthcare, robotics and the Internet-of-Things.Disadvantages:
Quest-V does not currently run on ARM multicore platforms with hardware virtualization (e.g., the Cortex A15).
Widespread adoption of any OS, be it Quest(-V) or any other, relies on the development and availability of libraries, drivers and applications.
Engineers often prefer to patch systems such as Linux to make their existing applications work more predictably, rather than invest the time to redevelop those applications for a new OS. This leads to short-term solutions that are often problematic in the long-term. Quest-V at least provides a way to integrate legacy applications, libraries and drivers into the development of new application services for real-time OSes such as Quest. Rather than wholesale development of new applications, it is possible to alter existing applications so that the most time- or safety-critical components are rewritten as Quest services accessed via real-time (inter-sandbox) remote procedure calls.