Transcript Amoeba
Amoeba Distributed
Operating System
Ken Baggett
CPSC 550
Spring 2006
History
The history of modern computing can be
divided into the following eras:
1970s: Timesharing (1 computer with many users)
1980s: Personal computing (1 computer per user)
1990s: Parallel computing (many computers per user)
History
80’s computers could be networked together and
files could be shared between users RPCs.
Parallel computing in the 90’s and today are
used to share CPU resources among a network
of computer systems.
This concept is referred to as distributed
computer systems or parallel computing
How can we exploit with the one-to-many
computer system configuration?
Ameoba
What is Amoeba
Amoeba is a distributed operating system
Developed by Andrew Tannenbaum
Uses timesharing
User logs into the system as a whole, not
just his local machine.
When the user runs a program, the system
decides which machine (or machines) in
the system should execute it.
This decision is invisible to the user.
Design Goals
The basic design goals of Amoeba are:
Distribution—Connecting together many machines
Parallelism—Allowing individual jobs to use multiple
CPUs easily
Transparency—Having the collection of computers act
like a single system
Performance—Achieving all of the above in an efficient
manner
Definitions of Amoeba
Communications
The definitions of the Amoeba communication calls are given in the
ANSI C language. All three calls use a Msg data structure, which is
a 32-byte header with several fields to hold capabilities and other
items. Note that each request or reply message can consist of just a
header or a header and an additional component.
trans(Msg *requestHeader, char *requestBuffer, int requestSize,
Msg *replyHeader, char*replyBuffer, int replySize) Client sends a
request message and receives a reply; the header contains a
capability for the object upon which an operation is being requested.
get_request(Msg *requestHeader, char *requestBuffer, int
requestSize)Server gets a request from the port specified in the
message header.
put_reply(Msg *replyHeader, char *replyBuffer, int replySize)
Server replies.
Features in Amoeba
Microkernel and Server Architecture
Amoeba is built upon a microkernel architecture.
The microkernel supports the basic process,
communications, and object primitives. It also
handles device I/O and memory management.
Each machine in the Amoeba system runs a small
identical software program - called the microkernel.
The function of the kernel is to allow efficient
communication between client processes, which run
application programs, and server processes, such as
the Bullet File server or the directory server.
Features
Threads
Each process has its own address space and contains multiple threads.
These threads have their own stack and program counter, but share the
global data and code of the process.
Remote Procedure Calls
RPC is the basic communication mechanism in Amoeba. Communication
consists of a client thread sending a message to a server thread, then
blocking until the server thread sends back a return message, at which time
the client is unblocked.
Amoeba uses stubs to access remote services which hide the details of the
remote services from the user. A special language in Amoeba called the
Amoeba Interface Language (AIL) generates these stubs automatically.
The stubs will then marshal parameters and hide the communication details
from the user.
Features
Group Communication
Amoeba provides a mechanism that allows all
receivers in a one-to-many configuration to
receive a transmitted message in the same
order. This simplifies parallel processing and
distributed programming problems.
Differences from Network OS
Amoeba
Programs can execute wherever OS decides.
No concept of host machine.
Objects and Capabilities are used to manage file
systems.
Network OS
Programs run locally unless specified.
User aware he is using a local host machine.
Files are maintained and accessed from local
machine unless using a remote file system.
Architecture
Four principle components
Workstations
Processor Pool
Specialized Servers (directory, file, block...)
WAN Gateways
Architecture
Architecture
Objects
Abstract data types with data and behaviors.
Amoeba primarily supports software objects, but hardware
objects also exist.
Each object is managed by a server process to which RPCs can
be sent. Each RPC specifies the object to be used, the operation
to be performed, and any parameters to be passed
Capabilities
128-bit value object description created and returned to the
caller when the object is created.
Subsequent operations on the object require the user to send its
capability to the server to both specify the object and prove the
user has permission to manipulate the object.
Capabilities are encrypted to prevent tampering.
How to use Amoeba
Amoeba is freeware
It can be loaded on a LAN or University
computer system
Editors such as elvis, jove, ed come with
the installation package
Compilers such as C, Pascal, Fortran 77,
Basic, and Modula 2
Orca - used for Parallel Programming
Applications
UNIX emulation
Parallel make
Traveling salesman
Alpha-beta search
Applications
Parallel make
Amoeba runs contains a processor pool with several processors.
One application for these processors in a UNIX environment is a
parallel version of make.
When make discovers that multiple compilations are needed,
they are run in parallel on different processors.
pmake was developed based on the UNIX make but with
additional code to handle parallelism.
many medium-sized files = considerable speedup
one large source file and many small ones = total time can
never be smaller than the compilation time of the large one.
A speedup of about a factor of 4 over sequential make has
been observed in practice on typical makefiles.
Applications
The Traveling Salesman
The computer is given a starting location and
a list of cities to be visited. The idea is to find
the shortest path that visits each city exactly
once, and then returns to the starting place.
Amoeba was programmed to run this
application in parallel by having one pool
processor act as coordinator, and the rest as
slaves.
The Traveling Salesman
Example: the starting place is London, and the cities to be visited include
New York, Sydney, Nairobi, and Tokyo
The coordinator might tell the first slave to investigate all paths starting with
London-New York, the second slave to investigate all paths starting with
London-Sydney, the third slave to investigate all paths starting with LondonNairobi...
All searches go on in parallel.
When a slave is finished, it reports back to the coordinator and gets a new
assignment.
Also, the algorithm can be applied recursively.
The first slave could allocate a processor to investigate paths starting with
London-New York-Sydney, another processor to investigate London-New YorkNairobi, and so forth.
Results show that about 75 percent of the theoretical maximum speedup
can be achieved using this algorithm, the remaining 1/4 being lost to
communication and other overhead
Significance of points
Amoeba is a distributed operating system which
successfully allows users to execute jobs transparently
over multiple CPUs.
It was primarily developed by Andrew Tannenbaum and
others at the Vrije Universiteit Amsterdam, Netherland.
Its basic design goals are –
Distribution—Connecting together many machines
Parallelism—Allowing individual jobs to use multiple CPUs easily
Transparency—Having the collection of computers act like a
single system
Performance—Achieving all of the above in an efficient manner.
Significance of Points
It is based on a microkernel architecture.
It uses objects to encapsulate data and processes and capabilities
to describe the objects.
The kernel provides just three major system calls
trans(Msg *requestHeader, char *requestBuffer, int requestSize,
Msg *replyHeader, char*replyBuffer, int replySize)
get_request(Msg *requestHeader, char *requestBuffer, int
requestSize)
put_reply(Msg *replyHeader, char *replyBuffer, int replySize)
It has proven to be successful at implementing speedup on many
common computer science algorithms including UNIX emulation,
parallel make, traveling salesman, and alpha-beta search.
Summary
The Amoeba distributed operating system succeeds in overcoming
many of the hurdles faces in distributed computing.
It abstracts away the use of RPCs using stubs and is scalable based
on available CPUs.
Although system updates seem to have stopped, the current version
appears to have reached a stable point in its architectural
development.
The programming languages included with the distribution are
common to most programmers and should make code creation easy
for Amoeba applications.
Results of application speedup and the fact that the system is freely
available make it worth evaluating at the university level.
References
[1] Tanenbaum, A.S, Sharp, G.J. “The Amoeba Distributed Operating System” Online: 2006
http://www.cs.vu.nl/pub/amoeba/Intro.pdf
[2] Ramsay, M., Keigel, T., Memmer, H. “Ameoba Distributed Operating System” Online
http://csserver.evansville.edu/~mr56/CS470/Final_Draft.pdf
[3] Coulouris, G. Dollimore, J., Kindberg, T. Distributed Systems – Concepts and Design, 1994,
Online: http://www.cdk3.net/oss/Ed2/Amoeba.pdf
[4] Sharp, G.J.: ‘‘The Design of a Window System for Amoeba,’’ Report IR-142, Dept. of Math. &
Computer Science, Vrije Universiteit, Dec. 1987.
[5] The Amoeba Reference Manual Users Guide Vrije University of Amsterdam, 1996 Online
2006: http://www.cs.vu.nl/pub/amoeba/manuals/usr.pdf
[6] Bal, H.E., Renesse R. van, and Tanenbaum, A.S.: ‘‘Implementing Distributed Algorithms Using
Remote Procedure Calls,’’ Proc. 1987 National Computer Conference, pp. 499-506, June 1987.
[7] Baalbergen, E.H.: ‘‘Parallel and Distributed Compilations in Loosely Coupled systems,’’ Proc.
Workshop on Large Grain Parallelism , Providence, RI, Oct 1986.
[8] Straven H. van, Renesse R. van, and Tanenbaum, A.S, “The Performance Of The Amoeba
Distributed Operating System” Online: 2006
https://dare.ubvu.vu.nl/bitstream/1871/2589/1/11008.pdf
[9] Tanenbaum, A.S, et al, “Experiences with the Amoeba Distributed Operating System” Online
2006:
http://citeseer.ist.psu.edu/cache/papers/cs/6593/ftp:zSzzSzftp.sys.toronto.eduzSzpubzSzamoeba
zSz03.pdf/tanenbaum90experiences.pdf
Questions?