Quest
    A lightweight, predictable and dependable kernel for multicore processors

Overview

Quest is a small operating system designed to be used as the basis for research and education. Richard West and Gary Wong developed the beginning of Quest in the summer of 2005. Since that time, several others such as Matt Danish and Ye Li have contributed to developments, including SMP support and extended driver development.

Quest is open source software available under the terms of the GNU General Public License v3.

Features

Why a New OS?

Given the current state-of-the-art in OS development, and the numerous systems already available, this is a natural question to ask. In particular, writing a new OS is time-consuming, and technically difficult. It is unlikely that without many man-years of development a new OS will ever have the maturity to support commercial-grade applications, partly due to the lack of driver support and rich APIs/libraries on which such applications depend. However, from our experience the code complexity of existing modern systems often becomes a hindrance when developing new policies and mechanisms. Similarly, many pre-existing systems have evolved from designs that are fundamentally based on principles from several decades ago, yet in that time there have been significant hardware changes. We now have multicore processors with hardware virtualization support, simultaneous multi-threading (SMT), shared on-chip caches, NUMA topologies with on-chip integrated memory controllers and interconnection networks, and power management features. It is true that many modern OSes have evolved to support these new hardware features but there is evidence to suggest a new approach is worthwhile considering e.g., due to scalability concerns associated with the management of many on-chip cores, and also the micro-architectural resource contention due to the inherent parallel access to caches, bus interconnects and memory.

With this in mind, Quest is a new OS that aims to support "time as a first-class resource". From the ground up, Quest manages all resources via time-budgeted and temporally-isolated virtual CPUs (VCPUs). The system features a hierarchical scheduling infrastructure, with both main and IO VCPUs to handle the execution of conventional tasks and system events associated with interrupts.  This means that real-time and non-real-time tasks can co-exist without interference, at least in terms of the resource time budgets they are guaranteed. This does not, however, guarantee the amount of progress a task makes in real-time, because micro-architectural resource contention is still possible. For example, one task may evict another's memory contents from a shared on-chip cache, or may compete for memory bus bandwidth. These factors all affect the execution time of tasks.

To ensure efficient progress is made by all tasks, and to try to bound the amount of interference between tasks caused by micro-architectural resource contention, Quest incorporates a real-time performance monitoring sub-system that uses hardware performance counters to track micro-architectural resource usage. From this, we are able to construct performance curves and various resource usage models, including predictions of cache occupancy and the effect this will have on task execution.

Aside from predictability and efficiency objectives, Quest also aims to ensure its integrity is not compromised by ill-written or malicious third party software. This aspect of safety is to prevent system failure when any sub-component behaves erroneously. In this regard, Quest utilizes various hardware and software features (including hardware virtualization) to isolate system components, so that if one component fails the system can recover.

Early Screenshots (using Bochs)

Quest shell snapshot

Quest snapshot of pacman

Further Information

  • Ye Li, Matthew Danish and Richard West, "Quest-V: A Virtualized Multikernel for High-Confidence Systems", Technical Report: arXiv:1112.5136, arXiv.org
[pdf]
  • Matthew Danish, Ye Li and Richard West, "Virtual-CPU Scheduling in the Quest Operating System", in Proceedings of the 17th IEEE Real-Time and Embedded Technology and Applications Symposium, Chicago, IL, USA, April 11-14, 2011
[pdf]
  • Slides presented at Charles River Analytics (CRA), Cambridge, MA on Quest VCPU Scheduling
[pdf]
  • Slides for the talk at the 17th IEEE Real-Time and Embedded Technology and Applications Symposium, Chicago, USA, April 13, 2011
[pdf]
  • Poster presented at the BU Science Day, Spring 2011 on Quest’s VCPU Scheduling Infrastructure
[pdf]
  • Poster describing the background to the hardware performance monitoring subsystem in Quest, based on collaborations with VMware
[pdf]
  • Early design overview (for the original uniprocessor version of Quest)
[pdf]

Downloads

Reference Development Platform

People

Acknowledgement

This work is funded in part by various grants, including: NSF #0615153 and  #1117025.

Department of Computer Science, Boston University

Page maintained by Rich West