Extensibility, Safety and Performance in the SPIN Operating System Notes | EduRev

Created by: Bhuvan Midha

: Extensibility, Safety and Performance in the SPIN Operating System Notes | EduRev

 Page 1


Extensibility, Safety and Performance in the
SPIN Operating System
Brian N. Bershad Stefan Savage Przemyslaw Pardyak Emin G¨ un Sirer
Marc E. Fiuczynski David Becker Craig Chambers Susan Eggers
Department of Computer Science and Engineering
University of Washington
Seattle, WA 98195
Abstract
This paper describes the motivation, architecture and per-
formance of SPIN, an extensible operating system. SPIN
provides an extension infrastructure, together with a core
set of extensible services, that allow applications to safely
change the operating system’s interface and implementation.
Extensions allow an application to specialize the underly-
ing operating system in order to achieve a particular level
of performance and functionality. SPIN uses language and
link-time mechanisms to inexpensively export ?ne-grained
interfaces to operating system services. Extensions are writ-
ten in a type safe language, and are dynamically linked into
the operating system kernel. This approach offers extensions
rapid access to system services, while protecting the operat-
ing system code executing within the kernel address space.
SPIN and its extensions are written in Modula-3 and run on
DEC Alpha workstations.
1 Introduction
SPIN is an operating system that can be dynamically spe-
cialized to safely meet the performance and functionality re-
quirements of applications. SPIN is motivated by the need to
support applications that present demands poorly matched by
an operating system’s implementation or interface. A poorly
matched implementation prevents an application from work-
ing well, while a poorly matched interface prevents it from
working at all. For example, the implementations of disk
buffering and paging algorithms found in modern operat-
ing systems can be inappropriate for database applications,
resulting in poor performance [Stonebraker 81]. General
This research was sponsored by the Advanced Research Projects
Agency, the National Science Foundation (Grants no. CDA-9123308 and
CCR-9200832) and by an equipment grant from Digital Equipment Corpo-
ration. Bershad was partially supported by a National Science Foundation
Presidential Faculty Fellowship. Chambers was partially sponsored by a
National Science Foundation Presidential Young Investigator Award. Sirer
was supported by an IBM Graduate Student Fellowship. Fiuczynski was
partially supported by a National Science Foundation GEE Fellowship.
purpose network protocol implementations are frequently in-
adequate for supporting the demands of high performance
parallel applications [von Eicken et al. 92]. Other applica-
tions, such as multimedia clients and servers, and realtime
and fault tolerant programs, can also present demands that
poorly match operating system services. Using SPIN,an
application can extend the operating system’s interfaces and
implementations to provide a better match between the needs
of the application and the performance and functional char-
acteristics of the system.
1.1 Goals and approach
The goal of our research is to build a general purpose op-
erating system that provides extensibility, safety and good
performance. Extensibility is determined by the interfaces
to services and resources that are exported to applications;
it depends on an infrastructure that allows ?ne-grained ac-
cess to system services. Safety determines the exposure of
applications to the actions of others, and requires that access
be controlled at the same granularity at which extensions are
de?ned. Finally, good performance requires low overhead
communication between an extension and the system.
The design of SPIN re?ects our view that an operating
system can be extensible, safe, and fast through the use of
language and runtime services that provide low-cost, ?ne-
grained, protected access to operating system resources.
Speci?cally, the SPIN operating system relies on four tech-
niques implemented at the level of the language or its runtime:
 Co-location. Operating system extensions are dynam-
ically linked into the kernel virtual address space. Co-
location enables communication between system and
extension code to have low cost.
 Enforced modularity. Extensions are written in Modula-
3 [Nelson 91], a modular programming language for
which the compiler enforces interface boundaries be-
tween modules. Extensions, which execute in the ker-
nel’s virtual address space, cannot access memory or
execute privileged instructions unless they have been
given explicit access through an interface. Modularity
Page 2


Extensibility, Safety and Performance in the
SPIN Operating System
Brian N. Bershad Stefan Savage Przemyslaw Pardyak Emin G¨ un Sirer
Marc E. Fiuczynski David Becker Craig Chambers Susan Eggers
Department of Computer Science and Engineering
University of Washington
Seattle, WA 98195
Abstract
This paper describes the motivation, architecture and per-
formance of SPIN, an extensible operating system. SPIN
provides an extension infrastructure, together with a core
set of extensible services, that allow applications to safely
change the operating system’s interface and implementation.
Extensions allow an application to specialize the underly-
ing operating system in order to achieve a particular level
of performance and functionality. SPIN uses language and
link-time mechanisms to inexpensively export ?ne-grained
interfaces to operating system services. Extensions are writ-
ten in a type safe language, and are dynamically linked into
the operating system kernel. This approach offers extensions
rapid access to system services, while protecting the operat-
ing system code executing within the kernel address space.
SPIN and its extensions are written in Modula-3 and run on
DEC Alpha workstations.
1 Introduction
SPIN is an operating system that can be dynamically spe-
cialized to safely meet the performance and functionality re-
quirements of applications. SPIN is motivated by the need to
support applications that present demands poorly matched by
an operating system’s implementation or interface. A poorly
matched implementation prevents an application from work-
ing well, while a poorly matched interface prevents it from
working at all. For example, the implementations of disk
buffering and paging algorithms found in modern operat-
ing systems can be inappropriate for database applications,
resulting in poor performance [Stonebraker 81]. General
This research was sponsored by the Advanced Research Projects
Agency, the National Science Foundation (Grants no. CDA-9123308 and
CCR-9200832) and by an equipment grant from Digital Equipment Corpo-
ration. Bershad was partially supported by a National Science Foundation
Presidential Faculty Fellowship. Chambers was partially sponsored by a
National Science Foundation Presidential Young Investigator Award. Sirer
was supported by an IBM Graduate Student Fellowship. Fiuczynski was
partially supported by a National Science Foundation GEE Fellowship.
purpose network protocol implementations are frequently in-
adequate for supporting the demands of high performance
parallel applications [von Eicken et al. 92]. Other applica-
tions, such as multimedia clients and servers, and realtime
and fault tolerant programs, can also present demands that
poorly match operating system services. Using SPIN,an
application can extend the operating system’s interfaces and
implementations to provide a better match between the needs
of the application and the performance and functional char-
acteristics of the system.
1.1 Goals and approach
The goal of our research is to build a general purpose op-
erating system that provides extensibility, safety and good
performance. Extensibility is determined by the interfaces
to services and resources that are exported to applications;
it depends on an infrastructure that allows ?ne-grained ac-
cess to system services. Safety determines the exposure of
applications to the actions of others, and requires that access
be controlled at the same granularity at which extensions are
de?ned. Finally, good performance requires low overhead
communication between an extension and the system.
The design of SPIN re?ects our view that an operating
system can be extensible, safe, and fast through the use of
language and runtime services that provide low-cost, ?ne-
grained, protected access to operating system resources.
Speci?cally, the SPIN operating system relies on four tech-
niques implemented at the level of the language or its runtime:
 Co-location. Operating system extensions are dynam-
ically linked into the kernel virtual address space. Co-
location enables communication between system and
extension code to have low cost.
 Enforced modularity. Extensions are written in Modula-
3 [Nelson 91], a modular programming language for
which the compiler enforces interface boundaries be-
tween modules. Extensions, which execute in the ker-
nel’s virtual address space, cannot access memory or
execute privileged instructions unless they have been
given explicit access through an interface. Modularity
enforced by the compiler enables modules to be isolated
from one another with low cost.
 Logical protection domains. Extensions exist within
logical protection domains, which are kernel names-
paces that contain code and exported interfaces. Inter-
faces, which are language-level units, represent views
on system resources that are protected by the operat-
ing system. An in-kernel dynamic linker resolves code
in separate logical protection domains at runtime, en-
abling cross-domain communication to occur with the
overhead of a procedure call.
 Dynamic call binding. Extensions execute in response
to system events. An event can describe any potential
action in the system, such as a virtual memory page fault
or the scheduling of a thread. Events are declared within
interfaces, and can be dispatched with the overhead of a
procedure call.
Co-location, enforced modularity, logical protection do-
mains, and dynamic call binding enable interfaces to be de-
?ned and safely accessed with low overhead. However, these
techniques do not guarantee the system’s extensibility. Ulti-
mately, extensibility is achieved through the system service
interfaces themselves, which de?ne the set of resources and
operations that are exported to applications. SPIN provides
a set of interfaces to core system services, such as memory
management and scheduling, that rely on co-location to ef-
?ciently export ?ne-grained operations, enforced modularity
and logical protection domains to manage protection, and
dynamic call binding to de?ne relationships between system
components and extensions at runtime.
1.2 System overview
The SPIN operating system consists of a set of extension
services and core system services that execute within the
kernel’s virtual address space. Extensions can be loaded
into the kernel at any time. Once loaded, they integrate
themselves into the existing infrastructure and provide system
services speci?c to the applications that require them. SPIN
is primarily written in Modula-3, which allows extensions
to directly use system interfaces without requiring runtime
conversion when communicating with other system code.
AlthoughSPIN relies on language features to ensure safety
within the kernel, applications can be written in any language
and execute within their own virtual address space. Only
code that requires low-latency access to system services is
written in the system’s safe extension language. For exam-
ple, we have used SPIN to implement a UNIX operating
system server. The bulk of the server is written in C, and
executes within its own address space (as do applications).
The server consists of a large body of code that implements
the DEC OSF/1 system call interface, and a small number of
SPIN extensions that provide the thread, virtual memory, and
device interfaces required by the server.
We have also used extensions to specialize SPIN to the
needs of individual application programs. For example, we
have built a client/server video system that requires few con-
trol and data transfers as images move from the server’s disk
to the client’s screen. Using SPIN the server de?nes an exten-
sion that implements a direct stream between the disk and the
network. The client viewer application installs an extension
into the kernel that decompresses incoming network video
packets and displays them to the video frame buffer.
1.3 The rest of this paper
The rest of this paper describes the motivation, design, and
performance of SPIN. In the next section we motivate the need
for extensible operating systems and discuss related work. In
Section 3 we describe the system’s architecture in terms of its
protection and extension facilities. In Section 4 we describe
the core services provided by the system. In Section 5 we
discuss the system’s performance and compare it against that
of several other operating systems. In Section 6 we discuss
our experiences writing an operating system in Modula-3.
Finally, in Section 7 we present our conclusions.
2 Motivation
Most operating systems are forced to balance generality and
specialization. A general system runs many programs, but
may run few well. In contrast, a specialized system may
run few programs, but runs them all well. In practice, most
general systems can, with some effort, be specialized to ad-
dress the performance and functional requirements of a par-
ticular application’s needs, such as interprocess communica-
tion, synchronization, thread management, networking, vir-
tual memory and cache management [Draves et al. 91, Ber-
shad et al. 92b, Stodolsky et al. 93, Bershad 93, Yuhara et al.
94, Maeda & Bershad 93, Felten 92, Young et al. 87, Harty
& Cheriton 91, McNamee & Armstrong 90, Anderson et al.
92, Fall & Pasquale 94, Wheeler & Bershad 92, Romer et al.
94, Romer et al. 95, Cao et al. 94]. Unfortunately, exist-
ing system structures are not well-suited for specialization,
often requiring a substantial programming effort to affect
even a small change in system behavior. Moreover, changes
intended to improve the performance of one class of appli-
cations can often degrade that of others. As a result, system
specialization is a costly and error-prone process.
An extensible system is one that can be changed dynam-
ically to meet the needs of an application. The need for
extensibility in operating systems is shown clearly by sys-
tems such as MS-DOS, Windows, or the Macintosh Operat-
ing System. Although these systems were not designed to be
extensible, their weak protection mechanisms have allowed
application programmers to directly modify operating sys-
tem data structures and code [Schulman et al. 92]. While
individual applications have bene?ted from this level of free-
dom, the lack of safe interfaces to either operating system
services or operating system extension services has created
system con?guration “chaos” [Draves 93].
2.1 Related work
Previous efforts to build extensible systems have demon-
strated the three-way tension between extensibility, safety
Page 3


Extensibility, Safety and Performance in the
SPIN Operating System
Brian N. Bershad Stefan Savage Przemyslaw Pardyak Emin G¨ un Sirer
Marc E. Fiuczynski David Becker Craig Chambers Susan Eggers
Department of Computer Science and Engineering
University of Washington
Seattle, WA 98195
Abstract
This paper describes the motivation, architecture and per-
formance of SPIN, an extensible operating system. SPIN
provides an extension infrastructure, together with a core
set of extensible services, that allow applications to safely
change the operating system’s interface and implementation.
Extensions allow an application to specialize the underly-
ing operating system in order to achieve a particular level
of performance and functionality. SPIN uses language and
link-time mechanisms to inexpensively export ?ne-grained
interfaces to operating system services. Extensions are writ-
ten in a type safe language, and are dynamically linked into
the operating system kernel. This approach offers extensions
rapid access to system services, while protecting the operat-
ing system code executing within the kernel address space.
SPIN and its extensions are written in Modula-3 and run on
DEC Alpha workstations.
1 Introduction
SPIN is an operating system that can be dynamically spe-
cialized to safely meet the performance and functionality re-
quirements of applications. SPIN is motivated by the need to
support applications that present demands poorly matched by
an operating system’s implementation or interface. A poorly
matched implementation prevents an application from work-
ing well, while a poorly matched interface prevents it from
working at all. For example, the implementations of disk
buffering and paging algorithms found in modern operat-
ing systems can be inappropriate for database applications,
resulting in poor performance [Stonebraker 81]. General
This research was sponsored by the Advanced Research Projects
Agency, the National Science Foundation (Grants no. CDA-9123308 and
CCR-9200832) and by an equipment grant from Digital Equipment Corpo-
ration. Bershad was partially supported by a National Science Foundation
Presidential Faculty Fellowship. Chambers was partially sponsored by a
National Science Foundation Presidential Young Investigator Award. Sirer
was supported by an IBM Graduate Student Fellowship. Fiuczynski was
partially supported by a National Science Foundation GEE Fellowship.
purpose network protocol implementations are frequently in-
adequate for supporting the demands of high performance
parallel applications [von Eicken et al. 92]. Other applica-
tions, such as multimedia clients and servers, and realtime
and fault tolerant programs, can also present demands that
poorly match operating system services. Using SPIN,an
application can extend the operating system’s interfaces and
implementations to provide a better match between the needs
of the application and the performance and functional char-
acteristics of the system.
1.1 Goals and approach
The goal of our research is to build a general purpose op-
erating system that provides extensibility, safety and good
performance. Extensibility is determined by the interfaces
to services and resources that are exported to applications;
it depends on an infrastructure that allows ?ne-grained ac-
cess to system services. Safety determines the exposure of
applications to the actions of others, and requires that access
be controlled at the same granularity at which extensions are
de?ned. Finally, good performance requires low overhead
communication between an extension and the system.
The design of SPIN re?ects our view that an operating
system can be extensible, safe, and fast through the use of
language and runtime services that provide low-cost, ?ne-
grained, protected access to operating system resources.
Speci?cally, the SPIN operating system relies on four tech-
niques implemented at the level of the language or its runtime:
 Co-location. Operating system extensions are dynam-
ically linked into the kernel virtual address space. Co-
location enables communication between system and
extension code to have low cost.
 Enforced modularity. Extensions are written in Modula-
3 [Nelson 91], a modular programming language for
which the compiler enforces interface boundaries be-
tween modules. Extensions, which execute in the ker-
nel’s virtual address space, cannot access memory or
execute privileged instructions unless they have been
given explicit access through an interface. Modularity
enforced by the compiler enables modules to be isolated
from one another with low cost.
 Logical protection domains. Extensions exist within
logical protection domains, which are kernel names-
paces that contain code and exported interfaces. Inter-
faces, which are language-level units, represent views
on system resources that are protected by the operat-
ing system. An in-kernel dynamic linker resolves code
in separate logical protection domains at runtime, en-
abling cross-domain communication to occur with the
overhead of a procedure call.
 Dynamic call binding. Extensions execute in response
to system events. An event can describe any potential
action in the system, such as a virtual memory page fault
or the scheduling of a thread. Events are declared within
interfaces, and can be dispatched with the overhead of a
procedure call.
Co-location, enforced modularity, logical protection do-
mains, and dynamic call binding enable interfaces to be de-
?ned and safely accessed with low overhead. However, these
techniques do not guarantee the system’s extensibility. Ulti-
mately, extensibility is achieved through the system service
interfaces themselves, which de?ne the set of resources and
operations that are exported to applications. SPIN provides
a set of interfaces to core system services, such as memory
management and scheduling, that rely on co-location to ef-
?ciently export ?ne-grained operations, enforced modularity
and logical protection domains to manage protection, and
dynamic call binding to de?ne relationships between system
components and extensions at runtime.
1.2 System overview
The SPIN operating system consists of a set of extension
services and core system services that execute within the
kernel’s virtual address space. Extensions can be loaded
into the kernel at any time. Once loaded, they integrate
themselves into the existing infrastructure and provide system
services speci?c to the applications that require them. SPIN
is primarily written in Modula-3, which allows extensions
to directly use system interfaces without requiring runtime
conversion when communicating with other system code.
AlthoughSPIN relies on language features to ensure safety
within the kernel, applications can be written in any language
and execute within their own virtual address space. Only
code that requires low-latency access to system services is
written in the system’s safe extension language. For exam-
ple, we have used SPIN to implement a UNIX operating
system server. The bulk of the server is written in C, and
executes within its own address space (as do applications).
The server consists of a large body of code that implements
the DEC OSF/1 system call interface, and a small number of
SPIN extensions that provide the thread, virtual memory, and
device interfaces required by the server.
We have also used extensions to specialize SPIN to the
needs of individual application programs. For example, we
have built a client/server video system that requires few con-
trol and data transfers as images move from the server’s disk
to the client’s screen. Using SPIN the server de?nes an exten-
sion that implements a direct stream between the disk and the
network. The client viewer application installs an extension
into the kernel that decompresses incoming network video
packets and displays them to the video frame buffer.
1.3 The rest of this paper
The rest of this paper describes the motivation, design, and
performance of SPIN. In the next section we motivate the need
for extensible operating systems and discuss related work. In
Section 3 we describe the system’s architecture in terms of its
protection and extension facilities. In Section 4 we describe
the core services provided by the system. In Section 5 we
discuss the system’s performance and compare it against that
of several other operating systems. In Section 6 we discuss
our experiences writing an operating system in Modula-3.
Finally, in Section 7 we present our conclusions.
2 Motivation
Most operating systems are forced to balance generality and
specialization. A general system runs many programs, but
may run few well. In contrast, a specialized system may
run few programs, but runs them all well. In practice, most
general systems can, with some effort, be specialized to ad-
dress the performance and functional requirements of a par-
ticular application’s needs, such as interprocess communica-
tion, synchronization, thread management, networking, vir-
tual memory and cache management [Draves et al. 91, Ber-
shad et al. 92b, Stodolsky et al. 93, Bershad 93, Yuhara et al.
94, Maeda & Bershad 93, Felten 92, Young et al. 87, Harty
& Cheriton 91, McNamee & Armstrong 90, Anderson et al.
92, Fall & Pasquale 94, Wheeler & Bershad 92, Romer et al.
94, Romer et al. 95, Cao et al. 94]. Unfortunately, exist-
ing system structures are not well-suited for specialization,
often requiring a substantial programming effort to affect
even a small change in system behavior. Moreover, changes
intended to improve the performance of one class of appli-
cations can often degrade that of others. As a result, system
specialization is a costly and error-prone process.
An extensible system is one that can be changed dynam-
ically to meet the needs of an application. The need for
extensibility in operating systems is shown clearly by sys-
tems such as MS-DOS, Windows, or the Macintosh Operat-
ing System. Although these systems were not designed to be
extensible, their weak protection mechanisms have allowed
application programmers to directly modify operating sys-
tem data structures and code [Schulman et al. 92]. While
individual applications have bene?ted from this level of free-
dom, the lack of safe interfaces to either operating system
services or operating system extension services has created
system con?guration “chaos” [Draves 93].
2.1 Related work
Previous efforts to build extensible systems have demon-
strated the three-way tension between extensibility, safety
and performance. For example, Hydra [Wulf et al. 81] de-
?ned an infrastructure that allowed applications to manage
resources through multi-level policies. The kernel de?ned the
mechanism for allocating resources between processes, and
the processes themselves implemented the policies for man-
aging those resources. Hydra’s architecture, although highly
in?uential, had high overhead due to its weighty capability-
based protection mechanism. Consequently, the system was
designed with “large objects” as the basic building blocks,
requiring a large programming effort to affect even a small
extension.
Researchers have recently investigated the use of micro-
kernels as a vehicle for building extensible systems [Black
et al. 92, Mullender et al. 90, Cheriton & Zwaenepoel
83, Cheriton & Duda 94, Thacker et al. 88]. A microker-
nel typically exports a small number of abstractions that in-
clude threads, address spaces, and communication channels.
These abstractions can be combined to support more conven-
tional operating system services implemented as user-level
programs. Application-speci?c extensions in a microkernel
occur at or above the level of the kernel’s interfaces. Unfor-
tunately, applications often require substantial changes to a
microkernel’s implementation to compensate for limitations
in interfaces [Lee et al. 94, Davis et al. 93, Waldspurger &
Weihl 94].
Although a microkernel’s communication facilities pro-
vide the infrastructure for extending nearly any kernel ser-
vice [Barrera 91, Abrossimov et al. 89, Forin et al. 91], few
have been so extended. We believe this is because of high
communication overhead [Bershad et al. 90, Draves et al.
91, Chen & Bershad 93], which limits extensions mostly
to coarse-grained services [Golub et al. 90, Stevenson &
Julin 95, Bricker et al. 91]. Otherwise, protected interac-
tion between system components, which occurs frequently
in a system with ?ne-grained extensions, can be a limiting
performance factor.
Although the performance of cross-domain communica-
tion has improved substantially in recent years [Hamilton
& Kougiouris 93, Hildebrand 92, Engler et al. 95], it still
does not approach that of a procedure call, encouraging the
construction of monolithic, non-extensible systems. For ex-
ample, the L3 microkernel, even with its aggressive design,
has a protected procedure call implementation with over-
head of nearly 100 procedure call times [Liedtke 92, Liedtke
93, Int 90]. As a point of comparison, the Intel 432 [Int 81],
which provided hardware support for protected cross-domain
transfer, had a cross-domain communication overhead on the
order of about 10 procedure call times [Colwell 85], and was
generally considered unacceptable.
Some systems rely on “little languages” to safely extend
the operating system interface through the use of interpreted
code that runs in the kernel [Lee et al. 94, Mogul et al.
87, Yuhara et al. 94]. These systems suffer from three
problems. First, the languages, being little, make the expres-
sion of arbitrary control and data structures cumbersome, and
therefore limit the range of possible extensions. Second, the
interface between the language’s programming environment
and the rest of the system is generally narrow, making sys-
tem integration dif?cult. Finally, interpretation overhead can
limit performance.
Many systems provide interfaces that enable arbitrary code
to be installedinto the kernel at runtime [Heidemann & Popek
94, Rozier et al. 88]. In these systems the right to de?ne ex-
tensions is restricted because any extension can bring down
the entire system; application-speci?c extensibility is not pos-
sible.
Several projects [Lucco 94, Engler et al. 95, Small &
Seltzer 94] are exploring the use of software fault isola-
tion [Wahbe et al. 93] to safely link application code, writ-
ten in any language, into the kernel’s virtual address space.
Software fault isolation relies on a binary rewriting tool that
inserts explicit checks on memory references and branch in-
structions. These checks allow the system to de?ne protected
memory segments without relying on virtual memory hard-
ware. Software fault isolationshows promise as a co-location
mechanism for relatively isolated code and data segments. It
is unclear, though, if the mechanism is appropriate for a sys-
tem with ?ne-grained sharing, where extensions may access
a large number of segments. In addition, software fault iso-
lation is only a protection mechanism and does not de?ne an
extension model or the service interfaces that determine the
degree to which a system can be extended.
Aegis [Engler et al. 95] is an operating system that re-
lies on ef?cient trap redirection to export hardware services,
such as exception handling and TLB management, directly
to applications. The system itself de?nes no abstractions
beyond those minimally provided by the hardware [Engler
& Kaashoek 95]. Instead, conventional operating system
services, such as virtual memory and scheduling, are im-
plemented as libraries executing in an application’s address
space. System service code executing in a library can be
changed by the application according to its needs. SPIN
shares many of the same goals as Aegis although its ap-
proach is quite different. SPIN uses language facilities to
protect the kernel from extensions and implements protected
communication using procedure call. Using this infrastruc-
ture, SPIN provides an extension model and a core set of
extensible services. In contrast, Aegis relies on hardware
protected system calls to isolate extensions from the kernel
and leaves unspeci?ed the manner by which those extensions
are de?ned or applied.
Several systems [Cooper et al. 91, Redell et al. 80,
Mossenbock 94, Organick 73] like SPIN, have relied on lan-
guage features to extend operating system services. Pilot,
for instance, was a single-address space system that ran pro-
grams written in Mesa [Geschke et al. 77], an ancestor of
Modula-3. In general, systems such as Pilot have depended
on the language for all protection in the system, not just for
the protection of the operating system and its extensions. In
contrast, SPIN’s reliance on language services applies only to
extension code within the kernel. Virtual address spaces are
used to otherwise isolate the operating system and programs
from one another.
3The SPIN Architecture
The SPIN architecture provides a software infrastructure for
safely combining system and application code. The pro-
Page 4


Extensibility, Safety and Performance in the
SPIN Operating System
Brian N. Bershad Stefan Savage Przemyslaw Pardyak Emin G¨ un Sirer
Marc E. Fiuczynski David Becker Craig Chambers Susan Eggers
Department of Computer Science and Engineering
University of Washington
Seattle, WA 98195
Abstract
This paper describes the motivation, architecture and per-
formance of SPIN, an extensible operating system. SPIN
provides an extension infrastructure, together with a core
set of extensible services, that allow applications to safely
change the operating system’s interface and implementation.
Extensions allow an application to specialize the underly-
ing operating system in order to achieve a particular level
of performance and functionality. SPIN uses language and
link-time mechanisms to inexpensively export ?ne-grained
interfaces to operating system services. Extensions are writ-
ten in a type safe language, and are dynamically linked into
the operating system kernel. This approach offers extensions
rapid access to system services, while protecting the operat-
ing system code executing within the kernel address space.
SPIN and its extensions are written in Modula-3 and run on
DEC Alpha workstations.
1 Introduction
SPIN is an operating system that can be dynamically spe-
cialized to safely meet the performance and functionality re-
quirements of applications. SPIN is motivated by the need to
support applications that present demands poorly matched by
an operating system’s implementation or interface. A poorly
matched implementation prevents an application from work-
ing well, while a poorly matched interface prevents it from
working at all. For example, the implementations of disk
buffering and paging algorithms found in modern operat-
ing systems can be inappropriate for database applications,
resulting in poor performance [Stonebraker 81]. General
This research was sponsored by the Advanced Research Projects
Agency, the National Science Foundation (Grants no. CDA-9123308 and
CCR-9200832) and by an equipment grant from Digital Equipment Corpo-
ration. Bershad was partially supported by a National Science Foundation
Presidential Faculty Fellowship. Chambers was partially sponsored by a
National Science Foundation Presidential Young Investigator Award. Sirer
was supported by an IBM Graduate Student Fellowship. Fiuczynski was
partially supported by a National Science Foundation GEE Fellowship.
purpose network protocol implementations are frequently in-
adequate for supporting the demands of high performance
parallel applications [von Eicken et al. 92]. Other applica-
tions, such as multimedia clients and servers, and realtime
and fault tolerant programs, can also present demands that
poorly match operating system services. Using SPIN,an
application can extend the operating system’s interfaces and
implementations to provide a better match between the needs
of the application and the performance and functional char-
acteristics of the system.
1.1 Goals and approach
The goal of our research is to build a general purpose op-
erating system that provides extensibility, safety and good
performance. Extensibility is determined by the interfaces
to services and resources that are exported to applications;
it depends on an infrastructure that allows ?ne-grained ac-
cess to system services. Safety determines the exposure of
applications to the actions of others, and requires that access
be controlled at the same granularity at which extensions are
de?ned. Finally, good performance requires low overhead
communication between an extension and the system.
The design of SPIN re?ects our view that an operating
system can be extensible, safe, and fast through the use of
language and runtime services that provide low-cost, ?ne-
grained, protected access to operating system resources.
Speci?cally, the SPIN operating system relies on four tech-
niques implemented at the level of the language or its runtime:
 Co-location. Operating system extensions are dynam-
ically linked into the kernel virtual address space. Co-
location enables communication between system and
extension code to have low cost.
 Enforced modularity. Extensions are written in Modula-
3 [Nelson 91], a modular programming language for
which the compiler enforces interface boundaries be-
tween modules. Extensions, which execute in the ker-
nel’s virtual address space, cannot access memory or
execute privileged instructions unless they have been
given explicit access through an interface. Modularity
enforced by the compiler enables modules to be isolated
from one another with low cost.
 Logical protection domains. Extensions exist within
logical protection domains, which are kernel names-
paces that contain code and exported interfaces. Inter-
faces, which are language-level units, represent views
on system resources that are protected by the operat-
ing system. An in-kernel dynamic linker resolves code
in separate logical protection domains at runtime, en-
abling cross-domain communication to occur with the
overhead of a procedure call.
 Dynamic call binding. Extensions execute in response
to system events. An event can describe any potential
action in the system, such as a virtual memory page fault
or the scheduling of a thread. Events are declared within
interfaces, and can be dispatched with the overhead of a
procedure call.
Co-location, enforced modularity, logical protection do-
mains, and dynamic call binding enable interfaces to be de-
?ned and safely accessed with low overhead. However, these
techniques do not guarantee the system’s extensibility. Ulti-
mately, extensibility is achieved through the system service
interfaces themselves, which de?ne the set of resources and
operations that are exported to applications. SPIN provides
a set of interfaces to core system services, such as memory
management and scheduling, that rely on co-location to ef-
?ciently export ?ne-grained operations, enforced modularity
and logical protection domains to manage protection, and
dynamic call binding to de?ne relationships between system
components and extensions at runtime.
1.2 System overview
The SPIN operating system consists of a set of extension
services and core system services that execute within the
kernel’s virtual address space. Extensions can be loaded
into the kernel at any time. Once loaded, they integrate
themselves into the existing infrastructure and provide system
services speci?c to the applications that require them. SPIN
is primarily written in Modula-3, which allows extensions
to directly use system interfaces without requiring runtime
conversion when communicating with other system code.
AlthoughSPIN relies on language features to ensure safety
within the kernel, applications can be written in any language
and execute within their own virtual address space. Only
code that requires low-latency access to system services is
written in the system’s safe extension language. For exam-
ple, we have used SPIN to implement a UNIX operating
system server. The bulk of the server is written in C, and
executes within its own address space (as do applications).
The server consists of a large body of code that implements
the DEC OSF/1 system call interface, and a small number of
SPIN extensions that provide the thread, virtual memory, and
device interfaces required by the server.
We have also used extensions to specialize SPIN to the
needs of individual application programs. For example, we
have built a client/server video system that requires few con-
trol and data transfers as images move from the server’s disk
to the client’s screen. Using SPIN the server de?nes an exten-
sion that implements a direct stream between the disk and the
network. The client viewer application installs an extension
into the kernel that decompresses incoming network video
packets and displays them to the video frame buffer.
1.3 The rest of this paper
The rest of this paper describes the motivation, design, and
performance of SPIN. In the next section we motivate the need
for extensible operating systems and discuss related work. In
Section 3 we describe the system’s architecture in terms of its
protection and extension facilities. In Section 4 we describe
the core services provided by the system. In Section 5 we
discuss the system’s performance and compare it against that
of several other operating systems. In Section 6 we discuss
our experiences writing an operating system in Modula-3.
Finally, in Section 7 we present our conclusions.
2 Motivation
Most operating systems are forced to balance generality and
specialization. A general system runs many programs, but
may run few well. In contrast, a specialized system may
run few programs, but runs them all well. In practice, most
general systems can, with some effort, be specialized to ad-
dress the performance and functional requirements of a par-
ticular application’s needs, such as interprocess communica-
tion, synchronization, thread management, networking, vir-
tual memory and cache management [Draves et al. 91, Ber-
shad et al. 92b, Stodolsky et al. 93, Bershad 93, Yuhara et al.
94, Maeda & Bershad 93, Felten 92, Young et al. 87, Harty
& Cheriton 91, McNamee & Armstrong 90, Anderson et al.
92, Fall & Pasquale 94, Wheeler & Bershad 92, Romer et al.
94, Romer et al. 95, Cao et al. 94]. Unfortunately, exist-
ing system structures are not well-suited for specialization,
often requiring a substantial programming effort to affect
even a small change in system behavior. Moreover, changes
intended to improve the performance of one class of appli-
cations can often degrade that of others. As a result, system
specialization is a costly and error-prone process.
An extensible system is one that can be changed dynam-
ically to meet the needs of an application. The need for
extensibility in operating systems is shown clearly by sys-
tems such as MS-DOS, Windows, or the Macintosh Operat-
ing System. Although these systems were not designed to be
extensible, their weak protection mechanisms have allowed
application programmers to directly modify operating sys-
tem data structures and code [Schulman et al. 92]. While
individual applications have bene?ted from this level of free-
dom, the lack of safe interfaces to either operating system
services or operating system extension services has created
system con?guration “chaos” [Draves 93].
2.1 Related work
Previous efforts to build extensible systems have demon-
strated the three-way tension between extensibility, safety
and performance. For example, Hydra [Wulf et al. 81] de-
?ned an infrastructure that allowed applications to manage
resources through multi-level policies. The kernel de?ned the
mechanism for allocating resources between processes, and
the processes themselves implemented the policies for man-
aging those resources. Hydra’s architecture, although highly
in?uential, had high overhead due to its weighty capability-
based protection mechanism. Consequently, the system was
designed with “large objects” as the basic building blocks,
requiring a large programming effort to affect even a small
extension.
Researchers have recently investigated the use of micro-
kernels as a vehicle for building extensible systems [Black
et al. 92, Mullender et al. 90, Cheriton & Zwaenepoel
83, Cheriton & Duda 94, Thacker et al. 88]. A microker-
nel typically exports a small number of abstractions that in-
clude threads, address spaces, and communication channels.
These abstractions can be combined to support more conven-
tional operating system services implemented as user-level
programs. Application-speci?c extensions in a microkernel
occur at or above the level of the kernel’s interfaces. Unfor-
tunately, applications often require substantial changes to a
microkernel’s implementation to compensate for limitations
in interfaces [Lee et al. 94, Davis et al. 93, Waldspurger &
Weihl 94].
Although a microkernel’s communication facilities pro-
vide the infrastructure for extending nearly any kernel ser-
vice [Barrera 91, Abrossimov et al. 89, Forin et al. 91], few
have been so extended. We believe this is because of high
communication overhead [Bershad et al. 90, Draves et al.
91, Chen & Bershad 93], which limits extensions mostly
to coarse-grained services [Golub et al. 90, Stevenson &
Julin 95, Bricker et al. 91]. Otherwise, protected interac-
tion between system components, which occurs frequently
in a system with ?ne-grained extensions, can be a limiting
performance factor.
Although the performance of cross-domain communica-
tion has improved substantially in recent years [Hamilton
& Kougiouris 93, Hildebrand 92, Engler et al. 95], it still
does not approach that of a procedure call, encouraging the
construction of monolithic, non-extensible systems. For ex-
ample, the L3 microkernel, even with its aggressive design,
has a protected procedure call implementation with over-
head of nearly 100 procedure call times [Liedtke 92, Liedtke
93, Int 90]. As a point of comparison, the Intel 432 [Int 81],
which provided hardware support for protected cross-domain
transfer, had a cross-domain communication overhead on the
order of about 10 procedure call times [Colwell 85], and was
generally considered unacceptable.
Some systems rely on “little languages” to safely extend
the operating system interface through the use of interpreted
code that runs in the kernel [Lee et al. 94, Mogul et al.
87, Yuhara et al. 94]. These systems suffer from three
problems. First, the languages, being little, make the expres-
sion of arbitrary control and data structures cumbersome, and
therefore limit the range of possible extensions. Second, the
interface between the language’s programming environment
and the rest of the system is generally narrow, making sys-
tem integration dif?cult. Finally, interpretation overhead can
limit performance.
Many systems provide interfaces that enable arbitrary code
to be installedinto the kernel at runtime [Heidemann & Popek
94, Rozier et al. 88]. In these systems the right to de?ne ex-
tensions is restricted because any extension can bring down
the entire system; application-speci?c extensibility is not pos-
sible.
Several projects [Lucco 94, Engler et al. 95, Small &
Seltzer 94] are exploring the use of software fault isola-
tion [Wahbe et al. 93] to safely link application code, writ-
ten in any language, into the kernel’s virtual address space.
Software fault isolation relies on a binary rewriting tool that
inserts explicit checks on memory references and branch in-
structions. These checks allow the system to de?ne protected
memory segments without relying on virtual memory hard-
ware. Software fault isolationshows promise as a co-location
mechanism for relatively isolated code and data segments. It
is unclear, though, if the mechanism is appropriate for a sys-
tem with ?ne-grained sharing, where extensions may access
a large number of segments. In addition, software fault iso-
lation is only a protection mechanism and does not de?ne an
extension model or the service interfaces that determine the
degree to which a system can be extended.
Aegis [Engler et al. 95] is an operating system that re-
lies on ef?cient trap redirection to export hardware services,
such as exception handling and TLB management, directly
to applications. The system itself de?nes no abstractions
beyond those minimally provided by the hardware [Engler
& Kaashoek 95]. Instead, conventional operating system
services, such as virtual memory and scheduling, are im-
plemented as libraries executing in an application’s address
space. System service code executing in a library can be
changed by the application according to its needs. SPIN
shares many of the same goals as Aegis although its ap-
proach is quite different. SPIN uses language facilities to
protect the kernel from extensions and implements protected
communication using procedure call. Using this infrastruc-
ture, SPIN provides an extension model and a core set of
extensible services. In contrast, Aegis relies on hardware
protected system calls to isolate extensions from the kernel
and leaves unspeci?ed the manner by which those extensions
are de?ned or applied.
Several systems [Cooper et al. 91, Redell et al. 80,
Mossenbock 94, Organick 73] like SPIN, have relied on lan-
guage features to extend operating system services. Pilot,
for instance, was a single-address space system that ran pro-
grams written in Mesa [Geschke et al. 77], an ancestor of
Modula-3. In general, systems such as Pilot have depended
on the language for all protection in the system, not just for
the protection of the operating system and its extensions. In
contrast, SPIN’s reliance on language services applies only to
extension code within the kernel. Virtual address spaces are
used to otherwise isolate the operating system and programs
from one another.
3The SPIN Architecture
The SPIN architecture provides a software infrastructure for
safely combining system and application code. The pro-
tection model supports ef?cient, ?ne-grained access control
of resources, while the extension model enables extensions
to be de?ned at the granularity of a procedure call. The
system’s architecture is biased towards mechanisms that can
be implemented with low-cost on conventional processors.
Consequently, SPIN makes few demands of the hardware,
and instead relies on language-level services, such as static
typechecking and dynamic linking.
Relevant properties of Modula-3
SPIN and its extensions are written in Modula-3, a general
purpose programming language designed in the early 1990’s.
The key features of the language include support for inter-
faces, type safety, automatic storage management, objects,
generic interfaces, threads, and exceptions. We rely on the
language’s support for objects, generic interfaces, threads,
and exceptions for aesthetic reasons only; we ?nd that these
features simplify the task of constructing a large system.
The design of SPIN depends only on the language’s safety
and encapsulation mechanisms; speci?cally interfaces, type
safety, and automatic storage management. An interface de-
clares the visible parts of an implementation module,which
de?nes the items listed in the interface. All other de?nitions
within the implementation module are hidden. The com-
piler enforces this restriction at compile-time. Type safety
prevents code from accessing memory arbitrarily. A pointer
may only refer to objects of its referent’s type, and array
indexing operations must be checked for bounds violation.
The ?rst restriction is enforced at compile-time, and the sec-
ond is enforced through a combination of compile-time and
run-time checks. Automatic storage management prevents
memory used by a live pointer’s referent from being returned
to the heap and reused for an object of a different type.
3.1 The protection model
A protection model controls the set of operations that can
be applied to resources. For example, a protection model
based on address spaces ensures that a process can only ac-
cess memory within a particular range of virtual addresses.
Address spaces, though, are frequently inadequate for the
?ne-grained protection and management of resources, being
expensive to create and slow to access [Lazowska et al. 81].
Capabilities
All kernel resources in SPIN are referenced by capabilities.
A capability is an unforgeable reference to a resource which
can be a system object, an interface, or a collection of in-
terfaces. An example of each of these is a physical page,
a physical page allocation interface, and the entire virtual
memory system. Individual resources are protected to en-
sure that extensions reference only the resources to which
they have been given access. Interfaces and collections of
interfaces are protected to allow different extensions to have
different views on the set of available services.
Unlike other operating systems based on capabilities,
which rely on special-purpose hardware [Carter et al. 94],
virtual memory mechanisms [Wulf et al. 81], probabilistic
protection [Engler et al. 94], or protected message chan-
nels [Black et al. 92], SPIN implements capabilities directly
using pointers, which are supported by the language. A
pointer is a reference to a block of memory whose type is
declared within an interface. Figure 1 demonstrates the def-
inition and use of interfaces and capabilities (pointers) in
SPIN.
INTERFACE Console; (* An interface. *)
TYPE T <: REFANY; (* Read as "Console.T is opaque." *)
CONST InterfaceName = "ConsoleService";
(* A global name *)
PROCEDURE Open():T;
(* Open returns a capability for the console. *)
PROCEDURE Write(t: T; msg: TEXT);
PROCEDURE Read(t: VAR msg: TEXT);
PROCEDURE Close(t: T);
END Console;
MODULE Console; (* An implementation module. *)
(* The implementation of Console.T *)
TYPE Buf = ARRAY [0..31] OF CHAR;
REVEAL T = BRANDED REF RECORD (* T is a pointer *)
inputQ: Buf; (* to a record *)
outputQ: Buf;
(* device speci?c info *)
END;
(* Implementations of interface functions *)
(* have direct access to the revealed type. *)
PROCEDURE Open():T = ...
END Console;
MODULE Gatekeeper; (* A client *)
IMPORT Console;
VAR c: Console.T; (* A capability for *)
(* the console device *)
PROCEDURE IntruderAlert() =
BEGIN
c := Console.Open();
Console.Write(c, "Intruder Alert");
Console.Close(c);
END IntruderAlert;
BEGIN
END Gatekeeper;
Figure 1: The Gatekeeper module interacts with SPIN’s Console service
through the Console interface. Although Gatekeeper.IntruderAlert manip-
ulates objects of type Console.T, it is unable to access the ?elds within the
object, even though it executes within the same virtual address space as the
Console module.
The compiler, at compile-time, prevents a pointer from
being forged or dereferenced in a way inconsistent with its
type. There is no run-time overhead for using a pointer,
passing it across an interface, or dereferencing it, other than
the overhead of going to memory to access the pointer or
its referent. A pointer can be passed from the kernel to a
user-level application, which cannot be assumed to be type
safe, as an externalized reference. An externalized reference
is an index into a per-application table that contains type safe
references to in-kernel data structures. The references can
Page 5


Extensibility, Safety and Performance in the
SPIN Operating System
Brian N. Bershad Stefan Savage Przemyslaw Pardyak Emin G¨ un Sirer
Marc E. Fiuczynski David Becker Craig Chambers Susan Eggers
Department of Computer Science and Engineering
University of Washington
Seattle, WA 98195
Abstract
This paper describes the motivation, architecture and per-
formance of SPIN, an extensible operating system. SPIN
provides an extension infrastructure, together with a core
set of extensible services, that allow applications to safely
change the operating system’s interface and implementation.
Extensions allow an application to specialize the underly-
ing operating system in order to achieve a particular level
of performance and functionality. SPIN uses language and
link-time mechanisms to inexpensively export ?ne-grained
interfaces to operating system services. Extensions are writ-
ten in a type safe language, and are dynamically linked into
the operating system kernel. This approach offers extensions
rapid access to system services, while protecting the operat-
ing system code executing within the kernel address space.
SPIN and its extensions are written in Modula-3 and run on
DEC Alpha workstations.
1 Introduction
SPIN is an operating system that can be dynamically spe-
cialized to safely meet the performance and functionality re-
quirements of applications. SPIN is motivated by the need to
support applications that present demands poorly matched by
an operating system’s implementation or interface. A poorly
matched implementation prevents an application from work-
ing well, while a poorly matched interface prevents it from
working at all. For example, the implementations of disk
buffering and paging algorithms found in modern operat-
ing systems can be inappropriate for database applications,
resulting in poor performance [Stonebraker 81]. General
This research was sponsored by the Advanced Research Projects
Agency, the National Science Foundation (Grants no. CDA-9123308 and
CCR-9200832) and by an equipment grant from Digital Equipment Corpo-
ration. Bershad was partially supported by a National Science Foundation
Presidential Faculty Fellowship. Chambers was partially sponsored by a
National Science Foundation Presidential Young Investigator Award. Sirer
was supported by an IBM Graduate Student Fellowship. Fiuczynski was
partially supported by a National Science Foundation GEE Fellowship.
purpose network protocol implementations are frequently in-
adequate for supporting the demands of high performance
parallel applications [von Eicken et al. 92]. Other applica-
tions, such as multimedia clients and servers, and realtime
and fault tolerant programs, can also present demands that
poorly match operating system services. Using SPIN,an
application can extend the operating system’s interfaces and
implementations to provide a better match between the needs
of the application and the performance and functional char-
acteristics of the system.
1.1 Goals and approach
The goal of our research is to build a general purpose op-
erating system that provides extensibility, safety and good
performance. Extensibility is determined by the interfaces
to services and resources that are exported to applications;
it depends on an infrastructure that allows ?ne-grained ac-
cess to system services. Safety determines the exposure of
applications to the actions of others, and requires that access
be controlled at the same granularity at which extensions are
de?ned. Finally, good performance requires low overhead
communication between an extension and the system.
The design of SPIN re?ects our view that an operating
system can be extensible, safe, and fast through the use of
language and runtime services that provide low-cost, ?ne-
grained, protected access to operating system resources.
Speci?cally, the SPIN operating system relies on four tech-
niques implemented at the level of the language or its runtime:
 Co-location. Operating system extensions are dynam-
ically linked into the kernel virtual address space. Co-
location enables communication between system and
extension code to have low cost.
 Enforced modularity. Extensions are written in Modula-
3 [Nelson 91], a modular programming language for
which the compiler enforces interface boundaries be-
tween modules. Extensions, which execute in the ker-
nel’s virtual address space, cannot access memory or
execute privileged instructions unless they have been
given explicit access through an interface. Modularity
enforced by the compiler enables modules to be isolated
from one another with low cost.
 Logical protection domains. Extensions exist within
logical protection domains, which are kernel names-
paces that contain code and exported interfaces. Inter-
faces, which are language-level units, represent views
on system resources that are protected by the operat-
ing system. An in-kernel dynamic linker resolves code
in separate logical protection domains at runtime, en-
abling cross-domain communication to occur with the
overhead of a procedure call.
 Dynamic call binding. Extensions execute in response
to system events. An event can describe any potential
action in the system, such as a virtual memory page fault
or the scheduling of a thread. Events are declared within
interfaces, and can be dispatched with the overhead of a
procedure call.
Co-location, enforced modularity, logical protection do-
mains, and dynamic call binding enable interfaces to be de-
?ned and safely accessed with low overhead. However, these
techniques do not guarantee the system’s extensibility. Ulti-
mately, extensibility is achieved through the system service
interfaces themselves, which de?ne the set of resources and
operations that are exported to applications. SPIN provides
a set of interfaces to core system services, such as memory
management and scheduling, that rely on co-location to ef-
?ciently export ?ne-grained operations, enforced modularity
and logical protection domains to manage protection, and
dynamic call binding to de?ne relationships between system
components and extensions at runtime.
1.2 System overview
The SPIN operating system consists of a set of extension
services and core system services that execute within the
kernel’s virtual address space. Extensions can be loaded
into the kernel at any time. Once loaded, they integrate
themselves into the existing infrastructure and provide system
services speci?c to the applications that require them. SPIN
is primarily written in Modula-3, which allows extensions
to directly use system interfaces without requiring runtime
conversion when communicating with other system code.
AlthoughSPIN relies on language features to ensure safety
within the kernel, applications can be written in any language
and execute within their own virtual address space. Only
code that requires low-latency access to system services is
written in the system’s safe extension language. For exam-
ple, we have used SPIN to implement a UNIX operating
system server. The bulk of the server is written in C, and
executes within its own address space (as do applications).
The server consists of a large body of code that implements
the DEC OSF/1 system call interface, and a small number of
SPIN extensions that provide the thread, virtual memory, and
device interfaces required by the server.
We have also used extensions to specialize SPIN to the
needs of individual application programs. For example, we
have built a client/server video system that requires few con-
trol and data transfers as images move from the server’s disk
to the client’s screen. Using SPIN the server de?nes an exten-
sion that implements a direct stream between the disk and the
network. The client viewer application installs an extension
into the kernel that decompresses incoming network video
packets and displays them to the video frame buffer.
1.3 The rest of this paper
The rest of this paper describes the motivation, design, and
performance of SPIN. In the next section we motivate the need
for extensible operating systems and discuss related work. In
Section 3 we describe the system’s architecture in terms of its
protection and extension facilities. In Section 4 we describe
the core services provided by the system. In Section 5 we
discuss the system’s performance and compare it against that
of several other operating systems. In Section 6 we discuss
our experiences writing an operating system in Modula-3.
Finally, in Section 7 we present our conclusions.
2 Motivation
Most operating systems are forced to balance generality and
specialization. A general system runs many programs, but
may run few well. In contrast, a specialized system may
run few programs, but runs them all well. In practice, most
general systems can, with some effort, be specialized to ad-
dress the performance and functional requirements of a par-
ticular application’s needs, such as interprocess communica-
tion, synchronization, thread management, networking, vir-
tual memory and cache management [Draves et al. 91, Ber-
shad et al. 92b, Stodolsky et al. 93, Bershad 93, Yuhara et al.
94, Maeda & Bershad 93, Felten 92, Young et al. 87, Harty
& Cheriton 91, McNamee & Armstrong 90, Anderson et al.
92, Fall & Pasquale 94, Wheeler & Bershad 92, Romer et al.
94, Romer et al. 95, Cao et al. 94]. Unfortunately, exist-
ing system structures are not well-suited for specialization,
often requiring a substantial programming effort to affect
even a small change in system behavior. Moreover, changes
intended to improve the performance of one class of appli-
cations can often degrade that of others. As a result, system
specialization is a costly and error-prone process.
An extensible system is one that can be changed dynam-
ically to meet the needs of an application. The need for
extensibility in operating systems is shown clearly by sys-
tems such as MS-DOS, Windows, or the Macintosh Operat-
ing System. Although these systems were not designed to be
extensible, their weak protection mechanisms have allowed
application programmers to directly modify operating sys-
tem data structures and code [Schulman et al. 92]. While
individual applications have bene?ted from this level of free-
dom, the lack of safe interfaces to either operating system
services or operating system extension services has created
system con?guration “chaos” [Draves 93].
2.1 Related work
Previous efforts to build extensible systems have demon-
strated the three-way tension between extensibility, safety
and performance. For example, Hydra [Wulf et al. 81] de-
?ned an infrastructure that allowed applications to manage
resources through multi-level policies. The kernel de?ned the
mechanism for allocating resources between processes, and
the processes themselves implemented the policies for man-
aging those resources. Hydra’s architecture, although highly
in?uential, had high overhead due to its weighty capability-
based protection mechanism. Consequently, the system was
designed with “large objects” as the basic building blocks,
requiring a large programming effort to affect even a small
extension.
Researchers have recently investigated the use of micro-
kernels as a vehicle for building extensible systems [Black
et al. 92, Mullender et al. 90, Cheriton & Zwaenepoel
83, Cheriton & Duda 94, Thacker et al. 88]. A microker-
nel typically exports a small number of abstractions that in-
clude threads, address spaces, and communication channels.
These abstractions can be combined to support more conven-
tional operating system services implemented as user-level
programs. Application-speci?c extensions in a microkernel
occur at or above the level of the kernel’s interfaces. Unfor-
tunately, applications often require substantial changes to a
microkernel’s implementation to compensate for limitations
in interfaces [Lee et al. 94, Davis et al. 93, Waldspurger &
Weihl 94].
Although a microkernel’s communication facilities pro-
vide the infrastructure for extending nearly any kernel ser-
vice [Barrera 91, Abrossimov et al. 89, Forin et al. 91], few
have been so extended. We believe this is because of high
communication overhead [Bershad et al. 90, Draves et al.
91, Chen & Bershad 93], which limits extensions mostly
to coarse-grained services [Golub et al. 90, Stevenson &
Julin 95, Bricker et al. 91]. Otherwise, protected interac-
tion between system components, which occurs frequently
in a system with ?ne-grained extensions, can be a limiting
performance factor.
Although the performance of cross-domain communica-
tion has improved substantially in recent years [Hamilton
& Kougiouris 93, Hildebrand 92, Engler et al. 95], it still
does not approach that of a procedure call, encouraging the
construction of monolithic, non-extensible systems. For ex-
ample, the L3 microkernel, even with its aggressive design,
has a protected procedure call implementation with over-
head of nearly 100 procedure call times [Liedtke 92, Liedtke
93, Int 90]. As a point of comparison, the Intel 432 [Int 81],
which provided hardware support for protected cross-domain
transfer, had a cross-domain communication overhead on the
order of about 10 procedure call times [Colwell 85], and was
generally considered unacceptable.
Some systems rely on “little languages” to safely extend
the operating system interface through the use of interpreted
code that runs in the kernel [Lee et al. 94, Mogul et al.
87, Yuhara et al. 94]. These systems suffer from three
problems. First, the languages, being little, make the expres-
sion of arbitrary control and data structures cumbersome, and
therefore limit the range of possible extensions. Second, the
interface between the language’s programming environment
and the rest of the system is generally narrow, making sys-
tem integration dif?cult. Finally, interpretation overhead can
limit performance.
Many systems provide interfaces that enable arbitrary code
to be installedinto the kernel at runtime [Heidemann & Popek
94, Rozier et al. 88]. In these systems the right to de?ne ex-
tensions is restricted because any extension can bring down
the entire system; application-speci?c extensibility is not pos-
sible.
Several projects [Lucco 94, Engler et al. 95, Small &
Seltzer 94] are exploring the use of software fault isola-
tion [Wahbe et al. 93] to safely link application code, writ-
ten in any language, into the kernel’s virtual address space.
Software fault isolation relies on a binary rewriting tool that
inserts explicit checks on memory references and branch in-
structions. These checks allow the system to de?ne protected
memory segments without relying on virtual memory hard-
ware. Software fault isolationshows promise as a co-location
mechanism for relatively isolated code and data segments. It
is unclear, though, if the mechanism is appropriate for a sys-
tem with ?ne-grained sharing, where extensions may access
a large number of segments. In addition, software fault iso-
lation is only a protection mechanism and does not de?ne an
extension model or the service interfaces that determine the
degree to which a system can be extended.
Aegis [Engler et al. 95] is an operating system that re-
lies on ef?cient trap redirection to export hardware services,
such as exception handling and TLB management, directly
to applications. The system itself de?nes no abstractions
beyond those minimally provided by the hardware [Engler
& Kaashoek 95]. Instead, conventional operating system
services, such as virtual memory and scheduling, are im-
plemented as libraries executing in an application’s address
space. System service code executing in a library can be
changed by the application according to its needs. SPIN
shares many of the same goals as Aegis although its ap-
proach is quite different. SPIN uses language facilities to
protect the kernel from extensions and implements protected
communication using procedure call. Using this infrastruc-
ture, SPIN provides an extension model and a core set of
extensible services. In contrast, Aegis relies on hardware
protected system calls to isolate extensions from the kernel
and leaves unspeci?ed the manner by which those extensions
are de?ned or applied.
Several systems [Cooper et al. 91, Redell et al. 80,
Mossenbock 94, Organick 73] like SPIN, have relied on lan-
guage features to extend operating system services. Pilot,
for instance, was a single-address space system that ran pro-
grams written in Mesa [Geschke et al. 77], an ancestor of
Modula-3. In general, systems such as Pilot have depended
on the language for all protection in the system, not just for
the protection of the operating system and its extensions. In
contrast, SPIN’s reliance on language services applies only to
extension code within the kernel. Virtual address spaces are
used to otherwise isolate the operating system and programs
from one another.
3The SPIN Architecture
The SPIN architecture provides a software infrastructure for
safely combining system and application code. The pro-
tection model supports ef?cient, ?ne-grained access control
of resources, while the extension model enables extensions
to be de?ned at the granularity of a procedure call. The
system’s architecture is biased towards mechanisms that can
be implemented with low-cost on conventional processors.
Consequently, SPIN makes few demands of the hardware,
and instead relies on language-level services, such as static
typechecking and dynamic linking.
Relevant properties of Modula-3
SPIN and its extensions are written in Modula-3, a general
purpose programming language designed in the early 1990’s.
The key features of the language include support for inter-
faces, type safety, automatic storage management, objects,
generic interfaces, threads, and exceptions. We rely on the
language’s support for objects, generic interfaces, threads,
and exceptions for aesthetic reasons only; we ?nd that these
features simplify the task of constructing a large system.
The design of SPIN depends only on the language’s safety
and encapsulation mechanisms; speci?cally interfaces, type
safety, and automatic storage management. An interface de-
clares the visible parts of an implementation module,which
de?nes the items listed in the interface. All other de?nitions
within the implementation module are hidden. The com-
piler enforces this restriction at compile-time. Type safety
prevents code from accessing memory arbitrarily. A pointer
may only refer to objects of its referent’s type, and array
indexing operations must be checked for bounds violation.
The ?rst restriction is enforced at compile-time, and the sec-
ond is enforced through a combination of compile-time and
run-time checks. Automatic storage management prevents
memory used by a live pointer’s referent from being returned
to the heap and reused for an object of a different type.
3.1 The protection model
A protection model controls the set of operations that can
be applied to resources. For example, a protection model
based on address spaces ensures that a process can only ac-
cess memory within a particular range of virtual addresses.
Address spaces, though, are frequently inadequate for the
?ne-grained protection and management of resources, being
expensive to create and slow to access [Lazowska et al. 81].
Capabilities
All kernel resources in SPIN are referenced by capabilities.
A capability is an unforgeable reference to a resource which
can be a system object, an interface, or a collection of in-
terfaces. An example of each of these is a physical page,
a physical page allocation interface, and the entire virtual
memory system. Individual resources are protected to en-
sure that extensions reference only the resources to which
they have been given access. Interfaces and collections of
interfaces are protected to allow different extensions to have
different views on the set of available services.
Unlike other operating systems based on capabilities,
which rely on special-purpose hardware [Carter et al. 94],
virtual memory mechanisms [Wulf et al. 81], probabilistic
protection [Engler et al. 94], or protected message chan-
nels [Black et al. 92], SPIN implements capabilities directly
using pointers, which are supported by the language. A
pointer is a reference to a block of memory whose type is
declared within an interface. Figure 1 demonstrates the def-
inition and use of interfaces and capabilities (pointers) in
SPIN.
INTERFACE Console; (* An interface. *)
TYPE T <: REFANY; (* Read as "Console.T is opaque." *)
CONST InterfaceName = "ConsoleService";
(* A global name *)
PROCEDURE Open():T;
(* Open returns a capability for the console. *)
PROCEDURE Write(t: T; msg: TEXT);
PROCEDURE Read(t: VAR msg: TEXT);
PROCEDURE Close(t: T);
END Console;
MODULE Console; (* An implementation module. *)
(* The implementation of Console.T *)
TYPE Buf = ARRAY [0..31] OF CHAR;
REVEAL T = BRANDED REF RECORD (* T is a pointer *)
inputQ: Buf; (* to a record *)
outputQ: Buf;
(* device speci?c info *)
END;
(* Implementations of interface functions *)
(* have direct access to the revealed type. *)
PROCEDURE Open():T = ...
END Console;
MODULE Gatekeeper; (* A client *)
IMPORT Console;
VAR c: Console.T; (* A capability for *)
(* the console device *)
PROCEDURE IntruderAlert() =
BEGIN
c := Console.Open();
Console.Write(c, "Intruder Alert");
Console.Close(c);
END IntruderAlert;
BEGIN
END Gatekeeper;
Figure 1: The Gatekeeper module interacts with SPIN’s Console service
through the Console interface. Although Gatekeeper.IntruderAlert manip-
ulates objects of type Console.T, it is unable to access the ?elds within the
object, even though it executes within the same virtual address space as the
Console module.
The compiler, at compile-time, prevents a pointer from
being forged or dereferenced in a way inconsistent with its
type. There is no run-time overhead for using a pointer,
passing it across an interface, or dereferencing it, other than
the overhead of going to memory to access the pointer or
its referent. A pointer can be passed from the kernel to a
user-level application, which cannot be assumed to be type
safe, as an externalized reference. An externalized reference
is an index into a per-application table that contains type safe
references to in-kernel data structures. The references can
later be recovered using the index. Kernel services that intend
to pass a reference out to user level externalize the reference
through this table and instead pass out the index.
Protection domains
A protection domain de?nes the set of accessible names avail-
able to an execution context. In a conventional operating
system, a protection domain is implemented using virtual ad-
dress spaces. A name within one domain, a virtual address,
has no relationship to that same name in another domain.
Only through explicit mapping and sharing operations is it
possible for names to become meaningful between protection
domains.
In SPIN the naming and protection interface is at the level
of the language, not of the virtual memory system. Conse-
quently, namespace management must occur at the language
level. For example, if the name c is an instance of the type
Console.T, then both c and Console.T occupy a portion of
some symbolic namespace. An extension that rede?nes the
type Console.T, creates an instance of the new type, and
passes it to a module expecting a Console.T of the original
type creates a type con?ict that results in an error. The error
could be avoided by placing all extensions into a global mod-
ule space, but since modules, procedures, and variable names
are visible to programmers, we felt that this would introduce
an overly restrictive programming model for the system. In-
stead, SPIN provides facilities for creating, coordinating, and
linking program-level namespaces in the context of protec-
tion domains.
A SPIN protection domain de?nes a set of names, or pro-
gram symbols, that can be referenced by code with access
to the domain. A domain, named by a capability, is used to
control dynamic linking, and corresponds to one or more safe
object ?les with one or more exported interfaces. An object
?le is safe if it is unknown to the kernel but has been signed
by the Modula-3 compiler, or if the kernel can otherwise as-
sert the object ?le to be safe. For example, SPIN’s lowest
level device interface is identical to the DEC OSF/1 driver
interface [Dig 93], allowing us to dynamically link vendor
drivers into the kernel. Although the drivers are written in C,
the kernel asserts their safety. In general, we prefer to avoid
using object ?les that are “safe by assertion” rather than by
compiler veri?cation, as they tend to be the source of more
than their fair share of bugs.
Domains can be intersecting or disjoint, enabling appli-
cations to share services or de?ne new ones. A domain is
created using the Create operation, which initializes a domain
with the contents of a safe object ?le. Any symbols exported
by interfaces de?ned in the object ?le are exported from the
domain, and any imported symbols are left unresolved. Un-
resolved symbols correspond to interfaces imported by code
within the domain for which implementations have not yet
been found.
The Resolve operation serves as the basis for dynamic
linking. It takes a target and a source domain, and resolves
any unresolved symbols in the target domain against symbols
exported from the source. During resolution, text and data
symbols are patched in the target domain, ensuring that, once
resolved, domains are able to share resources at memory
INTERFACE Domain;
TYPE T <: REFANY; (* Domain.T is opaque *)
PROCEDURE Create(coff:CoffFile.T):T;
(* Returns a domain created from the speci?ed object
?le (‘‘coff’’ is a standard object ?le format). *)
PROCEDURE CreateFromModule():T;
(* Create a domain containing interfaces de?ned by the
calling module. This function allows modules to
name and export themselves at runtime. *)
PROCEDURE Resolve(source,target: T);
(* Resolve any unde?ned symbols in the target domain
against any exported symbols from the source.*)
PROCEDURE Combine(d1, d2: T):T;
(* Create a new aggregate domain that exports the
interfaces of the given domains. *)
END Domain.
Figure 2: The Domain interface. This interface operates on instances of
type Domain.T, which are described by type safe pointers. The implemen-
tation of the Domain interface is unsafe with respect to Modula-3 memory
semantics, as it must manipulate linker symbols and program addresses
directly.
speed. Resolution only resolves the target domain’s unde-
?ned symbols; it does not cause additional symbols to be
exported. Cross-linking, a common idiom, occurs through a
pair of Resolve operations.
The Combine operation creates linkable namespaces that
are the union of existing domains, and can be used to bind
together collections of related interfaces. For example, the
domain SpinPublic combines the system’s public interfaces
into a single domain available to extensions. Figure 2 sum-
marizes the major operations on domains.
The domain interface is commonly used to import or export
particular named interfaces. A module that exports an inter-
face explicitly creates a domain for its interface, and exports
the domain through an in-kernel nameserver. The exported
name of the interface, which can be speci?ed within the inter-
face, is used to coordinate the export and import as in many
RPC systems [Schroeder & Burrows 90, Brockschmidt 94].
The constant Console.InterfaceName in Figure 1 de?nes a
name that exporters and importers can use to uniquely iden-
tify a particular version of a service.
Some interfaces, such as those for devices, restrict access
at the time of the import. An exporter can register an au-
thorization procedure with the nameserver that will be called
with the identity of the importer whenever the interface is
imported. This ?ne-grained control has low cost because
the importer, exporter, and authorizer interact through direct
procedure calls.
3.2 The extension model
An extension changes the way in which a system provides
service. All software is extensible in one way or another,
but it is the extension model that determines the ease, trans-
parency, and ef?ciency with which an extension can be ap-
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!