Notes on "Exokernel: An Operating System Architecture for Application-Level Resource Management"

By Athanasios Kyparlis

1. Objective of paper:

"Exo" means "out" in Greek. This paper presents an OS architecture whose main characteristic is the minimization of the kernel and the transfer of traditional kernel functionality OUTside the kernel in application-level modules. It presents the design principles of this approach, a prototype minimal exokernel and an application-level `Library OS' working on top of this exokernel.

2. Motivation:

In traditional OS's the kernel provides high-level abstractions to all overlying applications. Their necessary generality can significantly limit the performance and implementation freedom of applications. Lowering the level of kernel-provided abstractions allows applications to exploit domain-specific optimizations in resource management. This is another instance of the end-to-end argument: `Applications know better than the OS what the goal of their resource management decisions should be and therefore, they should be given as much control as possible over those decisions.' This is accomplished by providing the necessary functionality through application-level Operating Systems which are implemented as libraries ("Library OS's"). The exokernel need only provide primitives to multiplex the hardware resources.

Additional advantages:

The number of kernel crossings is reduced as more things are done in application-space.

The cost of a kernel crossing itself is reduced as the kernel internal state and data structures are minimal.

The flexibility of the system increases because it's easier to make changes in existing abstractions or introduce new ones.

3. Main implementation issue: Safety

Figure 1. The Structure of Exokernel-based systems.

There is a qualitative difference between a traditional OS and an exokernel OS. The kernel is part of the Trusted Computing Base (TCB) of a computer system. Its correctness is proved (or assumed) and is necessary for the correct operation of the rest of the system. Applications, however, are untrusted and perhaps, even, malicious modules of code. The exokernel approach transfers resource management from the `safe' kernel environment to the `un-safe' application environment. This creates the need to support resource protection separately from resource management.

An exokernel achieves this by:

tracking ownership of resources using secure bindings.

guarding all resource usage or binding points using explicit allocation and revocation of resources. Allocations and revocations are also made visible to library OS's, so that the latter can participate in resource management protocols.

revoking access to resources using an abort protocol to break secure bindings of uncooperative library OS's by force.

A secure binding is a protection mechanism that decouples authorization from the use of a resource. It allows library OS's to bind to resources. In the paper, three techniques to implement secure bindings are discussed:

hardware mechanisms: for example, a file server can provide applications with capabilities for the various physical pages. The more simple hardware supported binding is a TLB entry, containing the mapping of a virtual to a physical address in a library OS's page table.

software caching: A small hardware TLB can be coupled with a large software TLB that acts as a cache for the hardware one.

downloading application code into the exokernel: this untrusted code is made safe by a combination of code inspection and sandboxing. One example is packet filters, which are used to manage incoming network messages.

Downloading code into the kernel can more generally be used to minimize the number of kernel crossings and place a bound on the execution time of the downloaded code. This code can be executed even when the corresponding application is not scheduled. These modules of code are called Application-specific Safe Handlers (ASHs). An important feature of the prototype exokernel is that it supports runtime compilation of these code modules (dynamic code generation).

4. Implementations and Performance Results:

Aegis is a first prototype of an exokernel. It uses user-specified interrupt and exception handling code. It uses TLB entries as a form of secure bindings and has a large software TLB cache. The CPU is modeled as a linear vector of CPU time slices and "round robin" scheduling is used. A process, however, can donate the rest of its current time slice or the rest of its time slices to another process (Asynchronous or Synchronous Protected Control Transfer). Aegis guarantees the atomicity of the transfer and the preservation of the application-visible register set. The authors present a comparison of Aegis with Ultrix's basic primitives. Aegis is roughly one order of magnitude faster.

On top of Aegis various Library OS's can run. A prototype library OS is ExOS. ExOS manages abstractions like virtual memory and process at application level. It supports ASHs for general use (not only in the context of networking). An ExOS ASH can perform general computation, thus being useful in various occasions where latency-critical operations are needed. Another important feature of ExOS is its extensibility, as various special-purpose implementations of abstractions can be active at the same time, meeting the needs of applications optimally. The presented comparison of ExOS with Ultrix and other state-of-the-art OS's is very promising, especially if you factor in the fact that ExOS is still immature.

5. Possible drawbacks

The exokernel approach produces the smallest possible microkernels. Their level is so low that they are actually hardware dependent. As a result, a lot of the system's functionality has to be implemented in higher levels. It is a standing question whether the higher cost of implementing an application can be justified by the gain in performance, especially if the scope of the application is limited. Another open subject is the practicality of ASHs. Proving ASH code safe is a non-trivial task and can be formidably difficult sometimes. It is not clear, however, if an exokernel system can perform well with no downloaded code. Finally, the major drawback of exokernel is that it hasn't been tested in real-life systems yet. Its future will be decided there, ultimately.

6. Conclusions

Exokernel is a new, inspiring approach to OS design. Extending the end-to-end argument in OS design, it advocates the minimization of OS kernels and the transfer of resource management to application-level untrusted code in order to obtain flexibility and primitives with better performance. Its main concern is to maintain system safety in this new setting. Although the first experimental results are promising, the exokernel approach has yet to be tested in real life systems.

7. References

Úlfar Erlingsson, Athanasios Kyparlis. Microkernels: The extent to which simple, efficient operations are a good choice in a kernel interface design. Project for CS601, Cornell University, Fall 1996.

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. 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.

Athanasios Kyparlis <kyparlis@cs.cornell.edu>