microkernels

[shapj@us.ibm.com]

Actually, I was probably the cause for this round of the debate, so I'ld like to
participate.  If someone will be kind enough to tell me how to do so, I shall
simply join the tunes list for the moment.

Rather than try to join the discussion at hand, though, perhaps you will indulge
me in some general comments on the differences (or lack thereof) between
microkernel and monolithic kernels -- I've been involved with several operating
system efforts at several points on the spectrum.

My first comment, I suppose, is that there isn't any *intrinsic* advantage to
either design. Some thoughts on things that are *not* compelling arguments pro
or con:

PERFORMANCE

People have argued about performance, but the arguments are mostly pretty
stupid. First, the comparisons begin with a questionable assumption: that the
two systems should run comparable APIs. Typically, the POSIX API is used as the
interface to measure. But let's test the assumption! If you wanted to run POSIX
then Linux or FreeBSD or (your UNIX here) are quite good at doing that.  In all
likelihood a general microkernel is not going to do as well as a monolithic
system designed specifically for a single API.

An aside: I'm benchmarking EROS at the moment, and the kernel entry/exit
mechanism of EROS is considerably more general than the POSIX kernel interface.
Any kernel entry can perform a directed context switch. On the negative side,
this means that the minimal overhead to enter the kernel is higher than that of
Linux.  EROS kernel will *never* support trivial system calls such as getppid()
as well as Linux does.  On the other hand, it is considerably faster at some
things than Linux is for reasons that are equally dependent on the architecture.

Given that UNIX is likely the fastest POSIX implementation, If you went to a
microkernel architecture you were looking for something other than performance.
Perhaps you wanted better fault isolation.  Perhaps you wanted to be able to
configure the system more easily.  In any of these cases, you decided that
something was more important than the last bit of performance, and you hope to
get whatever that may be by using a microkernel.

On the other hand, you may have decided that some microkernel offers features --
footprint, performance on your app, ease of assurance and inspection -- that are
more important than running POSIX.

In either case, the performance comparison is moot, because you decided going in
that performance wasn't the primary concern.

I think this is in contrast with one of the points made in the discussion:

> a) design comparisons are more meaningfully done "at constant functionality"

The only meaningful comparison is to ask how the applications you care about
execute on the final system.  The notion of "at constant functionality" is a
misnomer -- if you have chosen a microkernel in the first place you have already
decided that there is a functional differentiation that you wish to leverage.

In spite of the fact that such comparisons place microkernels at an inherent
disadvantage, several microkernels are now coming within a few percent of native
Linux performance.

DRIVERS IN/OUT OF KERNEL

I used to use this as a metric for microkernels.  I don't anymore.  For reasons
of performance it is now essential that some drivers live within the supervisor,
and for reasons of security it is vital to restrict which processes can access
physical memory, device registers, and DMA.  The usual solution is to run them
as processes that execute in the kernel address space.

Running drivers as seperate processes that execute in the kernel address space
doesn't help any, as it provides not fault isolation.  It also adds considerable
overhead to the drivers (I did the process-based implementation in EROS at one
point and backed out because the overhead was very large).  Just because the
drivers are compiled in a separate binary doesn't make the kernel a microkernel.
Heck, in Chorus and some other systems the drivers can be moved in and out of
the kernel to suit.

This is sort of like the debates about whether machines with a string move
engine or a "compare and swap" operation can be considered RISC machines.  The
argument is silly.  Transistor counts are equally silly.

If there is one, I think the difference between a microkernel and a monolithic
kernel lies in simplifications of the main control flow and data flow paths, and
the minimization of the number of abstractions that lie within the performance
"core" of the operating system. Reductions in the number of abstractions and
interdependencies increases implementation options.

COMMENTS

Stepping off my soap box :-), some responses on specific parts of the
conversation at hand:

>> 1)  Micro kernels look good for hard realtime systems:
>>     A) The source code is smaller and easier to prove and verify,
>>        and predict.
>Is it the micro-kernel approach that simplifies things,
>or is it not the fact that you have smaller and simpler overall systems?

Actually, Eric has a point here -- though I disagree about predictability.
There is a lot of data that says that bugs rise faster than lines of code --
some would suggest exponentially faster.  To the extent that it is possible to
divide things into forcibly isolated components with well-defined interfaces,
and to *enforce* the isolation, one achieves better separation of concerns and
better testability.

One problem with libraries is that they don't really achieve this.  You take a
library and test it, and you arrive at some confidence in it's correctness --
let's say 95% (which is about the best I've seen from real testing practices
anywhere).  That's a 5% chance of a bug, and inevitably the bugs you didn't
catch are the harder ones to find.  You now compile together 20 such module, and
the chance of a fatal bug is...

So you really do get advantages in inspectability and verifiability.

In predictability I'm not convinced.  The problem is that all of those processes
tend to be mapped at conflicting addresses, leading to conflict behavior in the
data cache.  This can be quite serious, and apparently minor alterations in the
data and instruction cache behavior can have huge impact on performance.

[Eric wrote:[
>    A) Functionally is exported at a higher level, so mistakes in the initial
>       abstraction can be corrected. vs. Microkernels which must get it right
>       the first time.

I don't think this is true.  Abstractions can be bungled at any level.  Also, to
the extent that microkernels export more primitive abstractions (a questionable
assertion), the nature of what those abstractions must do is clearer and it is
easier to get them right. While there were some egregious mistakes concerning
data motion in Mach and some other early systems, I think it's fair to say that
early monolithic systems had egregious mistakes as well.

[Francois writes:]
> Can you show me one single thing of interest other than [proprietary
> software] in micro-kernels, that cannot be done in a safer and more
> efficient way by using a suitable module system in whatever high-level
> language is used to program the system?

You seem to be confusing "binary" and "proprietary". Once again, I caution you
not to get so caught up in your rhetoric that you lose track of what's
substantiable.  There are many reasons to want to support binary integration.
The most obvious are enabling add-on modules that users can safely accept.
There exists no language-based protection system today that has proven secure in
the field.  This is in part because language systems are inherently more complex
than operating systems.  A language-based module system is a fine thing to have,
but solutions that restrict programmers to a single language empirically do not
receive wide acceptance.

> That's why C is not such a good systems programming language,
> and why Modula-3, SML, and even Perl, are better choices.

Plus ca change, plus ca reste la meme

We certainly thought C was a poor choice when the EROS effort started.  We'll
shortly be converting to C because the level of abstraction in C++ is too high
to get a good, comprehensible kernel.  There are many (perhaps most) systems
that can and should be written in high-level languages.  A nucleus isn't one of
them.  Also, can you explain how you propose to verify the correctness and
security of the runtimes and compilers for any of these languages?

For a nucleus, I'ld rather have a non-optimizing compiler for a low level
language for which I can verify the compiler.

>>    E) On current hardware the main cost of a cost of a context switch
>>       is losing cache, and tlb state.  Monolithic kernels handle this
>>       quite well.
>Micro-kernel multiply this cost by a number of context switch
>proportional to the number of "servers" involved, i.e. proportional
>to the extent the micro-kernel "philosophy" was followed.

On some hardware, the cost of the user/supervisor crossing is also significant,
and with tagged TLBs the TLB cost is quite low.  It can certainly be done faster
in a language-based solution.

The cost argument, however, is empirically false.  Separation into components
leads to other simplifications in the code that cannot be realized in the
absence of an encapsulation boundary.  With KeyKOS, they frequently found a net
*improvement* from breaking applications up.

>Java, for all its warts, at least recalls us that security
>is a high-level concept, not a low-level concept.

Perhaps, but it also reminds us that *protection* is a low level concept.  Java
got this wrong, which is why Java has no meaningful security and never will.
Even in the no-kernel approach, one must build on the right primitives.

Jonathan S. Shapiro, Ph. D.
IBM T.J. Watson Research Center
Email: shapj@us.ibm.com
Phone: +1 914 784 7085  (Tieline: 863)
Fax: +1 914 784 7595