A Comparison of Two Distributed
`Systems: Amoeba and Sprite
`
`Fred Douglisx
`Matsushita Information TÞchnology Laboratory
`John K. Ousterhout
`University of California, Berkeley
`M. Frans Kaashoek
`Andrew S. Thnenbaum
`Vrije Universiteit
`Amsterdam, The Netherlands
`
`ABSTRACT This paper compares two distributed oper-
`ating systems, Amoeba and Sprite. Although the sys-
`tems share many goals, they diverged on two philo-
`sophical grounds: whether to emphasize a distributed
`computing model or traditional UNIX-style applica-
`tions, and whether to use a workstation-centered model
`of computation or a combination of terminals and a
`shared processor pool. Many of the most prominent
`features of the systems (both positive and negative) fol-
`low from the philosophical differences. For example,
`Amoeba provides a high-performance user-level IPC
`mechanism, while Sprite's RPC mechanism is only
`available for kernel use; Sprite's file access perfor-
`mance benefits from client-level caching, while Amoeba
`
`This work was supported in part by the Netherlands Organization for Scientific Research
`(N.W.O.) under grant NF 62-334.
`
`@ Computíng Systems, Vol. 4 . No. 4 . Fall 1991 353
`
`Unified Patents Inc., Exhibit 1004, pg. 1
`
`

`

`caches files only on servers; and Sprite uses a process
`migration model to share compute power, while
`Amoeba uses a centralized server to allocate processors
`and distribute load automatically.
`
`I . Introduction
`
`The shift from time-sharing computers to collections of processors
`connected by a local-area network has motivated the development of
`numerous distributed operating systems [Abrossimov et al. 1989;
`Cheriton 1988; Mullender et al. l99O:' Ousterhout et al. 19881. This
`paper compares two distributed systems, Amoeba [Mullender et al.
`1990; Thnenbaum et al. 19901 and Sprite [Nelson et al. 1988; Ouster-
`hout et al. 19881, which have taken two substantially different ap-
`proaches to building distributed systems. These approaches have devel-
`oped as a result of different philosophies about the role of distributed
`qystems and the allocation of resources within them. By comparing
`these two systems in the context of our experiences with them, we
`draw conclusions about operating system organization that may aid the
`design of future distributed systems.
`We have chosen to compare Amoeba and Sprite for three reasons.
`First, they take different approaches toward user applications in a dis-
`tributed system. Sprite is primarily intended to run UNIX applications
`on a network of workstations, and it hides the distribution of the sys-
`tem behind a shared file system. It distributes the operating system but
`does not provide special support for distributed applications. Amoeba
`is intended as a testbed for distributed and parallel applications, as well
`as traditional applications. It provides a high-performance mechanism
`for user-to-user remote procedure calls (RPCs) [Birrell & Nelson
`19841, as well as a language to support parallel programming, so ap-
`plications can easily take advantage of multiple processors. At the
`same time, it hides the physical distribution of the system, and pro-
`cesses cannot even determine where they physically execute. Second,
`Amoeba and Sprite allocate processing resources in substantially dif-
`
`354 F. Douglis, J. Ousterhout, M. Kaashoek, and A. Tanenbaum
`
`Unified Patents Inc., Exhibit 1004, pg. 2
`
`

`

`ferent fashions. Amoeba users share a single "processor pool," while
`Sprite associates users with individual workstations. Third, we have
`personal experience with both systems over the course of several
`years. We know a good deal about the historical development of the
`systems and have personal knowledge of both their strengths and
`weaknesses. We also have access to both systems and are able to com-
`pare their performance on identical hardware.
`Naturally, there are many distributed systems besides Amoeba and
`Sprite. It would be possible to compare several contemporary dis-
`tributed systems in a survey fashion, much as Tanenbaum and van Re-
`nesse did in 1985 [Thnenbaum & van Renesse 1985]. However, with
`the exception of Section 4 below, we have chosen to restrict our com-
`parison to two systems. We believe that limiting the scope of this pa-
`per permits us to consider issues in greater detail than would otherwise
`be possible.
`The rest of this paper is organized as follows. Section 2 elaborates
`on the fundamental design philosophies behind the two systems. Sec-
`tion 3 relates these philosophies to several operating system issues:
`kernel architectures, communication, ûle systems, and process man-
`agement. Section 4 discusses how these issues have been addressed by
`other systems. Section 5 briefly reviews the development history of
`Amoeba and Sprite and describes their current research directions. Fi-
`nally, Section 6 draws several conclusions.
`
`2. Design Philosophies
`
`The Amoeba and Sprite projects began with many similar goals. Both
`projects recognized the trend towards large numbers of powerful but
`inexpensive processors connected by high-speed networks, and both
`projects set out to build operating systems that would enhance the
`power and usability of such configurations. Both design teams focussed
`on two key issues: shared storage and shared processing power. The
`first issue was how to implement a distributed file system that would
`allow secondary storage to be shared among all the processors without
`degrading performance or forcing users to worry about the distributed
`nature of the file system. The second issue was how to allow collec-
`tions of processors to be harnessed by individual users, so that appli-
`cations could benefit from the large number of available machines.
`
`A Comparison of Two Distributed Systems: Amoeba and Sprite 355
`
`Unified Patents Inc., Exhibit 1004, pg. 3
`
`

`

`However, in spite of their similarities, the Amoeba and Sprite
`projects diverged on two philosophical grounds. The first philosophical
`difference is the expected computing model. The Amoeba designers
`predicted that networked systems would soon have many more proces-
`sors than users, and they envisioned that future software would be de-
`signed to take advantage of massive parallelism. One of the key goals
`of the Amoeba project was to develop new operating system facilities
`that would support parallel and distributed computations, in addition to
`traditional applications, on a network with hundreds of processors. In
`contrast, Sprite assumed a more traditional model of computation,
`along the lines of typical UNIX applications. The goal of the Sprite
`designers was to develop new technologies for implementing UNIX-
`like facilities (particularþ file systems) on networked workstations,
`and they assumed that the distributed nature of the system would not
`generally be visible outside the kernel.
`The second philosophical difference is the way that processes are
`associated with processors. Sprite again took a more traditional ap-
`proach, where each user has a (mostly private) workstation and the
`user's processes are normally executed on that workstation. Although
`active users are guaranteed exclusive access to their workstations,
`Sprite provides a process migration mechanism that applications can
`use to offload work to idle machines all around the network. In con-
`trast, Amoeba assumed that computing power would be shared equally
`by all users. Users would not have personal processors; instead, com-
`puting resources would be concentrated in a processor pool containing
`a very large number of processors. Thus processing power is managed
`in a much more centralized fashion in Amoeba than in Sprite.
`
`2.1 Application Environment
`
`Amoeba and Sprite differ greatly in the applications they are intended
`to run and the resulting execution environment they provide. Amoeba
`provides an object-based distributed system, while Sprite runs a net-
`work operating system that is oriented around a shared file system.
`In Amoeba, each entity such as a process or file is an object, and
`each object is identified by a capability lDennis & Horn 19661. The
`capability includes a port which is a logical address that has no con-
`nection to the physical address of the server managing the object.
`
`356 F. Douglis, J. Ousterhout, M. Kaashoek, and A. Tänenbaum
`
`Unified Patents Inc., Exhibit 1004, pg. 4
`
`

`

`Thus, the location of the server is hidden from any objects that inter-
`act with it.
`In addition to providing a uniform communication model, Amoeba
`eases the task of writing distributed applications. It provides automatic
`stub generation for remote procedure calls from a procedural interface
`declaration [van Rossum 1989]. It also supplies a programming lan-
`guage, called Orca, that simplifies writing parallel applications on a
`distributed system [Bal et al. 1990].
`By comparison, Sprite is intended to ease the transition from
`UNIX time-sharing systems to networked workstations. Since most of
`the applications running on Sprite are such things as compilations, ed-
`iting, and text formatting, the design of Sprite has emphasized loca-
`tion-transparent file access, consistent access to shared files, and high
`file system performance. In particular, Sprite caches file data on client
`workstations in order to perform many file operations without the need
`for network transfers [Nelson et al. 1988]. On the other hand, because
`applications on UNIX typically performed little or no interprocess
`communication (other than pipes), little effort was made to support
`special protocols for communication over the network at user-level. In-
`stead, the file system provides a simple but relatively inefficient
`method for location-transparent user-level IPC when it is needed.
`The decision to model a new system after an existing one has both
`positive and negative consequences. On the positive side, compatibility
`with UNIX has helped Sprite to develop quickly into a system that
`many people use for all their day-to-day computing. In particular,
`most UNIX applications can be run on Sprite by recompiling. On the
`negative side, UNIX compatibility has restricted Sprite's application
`domain, and it has complicated several aspects of the system (such as
`process migration, described below). Compatibility with UNIX was
`less of a goal for Amoeba; because Amoeba is only partially compat-
`ible with UNIX, it is more difficult to port existing software to it.
`However, it offers more flexibility in the design of new software and
`more opportunities to do research on distributed and parallel languages
`and applications.
`
`2.2 Processor Allocation
`
`Allocation of processors in a distributed system ranges from a pure
`"workstation" model, in which each user executes tasks on exactly one
`
`A Comparison of Two Distributed Systems: Amoeba and Sprite 357
`
`Unified Patents Inc., Exhibit 1004, pg. 5
`
`

`

`machine, to a pure "processor pool" model, in which all users have
`equal access to all processors. The workstation model makes each host
`essentially autonomous; for example, each host maintains its own list
`of processes, which may typically be viewed only from that host. To
`execute commands on another host, a user must normally perform an
`explicit remote login. With the processor pool approach, the system is
`more integrated. Processors are dynamically allocated to processes re-
`gardless of the location of the user running them, and users may view
`the state of their processes anywhere in the system. Amoeba and
`Sprite implement two system architectures that fall between these two
`extremes. Amoeba's architecture is closer to the processor pool ap-
`proach, while Sprite's is closer to the workstation model.
`Amoeba's system architecture is organized around a centralized
`processor pool, as shown in Figure 1. Each "pool processor" has a
`network interface and RAM associated with it, and these processors
`are dynamically allocated to processes as they are needed. However,
`unlike a system with a "pure" processor pool model, Amoeba also use
`processors outside the processor pool for system services. For example,
`the file server and directory server both run on dedicated processors.
`This separation avoids contention between user processes and system
`functions. Finally, users interact with the system using a graphics ter-
`minal, such as an "X-terminal." The terminal is essentially a cheap
`dedicated processor, a bit-mapped display, and a network interface.
`Only a display server runs on the graphics terminal; all other applica-
`tions run in the processor pool.
`
`Graphics terminals
`
`Time se¡ver File server D¡rectofy sêrver
`Specialized servers
`
`Figure l: An Amoeba system consists of a processor pool, specialized
`servers, and graphics terminals.
`
`358 F. Douglis, J. Ousterhout, M. Kaashoek, and A. Tanenbaum
`
`Unified Patents Inc., Exhibit 1004, pg. 6
`
`

`

`Workstations
`
`File server
`
`Figure 2: A Sprite system consists of workstations and file servers,
`
`The designers of Amoeba chose the processor pool model for three
`reasons. First, as we have indicated, they assumed that as processor
`and memory chips continue to decrease in price, the number of pro-
`cessors in future systems would greatly outnumber the users. In their
`opinion, it would be easier to place hundreds of processors in racks in
`a machine room than to distribute those processors equally among
`each user, and the addition of a new processor would benefit all users
`equally. Second, they assumed that the cost of adding a new pool pro-
`cessor would be substantially less than the cost of adding a worksta-
`tion, since a pool processor would require only a processor, memory,
`and a network interface; a fixed amount of capital could make a larger
`increase in computing resources under the processor pool model.
`Third, they wanted to make the entire distributed system appear as a
`single time-sharing system. Users not only should not be concerned
`with the physical distribution of the hardware, they should not be
`aware of it at all.
`Sprite's processing power is distributed among a collection of per-
`sonal workstations, as shown in Figure 2, blut it does not implement a
`"pure" workstation model. Each user has priority over one worksta-
`tion, is guaranteed the full processing power of that workstation, and
`executes commands on that workstation by default. However, Sprite
`also provides a facility to execute commands using the processing
`power of idle hosts. These commands appear to the user to run on the
`user's own workstation. In keeping with the workstation model, Sprite
`recognizes the preeminence of workstation owners on their own ma-
`
`A Comparison of Two Distributed Systems: Amoeba and Spite 359
`
`Unified Patents Inc., Exhibit 1004, pg. 7
`
`

`

`chines by migrating "foreign" processes away from a workstation if its
`owner returns.
`In addition to workstations, Sprite provides dedicated file servers
`that are not normally used for application programs. It is also possible
`to add processing resources to the system without associating them
`with individual users. For example, a rack of processors could be used
`as a shared compute server, offering the same cost advantages as an
`Amoeba processor pool.
`The designers of Sprite chose a workstation-based model for three
`reasons. First, they believed that workstations offered the opportunity
`to isolate system load, so that one user would not suffer a degradation
`in performance due to a high load on the system from another user.
`Second, they hypothesized that much of the power of newer and faster
`machines would be used to provide better user interfaces. The best
`way to use this power would be to put it as close to the display as pos-
`sible; i.e., in a workstation. Third, to the designers of Sprite, there
`appeared to be no difference between a graphics terminal and a disk-
`less workstation except for,more memory on the workstation; why not
`perform all computation on the workstations, rather than just interac-
`tive tasks?
`
`3. Design Consequences
`
`The decision of whether to organize processing resources into a shared
`pool or individual workstations has affected the design of Amoeba and
`Sprite in several ways. For example, Amoeba assigns processes to the
`most desirable processor in the system, achieving some dynamic load
`balancing. It does not implement client file caching, because the effec-
`tiveness of caching is decreased when the process that reads a new file
`is not likely to execute on the processor where the file was just writ-
`ten. Sprite caches files on workstations, and it implements process mi-
`gration to preserve response time on workstations.
`In this section, we discuss how the design philosophies described
`above affected operating system issues such as kernel architectures, in-
`terprocess communication, f,le systems, and process management.
`Amoeba and Sprite have made different sets of tradeoffs and differ
`both in the functionality they provide and the performance of many
`operations. While the design philosophies have affected both of these
`
`360 F. Douglis, J. Ousterhout, M. Kaashoek, and A. Tanenbaum
`
`Unified Patents Inc., Exhibit 1004, pg. 8
`
`

`

`areas, in some cases performance has been affected by low-level im-
`plementation details as well. We evaluate both functionality and per-
`formance,l distinguishing between the effects of design and implemen-
`tation on performance when appropriate.
`
`3.1 Kernel Architectures
`
`One of the greatest differences between Amoeba and Sprite is their ba-
`sic kernel architectures. Sprite follows the traditional UNIX mono-
`lithic model, with all of the kernel's functionality implemented in a
`single privileged address space. Processes access most services by
`trapping into the kernel, and each kernel provides services for those
`processes running on its host. The only shared kernel-level service
`provided by Sprite is the file system. In contrast, Amoeba implements
`a "microkernel," with a minimal set of services (most importantly,
`communication and low-level process management) implemented
`within the kernel. Other services, such as the file system and process
`placement, are provided by separate processes that may be accessed
`directly from anywhere in the system. As a result, some services that
`would be provided independently on each Sprite workstation (such as
`the time-of-day clock) may be provided in Amoeba by a single net-
`work-wide server.
`There were two principal reasons for the decision to use a mono-
`lithic kernel in Sprite. First, the performance implications of micro-
`kernels were unclear at the time (even today they are still somewhat
`controversial). Communicating with user-level processes is more ex-
`pensive than just trapping into the kernel, since hardware registers
`(such as the virtual memory context) typically must be modified.
`Thus, although it is possible to minimize the overhead of changing
`protection domains [Bershad et 41. 1989], there are still additional
`costs associated with user-level services relative to kernel-level ser-
`vices. Second, placing all the kernel facilities together in a single ad-
`dress space made it possible for them to work together and share data
`structures. For example, the file cache and virtual memory system
`work together to share the physical memory of a machine [Nelson et
`
`l. Measurements in this paper rvere taken on 8-Mbyte Sun 3/60 workstations (20 MHz
`Motorola 68020 processors, or about 3 MIPS), using Lance Ethernet controllers on a 10
`megabits/second Ethernet. The file server for both systems used a SCSI-3 controller and
`a Wren IV SCSI disk.
`
`A Comparison of Two Distributed Systems: Amoeba and Sprite 361
`
`Unified Patents Inc., Exhibit 1004, pg. 9
`
`

`

`al. 19881, and the process migration mechanism has a close relation-
`ship with all the major parts of the system. Although such close coop-
`eration could also have been achieved in the microkernel model,
`shared memory would have been precluded and additional context
`switches would have been incurred on each cross-module invocation.
`Amoeba's microkernel approach was motivated by uniformity,
`modularity, and extensibility. Since services are obtained through
`RPC, both kernel-level and user-level services may be accessed
`through a uniform, location-transparent interface. Users may extend or
`replace standard services with their own by using different capabili-
`ties. Finally, separate services permit the functionality of the system to
`be distributed and replicated on multiple processors to gain perfor-
`mance and fault tolerance.
`In light of the advantages of the microkernel approach, one may
`ask whether any potential overhead from separate server processes is
`significant enough to detract from their design. A comparison between
`the performance of Amoeba and Sprite offers the opportunity to an-
`swer this question, especially since Sprite's performance during system
`calls and context switching is similar to several commercial UNIX-
`based systems [Ousterhout 1990].
`As one might expect, performance differences between Amoeba's
`microkernel and Sprite's monolithic kernel depend on service access
`patterns. Since a kernel call is inherently faster than a remote proce-
`dure call, obtaining a simple service from a different process can be
`substantially slower than obtaining it from the kernel. For example,
`the minimum cost of a kernel call in Sprite on a Sun 3/60 workstation
`is about 70 microseconds, while the minimum cost of an RPC between
`two distinct processes on an Amoeba processor is 500 microseconds.
`Furthermore, a service may be provided by each kernel in Sprite but
`by a single global server in Amoeba. Accessing a service over the Eth-
`ernet in Amoeba takes at least 1200 microseconds.
`However, the overall performance of the system depends on many
`factors. For example, Amoeba's lack of swapping or paging improves
`performance considerably: as we describe below, process creation and
`context switching are both generally faster in Amoeba than in Sprite.
`Overall performance is more likely to be affected by system character-
`istics such as the speed of communications and the use of file caching
`than by the choice between a microkernel or monolithic kernel. If a
`microkernel could be tolerably efficient for trivial operations and at
`
`362 F. Douglis, J. Ousterhout, M. Kaashoek, and A. Tänenbaum
`
`Unified Patents Inc., Exhibit 1004, pg. 10
`
`

`

`least as good as a monolithic kernel for more complicated operations,
`the advantages of the microkernel approach-most importantly, mod-
`ularity and extensibility-would appear to outweigh any potential dis-
`advantages in performance.
`
`3.2 Communication Mechanisms
`
`Both Amoeba and Sprite implement communication mechanisms to
`enable processes to communicate with each other and to hide machine
`boundaries. Their mechanisms for doing so, however, are different.
`Amoeba presents the whole system as a collection of objects, on each
`of which a set of operations can be performed using RPC. Like
`Amoeba, Sprite uses RPC for kernel-to-kernel communication. Sprite
`has not really addressed the problems of building distributed applica-
`tions, but it does provide a mechanism that can be used to support
`some kinds of client-server communication.
`Considering kernel communication in isolation, Amoeba and
`Sprite have more in common than not. Both use RPC to communicate
`between kernels on different machines. The implementations vary in
`minor ways. Sprite uses the implicit acknowledgements of the Birrell-
`Nelson design lBirrell & Nelson 1984] to avoid extra network mes-
`sages when the same parties communicate repeatedly. On the other
`hand, Amoeba sends an explicit acknowledgement for the server's re-
`ply to make it possible for the server to free its state associated with
`the RPC. This simplifies the implementation of the RPC protocol but
`requires an additional packet to be built and delivered to the network.
`Despite this extra packet, Amoeba obtains lower latency for the null
`RPC (passing no data): it takes 1.1 msec to perform a null RPC in
`Amoeba between kernels on two Sun 3/60 workstations, compared to
`1.9 msec in Sprite. The difference is largely due to the necessity to
`perform a context-switch in Sprite when an RPC is received. For large
`RPCs, Sprite uses a blast protocol to send many packets without indi-
`vidual acknowledgments. This compensates for the other overhead in
`the RPC system, resulting in a slightly higher maximum kernel-to-ker-
`nel bandwidth: 820 Kbytesisec in Sprite compared to 814 Kbytes/sec
`in Amoeba. Table 1(a) summarizes the performance of kernel-to-ker-
`nel RPC in each system.
`User-level communication, however, differs greatly between the
`two systems. Amoeba uses the same model for user-level as for
`
`A Comparison of Two Distributed Systems: Amoeba and Sprite 363
`
`Unified Patents Inc., Exhibit 1004, pg. 11
`
`

`

`Size
`(Bytes)
`
`0
`16384
`30000
`
`Size
`(Bytes)
`
`0
`16384
`30000
`
`Kernel-level Latency
`User-level Latency
`(msec)
`(msec)
`Sprite
`Amoeba
`Sprite
`Á.moeba
`1.1
`1.9
`7.9
`1,.2
`20.0
`2L.0
`19.5
`33.5
`36.0
`36.0
`62.8
`(u)
`b
`Täble 1: Communication latency in Amoeba and Sprite. Measure-
`ments were taken for transfer units of 0 bytes, 16 Kbytes (the largest
`transfer permitted for kernel-to-kernel RPC in Sprite), and 30000
`bytes (the largest transfer permitted during a single RPC in Amoeba).
`Part (a) shows kernel-to-kernel RPC performance. Amoeba provides
`appreciably lower latency for small RPCs but Sprite provides better
`performance at its largest transfer unit. The difference in the perfor-
`mance of large transfers arises because individual fragments in Sprite
`are not acknowledged. Part (b) shows the performance of user-level
`IPC. Amoeba's remote procedure calls are substantially faster than
`Sprite pseudo-device operations for all data sizes. Measurements were
`made on two Sun 3/60 workstations connected by a lO-Mbit Ethernet.
`
`kernel-level communications, with marginal overhead over the kernel
`case. Communication in Sprite is integrated into the file system name
`space using "pseudo-devices," which permit synchronous and asyn-
`chronous communication between user processes using the flle system
`read, write and I/O control kernel calls [Welch & Ousterhout 1988].
`User-level communication in Sprite is more expensive than in Amoeba
`for four reasons: first, Sprite's user-level communication is layered on
`a kernel-to-kernel RPC that is significantly slower than Amoeba's for
`small transfers and about the same performance for large transfers;
`second, as a result of this layering, the Sprite calls involve additional
`locking and copying that Amoeba avoids; third, all buffers in Amoeba
`are contiguous and resident in physical memory, so no per-page
`checks need be performed; and fourth, Amoeba performs context
`switching much faster than Sprite (see Section 3.4). Thus, these differ-
`ences in performance arise from both lowlevel implementation differ-
`ences, such as contiguous buffers and context-switching speeds, and
`the higher-level philosophical differences that led to Sprite's layered
`approach. Table 1(b) demonstrates how Amoeba consistently outper-
`forms Sprite at user level.
`
`364 F. Douglis, J. Ousterhout, M. Kaashoek, and A. Tanenbaum
`
`Unified Patents Inc., Exhibit 1004, pg. 12
`
`

`

`3.3 Fíle System
`
`Both Amoeba and Sprite provide a single globally shared, location-
`transparent file system. In either system a user can access any file sys-
`tem object from any location without being aware of the location of
`the object. The design of Sprite's file system was strongly influenced
`by Sprite's workstation environment and file-intensive applications. In
`particular, it caches data on both clients and servers to achieve high
`performance, and it adjusts the size of the file cache in response to de-
`mands for physical memory. Distributed applications on Amoeba are
`not necessarily file-intensive, and each new process is typically placed
`on a different processor, so client caching was not as important in
`Amoeba as in Sprite. Instead, Amoeba has emphasized the transpar-
`ency and fault-tolerance necessary for a large distributed system.
`Sprite provides a traditional UNIX open-close-read-write interface,
`with naming and file access performed in the kernel [Welch 1990].
`Processes perform kernel calls to open files and obtain tokens they
`may use to perform further operations on the files. The kernel of the
`host running a process, known as the client identifies the server for a
`file using an associative table based on the leading characters of the
`file's name. The client passes the file's full path name to the server,
`where name lookup and protection checking occur. The kernel of the
`file server returns either a handle that may be used to perform I/O on
`the f,le, a new path name to open (in the case of symbolic links), or
`an error condition. Once the client has obtained a handle for a file, it
`performs I/O operations by passing the handle to the server named in
`the handle. For ordinary files I/O is handled by the same server that
`looked up the name, but for devices the I/O server may be different
`than the server that looks up the file name (this scheme permits
`devices on diskless workstations to be accessed remotely). Sprite file
`servers support read and write operations of arbitrary size and align-
`ment.
`Sprite's file system emphasizes caching and scalability. Both
`clients and servers cache files in their main memories, reducing con-
`tention for network and disk bandwidth, and file-server processors
`[Nelson et al. 1988]. The size of the file cache varies dynamically as
`the demands for file data and virtual memory change: a variable cache
`size permits applications to perform better than in systems with a fixed
`partition between file data and virtual memory. The I/O server is
`
`A Comparison of Two Distributed Systems: Amoeba and Sprite 365
`
`Unified Patents Inc., Exhibit 1004, pg. 13
`
`

`

`responsible for ensuring that a process reading a file sees the most re-
`cently written data; in particular, it disables client caching for a file if
`one host has the file open for writing while another host is accessing
`it. If a server crashes, or there is a network partition, clients use an
`idempotent reopen protocol to reestablish the state of their open files
`with the server and ensure that cached file data remains valid [Baker
`& Ousterhout 19901. Sprite uses a block-based file access model. Files
`are stored in blocks that may or may not be contiguous on disk, and
`not all of a file need be in memory at once. A file is transferred to and
`from its I/O server in blocks of 4 Kbytes.
`Amoeba splits naming and access into two different servers, a di-
`rectory server and a file server, in order to provide flexibility. The di-
`rectory server translates names into capabilities, and permits processes
`to create new mappings of names to capabilities and sets of capabili-
`ties. It places no restrictions on the location of objects referenced by a
`directory, thus one directory may contain entries for files on different
`file servers or objects that are not files. (By comparison, this would
`typically not be possible in a system that provided a single combined
`tle and directory service.) It automatically replicates directory entries
`as they are created, and replicates files asynchronously.
`The standard Amoeba file server, known as the Bullet Server em-
`phasizes network transfer speed and simplicity [van Renesse et al.
`19891. The Bullet Server provides an immutable file store, which sim-
`plifies file replication. The server's principal operations arc read-fi\e,
`create-fi\e, and delete-fi\e. Aprocess may create a new file, specifying
`its initial contents and receiving a capability for it. It may then modify
`the contents, but the file may not be read until it has been committed.
`Once the process has committed the file, it is immediately written
`through to disk for reliability. (V/rite-through may be disabled at the
`option of the caller, but this option is rarely used in practice.) At this
`point, the file may be read by anyone with the appropriate permission,
`but may never be modified. The only permissible operations on a com-
`mitted file are reading and deletion.
`In addition to its goal of simplicity, the implementation of the Bul-
`let Server has been influenced by the distributed nature of Amoeba's
`software architecture. since the Bullet server runs on a dedicated ma-
`chine, it is normally run as a collection of threads within the kernel,
`but it can equally well run in user space at the cost of some additional
`
`Unified Patents Inc., Exhibit 1004, pg. 14
`
`

`

`copying between the user process and the kernel thread that manages
`disks. All files are stored contiguously in memory and on disk. The
`sefver alleviates fragmentation problems by compacting memory and
`disks as needed. It is responsible for replicating files on multiple disks,
`while a Separate "object manager" replicates files on multiple instances
`of the Bullet Server. Because of the d