\chapter{Review of Microkernels}


\section{What is a Microkernel?}

An Operating System is generally considered to be a set of
standard utility programs, plus a kernel which provides
services to allow programs to run.  The kernel provides
abstraction from the hardware and presents a higher level
interface to user programs.  It also normally provides
protection from other tasks and controls communication
between tasks.

The fundamental goal of a microkernel-based system is to
remove as much functionality as possible from the kernel.
As many services as possible should be provided by tasks
external to the microkernel.

This has two main advantages, firstly it allows testing and
debugging of the kernel to occur in an environment which
provides greater functionality.

Secondly, it can allow for multiple operating system
`personalities' to be run concurrently on the same machine. 
This benefits users by allowing scarce or expensive physical
resources to be shared.  If this is allowed by the specific
microkernel, it can also permit new versions to be tested
without disruption to other users of the machine.

The principle disadvantage of the microkernel approach is
that it will be slower than a monolithic kernel.  This can
be minimised by suitable design decisions, and we shall see
later how great an effect this has.


\section{Classification of Kernels}

It seems to be possible to classify kernels into three
different types.  Firstly, there are the monolithic
microkernels where all services are provided by the kernel
and there is a big distinction between kernel and non-kernel
systems.  Kernels are traditionally non-pageable for
engineering reasons and thus desirable additional features,
such as a filing system based on the ftp protocol do not get
added as this would lead to unacceptable memory usage by the
kernel.

Once we have the concept of a microkernel, the obvious
approach is to run an operating system emulator on top of it.
Effectively, the microkernel provides a virtual processor
which the emulator runs on.  This design is called a
single-server and these systems form the second category.
The microkernel will not be pageable and the single-server
may or may not be.  It is still monolithic to a great degree
however and it will still be very difficult to add
functionality to it.  Given this base, it is now feasible to
run and debug alternative versions of the single-server
concurrently with the base one, allowing for faster, more
convenient prototyping.

Thirdly, we can take the multiserver approach and split
the single-server into a collection of servers.  This
allows for some servers to be paged out if they are not
currently being used while others remain paged in.  If
one server contains bugs, its ability to affect other tasks
is greatly diminished and the problem can be isolated and
dealt with much more efficiently.  Again, replacement
servers can be developed concurrently with a `production'
collection of servers handling everyday usage.


\section{Examples of Kernel design}

There are many examples of the first class of kernel
available for study, such as Linux, NetBSD, FreeBSD and
OpenBSD.  We are not particularly concerned with these in
this project.

There are several microkernel designs which lend themselves
well to the second category (single-server) approach.  Mach
with the Lites single-server is probably the most popular
example of this type.  There is also an ongoing project at
GMD\footnote{The German National Research Center for
Information Technology} to port Linux to the L4 microkernel.

The Chorus \cite{coulouris} operating system was designed
for a multi-server approach.  In Chorus terminology, the
tasks are called actors.  In an attempt to improve performance,
actors may be co-located with the microkernel and run with
kernel privilege.  This is because switching from kernel mode
to user mode is extremely expensive with some processors,
notably the Intel x86 family.  One study \cite{lied95}
claims that switching to kernel mode and back to user mode
takes 107 cycles with the Intel 486.

Nevertheless, the Chorus microkernel and the Mach microkernel
share many similar concepts.  Both use the concept of ports to
implement interprocess communication (IPC), but they
implement protection in a different manner.  In Chorus,
a 64 bit key is used in addition to a port ID to make it
difficult for a malicious actor to send a message to an
unsuspecting actor.  In Mach, port send rights are
administered by the microkernel which allows tasks to revoke send
rights from tasks they no longer trust, and additionally to
implement send-once rights, where a client may allow a task
to send it a reply, but send no more messages.  L4 takes a
radically different approach by not attempting to implement
protection within the microkernel, but to adopt a distributed
protection scheme.

All three microkernels have very different ideas about
implementing device drivers.  Mach retains the device
drivers within the microkernel.  Chorus removes them into actors,
which are co-located with the microkernel, but they can still be
developed externally to the microkernel since it presents the
same API to the actor.  In L4, device drivers are not part
of the microkernel at all.  They are implemented as processes
which claim any interrupts they require and request portions
of the memory map which correspond to memory mapped I/O
regions.  Interrupts are implemented by the microkernel sending a
message to the driver which has claimed that interrupt. 
This is similar to Chorus, but L4 does not require
colocation in order to achieve acceptable performance.  This
is probably due to the extremely efficient IPC in L4. 

Writing new device drivers is one of the most common
requirements when developing, maintaining and porting
kernels, so a system which permits drivers to be developed,
tested and debugged more efficiently and safely is extremely
useful.

Mach and Chorus were developed in a very different way to
L4.  Their designers implemented features that they thought
would enable people to implement other operating systems on
top of the microkernel in an effective manner.  Instead, L4
implements what its designers consider to be a minimal set
of features that are sufficient to implement an operating
system.  The designers are then able to expend much more
effort on optimising the few remaining operations which are
used frequently.

For example, when IPC was designed in L4, the designers
calculated the minimum time possible for a message to be
delivered, assuming an optimum scenario.  They then set
themselves a target of double this.  A full description of
this method can be found in \cite{ipcdesign}.


\section{Why build multiservers?}

Once the decision has been taken to remove functionality
from the kernel and place the functionality of the operating
system into a user-level task, the next natural inclination
is to split the kernel up into separate bits.  This has the
advantage of shielding one portion of the kernel from
another and allows for replacement of part of the kernel
while leaving other portions undisturbed.  It can also allow
for operating systems with vastly different requirements to
run on the same machine.  For example, a real-time scheduler
can coexist with a typical Unix scheduler, allowing non-critical
tasks to run when the real-time systems are idle.

There may be additional overheads involved with this approach.
In particular if task switching is slow, communication between
the different servers involved will be slow.