Transcript Single Address Space Operating Systems

The Sombrero
Single Address Space Operating System
Donald S. Miller
Computer Science and Engineering Department
Arizona State University
7/7/2015 12:16:00 PM
ASU 64-bit OS Group
1
OUTLINE
• Review - Characteristics of a Single Address Space
Advantages that can be supplied by a SASOS
• Sombrero Project Basic Premises
• Sombrero Key Features
• Sombrero Design Overview
–
–
–
–
–
–
•
•
•
•
•
•
Basic Abstractions
Hardware Design
Software Protection Data Structures
Operating System Structure and System Architecture
Distributed System Design
Support for Object-Oriented Programming and Design
Sombrero vs. SASOSs built on stock RISC Processors - Opal & Mungi
Sombrero vs. other HW-Supported SASOSs - Monads & AS/400
Sombrero Prototype Status
Sombrero-II Architecture
Future Work
Summary
7/7/2015 12:16:00 PM
ASU 64-bit OS Group
2
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:00 PM
ASU 64-bit OS Group
3
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:00 PM
ASU 64-bit OS Group
4
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:00 PM
ASU 64-bit OS Group
5
ed to
7/7/2015 12:16:00 PM
ASU 64-bit OS Group
6
Sombrero Project Basic Premises
• Economic and technological tradeoffs will
increasingly favor single address space
operation and SASOSs within ten years.
• It is necessary to make changes to CPUresident protection and memory management
hardware in order to design a SASOS that
makes the paradigm shift viable.
• This hardware is feasible now and so is a
SASOS built on it.
7/7/2015 12:16:00 PM
ASU 64-bit OS Group
7
Sombrero - Key Features
• CPU-resident hardware protection
– provides a substrate for simpler/faster protection
domain and object operations
• An open and extensible architecture that provides
more choices for system structure
• Network-wide transparent distribution of the
single address space
• Direct system level support for OOD and OOP
• No TLB required - can be replaced by a single
CAM-resident inverted page table at the memory
bus
7/7/2015 12:16:00 PM
ASU 64-bit OS Group
8
Sombrero Design Overview
•
•
•
•
Basic Abstractions
Hardware Design
Software Protection Data Structures
Operating System Structure and System
Architecture
• Distributed System Design
• Support for Object-Oriented Programming and
Design
7/7/2015 12:16:00 PM
ASU 64-bit OS Group
9
BASIC ABSTRACTIONS
•Memory Object  Characterized by Range - a Distinct Variable Sized
Contiguous Allocation of the Virtual Address Space - contains Memory Regions,
sets of Virtual Addresses within a Range with Non-Overlapping Protection
Attributes.
•Protection Domain  Set of Memory Objects and Protection Domains Reachable
by a Thread executing within it and their Associated Access Permissions. There
are General and Carrier Protection Domains (GPDs and CPDs).
– GPD: Code, Data and other GPDs accessible to all threads within it
– CPD: Data and GPDs privately accessible to an Individual Thread
•Thread  State of a Computation Represented by Current or most Relevant CPU
Register State (PC, SP, General Registers, etc.), Reachable Carrier Protection
Domain Memory and Status Information.
•Principal  Unique Protected Identity that Represents a User or a System Service
- binds Resources and Activities to an Owning User.
7/7/2015 12:16:00 PM
ASU 64-bit OS Group
10
Sombrero Principals
7/7/2015 12:16:00 PM
ASU 64-bit OS Group
11
HARDWARE DESIGN
Sombrero RPLB
Range Protection Lookaside Buffer
• Functional Requirements
• Logical Design
• RPLB VLSI Synthesis
7/7/2015 12:16:00 PM
ASU 64-bit OS Group
12
FUNCTIONAL REQUIREMENTS
• 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:00 PM
ASU 64-bit OS Group
13
RPLB Logical Design
• Ranges and Regions
• Intra-Domain Operation
• Cross-Domain Operation
The RPLB stores co-located protection triples:
<Accessing PD, Accessed Resource, Access Rights>
where the PD and resource are represented by VAs
7/7/2015 12:16:00 PM
ASU 64-bit OS Group
14
RPLB LOGICAL DESIGN
• A Range is a
contiguous set of VAs
MATCH MASK
RANGE FUNCTION on 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0
• Unit of Protected
DON’T CARE MASK
and 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1
Resource Access is
RANGE MASK
Produces
0 0 0 0 1 1 0 d 1 d d d d d d d
Called a Region
where d is 0 or 1.
– Possibly noncontiguous set of VAs
within a Range
– Non-overlapping
Protection Attributes
from {rwxs}
• A Range Contains one
or more Regions
7/7/2015 12:16:00 PM
0H
CH or DH
80H - FFH
The RPLB Stores Region Definitions
• When Loaded with a Match Mask and a
Don’t Care Mask, Internal Combinational
Logic Produces a Range Mask that
Defines a Region
• The Figure shows the Definition of a
Region consisting of
0C80H - 0CFFH and 0D80H - 0DFFH
ASU 64-bit OS Group
15
RPLB Intra-Domain Operation
PROTECTION DATA
STORED IN REGION
CONTROL BLOCK (RCB)
RPLB STORED
LOGICAL
INFORMATION
CPU EMITTED
DATA
MATCH MASK
DON’T CARE
MASK
RANGE MASK
CURRENT VIRTUAL ADDRESS
GPD
or
CPD
GPD
or
CPD
GPDBR
ACCESS
RIGHTS R|W|X|S
ACCESS RIGHTS
R|W|X|S
ATTEMPTED
ACCESS TYPE
or
CPDBR
Data loaded from an
RCB into RPLB on an
RPLB miss
The Range Mask is
generated from the
RCB stored data at
RPLB load time
The Current CPU Virtual
address, protection
domains and attempted
access are compared to
the RPLB stored logical
information during
instruction execution
• On a Miss the RPLB is loaded with Protection Triples:
<Accessing PD VA, Accessed Region VA, Access Rights>
• These are Compared with CPU Emitted Data On Every Memory Reference
to Determine whether the Access is Allowed.
7/7/2015 12:16:00 PM
ASU 64-bit OS Group
16
RPLB Cross-Domain Operation
RPLB STORED
SWITCH ADDRESS
CPU EMITTED
DATA
SWITCH
ADDRESS
GPD
or
CPD
NEW GPD
NAME
CURRENT VIRTUAL ADDRESS
GPDBR
Data loaded from an
Access Descriptor
into RPLB on an
RPLB miss
ACCESS RIGHTS
R|W|X|S
ATTEMPTED
ACCESS TYPE
or
The Current CPU Virtual
Address is compared to
the RPLB stored switch
address during
instruction execution
CPDBR
•On a Miss the RPLB is loaded with Protection Triples:
<Accessing PD, Accessed PD Entry Point VA, Switch Access Right>
+ the New Protection Domain Virtual Address Name
• These are Compared with CPU Emitted Data On Every Non-Local
Memory Reference to Determine whether the Entry is Allowed.
• For Allowed Accesses, the New GPD VA Name is Stored in the
GPDBR and this is Followed by an Intra-Domain Access Attempt
7/7/2015 12:16:00 PM
ASU 64-bit OS Group
17
RPLB VLSI Synthesis
• Proof of Concept - 1995
– VHDL Simulation
– Mentor Design Tools
– ASU ULSI Laboratory
• Performance Estimate-1997
– Mentor Autologic II Synthesis Tool
– Synopsis Design Compiler
– Cascade Design Automation Static
Timing Analyzer
• Timing and Size Results
– Timing - 8-entry buffer
• single location - 500 MHz
• entire RPLB - 250 MHz
– Size - 1.27 mm2
• Conclusion
RPLB Architecture Synthesized with Synopsis
Design Compiler Using 0.35-micron Library
-- 500 MHz Pipelined Design Feasible
7/7/2015 12:16:00 PM
ASU 64-bit OS Group
18
Software Protection Data Structures
• Control Blocks
• Protection and Resource Access Lists (PRALs)
– Protection domain Access Lists (PALs)
– Resource Access Control Lists (RACLs)
• PRAL Simulation
7/7/2015 12:16:00 PM
ASU 64-bit OS Group
19
Control Blocks
• Memory Object Control Block (MOCB)
• Protection Domain Control Block
– General PD Control Block (GCB)
– Carrier PD Control Block (TCB)
• Access Descriptor (AD)
• Principal Control Block (PCB)
• Token Tracking Structure
7/7/2015 12:16:00 PM
ASU 64-bit OS Group
20
Protection and Resource Access Lists
GCB 1
PRALs contain the
data needed to
convert between user
policy information in
the form of
principals, resources
and access rights and
the CPU
representation of
these things in the
form of protection
domains, virtual
addresses and access
privileges.
7/7/2015 12:16:00 PM
PAL
AD for
G-1 M-1
AD for
G-1 Sw-2
AD for
G-1 M-2
.....
MOCB 1
RACL
RACL
GCB 2
PAL
MOCB 2
AD for
G-2 M-1
AD for
G-2 M-3
AD for
G-2 Sw-1
.....
RACL
RACL
MOCB 3
TCB 1
PAL
AD for
T-1 M-2
AD for
T-1 M-3
AD for
T-1 Sw-2
.....
RACL
LEGEND:
AD for G-i (T-i) M-j  Access Descriptor containing:
1. Access rights of GPDi (CPDi) to MOj
2. Entry in MOj's ACL for GPDi (CPDi).
AD for G-i (T-i) Sw-j  Access Descriptor containing:
1. Entry right of GPDi (CPDi) to GPDj and GPDj entry address
2. Entry in GPDj's ACL for GPDi (CPDi).
ASU 64-bit OS Group
(a)
21
Resource Access Control Lists
GCB 1
PAL
AD for
G-1 M-2
AD for
G-1 M-1
MOCB 1
RACL
RACL
GCB 2
PAL
MOCB 2
AD for
G-2 M-1
AD for
G-2 M-3
RACL
RACL
MOCB 3
TCB 1
PAL
AD for
T-1 M-2
AD for
T-1 M-3
RACL
A view of the PRAL drawing extracting the MOCB RACLs.
RACLs are classical Access Control Lists
7/7/2015 12:16:00 PM
ASU 64-bit OS Group
22
Protection Domain Access Lists
GCB 1
PAL
AD for
G-1 M-2
AD for
G-1 M-1
MOCB 1
RACL
RACL
MOCB 2
RACL
MOCB 3
TCB 1
PAL
AD for
T-1 M-2
AD for
T-1 M-3
RACL
A view of the PRAL drawing extracting an example of a GCB PAL and a TCB PAL for the
MOCBs. The Switch ADs are excluded for clarity.
PALs contain the same fundamental protection
information held by classical capability lists
7/7/2015 12:16:00 PM
ASU 64-bit OS Group
23
PRAL Simulation
• Compared performance of Sombrero
RPLB + PRAL vs. Alpha NT TLB + Page Tables
• Virtually everything had to be simulated
Simulation Driver/RPLB/PRAL/TLB and Page Tables
• Parameters: Number of Protection Domains
(Threads) and Number and Size of Objects
• Results
– RPLB miss penalty on average 2 times TLB miss penalty
– RPLB miss rate lower than TLB miss rate for many
common scenarios (e.g., objects greater than a page)
– RPLB performance roughly comparable to TLB
performance and better for larger objects
7/7/2015 12:16:00 PM
ASU 64-bit OS Group
24
Open and Extensible Architecture
• Peer-level modular system structure: Executive provides a
few basic services - user servers provide the rest.
Operating system service methods can be overridden by
user-defined function implementations.
• Communication between application programs, user
servers and executive services via ordinary procedure call
and return.
• OS services provided by instantiations of classes that are
implemented directly as protection domains.
• Services can be passive  significantly reduced IPC costs
• Pico-kernel (the CPU’s protection domain) handles
redirections caused by HW privilege mode changes and a
very few hardware-related operations.
• Thread mobility and upcalls enable a cleaner separation of
user policies and OS mechanisms
7/7/2015 12:16:00 PM
ASU 64-bit OS Group
25
Sombrero Architecture
User Programs
Sombrero
Services
Interface
Operating Environments
Sombrero Services
Kernel Protected Instructions
(a)
Unix
Environment
User
program
Protection
services
VA space
services
Window
package
Executive
7/7/2015 12:16:00 PM
Name
server
Sombrero
Services
Interface
pk
Thread
services
Physical
resource
mgmnt.
(b)
ASU 64-bit OS Group
Sombrero
Environment
Privileged
instructions &
HW event
sensing and
redirection
(a) Traditional View
(b) Peer-Level Domain view
26
Open and Extensible Architecture
(summary)
• The hardware in a HW-supported SASOS
can make use of the properties of a single
virtual address namespace to support
common referencing between programs.
• This frees the OS of having to perform this
time consuming operation at run-time and
allows alternative system structures that
provide more programmer-friendly ways to
obtain system services.
7/7/2015 12:16:00 PM
ASU 64-bit OS Group
27
Network-wide Transparent Distribution
of the Single Address Space
• Memory object, thread and protection domain
migration supported by distributed surrogate kernel
data structures enabled by tokens
• Transparent and implicit consistency and concurrency
policy - every VA is tied to a specific policy
• Granularity of data transmission determined by policy
• Copy-set management uses local data/minimizes
broadcasts
• Network routers use virtual addresses
7/7/2015 12:16:00 PM
ASU 64-bit OS Group
28
Distributed Object Copy Set Management
Last Known Writer Pointer
N1
W
writee
N4
N3
N2
Last Known Writer Pointer
W
N5
N2
N1
Last Known Writer Graph
N1
N3
N4
W
N5
N4
N5
B
A
N2
N3
Pruning of Last Known Writer Graph
W
N6
N1
N2
N3
N4
N5
W
N1
N2
A
The Modified Page Cache Graph: N5 currently holds the write
enabling token W which originated at N1. N6 is attempting to
read the Memory object.
N3
N4
N5
B
Pruning of Modified Page Cache Graph
Modified Page Cache Graph
CS
owner
CS
1st
CS
3rd
7/7/2015 12:16:00 PM
CS
2nd
CS
5th
CS
4th
ASU 64-bit OS Group
A Copy Set graph for a
Control Block with an
arity of two with the
owner node as its root.
CopySet Graph
29
Direct System Level Support for
Object-Oriented Design and Programming
• An object class can be implemented directly as a
protection domain and a server as an instantiation
of the class; executive base classes can be
extended via user overrides.
• Servers can be passive - exported service entry
points invoke methods. These are accessed with
ordinary procedure call instructions.
• Modular, peer level relationship between
applications and user and system servers
• Hardware protection provides encapsulation.
7/7/2015 12:16:00 PM
ASU 64-bit OS Group
30
Sombrero vs. SW- Supported SASOSs
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:00 PM
ASU 64-bit OS Group
31
Sombrero vs. HW-Supported SASOSs
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:00 PM
ASU 64-bit OS Group
32
Sombrero Prototype Status
• Prototype being developed on two Alpha 21164 boxes
running NT
• NT Alpha PALCode modified to specialize an NT
process to include full address range
• TLB misses outside normal address range forwarded to
Sombrero extension of PALCode
• Emulated RPLB triggered by TLB misses
• Threads assigned to PDs within the specialized process
• NT provides basic I/O and file facilities
• First prototype, proof of concept and performance
extrapolations expected before December 1998.
7/7/2015 12:16:00 PM
ASU 64-bit OS Group
33
Sombrero II Architecture
Completely peer-level system structure
SCSI bus
access
service
Interrupt
Vector
Policy
User 2
User
1
Protection
Service
SBCM
Video
driver
System and User Modules
Hardware Layer
FPU
Interrupt management
MMU including RPLB
Other CPU registers
• Kernel Services distributed among executive protection domains
• No central kernel and no hardware protected kernel mode
• A few Protection Domain Lock Registers name the protection domain that can
access sensitive protected instructions and registers
7/7/2015 12:16:00 PM
ASU 64-bit OS Group
34
Future Work
(a.k.a. Things not completely worked out yet)
• Implementation of a Universal Protection
Domain
– needed to reduce RPLB entries
• Mini-System Call/Vectored Exception
Mechanism for Sombrero II
– needed for high speed executive protection
domain communication
7/7/2015 12:16:00 PM
ASU 64-bit OS Group
35
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 network-wide
address space than contemporary process-oriented systems
for both single node and distributed systems.
The Sombrero SASOS and Sombrero RPLB are
Designed to Meet these Objectives
7/7/2015 12:16:00 PM
ASU 64-bit OS Group
36