Transcript MIT-Exokernel-by-Steve-Petzinger-Billy-Lehner-Fall

Overview of the MIT Exokernel
Operating System
James Madison University
CS 450 Abzug MWF 10:10-11:00
12/2/02
Steven Petzinger
Billy Lehner
MIT Exokernel Operating
System
•An Operating System Architecture for ApplicationLevel resource management
•Initial draft proposed at The ACM Symposium on
Operating Systems Principles (SOSP) conference,
1995 by Dawson Engler, Frans Kaashoek, and
James O’Toole
•Implementation for x86 computers: Xok/ExOS
Introduction/History
• Traditional OS’s limit unprivileged
applications’ ability to manage their own
resources, thus decreasing their performance
• Prior solutions included: 1
– Better microkernels
– Virtual machines
– Downloading untrusted code into the kernel
1
( Engler (1998), 13-14)
The Exokernel Architecture
(source: http://www.pdos.lcs.mit.edu/exo.html)
Kernel for x86: Xok
Default LibOS: ExOS
Principles of Exokernels
“The goal of an exokernel is to give efficient control of
resources to untrusted applications in a secure,
multiuser system” 1
•
•
•
•
•
Low-level interface
Fine-grained resource multiplexing
Limit management to protection
Visible allocation and revocation of resources
Expose kernel data structures and hardware
1
(Kaashoek, Engler, et. al., 1997)
Multiplexing the Hardware
Resources
2 main issues:
1) How to give applications control over a resource
2) How to protect it
(source for figure: Engler, Dawson R. (1998), 12)
Multiplexing Main Memory 1
1. Xok exposes the capabilities of the hardware (e.g., all
MMU protection and dirty bits) and many kernel data
structures (e.g., free lists, inverse page mappings).
2. When a libOS allocates a physical memory page, the
exokernel records the owner and permissions of the
allocating process.
3. The exokernel guards every access to the physical
memory page by requiring that the capability be presented
by the libOS requesting access.
4. When the exokernel detects a page fault of any kind
(writing to RO page, access page not present, etc) it
propagates the fault up to a user level (libOS) fault handler
1
(Pinckney, 1998)
Multiplexing the CPU 1
Processes:
1. Exokernel’s idea of a process is called an environment. An
environment consists in accounting information, page table,
locations of code to run when certain events happen, and
other custom data.
2. The kernel multiplexes the processor by dividing it into time
slices of a fixed number of ticks.
3. An environment may then allocate time slices in order to be
scheduled on the processor.
4. The kernel notifies a process that it is about to gain or lose
the processor by calling the processes' prologue and
epilogue code.
5. Each process is responsible for saving and restoring its
registers when it loses and gains the processor.
1
(Pinckney, 1998)
Protected Sharing
Problem: A libOS cannot necessarily trust all other
libOSes with access to a particular resource
Some solutions: 1
1. Software regions: areas of memory that can only be read
or written through system calls
2. Hierarchically named capabilities: child processes cannot
accidentally write to parent pages or software regions
3. Wakeup predicates: kernel functions that ensure that a
buggy or crashed process will not hang up a correctly
behaved one
4. Inexpensive critical sections implemented by disabling
software interrupts instead of using locks
1
( Kaashoek, Engler et. al. (1997), 3)
Multiplexing the Stable
Storage 1
• Each libOS contains one or more libFSes.
• Multiple libFSes can be used to share the same files
with different semantics.
• The Challenge for exokernels is to provide a means
to safely multiplex disks among multiple library file
systems (libFSes); giving libFSes as much control
over file management as possible while still
protecting files from unauthorized access
1
(Engler (1998), 36)
Xok’s File system: XN
1
XN provides access to stable storage at the level
of disk blocks with the goal of determining the
access rights of a given principal to a given disk
block as efficiently as possible.
XN Exports the following to the LibFS:
•a buffer cache registry
•free maps
•other on-disk structures.
1
(Engler (1998), 42)
C-FFS – ExOS’s default LibFS 1
C-FFS (Co-locating fast file system) is faster than inkernel file systems
C-FFS uses exokernel/XN control to:
•Embed inodes in directories
•Co-locate related files together on disk
•Fetch large chunks of disk on every read
In addition, C-FFS guarantees metadata integrity by
using “protected methods” to guard modifications
1
(Kaashoek, Engler et. al. (1998), [sld025.htm])
Protected Abstractions 1
Problem: Many of the resources protected by traditional
operating systems are themselves high-level
abstractions.
Example: Files consist of metadata, disk blocks, and
buffer cache pages, all of which are guarded by
access control on high-level file objects.
Xok uses 3 techniques. It:
1. Performs access control on all resources in the same
manner
2. Provides software abstractions to bind hardware
resources together.
3. Allows applications to download code for some
abstractions
1
(Kaashoek, Engler, et. al., 1997)
Protected Abstractions (cont.)
“The key to these exokernel software abstractions is
that they neither hinder low-level access to hardware
resources nor unduly restrict the semantics of the
protected abstractions they enable.” 1
Example: The Xok buffer cache registry binds disk
blocks to the memory pages caching them.
Applications have control over physical pages and
disk I/O, but can also safely use each other’s cached
pages.
1
(Kaashoek, Engler, et. al., 1997)
Performance 1
• Applications
– Unaltered Unix applications on Xok run comparably or
significantly faster compared to both FreeBSD and
OpenBSD.
– libOS-optimized applications appear at least as effective
as their equivalent in-kernel implementation.
• Aggressive I/I/O-centric applications that want to manage
their resources show dramatic improvements (up to 8x).
• Global
– When used to improve application speed, an exokernel
system can have dramatically improved global
performance, since there are more resources to go
around.
1
(Engler (1998), 49-56)
Generic Application Performance
(source: Engler (1998), 50)
Optimized Application Performance
(source: Engler (1998), 53)
Global (System) Performance
Times are in seconds and on a log scale. number/number refers to the the total number of applications run by
the script and the maximum number of jobs run concurrently. Total is the total running time of each experiment,
Max is the longest runtime of any process in a given run (giving the worst latency). Min is the minimum.
(source: Engler (1998), 54)
Advantages/Costs of
Exokernels 1
• Advantages
– Exposing kernel data structures
– The CPU interface
– Libraries are simpler than kernels
• Costs
–
–
–
–
Exokernel interface design is not simple
Information loss
Self-paging libOSes
Sociological Factors. . .
1
(Engler (1998), 68-69)
Lessons 1
•Some space for application data in kernel
structures can be helpful
•Simplifies the task of locating shared state; avoids
awkward (and complex) replication of indexing
structures at the application level.
•Exokernels do not require fast microbenchmark
performance
•The main benefit of an exokernel is not that it
makes primitive operations efficient, but that it gives
applications control over expensive operations such
as I/O.
•Locks are costly
•because of the trust, communication and
complexity involved with different libOSes, disabling
software interrupts for critical sections are used
instead
1
(Engler (1998), 69)
Bibliography
Engler, Dawson R. (1998). “The Exokernel Operating System
Architecture.” MIT Department of Electrical Engineering and
Computer Science.
Engler, Dawson R., Kaashoek, Frans M. et. al. (1998).
“Exokernels (or, making the operating system just another
application library).” MIT Lab for Computer Science. URL:
http://amsterdam.lcs.mit.edu/exo/exo-slides/sld001.htm
Kaashoek, Frans M., Engler, Dawson R. et. al. (1997).
“Application Performance and Flexibility on Exokernel Systems”.
Symposium on Operating Systems Principles (SOSP) 1997
conference.
MIT Lab for Computer Science (LCS) Parallel and Distributed
Operating Systems (PDOS) group (1998). “MIT Exokernel
Operating System: Putting the Application in Control.” URL:
http://www.pdos.lcs.mit.edu/exo.html
Pinckney, Thomas (1998). “Internal Structure of Xok/ExOS.” MIT
Laboratory for Computer Science. URL:
http://www.pdos.lcs.mit.edu/exo/exo-internals/internals.html