Transcript A2_MicroK-ExtOS

Operating System
Architectures
Kernel Design
Microkernels
Primary Reference/Microkernels
• “On μ-Kernel construction”, Jochen Liedtke,
Proc. 15th ACM Symposium on Operating
System Principles (SOSP), December 1995
• “Toward Real Microkernels”, Jochen
Liedtke, Communications of the ACM, Sept.
1996, vol. 39, No. 9.
Properties of Monolithic OS
• All OS functionality is included in a single
program (address space)
• UNIX, Linux, most commercial systems
• Strong points: well-understood, good
performance
• Problems: kernel components aren’t
protected from each other, not easily
extended/modified, structure may be
unclear
Monolithic Structure
(from Tanenbaum, Modern Operating Systems)
Main function
OS services
Utility
functions
MicroKernels - Outline
• OS kernel is very small – minimal functionality.
• Other OS functions provided at user level by
trusted servers.
– User-level process, but trusted by kernel
• Advantage: Design reflects good software
engineering practices
• Problem: performance
Microkernels
(from Tanenbaum, Modern Operating Systems)
User
User
file
process process server
pager
...
microkernel
memory process
server server
User
space
Kernel
space
Approach
• The microkernel layer provides a set of
minimal core services and is the interface
to the hardware layer
• Other services (drivers, memory
managers, etc.) are implemented as
separate modules with clearly defined
interfaces.
Example Systems
• Windows NT: introduced HAL layer to support
hardware independence; pushed some services
to user level.
• Amoeba (Tanenbaum’s research based OS)
• Chorus
• Mach (CMU and DARPA) – was the basis for the
MAC OS/X and GNU HURD
• L4 is a family of publicly available microkernels
– Home page: http://l4hq.org/
Major Advantages
• Modularity
• Flexibility and extensibility
– Easier to replace modules – fewer dependencies
– Different servers can implement the same service in
different ways
• Safety (each server is protected by the OS from
other servers) using standard OS memory
protection techniques
• Servers are largely hardware independent
• Correctness
– Easier to verify a small kernel
– Servers are isolated; errors in one don’t affect others
Discussion
• Microkernels embody quality-enhancing
principles from software engineering:
– Modularity, leading to
•
•
•
•
•
Easy to modify because changes can be localized
Cohesion
Flexibility
Safety
Etc.
Major Disadvantages
of Early Microkernels
• Slow – is this due to “cross-domain”
information transfers? Maybe
– Server-to-OS, OS-to-server IPC is thought to
be a major source of inefficiency
– Mode switches/context switches
• Generally it’s faster to communicate
between two modules that are both in OS
– no mode switching involved
Can MicroKernels Perform Well?
• Jochen Liedtke argued that μ-kernels could give
the same level of performance as a traditional
OS, and conducted experiments using his μkernels (L3 and later L4) to prove his claim.
• He claimed that 1st generation μ-kernels were not
implemented correctly; e.g., many were just
modifications of existing systems when it would
be better to start from scratch.
μ-kernel Concepts (1)
• He began by asking which “primitives” (basic
abstractions) should be in a μ-kernel.
• Criterion: a concept/function should be in the
kernel iff implementing it outside the kernel
would prevent the system from working
correctly.
– Implication: if it’s possible to do something more than
one way (e.g., scheduling, page replacement, …)
implement that something externally as a server
μ-kernel Concepts (2)
• Liedtke’s set of μ-kernel abstractions :
address spaces, threads and very efficient
thread communication (IPC), unique
identifiers for communication.
• To construct a full-featured operating
system, provide user-level services to
complement the kernel services.
Monolithic v Micro
Flexibility
• To show that these basic concepts were
sufficient he suggested how many basic
OS functions could be implemented on top
of the μ-kernel.
• Examples:
– Memory manager & pager
– Multimedia resource allocation
– Device drivers
– UNIX server …
Performance (1)
• Common belief: poor μ-kernel performance
was due to excessive mode switches and
context switches.
• Liedtke demonstrated empirically that mode
switching times could be improved by a
factor of 6 -10 in a well-designed μ-kernel.
• He concluded that context switches and
IPC could be implemented “fast enough”
Performance (2)
• Another criticism: Mach showed poor memory
system performance (measured by MCPI –
memory cycle overhead per instruction).
• Liedtke quoted measurements to show that the
Mach μ-kernel had a very large working set
which occupied much of the cache, leading to a
high cache miss rate for user processes
• Conclusion: performance due to poor μ-kernel
design, not inherent to μ-kernel concept.
Section 5 – Non-Portability
First generation μ-kernels were machineindependent; built on top of a machine dependent
layer (like Microsoft HAL)
Liedtke argued for machine-dependent systems:
• Better able to optimize performance based on
specific hardware features
• Able to avoid known hardware inefficiencies
• A single software layer is more efficient than a twolayer configuration.
L4 Was Machine Dependent
• The original L4 operating system was built
for the 386 architecture
• Today, L4 is a whole family of operating
systems; not all are machine dependent.
Conclusions (1)
• “μ-kernels can provide higher layers with a
minimal set of … abstractions that are
flexible enough to allow implementation of
arbitrary operating systems and allow
exploitation of a wide range of hardware.”
– Must choose the right abstractions
– Existing μ-kernels chose poorly, or too many,
or too specialized, …
Conclusions (2)
• “similar to optimizing code generators, μkernels must be constructed per processor
and are inherently not portable”
– Poor performance in μ-kernels is due in part
to inefficient implementations, poor choice of
data structures and algorithms – they aren’t
“tuned” to the processor’s needs
Conclusions (3)
• His design “…shows that it is possible to
achieve well performing μ-kernels through
processor-specific implementations of
processor-independent abstractions.”
Operating System
Architectures
Kernel Design:
Extensible Operating Systems
References
• “Exokernel: an Operating System Architecture for
Application-Level Resource Management”, Dawson R.
Engler, M. Frans Kaashoek, and James O’Toole jr; Proc.
of the 15th ACM Symposium on Operating Systems
Principles (SOSP ’95), December 1995.
• “Extensibility, Safety and Performance in the SPIN
Operating System”’, Brian N. Bershad, Stefan Savage,
Przemyslaw Pardyak, Emin Gun Sirer, Mar E. Fiuczynski,
David Becker, Craig Chambers, Susan Eggers, Proc. of
the 15th ACM Symposium on Operating Systems
Principles (SOSP ’95), December 1995.
Hierarchy of Communication
Mechanisms (Fastest to Slowest)
• Function calls within same process (stays in
same address space)
• System calls: mode switch + minimal context
saving/restoring + some processing
• Context Switch (also known as a process
switch): mode switches + processing +
significant state-saving & restoring actions
• IPC between processes (message passing, on
the same or different machines)
Motivation for Extensibility
• The traditional OS provides
– Various abstractions of system resources (virtual
address spaces, processes, files, interprocess
communication)
– General-purpose resource management algorithms
• System calls define user interface to OS
– Applications can’t request non-standard OS processing
• Able to handle most applications, but handles no
applications perfectly because there’s no easy
way to specialize the OS to individual needs.
Motivation (2)
• Make operating systems more responsive
to applications’ needs; e.g.,
– Do your own scheduling
– Choose your own page replacement algorithm
• Authors of the SPIN paper say they were
“…motivated by the need to support
applications that present demands poorly
matched by an operating system’s
implementation or interface.”
Cost of High-Level Abstractions
• OS use of high-level abstractions hides info that
applications could use to manage their own
resources; e.g.
– Database systems shouldn’t have to build
random-access files on top of OS file system
• Performance and functionality are limited; no
way to “tune” system to meet specific
characteristics of each process.
• A large, unmodifiable OS can’t easily incorporate
new research developments.
End-to-end Argument
• The end-to-end argument* argues that (highlevel) applications know their own needs best.
Services provided by low-level system
components (the OS, for example) are often
expensive and redundant and will need to be
done again, correctly, at a higher-level (the
application)
• Exokernel authors use this argument to support
their claim that OS should give applications
almost total control over high-level abstractions.
• SPIN has a similar philosophy.
“End-To-End Arguments In System Design”, by Jerome H. Saltzer, David P.
Reed, David D. Clark, ACM Transactions on Computer Systems, Nov., 1984.
Example Systems
• Exokernel
• SPIN
Exokernels
• Are a type of OS architecture, like a microkernel,
not a specific example.
• resource allocation & protection (in the kernel)
• resource management (done at user level with
user-level library operating systems or directly by
applications)
– Aegis is an example exokernel;
– EXOS is an example library OS.
• Goal: safe application control of resources
SPIN
• SPIN (based on Mach) provides a set of basic
core services, plus a mechanism to allow user
application to “specialize the kernel by
dynamically linking new code into the running
system. Kernel extensions can add new kernel
services, replace default policies, or simply
migrate application functionality into the kernel
address space.”
• http://www-spin.cs.washington.edu/
Extensibility Mechanisms
• Exokernels rely on application-specific library
operating systems to provide user modifications.
• SPIN relies on application-specific kernel
extensions for the same purpose.
• Exokernels are incomplete without a library OS
or an application that can manage resources;
SPIN is a complete OS that can be
modified/extended if desired.
What an Exokernel Does
• Multiplexes the hardware directly
– Instead of providing an abstraction of the hardware an
exokernel makes specific hardware resources directly
available to user level applications; e.g., disk blocks
instead of files
• Provides primitives for secure management of
physical resources; applications use them to
develop appropriate abstractions.
• http://pdos.csail.mit.edu/exo.html
Secure Bindings
• Secure bindings separate resource authorization
from resource usage
• Protection checks are applied at binding time;
checks at resource access time become simple
and straightforward. For example:
– If a page fault occurs and the application allocates a
page frame for the new page the exokernel can quickly
determine whether the application owns this frame.
• “Simply put, a secure binding allows the kernel to
protect resources without understanding them.”
Policy
• Most policy decisions are made by the library
operating systems, under the assumption that an
application or group of applications know best
how to manage resources.
• The exokernel must reserve enough policy to
balance resource sharing among competing
library OS’s – it is still the case that apps must
be protected from one another.
Performance
• When applications have direct control over
physical resources they are able to
implement abstractions very efficiently.
• Example: The authors cite measurements
showing that application-controlled file
caching can reduce run time by up to 45%.
• More about performance (old web page):
http://pdos.csail.mit.edu/exo.html
Library Operating Systems
• Untrusted - Built on top of an exokernel
• Can be tailored to a set of applications
with similar requirements.
• Run in user space – fewer system calls to
the exokernel => enhanced performance.
• Applications can interact with a library OS
or interface directly to the exokernel.
• Possible to provide a standard interface
(e.g. POSIX) for a familiar look.
What SPIN Does
• Gives applications a way to to change or
extend basic system services while
guaranteeing that
– No application can interfere with any other
application
– Performance will not be affected by slow
communication between OS and application
Performance
• Applications modify the system by writing
extensions, code that “changes the way in
which a system provides service”.
• Extensions are compiled and linked
directly to the kernel code when needed.
– Co-location (user’s extension code linked
directly to kernel code) reduces time lost to
mode switches and context switches.
• Compare to loadable modules used by
some operating systems today.
Safety
• Safety is provided by a trusted compiler.
• Written in Modula-3, the compiler is trusted to
generate “safe” code.
• User extensions are prevented from accessing
protected areas of memory
– It allows one module to access another only through
the defined interface.
– It provides “type safety”, such as checking for array
indexing errors, preventing pointers from referencing
objects of the wrong type, limiting features that are
error-prone.
Dynamic Call Binding
• Events activate the execution of an
extension (think of interrupt processing or
exception processing)
• Applications are allowed to define
handlers for the event.
– Procedures that process the event.
• Extensions are registered with a central
dispatcher and can be executed with the
overhead of a procedure call once linked.
Summary - SPIN
• SPIN developers claim it enables
extensibility without compromising safety
or performance
• SPIN provides a set of core services for
managing system resources
• Extensions allow applications to modify or
replace the core services
• Extensions are supported by co-location,
enforced modularity, logical protection
domains, and dynamic call binding.
Summary - ExoKernels
• Exokernels are responsible for resource
allocation/protection, user applications are
responsible for resource management.
• Exokernel primitives can be implemented
efficiently because they are simple
– Low-level multiplexing of hardware is fast.
• Library OSs enable applications to create
appropriate abstractions.
• Secure bindings provide protections
Overview of Kernel Architectures
• Microkernel
– Provides a few basic abstractions
– User level servers implement most functions
• Exokernel
– No abstractions; provides access directly to resources
– User level library OS’s implement all functions
• SPIN
– Provides traditional core OS services, but allows user
applications to modify them through “extensions”,
which essentially extend the basic system call
interface
Links
• http://www.cs.cornell.edu/courses/CS6410/2011fa/lectures/08extensible-kernels.pdf
• http://linux.softpedia.com/get/System/OperatingSystems/Kernels/DEX-Extensible-Operating-System-16531.shtml
• http://freshmeat.net/projects/dex-os/
• http://freshmeat.net/projects/dex-os/
• http://en.scientificcommons.org/42827731
• http://infoscience.epfl.ch/record/55749/files/00595179.pdf
Reading Assignment for Next Class
• Chapter 1 of the textbook