Transcript Single Address Space Operating Systems

Single Address Spaces
and
Single Address Space Operating Systems
Donald S. Miller
Computer Science and Engineering Department
Arizona State University
7/7/2015 12:16:28 PM
ASU 64-bit OS Group
1
OUTLINE
•
•
•
•
•
•
•
•
•
•
•
•
•
•
Introduction to Single Address Space Operating Systems
What is a Single Address Space?
What is a Single Address Space Operating System (SASOS)?
Characteristics of a Single Address Space
Advantages that can be provided by a SASOS
Why build a SASOS now?
Essence of the Single Address Space Paradigm
SASOSs vs. Process-Oriented OSs - a more detailed look
SASOSs with and without Additional Hardware Support
Motivation for Hardware Support for a SASOS
SASOS Applications
Current Technology Trends that Favor a HW-Supported SASOS
SASOS Disadvantages
Summary
7/7/2015 12:16:28 PM
ASU 64-bit OS Group
2
Process-Oriented Operating Systems
(Multiple Address Space Operating Systems)
and
Single Address Space Operating Systems
(SASOSs)
• Process-Oriented operating systems
– Multiple virtual address namespaces
– Unix® , NT™ , MVS
• Single address space operating systems
– Single VA namespace
– Opal, Mungi, Grasshopper, Monads, AS/400, Sombrero
• SASOSs feasible nowadays because of 64-bit CPUs
• Paradigm is different
7/7/2015 12:16:28 PM
ASU 64-bit OS Group
3
Why Single Address Space Operating Systems?
• Recent 64-bit Microprocessors have made an 18.4
Quintillion Byte Address Space Potentially Available
• Current Process-Oriented Operating Systems and
Processor Page-based Protection HW are Designed to
Conserve Virtual Addresses by Reusing them
• These Facts have led to Investigations of Alternative
Operating System and Processor Architecture Models
• One such Model is to establish a Single Address Space in
which all code and data reside and then Design an
Operating System Specifically to run in this Environment
• These Single Address Space OSs are called SASOSs
7/7/2015 12:16:28 PM
ASU 64-bit OS Group
4
Characteristics of a Single Address Space
• Virtual Addresses can be permanently and uniquely bound to
all code and data objects
– VAs can serve as unique names
– VA space can serve as the only namespace
• The Virtual Address namespace spans all levels of the storage
hierarchy on every node
– All Physical storage can be viewed as a hierarchy of caches for the
contents of virtual addresses
• The Virtual Address namespace is manipulated directly by the
CPU and access to it is controlled directly by memory and
protection management hardware
– the CPU can directly enforce principal protection and resource
allocation access policies on all objects defined in the system as it
manipulates virtual addresses
7/7/2015 12:16:28 PM
ASU 64-bit OS Group
5
Advantages that can be Provided by a SASOS
• Address translations remain the same for all programs
• Threads are free to travel throughout the VA space with no
changes in the environment in which they are running in
except for protection context
• Network-wide communication requires no prior or
additional setup
• Internal pointers and pointers into other objects remain the
same across all levels of storage and all programs
– marshalling, flattening and dynamic linking not needed
• Persistence without use of a separate file system
• Protection by restricting what a computation is allowed to
access rather than what it is allowed to address
– managing IPC is reduced to managing protection
7/7/2015 12:16:28 PM
ASU 64-bit OS Group
6
Advantages that can be Provided by a SASOS
(continued)
• SASOSs increase the available choices
– for structuring applications
– for structuring the operating system
– for sharing, protecting and storing data
– for communication between programs
• Fundamental Issue - how to structure an OS to provide
– a simple program development environment
– high performance
in a system where conserving address space is no longer a
driving concern
7/7/2015 12:16:28 PM
ASU 64-bit OS Group
7
Why build a SASOS now?
• What’s changed?
• What’s the reason for building a SASOS?
• Why aren’t people building them?
7/7/2015 12:16:28 PM
ASU 64-bit OS Group
8
What’s Changed?
• 64-bit RISC processors are available.
 a paradigm shift to single address space operation
is possible
• Modern software has become increasingly
large and complex
 increased SW engineering efforts are needed to
reduce the costs of program development
• Performance increases from reducing chip
feature sizes will begin to decline in about 10
years
 Increased performance will have to come from
architectural changes
7/7/2015 12:16:28 PM
ASU 64-bit OS Group
9
What’s the reason for building a SASOS?
• Reducing the costs of program development
– simpler mechanisms to support sharing and
communication between programs
• common naming mechanisms
• system level support for OOD and OOP
• Higher performance
– gains from architectural changes
• Increased support for distributed applications
– Object-oriented DDBMS systems
– CAD/CAM systems
– Distributed parallel computations
• Better match to needs of real-time applications
7/7/2015 12:16:28 PM
ASU 64-bit OS Group
10
Why aren’t people building them?
• Going from multiple to single address spaces is a
paradigm shift -there are costs associated with the
following in a single address space
– Understanding the paradigm shift
– Learning programming differences
– Mastering new approaches to HW/SW design
• The CPU protection hardware necessary to make a
SASOS viable introduces incompatible hardware
– new software may not run on the old hardware
– old software will not be able to take advantage of new HW
 consequent initial economic disadvantages.
7/7/2015 12:16:28 PM
ASU 64-bit OS Group
11
The Multiple to Single Address Space
Paradigm Shift
• PARADIGM  Constellation of beliefs, values, techniques
and so on shared by the members of a given community
that implicitly define the legitimate problems and methods
of a research field for succeeding generations of
practitioners1
• Shifting from multiple address spaces to a single address
space constitutes a paradigm shift
– brought about because in a single address space the set of virtual
addresses can be used as a system-wide namespace
So - What’s a namespace?
____________________
1. The Structure of Scientific Revolutions, 3rd Edition, Thomas S. Kuhn, University of Chicago Press, 1996.
7/7/2015 12:16:28 PM
ASU 64-bit OS Group
12
Names, Namespaces and Single Address Spaces
• A name is a string that identifies an object.
• A binding is a mapping between a name and an object.
• A namespace is a set of bindings of names to objects.
Alternatively, it’s a domain of possible names.
• Namespaces include file names, IP numbers, port
numbers and addresses in a virtual address space.
A single address space is one namespace that consists
of the entire range of virtual addresses. Each virtual
address is unique and is permanently bound to a byte
of a data object.
7/7/2015 12:16:28 PM
ASU 64-bit OS Group
13
Essence of the Multiple to Single Address Space
Paradigm Shift
Going from multiple namespaces in which object names can
vary and are determined by the logical structures
they are associated with, e.g., process, file or
record, or by the physical container that holds
them, e.g., cache, RAM or disk
Going to
a single network-wide namespace in which object
names are invariant and are determined by the
unique virtual addresses used to access them
Since VAs are directly operated upon by CPUs, the focus
shifts from naming objects by the changing logical or
physical structures associated with them to using VAs as the
primary identifying/locating /accessing mechanism for all
objects wherever they are and whenever they are used.
7/7/2015 12:16:28 PM
ASU 64-bit OS Group
14
Single Address Space vs.Multiple Address Space
Paradigms
Two sets of distinguishing characteristics
• Features that differentiate between all
SASOSs and process-oriented operating
systems
• Additional features that differentiate
between HW-supported SASOSs and
SASOSs built on stock RISC processors
7/7/2015 12:16:28 PM
ASU 64-bit OS Group
15
Single Address Space vs.Multiple Address Space
Paradigms
Process-Oriented OSs
•Each process runs in it’s own VA
Program VA
space on a single node - VAs are
Space
context dependent
Binding of •Process boundaries encapsulate
and bind temporary VA spaces,
Major
Abstractions execution state, objects, protection
domains and principals
Persistent •Persistent storage is in a separate
namespace - the file system
Storage
•Threads encapsulated within a
process - domain crossing and
Thread
Mobility machine migration without an
address space or thread context
switch essentially impossible
7/7/2015 12:16:28 PM
SASOSs
•All programs run in the same VA
namespace which spans all nodes VAs are not context dependent
•Execution state, objects, protection
domains and principals are not
bound to VAs and hence not bound
to each other
•Persistent storage is also in the same
virtual address namespace
•Threads can travel throughout the
virtual address space without an
address space switch or a thread
context switch
ASU 64-bit OS Group
16
Single Address Space vs.Multiple Address Space Paradigms
(continued)
Process-Oriented OSs
•Message-based communication
Data Exchange or RPC on top of message
passing is frequently required
and
Synchronization for data exchange and
synchronization
•IPC using shared memory
Shared
requires prior and additional
Memory
setup and mapping
Server
Options
Task and
Data
Migration
7/7/2015 12:16:28 PM
SASOSs
•Shared memory is the most
prevalent mechanism for data
exchange and synchronization
•No prior or additional setup
necessary for programs to
communicate using shared
memory
•Servers must be active
•Servers can be active or passive
•Task and data migration is
difficult - involves creating a
new namespace for data (DSM)
and dealing with distinct
machine namespaces for code
•Task and data migration is
straight-forward - objects and
threads exist at the same virtual
addresses on all nodes
ASU 64-bit OS Group
17
Software SASOSs vs. Hardware Supported SASOSs
• Software
– Use stock 64-bit RISC processors
– Require additional software communication
protocols for protection
– Examples: Opal, Mungi, Grasshopper
• Hardware supported
– Require additional CPU hardware for
protection
– Examples: AS/400, Monads, Sombrero
A HW-supported SASOS can take fuller advantage
of single address space characteristics.
7/7/2015 12:16:28 PM
ASU 64-bit OS Group
18
DESIRED PROTECTION
HARDWARE FUNCTIONALITY
• Separation of Address Translation and Address
Protection Functions
• Hardware Caching of Allowed Protection Domain
Crossings
• Protection Domains for Threads Distinct from the
General Protection Context
• Implicit Domain Crossing using Ordinary
Instructions
• Protection for Variable Granularity Object Sizes
7/7/2015 12:16:28 PM
ASU 64-bit OS Group
19
SASOSs on Stock Processors
vs.
SASOSs with Additional CPU Protection Hardware
SW SASOSs
HW-Supported SASOSs
System •Obtaining system services requires a •Obtaining operating system services
is orthogonal to entry into privileged
Services domain crossing AND entry into
privileged supervisor mode
supervisor mode
Operating•Layered system structure - operating
System system kernel, executive services and
Structure user-level servers layered on top of
each other
•System architecture can be flat and
modular - OS services, environment
servers and user-level programs
accessible to each other via ordinary
procedure calls
OOD •Direct support for OOD and OOP is • OOD and OOP can be directly
and
difficult - preprocessors and run-time supported - an object class can be
OOP
implemented directly as a protection
systems
are
needed
Support
domain and a server as an instantiation
of the class; base classes can be
extended via user-level overrides
7/7/2015 12:16:28 PM
ASU 64-bit OS Group
20
SASOSs on Stock Processors
vs.
SASOSs with Additional CPU Protection Hardware (continued)
SW SASOSs
HW-Supported SASOSs
•Copy set replication and
Replication consistency management is usually
Management
page based and requires broadcasts
reducing scalability
Fault •Network-wide fault tolerance can
Tolerance require additional mechanisms
Object •Page-based object granularity
Granularity
Privilege
Level
for Basic
Services
Protection
Policy and
Implement
ation
•Access authorization, resource
accounting and name services
typically require kernel services or
intervention
•OS support for protection policy
and protection implementation are
intertwined
7/7/2015 12:16:28 PM
•The common VA space enables
simple scaleable per-object copy set
replication and consistency
management
•Naturally provides a lowest level
cache for fault tolerance
•Object granularity can be
independent of page granularity
•Access authorization, resource
accounting and name services can be
done at user level
•Clean separation of OS support for
protection implementation and userlevel definition of protection policy
is simple
ASU 64-bit OS Group
21
Motivation for HW support for a SASOS
Additional CPU-resident protection HW is
essential to obtain
•A considerably improved program
development environment
•Much greater performance
•Better support for distributed applications
Because it makes fuller use of the properties of
a single address space to provide protection,
resource access and control transfer.
7/7/2015 12:16:28 PM
ASU 64-bit OS Group
22
Protection, Resource Access and Control Transfer
HW-Supported SASOSs vs. SASOSs Built on Stock RISC Processors
(Sombrero, AS/400 and Monads vs. Opal and Mungi)
• Centralized kernel-resident data structure
for protection triples vs. capabilities
• Single inverted page table at the memory
bus vs. multiple per-PD page tables
• Carrier protection domain vs. proxy/guard
and PD-extension for domain crossings
• Direct support for object-oriented program
development environment
• Implicit PD crossing at EVERY level
7/7/2015 12:16:28 PM
ASU 64-bit OS Group
23
Differences between HW-Supported SASOSs
(Sombrero vs. AS/400 and Monads)
• Flat 64-bit address space - no segments
• No HW memory tagging or additional CPU
instructions for capability and tag mgmt
• Network-wide single address namespace
• Single CAM-based inverted page table
• Simple extensible executive
• Availability of all single address space
property advantages to applications
7/7/2015 12:16:28 PM
ASU 64-bit OS Group
24
SASOS Applications
• Object-oriented distributed database
management systems
• Multiple database/multiple programming
model applications, e.g., CAD/CAM
• Distributed parallel computations
• Real-time systems
7/7/2015 12:16:28 PM
ASU 64-bit OS Group
25
‘Killer Ap’
To succeed a SASOS needs a Killer Application
• Must benefit from SASOS advantages
– common unique and permanent naming scheme
– communications support for numerous large
program modules
– sharing and protection support for a huge
distributed database
• It must be widely used and currently costly
Most likely candidate: Object-Oriented DDBMS
7/7/2015 12:16:28 PM
ASU 64-bit OS Group
26
Current Technological Trends that Favor a
Hardware-Supported SASOS
Trend
Advantage
• Increasing costs and difficulties
reducing CMOS chip feature
sizes below 0.1 micron
• Increased performance will
have to come from architectural
changes such as shifting to
single address space operation
• Large on-chip virtual caches
can enable higher performance,
and replacing TLB with a
single CAM-based inverted
page table at the memory bus
• Accessing code and data from
remote node has additional
advantage of not needing to be
remapped
• Increasing disparity between
CPU cycle times and RAM
access times and increasing chip
real-estate
• Decreasing ratio of inter-node
access time to disk access time
plus large local memories
7/7/2015 12:16:28 PM
ASU 64-bit OS Group
27
Current Technological Trends that Favor a
Hardware-Supported SASOS (continued)
Advantage
Trend
• Huge and inexpensive local
RAM memories - 128MB and
above
• Huge and inexpensive local
disks -  8 gigabytes
• Multicast-oriented networks,
e.g., ATM
7/7/2015 12:16:28 PM
• Local caching of services
leading to greater advantages
from thread mobility using
passive servers
• Local caching of persistent data
leading to greater advantages
from not having to “flatten”
data between disk and core
when files are replicated
• SASOS distributed copy set
management and VA space
distribution facilitated by
multicasts
ASU 64-bit OS Group
28
SASOS Disadvantages
• SASOSs built on stock 64-bit processors
– Programming and performance improvements
insufficient to overcome design, development
and software engineering costs associated with
shifting to the new paradigm.
• HW-Supported SASOS
– To make the shift to the single address space
paradigm worthwhile requires additional CPUresident HW causing:
• Backwards HW and SW incompatibilities
• Programming differences
• Mastering new approaches to HW/SW design
7/7/2015 12:16:28 PM
ASU 64-bit OS Group
29
Summary
• Advantages of a HW-Supported SASOS
– Improved program development environment
– Higher performance
– Better support for distributed applications
– A better match to the needs of real-time systems
CPU-resident protection hardware and a SASOS
that runs on it can be implemented now. This
combination makes fuller use of the properties of a
very large address space than contemporary
process-oriented systems for both single node and
distributed systems.
7/7/2015 12:16:28 PM
ASU 64-bit OS Group
30