Related Work

  The idea of using a single address space (SAS) within an operating system is not new -- indeed the model is found as far back as OS/360[Witt66]. And with the emergence of 64-bit microprocessors and architectures such as the DEC Alpha[Sites92], the HP PA-Risc[HP94], the Mips R4600 and the IBM PowerPC, many researchers have taken a new look at the SAS idea resulting in operating systems such as Angel[Murray93], Opal[Chase94] and Mungi[Heiser94].

The Angel system was developed by the Software Architecture Research Center (SARC) at City University, London. It is ``designed as a generic parallel and distributed operating system'', [Angel], and hence has support of distributed shared virtual memory (DSVM) as a major goal. It is based on a microkernel architecture which provides persistent virtual memory and a local RPC mechanism based on shared memory. The initial prototype implementation of Angel was an emulation running under SunOS. I am not aware of any subsequent native implementation.

Opal was developed by the Department of Computer Science, University of Washington. It provides dynamically variable size segments as a basic abstraction, and makes use of password capabilities[Anderson86] for access control. Threads explicitly attach to segments, presenting a capability for validation. Opal makes use of reference counts to automatically delete a segment after the last detach operation. It also supports explicit reference counting via a set of primitives[Chase95, pp. 49-50]. These may be used to prevent automatic deletion and hence provide persistent segments.

An implementation of Opal was produced running as a server task on top of the Mach microkernel. Segments were represented somewhat transparently by Mach memory objects , and a modified version of the Mach default pager was used to provide the backing store.

Mungi is an operating system which has been developed mainly by the School of Computer Science and Engineering at the University of New South Wales, Australia. Its main aim appears to be the support of persistent objects[Elphinstone96]. These are protected via a password capability scheme similar to that used by Opal, although in Mungi capabilities need not be presented explicitly to objects. Instead a cache of capabilities is maintained per task in its active protection domain .

The most recent implementation of Mungi is on top of the L4 microkernel for the Mips R4600 processor[Heiser97]. The Mungi API is represented as an L4 user-level server. Mungi system calls are implemented as lightweight IPC to this server, which can then either perform the system call itself or (in some cases) forward it to the L4 microkernel. This L4 server also incorporates a default pager for all Mungi tasks.

Nemesis is also a single address space operating system, yet its motivation for this is almost entirely orthogonal to that of these other systems:

• Persistence is not a major goal of the system, although it is of course possible to implement persistent objects (or whatever) at user-level on top of the architecture presented here.
• Distributed shared virtual memory (DSVM) is also not a design goal. While DSVM may in some cases provide a convenient abstraction, it does not scale and furthermore may unduly obfuscate the performance of certain applications. Once again, DSVM may be supported at user-level if it is desired.

As there is no built-in support for persistence, there is no need for reference counting to determine if there are outstanding users of a particular stretch. Memory resources allocated to a domain may be explicitly freed at any time, and are implicitly destroyed when the domain exits. This does not preclude the use of user-level stretch driver which maintains its own state on a backing store across reboots. It simply means that there are no assumptions built in regarding the use (or usefulness) or persistent memory mapped objects.

Furthermore, due to the non-distributed nature of the address space, the use of capabilities for access control is unnecessary. Rather than hide the unwieldly nature of explicit capabilities like Mungi, Nemesis does not use them at all. Clearly were a DSVM-style stretch driver to be implemented, it would require some form of authentication and identification mechanism. However this is a problem which should be solved by that particular stretch driver, not by the entire operating system.

Another aspect of the Nemesis memory management system which might be compared with other work is the removal of all paging operations from the kernel. Instead the NTSC is simply responsible for dispatching fault notifications.

At first this may sound rather similar to the ideas pioneered in Mach[Young87] and subsequently used in microkernel systems such as L4[Liedtke95b]. However it is considerably different from such microkernel architectures, or even from ``exokernel'' systems such as Aegis[Engler95]:

• Other systems allow the use of one or more external (i.e. non-kernel) pagers in order to provide flexibility/extensibility, to simplify the kernel or to support some higher-level ``library operating system''.
  However several applications will typically still share an external-pager, and hence the problem of QoS crosstalk remains.
• In Nemesis we require that every domain is self-paging .
  It must deal with any faults that it incurs. This, along with the use of the single address space and widespread sharing of text, ensures that the execution of each domain is completely independent to that of other domains save when interaction is desired.

The difference between previous approaches and the Nemesis one is illustrated in Figure 9.

  

Figure 9: External Paging versus Self Paging

The left-hand side on the figure shows the microkernel approach, with an external pager. Three applications are shown, with two of them causing page faults (or, more generally, memory faults). The third application has a server performing work on its behalf, and this server is also causing a memory fault. The kernel notifies the external pager and it must then deal with the three faults.

This causes two problems:

• Firstly, the process which caused the fault does not use any of its own resources (in particular, CPU time) in order to satisfy the fault. There is no sensible way in which the external pager (or the microkernel itself) can account for this. A process which faults repeatedly, then, degrades the overall system performance but bears only a fraction of the cost.
• Secondly, multiplexing happens in the server, i.e. the external pager needs some way to decide how to `schedule' the handling of the faults. However it will generally not be aware of any absolute (or even relative) timeliness constraints on the faulting clients. A first-come first-served approach is probably the best it can do.

On the right-hand side we once again have three applications, but no servers. Each application is causing a memory fault of some sort, which is trapped by the NTSC. However rather than sending a notification to some external pager, the NTSC simply notifies the faulting domain. Each domain will itself be responsible for handling the fault. Furthermore, the latency with which the fault will be resolved (assuming it is resolvable) is dependent on the guarantees held by that domain.