The Sprite Network Operating System -- Ousterhout etal. 1988
------------------------------------------------------------

Summary: Sprite is an operating system which provides a single
time-shared machine view on top of a network of workstations. Main
contributions include a new (and network-efficient) file system,
extensions to the virtual memory system, and a transparent process
migration mechanism.

------

Motivations for Sprite include: the difficulties in sharing and
administration in a network of machines running independent OSes;
large amounts of main memory in current systems, which allows for
aggressive file-caching; and availability of cheaper multiprocessor
workstations (extensions of uni-processor OSes might not be adequate
for multiprocessors)

System calls very similar to Unix. Interesting features include:
 - multithreaded kernel, and a kernel RPC facility 
 - idea of domains and prefix tables for dynamic and transparent
 reconfiguration (i.e. dynamic automounting) of network file systems
 - server and client side file caching (with cache consistency)
 - I/O devices are attached to files (like Unix), and the file system 
 allows remote I/O devices to be accessed (unlike Unix)
 - using ordinary files as backing storage for virtual memory
 - sharing of both code and data segments among processes
 - negotiation between file cache and virtual memory to optimize main
 memory usage
 - transparent process migration facility.

------

Details of the features:
------------------------

Sprite has a multithreaded kernel, which allows multiple processes to
be in kernel mode at the same time. This makes Sprite more efficient
on multiprocessor machines, but the kernel is more complex (due to locks)

The kernels of the individual machines access each other's services
using RPC; handcoded stubs; RPC made more efficient using implicit
acknowledgements (each message from a client serves as an implicit ack
for the previous message), and fragmentation (splitting up large RPC
messages into smaller messages with a single ack for all of them).

All kernels trust each other, and do not perform any
authentication. The network is assumed to be secure and there is no
encryption.

File System:
 - Sprite file system provides name transparency. Unlike NFS, a single
 file system hierarchy across all the workstations and transparent
 access to all devices in the system through the file system.
 - File system is a collection of domains (domain is equivalent to a
 mountable file system in Unix). Domains are mounted within each other
 to form the complete file system.
 - The domain structure is kept track of using a prefix table. Each
 entry in the table gives the full name of the top level directory in
 a domain, the server for that domain, and a token to pass to the
 server. The prefix tables are managed automatically by the kernel. To
 add a new entry to the table, a client kernel broadcasts a prefix name,
 and the server for that domain responds to the client with a token. 
 The client uses this broadcast mechanism when a server returns a
 new prefix during a lookup (due to a mount point in the server's
 domain), or when it encounters an error during a file open (due to
 server crash or due to relocation of the domain to a different
 server). 
 - A client lookups up a filename by first computing a maximum prefix
 match for the filename path from the prefix table entries and sending
 a request to that server. If the path involves a mount point in the
 server's domain, the server sends back the prefix for that mount
 point. This prefix lookup mechanism reduces traffic at the root domain
 server.
 - File system blocks are cached at both client and server. Delayed
 write strategy is used. Cache consistency: sequential write-sharing
 is allowed using version numbers to purge client caches; for
 concurrent write-sharing, Sprite disables client caching.

Virtual Memory:
 - Shared address space: Sprite allows processes to share code and
 data segments. Efficient process synchronization can be performed
 using low-level instructions such as test and set. Synchronization
 involves the kernel only if it requires process blocking.
 - Backing Storage: Sprite uses ordinary files for backing storage,
 with a separate dir for each workstation, and separate files for each
 process.
 - Sticky segments: The code segment of a process is stored in main
 memory even after a process exits, allowing new processes with same
 object file to startup faster
 - Backing files do not go through client file caches to avoid double
 caching.
 - Virtual Memory and file system share a common pool of main memory
 pages and the replacement algorithm replaces the oldest page in the pool.

Process Migration:
 - To migrate a process, the process if frozen and the virtual memory
 pages of the process are written to the backing files. Then, the
 process is migrated to the other machine and if the machine already
 has cached the object file it is used. The process starts executing
 on the remote machine and the vm pages are demand paged.
 - To achieve transparent remote execution, the kernel calls of the
 process are forwarded to the process' home machine.