Transcript ppt

Presentation of
Extensibility, Safety and Performance
in the
SPIN Operating System
Brain N. Bershad
Emin Gun Sirer
Craig Chambers
Stefan Savage
Marc E.Fiuczynski
Susan Eggers
By Anandhi Sundaram
Przemyslaw
David Becker
History & Goals

SPIN under development at university of
Washington
Motivation
OS has to support Multimedia, Distributed Memory
management, hence systems are structured to
support application specific extensions.
Goals



Extensibility : allow for extensions to dynamically
specialize OS services by providing fine-grain access
to system services through interfaces
Safety : isolate critical kernel interfaces from
malicious kernel extensions
Performance: provide low communication overhead
between extension and kernel
CS533 - Concepts of Operating Systems
Three Way Tension
DOS: provides for extensibility at

the cost of safety
Mach:
 Provides extensibility at the
cost of performance in the form
of expensive IPC
 Micro-kernel needs substantial
changes to compensate for
limitations in interfaces
L3 micro-kernel:
 IPC is improved by protected
procedure call implementation
(as in LRPC) with overhead of
nearly 100 procedure call times
CS533 - Concepts of Operating Systems
3
Different OS Structures
CS533 - Concepts of Operating Systems
4
Techniques Followed to Achieve Goals

Performance:
o
o

Safety:
o
o

Co-location - kernel and dynamically linked extension share
same virtual address space
Enables communication between system and extension code
to be cost of procedure call
Language support - restrictions are enforced using the
type-safe properties of Modula-3, the programming
language in which SPIN and its extensions are written
Dynamic linking - extensions exist within logical protection
domains. In-kernel dynamic linker enables cross-domain
communication at overhead of procedure call
Extensibility:
o
o
Provide fine-grain interfaces to core system services.
Dynamic call binding – provide relationship between system
components and extensions at runtime
CS533 - Concepts of Operating Systems
5
CS533 - Concepts of Operating Systems
6
CS533 - Concepts of Operating Systems
7
Implementing Safety


Previous Approaches:
 Hardware Protection through Address Spaces,
Coarse-grained and expensive
 Software-based Fault Isolation
(“Efficient Software-based Fault Isolation” paper)
SPIN relies on Language-level Support
 Modula-3 Properties
 Type Safety
 Automatic Storage Management
 Support for Interfaces
CS533 - Concepts of Operating Systems
8
Safety : Language Support
Type safety
Prevents access to memory arbitrarily,
compile-time check enforces pointer may
reference only to objects of its referent’s type
Array bound violation checks enforced by
combination of compile-time, run-time checks


Automatic storage management
CS533 - Concepts of Operating Systems
9
Safety : Language Support
Interfaces Hide Resources



Modula-3 Modules are composed of Interface (public
part), implementation or module (private part)
Interface: Gives only the types and procedure
Interfaces
Module: Procedure definitions and private declaration
hidden from clients
INTERFACE <interface-name>;
{Imports}
{Declarations}
END <interface-name>.
MODULE <module-name> [ EXPORTS <interface> { ","
<interface> ... } ];
{Imports}
{Declarations}
BEGIN (* Optional Module startup code; BEGIN required *)
END <module-name>.
CS533 - Concepts of Operating Systems
10
Safety : Interfaces
INTERFACE Console;
TYPE T <: REFANY
(* T is a pointer and only Console.T is visible *)
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 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;
;
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 specific info *)
END;
(* Implementations of interface functions *)
(* have direct access to the revealed type. *)
PROCEDURE Open():T = ...
END Console
BEGIN
END Gatekeeper;
CS533 - Concepts of Operating Systems
11
Capabilities




Capabilities are like ‘key’ provided to Extensions to
access resources through Interface provided by
Kernel.
Capabilities are implemented using Pointers declared
within Interface, Supported by Modula-3 language.
A Pointer can be passed from the kernel to a userlevel application as an externalized reference.
An Externalized reference is an INDEX into a perapplication table in the kernel, that contains type
safe references to in-kernel data structures.
CS533 - Concepts of Operating Systems
12
Protection Domains





Logical protection domains within a single address
space
In terms of dynamic linking, all domains are created
at runtime, by operating on accessible interfaces, or
by manipulating existing domains
Create, CreatefromModule,resolve, combine.
SpinPublic, SpinPrivate
A module that exports an interface explicitly
creates a domain for its interface, and exports the
domain through an in-kernel Nameserver
CS533 - Concepts of Operating Systems
13
Combined Domains SpinPublic,
SpinPrivate
CS533 - Concepts of Operating Systems
15
Extensibility






SPIN uses Events and Handlers to integrate
Extensions with the kernel
Event is procedure exported from an interface
Handler is procedure of same type as event
Extensions explicitly register handlers with Events
through a Central dispatcher
Central dispatcher routes events to handlers
In case of multiple handlers, one final result is
passed back to the event raiser
CS533 - Concepts of Operating Systems
16

Handler restrictions enforced by the primary module
– implementation module that statically exports the event
– other modules interact with the primary module
• can deny/accept the handler
• can associate guards for executing the handler

Dispatcher Scalability
CS533 - Concepts of Operating Systems
17
Core Services – Memory Management

Three basic fine-grain services provided by SPIN
o
o
o
o
o
Physical address service : controls the use and allocation of
physical pages.
Virtual address service
Translation service
Can be used by extensions/ applications to define
services like demand-paging, copy-on-write,
distributed shared memory, concurrent garbage
collection
Implementation: extension that implements UNIX
address space semantics for applications.
CS533 - Concepts of Operating Systems
18
Core Services – Thread Management



User-level threads require knowledge of kernel
events
Scheduler Activations have high communication
overhead due to kernel crossings
SPIN: An application can provide its own thread
package and scheduler that executes within the
kernel
CS533 - Concepts of Operating Systems
19
Core Services - Thread Management
SPIN defines structure for Implementation of thread
model





Strands similar to user-level threads, have no kernel
context
Scheduler multiplexes resources among Strands
An Application Specific thread package defines an
implementation of the strand Interface for its own
threads
The Interface : Two events Block, Unblock – raised by
kernel to signal changes in strand’s execution state to
application-specific Scheduler. Allows implementation of
new scheduling policies
Scheduler communicates with Thread Package using
Checkpoint and Resume
CS533 - Concepts of Operating Systems
20
Core Services - Thread Management




The responsibility for scheduling and synchronization
within the kernel belongs to the kernel for safety
reasons
Global scheduler implements a round-robin, preemptive,
priority policy
Some Implementations using Strand Interface:
o DEC OSF/1 kernel threads
o C-Threads
o Modula-3 Threads
SPIN’s core services are trusted services – The
interfaces are designed to ensure that, an extension’s
failure to use an interface correctly is isolated to the
extension itself
CS533 - Concepts of Operating Systems
21
System Performance




Microbenchmarks to reveal overhead of basic system
functions, such as protected procedure call, thread
management, and virtual memory were run on DEC
OSF/1, Mach and SPIN
Overhead of in-kernel protected communication can
be order of procedure call in SPIN
Inference: SPIN allows use of traditional
communication mechanisms having comparable
performance to other systems
SPIN’s extensible thread implementation does not
incur a performance penalty when compared to nonextensible systems, even when integrated with kernel
services.
CS533 - Concepts of Operating Systems
22
Applications using SPIN



Implementation of Network Protocol Stacks for
Ethernet and ATM networks using SPIN’s extension
architecture
Networked Video System consisting of Server and
Client Viewer exploits SPIN’s extension architecture
End-to-End application performance can benefit
from SPIN’s architecture
Conclusion :
It is possible to combine
extensibility, safety and performance in a single
system
CS533 - Concepts of Operating Systems
23
References



http://www-spin.cs.washington.edu
Extensibility, Safety and Performance in the SPIN Operating System,
Brian Bershad, Stefan Savage, Przemyslaw Pardyak, Emin Gun Sirer, David
Becker, Marc Fiuczynski, Craig Chambers, Susan Eggers, in "Proceedings of the
15th ACM Symposium on Operating System Principles (SOSP-15)", Copper
Mountain, CO. pp. 267--284.
A design, implementation and performance paper.
Abstract, Paper (postscript), Slides (postscript).
Language Support for Extensible Operating Systems ,
Wilson Hsieh, Marc Fiuczynski, Charles Garrett, Stefan Savage, David Becker,
Brian Bershad, Appeared in the Workshop on Compiler Support for System
Software, February 1996.
We've been pretty happy with M3, but we've had to deal with a few
shortcomings in order to use the language in a safe extensible operating
system. This paper describes how we've addressed those shortcomings.
Abstract, Paper (postscript), Slides (postscript).
CS533 - Concepts of Operating Systems
24
References


Safe Dynamic Linking in an Extensible Operating System ,
Emin Gun Sirer, Marc Fiuczynski, Przemyslaw Pardyak, Brian Bershad,
Appeared in the Workshop on Compiler Support for System Software,
February 1996.
Describes the dynamic linker we use to load code into the kernel. Key point is
the ability to create and manage linkable namespaces that describe interfaces
and collections of interfaces.
Paper (postscript), Slides (postscript).
http://www.cs.nyu.edu/courses/spring99/G22.3250-001/lectures/lect26.pdf
CS533 - Concepts of Operating Systems
25