Background

This page describes some of our motivations and long-term aims for the RMoX operating system. RMoX is currently being developed for PC104+ embedded hardware (embedded PCs), but we intend for it to go much further. In the medium to long-term, we plan to use RMoX on ordinary desktop PCs, and routinely test our builds on real hardware and in PC emulators.

Development work on RMoX is currently funded by EPSRC (UK research council), as part of grant EP/D061822/1.

Motivation:

Our motivations for creating RMoX are based on the following observations:

• Problems affecting reliability, efficiency and scalability in existing systems. The reliability of existing operating systems, referring to their intended operation, is often compromised by problems of incorrect implementation, arising as a result of the programming languages used to build them. Most operating systems are written in the C programming language, which although well suited to the low-level nature of OS programming, offers little in the way of safety guarantees. By this we mean avoiding things such as null or undefined pointer dereferencing, aliasing and race-hazard errors.

  Users generally have some experience of the end result, for errors in operating system code as well as applications generally. Though things have improved over the years, most users have experienced an OS crash in one form or another — a kernel panic in Linux, caused by a faulty device-driver, or something else in the kernel; the blue screen of death on Windows systems; the unhappy mac on Apple's Macintosh computers. And many of us have seen things such as malfunctioned ATM machines at banks, or broken displays at airports.

  Not having guarantees of correct program operation (for the OS and 3rd-party add-ons, as well as user applications), means the OS must assume the worst and ensure that a malfunctioning application cannot crash the rest of the system. In most cases, this means running an application inside a virtual machine, where the visible memory and access to hardware (e.g. I/O regions and machine configuration registers), is restricted. The handling of memory is typically done through virtual memory, where an application sees one set of addresses, mapped by the hardware and OS to real addresses — usually through a mechanism such as paging. Whilst this generally makes operating systems resilient to application failure, it severly damages efficiency. In particular, context switching from one virtual machine to another will involve the reprogramming of the MMU (memory management unit), and usually a flush of the processor's memory cache (or at least a flush of the separate TLB cache used for page-table-entries).

  The scalability of existing operating systems is often questionable. By the scalability of a system, we mean the ability to modify and maintain it in the face of changing user requirements and hardware availability. This typically affects many other software systems too. As more and more code is added to a system, there is a tendency for those systems to become increasingly unstable (errors are introduced into what was already there), and the system becomes increasingly harder to maintain. The general situation is that the cost of effecting changes a software system is proportional to the size of the system, and not the size of the change.

• Problems when dealing with concurrency. The majority of existing software, including most operating systems, are written in sequential programming languages, including many object-oriented languages. Examples of these include C, C++, Java, C#, Pascal, Visual Basic, etc.. These languages were not initially developed with support for concurrency in mind, and generally do not accommodate it well. "Why bother with concurrency?" one might ask. The usual answer is to improve performance, given the increase in available multiprocessor and multicore hardware. Now that processors have pretty much reached the limits of CPU speed and power dissipation, multiprocessor and multicore are the only viable way to get more performance from the hardware.

  To take advantage of parallel hardware, we need parallel programming languages, or at least, mechanisms that allow multiple threads of an application to execute on separate processing cores. The usual solution in most languages is threads-and-locks, where different parts of an application run in separate threads of execution, interacting by reading and writing shared data protected by locks. This is typically the case for multiprocessor-capable operating systems written in C or C++, such as Linux and Windows. Unfortunately, the threads-and-locks approach does not scale well — the more processors that are added to the system, the more contention there will be on the locks protecting shared data. Furthermore, there is little or no support in the language to guarantee that locking and unlocking is used correctly — to avoid unlocked accesses to shared data (race-hazards), or to ensure that each lock has a corresponding unlock — and when multiple locks are required (operating on multiple shared data structures), the possibility of deadlock exists. A good read on some of the reasons why we need concurrent programming can be found here: http://www.gotw.ca/publications/concurrency-ddj.htm.

The bottom line here is that the current approach to the design and implementation of software systems, including operating systems, is fundamentally unsustainable. We need to turn to languages and systems for which we can make reasonable guarantees of correctness, get good performance on the next generations of multicore processors, and maintain and modify easily.

Solution:

RMoX is our solution to the problems described above, at least as far as operating-systems are concerned. The bulk of the system is written in the occam-pi programming language (see http://occam-pi.org/). This is a concurrent programming language, that uses a model of processes and communication. The semantics of occam-pi are described by Hoare's CSP (see http://en.wikipedia.org/wiki/Communicating_sequential_processes), which allows for a level of formal reasoning not possible for many programming languages. Occam-pi itself is based on traditional occam (developed by Inmos for the Transputer), incorporating ideas of dynamics and mobility from Milner's pi-calculus, alongside a wealth of other features.

Programs written in occam-pi, including our RMoX operating system, are constructed as layered networks of communicating processes. Processes running in parallel communicate and synchronise with each other using channels — point-to-point synchronous communication links. Barriers are also provided for synchronisation between groups of processes. Building programs in this way is what we refer to as process-oriented programming.

There are several features of the occam-pi language, and our implementation of it, that make it suitable for programming large scale applications, such as operating systems:

• Strictly controlled alias and parallel usage checking, avoiding the read/write and write/write sharing of data between parallel processes (no race-hazards).

• A very lightweight implementation for scheduling parallel processes (thousands to millions of concurrent processes).

• Efficient cache-affine scheduling on uni-processor and multicore hardware.

• Low overheads for processes communication and synchronisation (tens to hundreds of CPU cycles).

RMoX is our attempt to create an operating system, or rather, a tool-box of operating-system components, that can be used to build lightweight, flexible and concurrent operating systems. We are taking a fairly organic approach to the development of RMoX — starting small and growing from there. Embedded PCs are our primary target application area, e.g. systems driving dedicated hardware setups (factory machinery, environmental monitoring, information kiosks, ...). As part of the EPSRC funded research, we have developed RMoX to run on an embedded PC/104+, with a flat-panel display and touchscreen. The running system consists of several hundred parallel processes, currently. The same system (with some minor modifications) boots successfully on desktop PCs as well, and works with the hardware for which we have written device drivers. However, RMoX is not a desktop OS yet — much more work needs to be done, but it on the way.

History:

The history of the occam-pi programming language stretches as far back as 1983 with traditional occam, developed by Inmos for the transputer. The transputer was the first processor developed specifically for parallel computing systems, with an on-chip hardware microcoded process scheduler, and hardware communication links. Slow by today's standards, but fast at the time (1980s). This was at a time when personal computers were beginning to take shape, with 80386 (1985) and 80486 (1989) based machines emerging. Due to a variety of factors, the transputer business failed to get enough momentum to keep going, and Inmos ultimately went out of business (absorbed into SGS Thompson, now STMicroelectronics). Some of the transputer still remains today in chips produced by ST (such as the ST20), acting as a logic unit in embedded application such as set-top boxes.

The last revision of occam from Inmos came in 1994, with occam 2.1. Shortly thereafter, the sources to the occam compiler and the rest of the transputer utilities were given to the University of Kent, to make available open-source. This is where KRoC, the Kent Retargetable occam Compiler, started development, using the existing occam compiler, in conjunction with transputer-to-sparc and transputer-to-i386 code translators, and run-time systems implementing the multiprocessing functionality of the transputer. The KRoC system has grown, and since 2003 supports a new dialect of the occam language: occam-pi. Unlike occam designed for execution on transputer networks, occam-pi is highly dynamic, with data and channel mobility, dynamic process creation, extended synchronisations, multi-level process priority, and many more features. Initial distributions of KRoC were binary-only (for technical reasons); the first open-source release appeared in 2000, for Linux running on i386 based platforms. KRoC is still primarily focused on the Intel IA32 family of (Pentium, Core2, ...), but we have experimented with other architectures (Sparc, MIPS, PowerPC, ...).

RMoX was started in 2002 as an experiment to see if writing an operating system in occam/occam-pi was feasible, and if so, what benefits that could provide to OS design and implementation. Initial development work was carried out by Fred Barnes, Christian Jacobsen and Brian Vinter, and progressed slowly over the following few years. Since 2006, the development of RMoX for PC104+ embedded systems has been funded by EPSRC, to the point we are at today, currently being developed by Fred Barnes, Carl Ritson and Adam Sampson.