Disclaimer: This survey is not finished work, and its discussion may not even reflect my current beliefs. It has been put online as a service to the web community, and should be useful as at least the references are correct!
The basic idea of microkernels is to minimize the kernel, and implement as much of it as possible outside the TCB. The kernel should only export simple, low-level operations which hopefully allow for more efficient application implementations. This idea dates back to [Hansen 70], and a good overview can be found in [Liedtke 96]. Traditionally kernels are 'monolithic' in the sense that they implement all their functionality in a relatively unstructured fashion within the TCB. The advantages of microkernels are obvious from a software engineering standpoint:
But this integration of most drivers and servers back into the TCB largely eliminates the benefits of the microkernel approach, in the end resulting in an even more complex monolithic-like OS kernel.
Recently there have been several second generation implementations following the microkernel philosophy, which claim to solve the flexibility and efficiency problems of the first generation. How these implementations achieve this goal differs wildly, with the following three being representative:
2. The First Generation
There were several real microkernel-based OSs built in the late eighties and
early nineties. Perhaps the two most notable of these are
Mach [Golub 90]
and Chorus [Guillemont 82].
Mach, developed at CMU, was the most successful and has been used in
several commercial systems, such as the NeXTSTEP OS.
2.1. Original Goals
There are two goals a new systems architecture must achieve in order to gain
widespread acceptance, those of efficiency and flexibility. Thus originally
microkernels had the goal of running applications faster than existing
monolithic kernels, or at least not slower. In addition, in order to achieve a
real advance in OS design, microkernels necessarily were to allow for new
application structures, as well as supporting all existing types of
Apart from the above there were great expectations for the microkernel
approach as it was being introduced, and many people expected most or all of
the following benefits:
2.3. Inter-Process Communication Performance
The first item above, IPC cost, has been the primary focus of work intended
to improve microkernel performance, since it has far more impact than MCPI.
Even so, attempts at improving IPC cost in first-generation microkernels, Mach
in particular, were not successful enough, due to the third reason above.
Table 1 below shows the final IPC performance of the Mach OS after much
work had been done to optimize the IPC.
The work on L3, which lead to L4, finally managed to break this performance
In [Liedtke 96] it is noted that this Mach IPC performance is bad enough that roughly 10000 instructions must be executed between successive RPC calls for only a 10% degradation in speed relative to a monolithic kernel. This prohibits fine-grained client/server application structures. More generally, the lack of efficiency in first-generation and traditional kernels prohibits flexible application/OS structures such as those supported by IPC.
In comparison the L4 and Exokernel IPCs are a generous order of magnitude faster, due to their clean-slate implementations. These kernels are able to do RPC calls every 400th instruction with only 10% degradation in speed, which should be fine-grained enough for almost all applications. The SPIN kernel is based on Mach, and therefore shares its high IPC cost, but this may not be fatal to its performance due to alternative approach to extensibility.
The values in the above table, from [Bershad 95], [Engler 95], and [Liedtke 95], should be taken with a grain of salt since the comparisons were done on different machines, running at different speeds and with different instructions. Even so the values should be a good indication of the relative difference in the IPC performance of the four systems.
3. The Current Generation
The following three systems take radically different approaches to improving
the performance of the first-generation microkernels. We therefore describe
each system in some detail and in isolation from the others, leaving a
comparison of them to the conclusion.
L4, [Liedtke 96],
was developed by J. Liedtke and his group in 1995 and is the direct
descendant of L3, a first-generation microkernel.
The from-scratch development of L4, along with its small size and simple
interfaces, allow it to escape the third legacy-code type of microkernel woes.
L4 is based on the thesis that microkernels are processor dependent, i.e., that like code optimizers, microkernels are inherently not portable, although they improve the portability of the whole system. L4 supplies three abstractions, address spaces, threads and IPC, and implements only seven system calls. The threads in L4 are user-level, but with support from the kernel for communication and address-space management. These two last abstractions, address spaces and IPC, are particular interesting in L4, and are discussed in detail below.
The initial address space represents the physical memory and is owned by the initial-memory server. The owner of a virtual page can, using operations provided by L4, transfer its ownership to (grant), or share it with (map), a consenting recipient process. The owner can also remove any shared pages (demap) from the recipient's address space, without any prior agreement between the two processes.
This functionality allows the implementation of memory management and paging outside the kernel. Mapping and demapping are adequate to implement memory managers and pagers on top of the microkernel. Granting is used only in special situations to avoid double bookkeeping and address-space overflow, see [Liedtke 95]. In order to verify process consent IPC is used to implement memory management and paging, which further emphasizes the need for fast IPC.
The microkernel should, therefore, only provide the minimal necessary set of primitives to securely multiplex hardware resources. Higher-level functionality is provided by library OSs, which are user-supplied and untrusted by the Exokernel. In order for the Exokernel to be as simple and efficient as possible even its exported interfaces are hardware dependent. Most of the time the Exokernel is simply exporting hardware functionality.
Figure 2 above shows the structure of an Exokernel-based system with two applications making use of different library OSs. As the Exokernel has to accommodate for untrusted higher-level OSs its main goal is to securely export and multiplex the hardware primitives and resources. The Exokernel employs three techniques to accomplish this, Secure Bindings, Visible Resource Revocation and Abort Protocols, each of which is discussed below.
A common hardware mechanism is the TLB. Secure bindings can be implemented as mappings from virtual to physical addresses, i.e., as a TLB entry. If the hardware TLB is not large enough it is wrapped in a larger software TLB to cache such mappings. Another hardware mechanism, available on some Silicon Graphics systems, is a frame buffer with an ownership field associated with each pixel. There the hardware deals with protection of the frame buffer, with the Exokernel only being involved when pixels change ownership. It is also possible to download code into the kernel which is invoked on every resource access or event to determine ownership and what actions the kernel should perform. A packet filter is an example of such code.
Actually, this feature of downloading code can be used for more than just the implementation of secure bindings. More generally, an Application-specific Safe Handler (ASH) can be downloaded into the kernel and be allowed to perform general computation. This capability is performance motivated and is used to reduce the number of context switches between kernel and user mode, especially in situations where time limits make these switches impractical, such as network ACKs on packet receives. The ASHs, and in general all downloaded code, are untrusted and are made safe by a combination of code inspection (type-safe languages are used), guarded interpretation and sandboxing, much as in SPIN.
SPIN, [Bershad 95],
is based on the last version of the Mach microkernel, adding to it the
ability to download safe code and thus extend the kernel. As such it shows,
in a way, the latest generation of techniques developed to combat the
lackluster performance of first-generation microkernel OSs. It's presentation
here is therefore both appropriate and necessary.
SPIN uses language and link-time mechanisms to allow the dynamic extension of kernel services. Applications can download code for new OS services into the kernel, and are thus able to create fine-grained OS interfaces tailored to their specific needs. The extensions are translated by a kernel compiler, dynamically linked into the kernel and executed within the kernel's virtual address space.
SPIN provides a set of core services for managing memory and processor resources. Their level is similar to the internal interfaces found in monolithic OSs. Kernel extensions can use the core services as building blocks, as well as just perform arbitrary computation. The core services include operations supporting application control over virtual-memory, e.g., translation services for addresses. The core services also include lower-level interfaces for process management, defining a set of events to be handled by the users thread package and scheduler, as well as including a global scheduler which determines the recipient threads package of an event.
Another, potentially more crucial, performance problem is the efficiency of the kernel compiler. Proving a code module safe is not a trivial task and the resulting latency of installing new kernel extensions can sometimes be unacceptable. However, the current version of SPIN uses an external compiler which is an improvement from previous interpreter or internal compiler based systems [Pu 88]. In SPIN the compiler can be multitasked and the size of the kernel is smaller. Further improvements to the compiler interface might include caching compiled code to reduce amortized compile-time latency, and specialized optimizations dealing with such things as nested IPC redirections.
First let us look at how the three systems we examined above meet the original
goals of microkernels stated in Section 2.1.
All three systems are reported to perform as well, or better, than the
traditional monolithic kernels, and all three can be said to support novel
application structures (recursive address spaces, library OSs and kernel
extensions respectively). So what remains is to check the enumerated list of
From the above it is clear that the current generation of microkernels have solved the IPC and legacy problems mentioned in Section 2.2, but they do not seem to have solved the problem of higher MCPI in microkernels (from [Chen 93]). This should actually be a great cause for concern, since, with rapidly increasing internal CPU speed, cache performance is becoming more and more of an issue. In [Liedtke 95], however, it is stated that making the kernel small enough to fit almost entirely into the cache will eliminate this problem. The SPIN approach of computing within the kernel may also be a solution to this problem, despite the large kernel size.
The one common aspect of the current generation of microkernels is extensibility through downloaded code proven safe. This capability seems crucial for future high-speed networking and distributed OSs, especially with the sharply increasing relative cost of process-switching [Engler 95]. It is thus curious that L4 does not as of yet support kernel-downloadable extensions. A reading of the L4 papers, however, reveals that the system does in fact not have very good network performance, and one can guess that it is only a matter of time before they remedy this with downloadable extensions.
The complexity of the interface exported by second-generation microkernels varies greatly. L4 and Exokernel both provide simple, low-level operations. L4 provides the rudimentary kernel abstractions required for address-space and thread management, while the Exokernel provides the bare hardware-dependent primitives required for secure multitasking of resources. SPIN, on the other hand, exports a varied interface, with an application seeing the first-generation microkernel interfaces inherited from Mach, as well as the internal interfaces for kernel-downloaded code. The existence of ASHes in the Exokernel blurs the global picture even more. The proper set of kernel-provided operations is thus probably a mixture of efficient low-level operations and the ability to extend the kernel with higher-level operations when they are needed, e.g., to support time-critical functionality such as networking.
The Exokernel's hardware dependence may perhaps be a serious drawback. In [Liedtke 95] it was found that building very low level abstractions, such as those exported by L4, is extremely CPU dependent, requiring completely different approaches for successive members of the Intel x86 family. This seems to indicate that building low-level library OSs on top of Exokernels may be something which needs to be redone for each generation of processors. Such a high level of non-portability would be a very serious impediment for any real acceptance of Exokernel-based OSs.
In conclusion, we should stress what we have already pointed out in the introduction. The most important liability of the second-generation microkernels is the complete lack of real OSs based on them. Only every-day practical experience can prove an OS truly viable. As these microkernels are very recent it is still far too early for their final judgement. Time can be their only definite judge.
B.N. Bershad, R.P. Draves and A. Forin. Using Microbenchmarks to Evaluate System Performance. In Proceedings of the Third Workshop on Workstation Operating Systems, pp. 148-153, Key Biscayne, FL, April 1992.
B.N. Bershad, S. Savage, P. Pardyak, E.G. Sirer, M.E. Fiuczynski, D. Becker, S. Eggers and C. Chambers. Extensibility, Safety and Performance in the SPIN Operating System. In Proceedings of the 15th ACM Symposium on Operating System Principles (SOSP)(Copper Mountain Resort, Colo., Dec. 1995) ACM Press, 1995, pp. 267-284.
J.B. Chen and B.N. Bershad. The Impact of Operating System Structure on Memory System Performance. In 14th ACM Symposium on Operating System Principles (SOSP), Asheville, NC, pp. 120-133.
D.R. Engler, M.F. Kaashoek and J. O'Toole. Exokernel, an operating system architecture for application-level resource management. In Proceedings of the 15th ACM Symposium on Operating System Principles (SOSP) (Copper Mountain Resort, Colo., Dec. 1995) ACM Press, 1995, pp. 251-266.
D. Golub, R. Dean, A. Forin, and R. Rashid. Unix as an application program. In Proceedings of the Usenix Summer Conference (Anaheim, Calif., June 1990). Usenix Association, 1990, pp. 87-96.
R. Grimm, G.R. Ganger, M.F. Kaashoek and D.R. Engler. Application-Controlled Storage Management. Submitted for publication.
M. Guillemont. The Chorus distributed operation system: Design and implementation. In Proceedings of the ACM International Symposium on Local Computer Networks (Firenze, Italy, Apr. 1982) ACM Press, 1982, pp. 207-223.
P.B. Hansen. The nucleus of a multiprogramming system. Communications of the ACM, 13(4):238-241, April 1970.
M.F. Kaashoek, D.R. Engler, G.R. Ganger and D.A. Wallach. Server operating systems. This paper appears in the 1996 SIGOPS European Workshop, September 9-11, 1996.
J. Liedtke. Improving IPC by kernel design. In 14th ACM Symposium on Operating System Principles (SOSP), Asheville, NC, pp. 175-188.
J. Liedtke. On microkernel construction. In Proceedings of the 15th ACM Symposium on Operating System Principles (SOSP) (Copper Mountain Resort, Colo., Dec. 1995) ACM Press, New york, 1995, pp. 237-250.
J. Liedtke. Toward Real Microkernels. Communications of the ACM, 39(9):70-77, September 1996.
C. Pu, H. Massalin and J. Ioannidis. The Synthesis Kernel. Computing Systems, 1(Jan. 1988): 11-32.