AOS Design Guide

Introduction

• Introduction
• Data Structures and Subsystems
• Inter-process communication
• Debugging
• L4 Server Thread Management
• Advanced Work
• Alternate System Models
  • Monolithic System
  • Single Address Space (SAS)
  • Multi-server
  • Microkernel
  • OS161 on seL4

The AOS project is a very large and complex system. Often the system is built in an ad-hoc manner with little or no design beforehand, frequently with the attitude that it will be cleaned up later.

This design methodology typically produces a system with only partial functionality. This also involves a lot of writing and re-writing the same code. It is usually also the case that "I'll do it later" never eventuates.

This page lists some of the design choices involved when building SOS to allow you to better understand the difficulties before they occur. You are free borrow or ignore as much or as little of this information as you like. This is only a guide, and any SOS project you want to produce is fine.

Data Structures and Subsystems

While designing SOS you will need to consider a number of different subsystems and data structures, and how they inter-relate.

Some systems you will need to consider include:

• A task/thread startup protocol
• I/O
  • File system access
  • Console access
  • A VFS-like layer
• (Virtual) Memory
  • Page tables
  • Swapping
  • Frame management
  • Heap management
• Thread and Process management
• Namespace(s)
• Drivers
• Scheduling, run queues and blocking system calls

Some systems you probably don't need to implement, but still might like to consider are:

• Resource management
• Access control / multi-user issues
• Networking
• A page-cache

Inter-process communication

In Milestone 0 you are required to pass data from an application to the OS in the form of text data for printing. This is an example of passing parameters and data between seL4 address spaces.

There are many ways to pass data between applications, not limited to the following:

• UNIX-like copyin/copyout
• Many short-IPC messages
• Long IPC strings (NB: These are not be supported by your kernel)
• frame mapping
• Memory objects

Which model you use is up to you, however some mechanisms are more appropriate for some systems and not others (eg. copyin/copyout will not work well with a multi-server OS, and tricky to implement as a recovery-on-fault approach). A poorly designed IPC primitive is a common problem and leads to an inefficient system. You must ensure it is capable of providing fast communication (eg. simple system calls) and also efficient when dealing with large amount of data (eg. file access). You must also ensure your IPC mechanism is free of denial of service (DOS).

Debugging

Debugging your SOS project can often be a very difficult task. For more information on debugging in seL4 have a look at this page.

L4 Server Thread Management

Regardless of what kind of OS personality you choose to write, you will need to deal with multiple asynchronous requests to your seL4 server(s). There are a number of ways this can be achieved. Once again, this list is neither exhaustive nor truly distinct.

• Single threaded servers

  Have a single server thread and use continuations to avoid blocking and DOS.

• Single thread per "application"

  At the cost of extra resources you can remove some of the problems of blocking threads.

• Single thread per "session"

  Having more than one seL4 server can create a headache for multi-threaded solutions. Using sessions semantics can help to solve this.

• Worker threads per sub-system

  Dedicating a thread to each subsystem can help place an upper-bound on the number of threads that need creating (and deleting).

• Stack-switching

  A light-weight alternative to multi-threading is to have a separate stack per client/application. This can be simpler than multiple threads to manage and easier than explicit continuations. Debugging, however, can be ... interesting.

• Worker thread pool

  Using a multi-threaded solution can leave to wasting of resources. By creating a pool of worker threads that can grown and shrink resource usage can be controlled.

All the above techniques are valid for use in SOS. Each has their own advantages that make them easier/nicer/faster/better/whatever. They also have their own problems with implementation and testing. Make sure your solution is deadlock free, DOS free, thread safe, efficient and easy to debug.

Advanced Work

In AOS you are encouraged to do extra work that you are specifically interested in. This can be in the form of additions to the SOS project, or entirely different OS related projects. Some suggested SOS enhancements for extra marks are listed below. Feel free to come up with your own ideas. If you would like to do one of these (or your own suggestion), talk to us about what is to be done and how marks will be awarded.

Disclaimer: None of these advanced features is easy or trivial. You should avoid making your project dependent on any of these as there is a good chance you will not complete it. You should try to make sure you at least one to two milestones ahead of the marking schedule before you attempt one of these. The motto is "make it work, then make it fancy".

• Device Driver

  Write a more complex device driver than the OSTS timer. Examples include a USB controllers, USB disk drives etc. Marks can be awarded based on a partially functional driver.

• Protocol Implementation

  Implement a common network protocol within your SOS project. For example, port (or implement your own) ssh daemon to SOS. The difficulty of the protocol or port will dictate the bonus marks for it.

• Virtualise SOS

  OS virtualisation is a hot topic right now. Demonstrate two copies of SOS running on seL4, each running user-land applications. Each copy of the OS must be segregated from the other, and share device drivers securely.

• Distributed SOS

  Add distributed shared memory and cross-node process creation support to SOS.

• Orthogonal Persistence

  Filesystems are passé. Implement orthogonal persistence in SOS so applications restart back to the point when the system was shutdown. Fault tolerance is not necessary.

• Multi-user SOS

  The standard SOS project has memory protection, but no access control. Implement ACL or capability based access control and provide resource accounting. Multiple concurrent users can be provided with a trivial telnet server.

Alternate System Models

There are a number of different general system structures you can use when building an OS personality on top of seL4. A few major categories are listed here. Be aware that this is in no way an exhaustive list, and you are encouraged to come up with or design your own. These categories are also very rough, and in no way well defined.

Monolithic System

Most operating systems, eg. Windows, Linux and any BSD (Net, Free, Open, ...) use a monolithic system model, with most, if not all, of the system implemented in a monolithic kernel.

By placing all system components in the same address space communication is done trivially with shared memory and function calls. Of course, this means that all code in that address space is trusted and can bring down the whole system.

This model is the most commonly used for SOS as it is the easiest to implement and debug. Within this model there is plenty of scope for creativity and ample work for two people. Other models are presented here so you can incorporate ideas and abstractions. Students with a keen caffeine dependence are welcome to try them for a system model. There are very few systems to source examples from and many have problems which are as yet unsolved. If you choose a system model other than monolithic, you have been warned.

Single Address Space (SAS">

Single-address-space systems are designed to make sharing between applications easier. By placing all applications and the kernel in the same address space (translation) pointers can be passed around while maintaining their meaning. To preserve security the system needs to implement protection as an orthogonal abstraction.

While a SAS is not necessarily an entirely different model (it could be monolithic or multi-server), it does offer some interesting design decisions. Instead of the typical SOS filesystem you could create a persistent system. A SAS also helps in making a distributed shared memory system.

Example single address space operating systems include Mungi, Nemesis and Sombrero.

Multi-server

A multi-server OS is the holy-grail of microkernel systems. By decomposing the system into components (eg. VFS, file systems, memory management, naming), each in their own address space, the system can be constructed in a more flexible way. Multi-server OSes have a strong tendency to move more work into application libraries rather than the OS modules, but still preserving security. An example Multi-Server OS is Minix 3.

Microkernel

L4 is a flexible and fast microkernel, however there are other designs for microkernel (and micro-kernel-like) systems including L3, EROS, Mach, Exokernel and K42.

You may choose to pick an existing microkernel (or come up with your own abstractions) and implement this on top of seL4. You will also need to implement elements of SOS on this system to demonstrate its usefulness.

OS161 on seL4

OS161 is a specific example of a (simple) monolithic kernel developed for educational purposes, written for the MIPS32 architecture.

One option for the project is to port OS161 to seL4 by adding a new 'seL4' architecture. Because OS161 is already quite complete, it will also be necessary to add extensions and features to make this project in-line with writing SOS from scratch.