A distributed adaptable 1
Kernel
(STATUS REPORT)
Kernel
Francisco J. Ballesteros1 - Christopher Hess2 - Fabio Kon2 - Sergio Arévalo3 - Roy H. Campbell2
1 Univ. Carlos III de Madrid nemo@gsyc.escet.urjc.es
2 Univ. of Illinois at Urbana-Champaign {ckhess,f-kon,rhc}@cs.uiuc.edu
3 Unix. Rey Juan Carlos de Madrid s.arevalo@escet.urjc.es
Kernel
whose task is to export distributed hardware resources to the 2K
operating system. 2K builds on those resources to provide a
network-centric, adaptable computing environment.
The kernel is an object-oriented redesign of an initial non-OO
prototype, named Off. It includes new features that provide basic
architectural-awareness support for 2K. Thus, we have developed
similar systems both with and without object-orientation and could
experience the benefits and drawbacks of using this methodology.
This paper describes how we used design patterns to build Off++, and how new patterns have emerged during the development process. We briefly discuss the impact of using OO in performance and present some preliminary results.
Off++ [8] is a minimal Kernel that provides just
enough services to run the 2K OS [6]. It builds on
the exokernel paradigm [4], extending it to export
a collection of physical resources throughout the network. Different
OS abstractions and middleware implementations can be installed and
operated in a distributed fashion.
In Off++, distributed object systems can ``buy'' their physical
resources from remote locations and install their own customized
middleware abstractions. In typical distributed object systems, a
middleware layer implements abstractions for objects over abstractions
provided by the OS. We intend to demonstrate (with the implementation
of 2K services on Off++) that the overhead of running 2K on top of
large, monolithic kernels can be avoided by downloading specialized
middleware on nodes running a minimal Kernel like Off++. In
[3], we pointed out that this approach could also be
used on legacy systems (such as UNIX) to provide convenient hosted
environments with a performance comparable to native and specialized
systems.
We built the kernel by redesigning an old prototype [2] with the help of design patterns. During the development process, new patterns were found and applied. Our experience shows that employing object orientation leads to a substantial memory overhead and some run-time overhead. However, we have also learned that choosing appropriate design patterns and coding carefully can be the way to mitigate such overheads, sometimes even achieving run-time speedups when compared to non-OO implementations.
In what follows, we briefly describe Off++ in section 2, showing several patterns which have been used intensively throughout the kernel. Section 3 outlines some lessons learned. Related work is shown in section 4. Section 5 concludes and presents our future work.
Off++ is organized as a set of (nested) resource containers exporting resource units. Most of the kernel code provides a framework supplying different resource unit allocators and a hierarchy of resource containers. The kernel is actually a collection of instances of resource containers built using this framework. Physical resources (such as page frames, IO ports, processor time slots, etc.) are associated with containers supporting both allocation and resource operation (e.g. IOBanks/IOPorts allow users to execute I/O operations).
The kernel interface is the set of interfaces implemented by resource containers and their respective resource units. Every object identifier is unique network-wide, providing the means for handling objects remotely.
Off++ provides Architectural Awareness through navigator and inspector objects which are associated to every relevant kernel object. User-level code can navigate through every system component and inspect component properties using a single interface (e.g. user code can navigate a node to locate memory banks, then ask for the ``dma-capable'' property value, and locate chunks of memory supporting DMA).
Intensive use of the composite pattern [5] to
structure system components leads to a simple implementation of
resource navigation and inspection. Users may operate on large
containers (even a whole machine) in very much the same way they
operate on concrete resource units. For example, the set of services
targeted at supporting migration![[*]](/mix/linux/install/latex2html-98.1p5/icons.gif/foot_motif.gif){kind=icon}
can be used on
entities ranging from whole nodes to single page frames. We have
learned that using design patterns to structure system services
simplifies both system structure and the kernel interface.
Chains of responsibility [5] provide customizable per-application resource revocation mechanisms. Whenever a resource container is exhausted, the kernel generates an event. Such event traverses a chain of responsibility starting within the application (which may also employ an internal chain of responsibility). The chain ends on a resource referee which is responsible for releasing resources from non-cooperating applications. Simply put, by using well-documented OO techniques we achieved the degree of flexibility of an exokernel without placing the burden of resource management into the user application.
Both ``processes'' and the resources they need (e.g. address spaces) are modeled as resource unit objects. Resource implementors (e.g. address space managers) are also modeled as objects.
An execution context (termed ``Shuttle'' in Off++) is modeled as a container of identifiers (termed ``properties'' in Off++) for those objects or resources needed for that context to run. Therefore, insertion and removal of new properties (i.e. resources making up a context) is allowed on a per-context basis. Implementors for objects referenced by execution contexts are called on demand, on a context switch, to install or uninstall resources. The use of an OO design and an intensive use of delegation allow the dynamic addition and removal of features like address spaces and protection domains, while maintaining the main kernel code unaware of what particular services are being used.
Depending on user customizations, Off++ Shuttles may be a replacement for either kernel threads, or for entire processes. The actual ``process'' abstraction perceived by the user is built by library code on top of kernel Shuttles.
The Off++ abstraction for inter-process communication is the portal. Portals are kernel objects which allow a thread (1) to move into another protection domain, and (2) to deliver a message that is handled on the other side of the portal by a different thread. Their identifiers are unique in the network; thus, they can be used remotely.
Portals borrow from Aspect-Oriented Programming that a portal adapts
the properties of the handler on-the-fly (as an aspect can adapt the
behavior of an object). Thus, it is feasible to adjust the set of
properties used by a server shuttle depending on the portal used to access it. As
an example, the protection domain for a server shuttle can be adjusted
automatically on IPC, as well as any user identifier, IO privilege
level, and any other shuttle property. As it happens with resources
referenced from execution contexts, delegation is used so that the
portal subsystem is unaware of how those resources (properties) are
implemented. In few words, the use of an OO design provides
customizable IPC in Off++.
We make intensive use of the strategy pattern for portal
implementation: we encapsulate algorithms needed to locate remote
portals, transfer messages through the network, secure transfer to
remote nodes, etc. into strategies that can be selected and specified
by the user. The kernel is kept simple by delegating those concrete
implementations to whatever service implementor the user has
specified. Clever applications might provide their own protocols
while, at the same time, simpler applications may be unaware that
certain protocols are being used to deliver their messages.
Library code builds VM abstractions such as memory objects and address spaces using address translation facilities provided by the kernel. Off++ virtual memory facilities map pages to page frames within a given address translation table (termed ``DTLB''). Being page frames objects that are unique network-wide, the system supports address translations to remote page frames. Moreover, as page frame implementation may vary, it also supports address translations to ``on-disk'' memory, simplifying the implementation of paging.
A chain of responsibility is employed to handle page faults. The kernel simply creates the page fault event and delivers it. Every protection domain can supply its own page fault handler, and delegate its handling at will. The architecture supports user-level adaptable VM by allowing applications to install their own handlers.
Extra run-time overhead comes from the use of virtual function calls. However, preliminary measures have shown that the overhead is usually not significant. Therefore, we are increasing the number of dynamic dispatches which helps reducing the amount of code in the kernel.
Interestingly enough, the extensive use of OO design patterns have been enabled a number of optimizations in the kernel. As an example, the interpreter pattern has been used to allow users to download programs into the kernel. The aim is not to allow downloading of generic user code into the kernel, but to download simple control structures packaging several system calls--to avoid protection domain crossing. Besides, intensive use of strategies and chains of responsibility also permit specialization of system services for concrete applications.
To allow non-OO languages to interact with the kernel, we made its interface procedural. Kernel objects are contacted through portals; developers using OO languages use wrappers around the procedural interface to get an OO interface. This decision has simplified the use of non-OO languages. As a procedural interface must be provided in any case (at least a trap-based kernel call must exist), object wrappers (or proxies) can be an add-on feature. Forcing clients to employ OO wrappers for making system calls would force non-OO clients to use procedural-wrappers-for-the-OO-wrappers, which would add extra overhead.
Using object orientation leads to numerous interfaces for numerous kernel objects being exported to users, adding additional complexity. However, by adopting the composite pattern to structure Off++ resources, most functionality is exported by top-level abstract classes. Thus, we keep the number of interfaces and their complexity manageable. Another effort to keep the interface simple is to add a new software layer wrapping every OS object within a simple, yet expressive, abstraction (like Plan9 wraps system services with files.) We have designed a new abstraction, the Box [1], which could be used at user-level to provide a simple interface, hiding the complexity of system objects from the human interface. Such abstraction will be implemented in 2K to hide interface complexity in both 2K and Off++.
Systems like the Exokernel [4] export physical
resources as Off++ does, but they are confined to a local node and
expose the whole hardware complexity to their users. Off++ uses object
orientation both to facilitate the use the hardware and to provide
maximum adaptability. Other OO systems, like Choices
[7], support customization by downloading new
classes into the kernel, but this may compromise system reliability
and raises additional security problems. Off++ is closer to an
exokernel as it simply exports the hardware. Customization takes place
at user level, which is safer. System services are modeled using
well-known design patterns, leading to a simple kernel interface. Due
to space constraints, we omit here a discussion of systems which
either do not export hardware resources or are not OO. To the best of
our knowledge, no system exports distributed hardware resources as
Off++ does.
At the present moment, Off++ runs on Intel-based PCs. It includes user level implementations of a TCP/IP stack and of virtual memory. We are currently working on the port of dynamicTAO, the CORBA ORB used by 2K, to Off++. We will conduct experiments to explore optimizations enabled by Off++ both in the ORB and 2K. Finally, we plan to implement the box abstraction on 2k/Off++.
Choices Operating System.
Kernel
This document was generated using the LaTeX2HTML translator Version 98.1p5 (May 15th, 1998)
Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 ooosws
The translation was initiated by Francisco J. Ballesteros on 1999-05-25