Pilot: An Operating System for a PC

How to design an OS for a personal computer?

Emphasis not on sharing (= fair allocation of resources) or security, but on serving the PC user

	Resource Allocation - efficiency rather than fairness
	Security - errors are more serious than maliciousness
	User convenience like PnP & automount is important - volume
	More aggressive hint from the user can be used - space
	More freedom for user to use system resources - direct device access
	We can't expect hardware level reliability for PC. How about more fault-tolerant file system - each block is absolute and inode becomes hint

Two types of interfaces: public (for client) & private (for internal use)

Representative public interfaces: file, virtual memory, streams, network communication, etc.

Each interface has named items

	Four types of items: type, procedure, constant, error signal
	Denoted as interface.item
	For example: File.Capability, File.Create, File.maxPagePerFile, File.Unknown

File

	Standard containers for data
	Rather low level file system with the expectation of higher level file system on top of it Flat-file structure (no directory hierarchy - ouch!) Few attributes: no creation time, owner, etc.
	264 files, max file size is 232 bytes
	File.Create( ) - create a file and return a capability
	Capability: 64-bit unique id - unique across all pilot machines Works well with removable volumes (e.g. floppy disk)
	Supports only Memory-mapped I/O
	Few attributes: type, size, permanence, immutable
	Size: Adjustable in page-sized units(512 bytes)
	Type: 16-bit tag, but not interpreted within Pilot
	Permanent and Temporary Files
	Immutability Permanently read only file - never changed in any circumstances Make possible to have multiple copies (=replica) with the same file id

Volume

	Represents a media (e.g., magnetic disk) where files are stored
	Very similar to partition in DOS, but single volume - multiple physical media and multiple volumes - single physical medium are possible
	PnP & Automount? Pilot knows coming and going of physical volumes and make the corresponding logical volume accessible Of course when a logical volume spans multiple physical volumes, it becomes accessible only when all those physical volumes have come

Underlying Virtual Memory System

	Linear virtual memory of up to 232 16-bit words
	All computations run in the same address space

Pilot's Spaces on top of underlying VM

	Address space is partitioned into spaces
	Spaces is like segments in Unix multiple pages per space the unit of protection
	Space is a (public) interface

Allocation of spaces: by Space.Create

	The set of all spaces in Pilot forms a tree by containment
	The root space corresponds the whole virtual memory
	New space can only be created as a subspace of existing space

Mapping to file pages: by Space.Map -- remember that only mmap in Pilot

	Map associates a space with a run of pages in a file
	A page in VM may only be accessed if exactly one of the nested spaces containing it is mapped
	The protection to the file is automatically propagated to the mapped space

Swapping in and out: hinted by Space.Activate, Space.Deactivate, and Space.Kill

	The lowest (i.e., the smallest) space of the missing page is swapped in or out
	Programmer can use spaces to put pages together whose access patterns are similar
	Hints to OS Space.Activate - the space will be used soon, so please swap it in Space.Deactivate - the space will not be used for a while Space.Kill - the contents of the space is no longer of interest, so don't even bother swap it out

Tight coupling between files and spaces

	Spaces are the only access path to the contents of files, and files are the only backing store for spaces
	Good idea? Claim: decouples buffer allocation from disk scheduling easy and uniform protection: propagation of file protection to spaces advice to OS becomes possible: Activate, Deactivate, Kill can simulate read/write on map, but read/write can't do reverse
	Space.ForceOut: blocking sync( ) in Unix

Three ways to access I/O devices: implicit, direct, indirect

Direct

	Pilot provides procedure calls, which are just (Mesa) wrapper functions of device-specific I/O operations
	Reasonable, because Pilot is the OS for PC!

Implicit

	Direct access are not allowed for some devices, e.g., disk
	For these devices, pilot provides high level abstraction for I/O: file, etc.

Indirect: Stream

	Direct access is very difficult for most devices
	Pilot provides Stream interface which is pretty much like Java I/O stream
	Transducer converts I/O device interface into a Stream interface
	Filter converts a Stream interface into another Stream interface
	A transducer and a series of filters form a pipeline with the transducer being attached to I/O device

Distinction between "tightly-coupled" processes and "loosely-coupled" processes

Tight - should use shared-memory to communicate (e.g., single-machine parallel program)

Mesa supports monitor and condition variable

Loose - should use Pilot communication interfaces (e.g., print server)

All machines in "Pilot internet" are Pilot machines, even routers

Protocol stacks are pretty much like TCP/IP stack

	Layer 0 - link layer
	Layer 1 - IP layer
	Layer 2 - Transport layer

Interfaces

	Socket - Layer 1 interface: support datagram service
	NetworkStream - Layer 2 interface: support stream service a transducer which converts socket device into a Stream NetworkStream.Create NetworkStream.Listen - listen in TCP NetworkStream.Handle - accept in TCP NetworkStream.Delete - close in TCP actually no tear-down process just delete data structures allocated parties should agree when to terminate communication

Mesa language features: recursion, coroutine, concurrent processes, signal, etc.

Procedure call: Pilot only handles traps which occur when space for activation records are exhausted

Coroutine: Pilot gets involved during initialization

Concurrent processes: Pilot creates processes and handles the termination

World-swap - actually two different machine exist at the same time in Pilot: one for normal execution and one for debugging

	Two worlds are different in: contents of memory version of Pilot accessible volumes even micro code
	Swap between two worlds save the context of the current world in a boot-file resume the execution of the other world by reading the saved context

Pilot is composed of components, which in turn are composed of Mesa modules

Hierarchical structure - they called "manager/kernel" structure with high-level manager being on top of kernel

Storage system is comprised of file-system and VM

Both systems maintains DBs which are too big to fit in memory. So file-system needs VM, and VM needs file-system and VM again. What a knot!

Solution? Layering!

Kernel: swapper & filer

	is small enough to fit in memory
	provides basic but powerful enough functions for full-fledged storage system
	handles majority of application's requests

Manager: file manager & VM manager

implements more powerful functions using functions provided by swapper and filer

Interaction between kernel & manager

	Manager-to-kernel interaction is obvious
	Kernel-to-manger interaction Kernel works only with pages and/or special files resident in memory--cache of VM When it can't work with the cache, it punts to manager. Manager fixes the problem, possibly using another function of kernel, then kernel retries the operation Indirect recursion or circular dependency, huh?

Hierarchy

	DB to implement space
	Maintained by VM manager
	Holds records per space: size, base page #, mapping info, etc.
	Not fit in memory
	Swapper uses resident "space cache" to track swapping info. What if info about a space is not in memory? Interaction between kernel & manager in 3.1

Swap unit cache

	Maintained by swapper
	Swap unit: smallest set of pages moved between memory and backing store
	Logical cache of Projection
	Indexed by page # page fault for a page, then swap in the swap unit containing the page

Projection

	Another swappable DB of all swap units
	Maintained by VM manager

Implementation splits roughly equal among Mesa, underlying machine, and Pilot

Basic monitors and condition variables are implemented by Mesa and machine

Pilot's concurrency support is implemented using those monitors and condition variables

Each file page has a label--separate record that gives info about the page

Which file it belongs to, etc.

Scavenger periodically scans entire volumes and construct map

Map is just redundant fast-lookup database for volumes

Robustness

	Pilot works with maps
	I/O devices compares map records passed by Pilot against page label
	Mismatch of map record and page label indicates the need to scavenge
	Any page damage just means the lost of the page. Remaining pages of the file is still OK!
	Luxurious options like RAID are not common for PC. Then reliability at the OS level. Great Idea!

High-level robustness

Scavenger can callback client software for application-specific checking. For example DB integrity check

Volumes of old Pilot can be easily migrated to newer Pilot

	New scavenger generates new version of map from old volume structure
	New pilot uses the new map generated!

Routers - software switches

Small group (6-8 people), 18 months

24,000 lines of Mesa