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

Supports Intel® 32-bit x86 architecture in protected mode
Software-based preemptive multi-tasking
Static priority-based, real-time Virtual CPU scheduler
Real-time hardware performance monitoring
Symmetric multi-processing, up to 8 logical CPUs
Boots from HD, CD-ROM, USB or Network (PXE)
Simple ATA and ATAPI support with ext2 and iso9660 filesystems
USB (v. 1.1) UHCI support: mass storage, network, serial port, video camera
PCI network cards: e1000, pcnet32, realtek 8169
TCP/IP networking provided by lwIP
Integration with ACPICA, a reference ACPI implementation
Sound Blaster 16 driver using DMA
Intel® hardware virtualization (VMX) support
Minimal Unix-style system call interface: fork/exec/open
Basic shell and 8042 keyboard driver

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)

Basic shell running the text adventure "Advent" ported from the PDP-11 Fortran version:

Here is a screen shot of Quest running pacman in a modified VGA resolution:

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

The Quest source code can be obtained from github

Reference Development Platform

While Quest will work on most x86 platforms with the right driver support, the hardware virtualization capabilities currently used for enhanced system safety require Intel processors with the following hardware flags (as reported under Linux via /proc/cpuinfo): vmx, ept, mtrr. Given our manpower resources, we have focused on Intel hardware-virtualization but AMD support wil be added in the future. This means you will need a multicore processor such as a Sandybridge, with extended page tables and memory type range registers.
To boot Quest we recommend using a motherboard with a PXE-compliant BIOS for network boots. Similarly, a motherboard with a built-in serial device (16550A-compatible UART or a PCI/PCIe slotcard) is recommended for serial debugging.
The following is a recommended base system:

Intel "Sandybridge" Core i3 2100 LGA 1155 3.1 GHz processor (alternatively, i5, i7 will do)
LGA 1155 motherboard. A Gigabyte GA-H67N-USB3-B3 mini-ITX board is quite nice if you desire a small form-factor. The ASRock Pro3-M mAATX is slightly larger but another excellent board.
NOTE: For the motherboard, it is desirable to have either the Z68 or H67 Intel chipset. These chipsets both support integrated graphics on the Core i3/i5/i7 CPUs. You also want a motherboard with a Realtek 8168/8111E integrated network chip. It is desirable but not required to have an RS232 serial header on the board, as well as PS/2 keyboard connectivity and a traditional PCI slot. The ASRock board above has all this, but such is it's popularity it's hard to find. The Gigabyte board is a mini ITX small form-factor board, typical of the boards in netbooks and tablet PCs. It lacks the serial header and PS/2 but this is not critical if you get a serial PCI-express card.

RECOMMENDED BUILD 1:

Intel Core i3 2100 LGA 1155 3.1GHz Processor
ASRock Z68 Pro3-M mATX Motherboard
2x2GB Corsair DDR3-1333 Memory
Serial DB-9 header connector (provides serial cable interface to back of case, and plugs into motherboard)
PS/2 or USB keyboard
Any mATX case with 200W+ power supply
CAT5 Ethernet cable to connect to another development machine
DB9 Serial cable to connect to another development machine

RECOMMENDED BUILD 2:

Intel Core i3 2100 LGA 1155 3.1GHz Processor
Gigabyte GA-H67N-USB3-B3 LGA 1155 H67 mini ITX Intel Motherboard
2x2GB Corsair DDR3-1333 Memory
Syba 1-port DB-9 Serial (RS-232) PCI-e Controller Card, Moschip 9820 Chipset
USB keyboard
Thermaltake Element Q case/power supply
Ethernet cable to connect to another development machine
DB9 Serial cable to connect to another development machine

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