Transcript Berkeley NOW

Operating System Architecture for
Incredibly Diverse Devices
David Culler
http://www.cs.berkeley.edu/~culler
U.C. Berkeley
Expeditions Meeting
8/16/1999
Away from the ‘average’ Device
Massive Cluster
Clusters
Gigabit Ethernet
Server
Client
Scalable, Available
Internet Services
Info. appliances
8/16/99
Expeditions Diverse OS
2
Convergence at the Extremes
• Powerful Services on “Small” Devices
– massive computing and storage in the infrastructure
– active adaptation of form and content “along the way”
• Extremes more alike that either is to the middle
– More specialized in function
– Communication centric design
» wide range of networking options
– Federated System of Many Many Systems
– Hands-off operation, mgmt, development
– High Reliability, Availability
– Scalability
– Power and space limited
– simplicity
• They have to “work or die!”
8/16/99
Expeditions Diverse OS
3
Body of Work in the Very Large
• Academic: metacomputing, computational grid
– Glunix (UCB), Globus(ANL), Legion (UVA), IPG (NASA),
Harness, NetSolve, Snipe (UTK), EMOP, Apples, Cactus, MetaChaos, ...
• Commercial
– LSF
8/16/99
Expeditions Diverse OS
4
Dominant thrust: Glue over big OS
• Nodes a full OS and Institutional structure
– accounts, authentication, resources, execution, storage,
policy
• User constructs a personal virtual machine
spanning numerous, potentially diverse
resources
– mapping from uniform metasystem mechanisms to site
specific mechanism
» naming, authentication, transparent execution, storage,
scheduling
– uniform, multiprotocol communication mechanism
• “Many nodes in a net”, not “Unix on Steroids”
– mgmt is fundamental problem, but still unadressed
8/16/99
Expeditions Diverse OS
5
And in the small...
• Academic
– microkernels, Exokernel, OSKit, ucLinux, ELKS,
• Commercial
– PalmOS, PSION, GeoWorks, WinCE, Inferno, QNX, VxWorks,
javaos, chorusOS, BeOS,
– jini, corba, dcom, ...
=> tracks the 80386
– when it becomes ~ 1990 PC Unix will run on it
8/16/99
Expeditions Diverse OS
6
Small OS Dominant thrust
• Unix on a diet + real time seasoning
• Microkernel finally works on small devices
– ability to remove components (modularity) + fault boundaries
more important than performance
– legacy applications less dominant
8/16/99
Expeditions Diverse OS
7
Design Issues for “Small Device OS”
•
•
•
•
•
•
•
•
Managing address spaces
Thread scheduling
IP stack
Windowing System
Device drivers
File system
Applications Programming Interface
Power management
8/16/99
Expeditions Diverse OS
8
Core Questions
• What are the principles of design for tiny
operating systems?
– How are they different from a desktop or server?
• Where should we look for ideas and experience?
• How can operating systems be made radically
simpler?
• How should we proceed with the investigation?
8/16/99
Expeditions Diverse OS
9
1st Stab at Principles for Simple OS
• Communication is fundamental
– treated as part of the hardware. No comm is like no power
– you don’t bring up the device then “configure comm.”
• hands off: a direct “user interface” is the
exception not the norm
– typical device has a network on one side + sensor/actuators
on the other
» buttons and display a special case
– all deployment, development, configuration, mgmt,
programming, is through the communication interface
• schedule data movement, not arbitrary threads
of computation
• constant self-checking and telemetry
– rely on the infrastructure for hard stuff
8/16/99
Expeditions Diverse OS
10
other places to look for ideas
• Operating systems that are not called “operating
systems”
• eg: modern disk controller
– event scheduler handling stream of commands from network
link, controlling complex array of sensors and actuators,
performing sophisticated calculations to determine what and
when (scheduling and caching) as well as transforming data
on the fly
– automatic connection, enumeration, configuration
Network link:
- EIDE, SCSI
- FCAL, SSA
- USB, 1394
- ???
Complex array
of
Sensors and
actuators
– but several simplifying assumptions must be removed
8/16/99
Expeditions Diverse OS
11
OS as little more than FSM
• Primary focus is scheduling discrete chunks of
data movement
– not general thread scheduling and unlimited memory
management
– there may be a bounded amount of work to xform or check
data
• Commands are an event stream merged with
sensor/actuator events
• General thread must be compiled to sequence of
bounded atomic transactions
– spagetti part of an application is configuring the flows
– steady-state is straight-forward event processing + signaling
unusual events
• Simplify network-based debug and mgmt
8/16/99
Expeditions Diverse OS
12
Adaptation in Flows
• View data transfers as
continuous flows
– plumbing as programming model
– reservoirs provide slack
– trade bandwidth for robustness
• Natural form of adaptation
– ex: faster consumer gets more data
– flow equations provide goal, simple error bounds,
and react
– performance availability
8/16/99
Expeditions Diverse OS
13
Example: streaming output
High water mark => stop input
low water mark => start input
• Events associated with particular configuration
of reservoirs and flows drive operation
scheduling
– hard to effect through queue management and priorities of
threads
8/16/99
Expeditions Diverse OS
14
Availability => Performance availability
10
10
5
7
5
10
5
5
5
5
3
7
3
8
8/16/99
8
2
10
5
5
1
1
8
Expeditions Diverse OS
8
15
Alternative: Comm = Location
independent Access to shared storage
• Key Concepts from Parallel Architecture
– hierarchical composition of cache-coherence protocols +
consistency models
– natural framework for adaptation (pull what you touch)
• Key Extensions
– active elements in the protocol hierarchy
– intermittent connection
– narrow interface with commitment
• Pilot --- RMI Proxy --- Ninja Service Prototype
–
8/16/99
device OS = protocol
engine Diverse OS
Expeditions
16
How to proceed?
• A lot of experience to be gained from the
chopped desktop OS efforts
– same time-to-mkt benefit research prototype
– brings many small, interesting devices on line
– bring Universal Computing Lab on-line (IRDA + 802.11)
• and from meta-OS efforts
• Build simulation environment for bottom-up
development
– currently exploring UCLA GloMo simulator
• Develop ‘always-on’ networking component for
expedition testbed
• Deploy for unusual new devices
– smart boulders -> pebbles -> dust
8/16/99
Expeditions Diverse OS
17