Transcript Operating System Architectures - UAH

Operating System
Architectures
Kernel Design
Microkernels
Primary Reference
• “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 process, trusted by kernel
• Advantages: maintainability, flexibility,
modularity
• Problems: 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.
– Other layers not very small
• 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
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)
• Servers are largely hardware independent
• Correctness
– Easier to verify a small kernel
– Servers are isolated; errors in one don’t affect others
Major Disadvantages
of Early Microkernels
• Slow – due to “cross-domain” information
transfers?
– Server-to-OS, OS-to-server IPC is thought to
be a major source of inefficiency
• Much faster to communicate between two
modules that are both in OS
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.
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)
• 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
System calls (mode switch)
Context Switch (process switch)
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)
– Provides general-purpose resource management
algorithms
• System calls define user interface to OS
• 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 may be forced to build
random-access files on top of the OS file
system
• Performance and functionality are limited
• 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 (they will need to be
done again, correctly, at a higher-level)
• 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, not a
specific example.
• They separate resource allocation &
protection (in the kernel) from resource
management (done at user level with userlevel library operating systems)
– Aegis is an example exokernel;
– EXOS is an example library OS.
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; SPIN is a complete OS that
can be modified/extended.
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.
• “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 (extension code linked directly to
kernel code) reduces time lost to mode
switches and context switches.
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
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 enables extensibility without
compromising safety or performance
• It 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 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://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 Thursday
• Topic: Virtual Machine Monitors
• Papers:
– “Virtual Machine Monitors: Current Technology and
Future Trends”, Rosenblum & Garfinkel
You can skip “I/O Virtualization” and skim “What’s
Ahead”
– If time permits:
• “Xen and the Art of Virtualization”, Barham, et al.
Sections 1 & 2, skim section 4 for an idea of how systems are
evaluated, and read section 5
• “Scale and Performance in the Denali Isolation Kernel”, sections
1 & 2.