CIS 630 TERM PAPER

Winter 2001

Iustin Benche

Dept. of Computer Science

University of Oregon

Abstract

The paper discusses the features found in Amoeba operating system. We describe in details how the communication is implemented in this system, focusing on RPC and security. We compare this approach with solutions found in other operating systems.

Contents

1. Introduction

2. The Amoeba Hardware Architecture

3. The Amoeba Software Architecture

4. Communication in Amoeba

5. Amoeba's File System

6. Process Management

7. Comparisons with solutions found in actual distributed systems

8. Conclusions

1. Introduction

Amoeba is a distributed system developed at the Free University and Center for Mathematics and Computer Science in Amsterdam. The Amoeba Project was started in 1981 by Mullender and Tanenbaum, and it was continued in early 1990s. This paper discusses the feature of the version published in 1989.

Amoeba is a distributed operating system designed to connect together a large number of machines in a transparent way. Its goal is to make the entire system look to the user like a single computer.

As key features of this system, we can say that the Amoeba software is based on objects, and it has a unique and fast file system. Among other features, these will ensure that Amoeba has some of the key features required from a distributed system: fast, high performance, fault tolerant, easy to use, the details of the implementation of communication are transparent to the user, the system is extensible, we can reuse code written for application for other operating systems.

2. The Hardware Architecture

The Amoeba hardware architecture consists of four components, as we can see in figure 1.

Fig. 1. The Amoeba Hardware Architecture

The workstations are intended to execute only processes that interact intensively with the user (window manager, command interpreter, editors, graphical user interfaces).

The processor pool gather a lot of processors, which can be on different machines, with different architectures. They provide the computing power for the Amoeba system. User's applications that require a lot of processing will be executed by processors from this pool. One application form a single user can be allocated to a number of processors which can solve the problem in parallel. After execution, each processor is returned to the pool to be used for next jobs.

High performance can be achieved with such architecture because a very intensive calculation from a single user can be solved in a short amount of time by allocating a large amount of computing power.

The system permits a dynamically growth of the pool, we can add processors at run time; if some processors crash, the jobs they solve have to be restarted, but this does not determine the failure of the entire system.

Another part of the Amoeba hardware architecture are the specialized servers components. These are machine that run dedicated processes that have unusual resource demands (file servers, database servers).

The last component, the gateway, allows Amoeba systems to interact with other systems.

3. The Software Architecture

Amoeba is an object-based system using clients and servers. Clients processes use remote procedure calls to send requests to server processes for carryout out the operations on objects. Each object is both identified and protected by a capability. Capabilities have the set of operations that the holder may carry out on the object coded into them and they contain enough redundancy and cryptographic protection to make it infeasible to guess an object's capability. Thus, keeping capabilities secret by embedding them in a huge address space is the key to protection in Amoeba. Due to cryptographic protection, capabilities can be managed outside the kernel, by user processes themselves.

Each object has some number of operations that processes can perform on it. Objects are generally large, due to the overhead required in accessing an object. Each object is managed by an object server process. Operations on an object are performed by sending a message to the object's server.

When an object is created, the server returns a capability to the process creating it. The capability is used to address and protect the object.

As we can see in figure 2, a capability consist of 128 bits, with the following meaning: the service port field identifies the server, the object number tells which object is being referred to, since a server will have a lot of objects, the rights field specifies which operations are allowed. When an object is created, the server picks a random check field and stores it both in the new capability and inside its own tables. All the rights bits in a new capability are initially on, and it is this owner capability that is returned to the client. When the capability is sent back to the server in a request to perform an operation, the check field is verified.

Fig. 2. Structure of a capability

The Amoeba kernel has four primary functions:

• manage processes and threads;

• provide low-level memory management support;

• support communication;

• handle low-level IO.

All other services are provided by user-level processes.

4. Communication in Amoeba

Amoeba's conceptual model is that of a client thread performing operations on objects. Operations are implemented by making remote procedure calls. Amoeba supports two form of communication: RPC, which is based on point-to-point message passing, and group communication. At the lowest level, an RPC consists of a request message sent by a client to a server followed by a reply message from the server back to the client. Group communication uses hardware broadcasting or multicasting if it is available, otherwise it transparently simulates it with individual messages.

Fig. 3. Remote Procedure Calls

do_Operation is used by the client to get work done. It consists of sending a message to a server and then blocking until a reply comes back. get_Request is used by the servers to announce their willingness to accept messages addressed to a specific port. send_reply is also used by servers, to send replies back. All communication in Amoeba is of the form: a client sends a request to a server, the server accepts the request, does the work, and sends back the reply.

Even though the kernel provides only these three basic system calls to user processes: do_operation, get_request and send_reply, another interface has been build to allow easier development for users.

Interfaces for object manipulation are specified in a notation called Amoeba Interface Language. The AIL stub compiler can generate client and server stubs routines for a number of programming languages and machine architectures. For each parameter type, marshaling code is compiled into the stubs which converts data types of the language to data types and internal representations of AIL.

Each standard server defines a procedural interface that clients can call. These library routines are stubs that pack the parameters into messages and invoke the kernel primitives to actually send the message. During message transmission, the stub, and hence the calling thread, is blocked. When the reply comes back, the stub returns the status and results to the client.

In order for a client thread to do an RPC with a server thread, the client must know the server's address. Addressing is done by allowing any thread to choose a random 48-bit number, called a port, to be used as the address for messages sent to it. Different threads in a process may use different ports is they so desire. All messages are addressed from a sender to a destination port. A port is nothing more than a kind of logical thread address. There is no data structure and no storage associated with a port. It is similar to an IP address, except that it is not tied to any particular physical location. The first field in each capability gives the port of the server that manages the object.

The AIL compiler generates code to marshal or unmarshal the parameters of remote procedure calls into and out of message buffers and then call the Amoeba's transport mechanism for the delivery of request and reply messages. Messages consist of two parts, a header and a buffer. The header has a fixed format and contains addressing information (including the capability of the object that the RPC refers to), an operation code which selects the function to be called on the object, and some space for additional parameters. The buffer can contain data.

Before a request for an operation on an object can be delivered to a server thread that manages the object, the location of such a thread must be found. All capabilities contain a Service Port field, which identifies the service that manages the object the capability refers to. When a server thread makes a get_request call, it provides its service port to the kernel, which records it in an internal table. When a client thread calls do_Operation, it is the kernel's job to find a server thread with an outstanding get_request that matches the port in the capability provided by the client.

When a do_Operation call comes into a kernel, a check is made to see if the port in question is already known. If not, the kernel broadcasts a special locate packet onto the network asking if anyone out there has an outstanding get_request for the port in question. If one or more kernels have servers with outstanding get_requests, they respond by sending their network addresses. The kernel doing the broadcasting records the (port, network address) pair in a cache for future use. Only if a server dies or migrates will another broadcast be needed.

Client requests, addressed using an object's capability are delivered to one of the servers with outstanding get_request calls on the capability's port. For a public service (a file system, a database system), the port will generally be made known to all users. The ports used by an ordinary user process will, in general, be kept secret. Knowledge of a port is taken by the system as an evidence that the sender has a right to communicate with the service. This protection ensures access to servers, but not to objects, because for that we have stronger protection, given by the rights field.

This mechanism provides a authentication for clients (although someone could find out the capability of some objects, this cannot be verified by this implementation), but it does not ensure anything about the authentication of servers. The solution for server authentication is a cryptographic one: we build a F-box out of cryptographic algorithms. In any event, we assume that messages entering and leaving every processor undergo a simple transformation that users cannot bypass.

F performs a transformation which will make unfeasible for an intruder to impersonate as a server. Each port is written as a pair of ports, P and G, related by P = F(G), where F is a publicly-known one-way function (computing the inverse of this function is a problem that takes years to be computed, given any existing computational power, if at all possible).

5. Amoeba's File System

A typical user has access to literally thousands of capabilities, some of them private objects, some of the public. Even if the user can store information about the capabilities of his own objects, the server will have to inform him every time about some public objects. It is therefore useful to have a public place where users can find capabilities of shared objects, so that when a new object is made sharable, its capability need be put in only one place so everyone can find it easily, and not to be distributed to all potentially interested user in that object.

Hierarchical directory structures are ideal for implementing partially shared name spaces. Objects that are shared between members of a project team can be stored in a directory that only team members have access to. A capability for a directory is thus a capability for many other capabilities.

A directory can be seen as a set of pairs of the form (name, capability), having these basic operations: lookup, enter, delete.

Lookup is uses for finding an object name in a directory and returning its capability. Enter adds objects to directories, and delete remove objects from directories.

The Directory Service is a critical part of this system - clients can not find where are the servers that can execute their operations without it. Because of this, the Directory Service must never stop. It replicates its internal tables on multiple disks so that no single-site failure will bring it down.

As a file server, in Amoeba a very unusual solution was implemented. The Bullet Service is implemented by a number of Bullet Servers, each of them supporting a set of operations on some objects of type file. These operations are: read_file, create_file, delete_file.

When a file is created, the user normally provides all the data at once, creating the file and getting back a capability for it.

All files are immutable, once created they cannot be changed. Since files cannot change, the Directory Service can replicate them for redundancy without having the problems of concurrent updates - we do not have a write operation.

Because we know from the beginning the size of the file, which cannot grow, files can be stored contiguously on disk. When a read operation is done, the object number in the capability is used as an index into Bullet Server's table, and the file is read into the cache in a single disk operation.

The Directory Service takes care of atomic updates by allowing mapping of arbitrary sets of names onto arbitrary sets of capabilities to be changed atomically. The objects referred to by these capabilities must be immutable, either because the service that manage them refuse to change them, or because the users refrain from changing them.

6. Process Management

A process in Amoeba is basically an address space and a collection of threads that run in it. A process is an object in Amoeba. When a process is created, the parent process is given a capability for the child process, just as with any other newly created object. Using this capability, the child process can be suspended, restarted or destroyed.

Processes have explicit control over their address space. They can add new segments to their address space by mapping them in and remove segments by mapping them out. Besides virtual address and length, a capability can be specified in a map operation. This capability must belong to a file-like object which is read by the kernel to initialize the new segment. This allows processes to do mapped-file I/O.

Process management is handling by calling kernel threads running on every machine. To create a process on a given machine, another process does an RPC with that machine's process server, providing it with the necessary information.

A process descriptor consists of four parts, as shown in figure 4.

Fig. 4. A process descriptor

The host descriptor describes on what machine the process may run (architecture, instruction set, memory needs) or a class of machines, a group of machines or a particular machine. A kernel that does not match the host descriptor will refuse to execute the process.

Another part of the descriptor is the capability of the process - this is the one which every client that manipulates the process needs. The capability of the handler is needed because the handler is a service which deals with process exit, exceptions, signals and other anomalies of the process.

The memory map has an entry for each segment in the address space of the process to be. An entry gives virtual address, segment length, how the segment should be mapped, and the capability of a file or segment which the new segment should be initialized.

The thread map describes the initial state of each thread in the new process, processor status word, program counter, stack pointer, stack base, register values and system call state.

When a process starts up, it has at least one thread and possibly more. The number of threads is dynamic. During execution, the process can create additional threads, and existing threads can terminate. When a new thread is created, the parameters to the call specify the procedure to run and the size of the initial stack.

Three methods are provided for thread synchronization: signals, muteness and semaphores.

All threads are managed by the kernel. The advantage of this design is that when a thread does an RPC, the kernel can block that thread and schedule another one in the same process if one is ready. Thread scheduling is done using priorities, with kernel threads having higher priority than user threads.

7. Comparisons with solutions found in actual distributed systems

I would like to present some results of the Amoeba operating system, and then to present some new distributed system concepts that are similar to the ones from Amoeba.

The results of this operation system, as the authors claims, have emphasized that the decision to design a distributed operating system without attempting to restrict to existing operating systems or operating system interfaces was a good one. It was relatively easy to port UNIX software to Amoeba. The use of objects and capabilities has given some important advantages. The Amoeba kernel is small and simple.

We present only a few concepts from actual distributed systems which are found also in Amoeba:

1. CORBA's IDL is similar to AIL.

2. Java RMI, CORBA are similar to Amoeba's RPC

3. Java RMIRegistry, Naming Service in CORBA are similar to Locating Objects and Directory Service in Amoeba

4. Encryption Sockets in Java RMI are similar to cryptographic security in Amoeba

7.1 CORBA's IDL

A CORBA object can be implemented by a language that is not object-oriented. Therefore classes cannot be found in CORBA IDL, which means that instances of classes cannot be passed as arguments. However, data structures of various types and arbitrary complexity can be passed as arguments.

The CORBA Interface Definition Language provides facilities for defining modules, interfaces, types, attributes and method signatures. The grammar of IDL is a subset of ANSI C++ with additional constructs to support method signatures.

A CORBA IDL interface specifies a name and a set of methods that clients can request.

Each parameter is marked as being for input or output or both, using the keywords in, out, or inout. The return value provides an additional out parameter - it can be indicated as void if there is no out parameter.

The parameters may be any one of the primitive types, or one of the constructed types such as struct or array. Any parameter whose type is specified by the name of a IDL interface is a reference to a CORBA object and the value of a remote object reference is passed. Arguments of primitive and constructed types are copied and passed by value. On arrival, a new value is created in the recipient's process.

Object is the name of a type whose values are remote object references.

CORBA IDL allows exceptions to be defined in interfaces and thrown by their methods.

Remote invocation in CORBA has at-most-once call semantics as the default. However, IDL may specify that the invocation of a particular method has maybe semantics by using the oneway keyword. The client does not block on oneway requests, which can be used only for methods without results.

7.2 Java RMI, CORBA

We review first what are the common solution used in present systems to implement distributed applications: TCP sockets, RPC, CORBA, Java RMI.

A socket is an abstraction that represents a terminal for communications between processes across a network. Sockets can be used for an active communication between two computer on a network, where they establish a connection-oriented service, or a connectionless communication. Using sockets requires the programmer to design complex communication protocols at the application level. The main problem is converting the data from local representation to network representation and then back to the local representation.

RPC is a mechanism that allows the programmers to register their applications to a network address. Once registered, the procedures from these applications can be called from remote clients as if they were local procedures. This mechanism is useful for distributed procedural code, but not for object-oriented code because many of the arguments and return values sent to methods are in fact objects, and RPC supports only a limited set of basic data types.

CORBA is an architecture that allows the programmers to access objects that exist on different machines with the level of abstraction we have in RPC.

CORBA uses a language-neutral interface description language that can be used to define the interaction of objects distributed over a network. The main advantage is that CORBA is not linked directly to any programming language, the objects can be written in C++, Java, ADA, etc. Still, CORBA is very complex.

Java RMI is an object-based distributed computing architecture written completely in Java. The Java RMI package is a set of classes and interfaces that enables the programmer to create distributed Java-to-Java applications, in which the methods of remote Java objects can be invoked from another Java virtual machines, possibly on different hosts.

Java RMI is responsible for the following: establish a network connection, find objects on server, call methods, marshal parameters, transfer exceptions, multiplex requests, distributed garbage collection.

7.3 Java Naming Service, RMIRegistry

To invoke a method on a remote object by a caller, that caller must first obtain a reference to the remote object. Most of the time, the reference will be obtained as a parameter to, or a return value from another remote method call. In order to be available for the network, an object must be registered by the server. When a client want to access a remote object, it must obtain a reference to that object. From this point forward we hold a reference to a remote object through its stub, and any call of the remote objects' methods will be as if the object is local.

java.rmi.Naming class allows remote object to be retrieved and defined using the Uniform Resource Locator syntax. The URL consists of protocol, host, port, and name fields. The lookup method returns the remote object associated with the file portion of the name. The bind method binds the specified name to the remote object. It throws an exception if the name is already bound to an object. The rebind method always bind the name to the object even if the name is already bound; the old binding is lost. The unbind method removes the binding between the name and the remote object. The list method returns an array of Strings containing a snapshot of the URLs bound in the registry. Only the host and port information of the URL is needed to contact a registry for the list of its contents, the 'file' part of the URL is ignored.

The RMI runtime substitutes a reference to the remote object's stub for the actual remote object reference specified by the obj argument. Remote implementation objects never leave the virtual machine where they are created, so when a client performs a lookup in a server's remote object registry, a reference to the stub is returned.

The RMIRegistry is a simple server-side bootstrap name server that allows remote clients to get a reference to a remote object. In fact, RMI Registry is a Java application running on the server machine.

It is typically used only to locate the first remote object an application needs to talk to. That object in turn will provide application specific support for finding other objects. Through the registry, the remote objects become available to the network. It also dispatches the remote object's stub and skeleton when requests are mode from the client and the server.

7.4 CORBA Naming Service

The CORBA Naming Service allows names to be bound to the remote object references of CORBA objects within naming contexts.

A name with one or more components can be resolved, starting in any naming context. To resolve a name with several components, the naming service looks in the starting context for a binding that matches the first component. If one exists, it will be either a remote object reference or a reference to another naming context. If the result is a naming context, the second component of the name is resolved in that context. This procedure is repeated until all the components of a name have been resolved and a remote object reference obtained, unless the matching fails on the way.

The class NamingContext provides a series of methods which can be used to obtain reference to remote objects by name. Clients can use the resolve method to look up object references by name. Servers or remote objects use the bind operation to register names for their objects and unbind to remove them. The bind operation binds a given name and remote object reference and is invoked in the context in which the binding is to be added.

The bind_new_context operation is used to create a new context and to bind it with the given name in the context on which is was invoked. Another method called bind_context binds a given naming context to a given name in the context on which it was invoked. The unbind method can be used to remove context as well as names.

The operation list is intended to be used for browsing the information available from a context in the Naming Service. It returns a list of bindings from a target NameContext. Each binding consists of a name and a type - an object or a context.

The CORBA name space allows for the federation of Naming Services, using a scheme in which each server provides a subset of the name graph.

The Java implementation of the CORBA Naming Service is very simple and is called transient because it stores all of its binding in volatile memory.

7.5 Encryption Sockets in Java RMI

Starting with JDK1.2, custom socket types were introduces to provide a more flexible customization of protocols that are used to communicate between remote objects. Now it is possible to create a RMISocketFactory that produces more then one type of sockets. This gives us the possibility to create sockets that realize data connections. Installing our own RMI socket factory allows the RMI transport layer to use a non-TCP or custom transport protocol over IP, rather than TCP, provided by java.net.Socket, which RMI uses by default.

The type of socket to be produced is an application specific decision. We may choose the type of socket that is appropriate for our application. If the server handles a lot of sensitive data, we may want to consider a socket that encrypts the data. If our server deals with video files, which are large, it is recommended to use a socket that makes data compression.

8. Conclusions

The paper has reviewed the Amoeba distributed operating systems, describing its main features and how useful they proved to be over time. The hardware architecture allows the connection in single processor pool of a lot of computing power, consisting of processors found one different machines, with possible different architectures. This is a goal of any distributed operating system, and is currently achieved by creating and running code independent of platform - in Java, or by providing some protocols to communicate over a common interface definition language - using CORBA.

The software architecture reveals an object-oriented architecture, with some unique identifiers for each object.

In the communication, we saw that Amoeba, using some RPC constructed over three primitive operations simulates a remote object method calling. However, the AIL, Amoeba Interface Language allows the definition of only a limited number of types of data. CORBA's IDL is very similar, and it looks like an extension of AIL.

Locating the objects is done is Amoeba using local agents and broadcast communication. More advanced solution in CORBA or Java RMI, using Naming Services or just Registry application implement the same feature.

We saw that the need for secure communication can be solve with hardware or software solution, using encryption algorithm, solution which can be found on systems using encrypted sockets, in Java or CORBA.

Process management in Amoeba is done considering processes and threads as objects.

However, the file system used in Amoeba is quite unique, the representation of files in contiguously form on disk, a set of operation which does not include and features that are not found in other systems, and the utility of it has not been, apparently, proved.

All the features of Amoeba discussed in this paper are captured from a 'on-going' stage. Since 1989, it has evolved, some new features have been added (group communication using a reliable broadcast protocol), some of them have been modified (the RPC primitives are get_Request, put_Reply and trans, and the structure of a request message has been modified), and , eventually, a custom protocol for message transmission has been developed (Fast Local Internet Protocol).

But all these changes, and the features discussed from other distributed operating system makes Amoeba a very useful learning tool, and a proof that the research in current developments of distributed systems can be assisted by judicious reviews of past research.

Bibliography:

1. Mullender Sape, Guido van Rossum, Tanenbaum Andrew, Robbert van Renesse, Hans van Staveren - Amoeba - A Distributed Operating System for the 1990s, http://citeseer.nj.nec.com/mullendar90amoeba.html

2. Tanenbaum Andrew - The Amoeba Microkernel (1994), http://citeseer.nj.nec.com/378298.html

3. Tanenbaum Andrew - A Comparison of Three Microkernels, http://citeseer.nj.nec.com/tanenbaum95comparison.html

4. Bodhisattwa Mukherjee, Karsten Schwan, Prabha Gopinath - A Survey of Multiprocessor Operating System Kernels (1993), http://citeseer.nj.nec.com/mukherjee93survey.html

5. Tannenbaum Andrew, Robbert van Renesse, Hans van Staveren, Gregory Sharp, Sape Mullender, Jack Jansen, Guido van Rossum - Experiences with the Amoeba Distributed Operating System, http://citeseer.nj.nec.com/89039.html

6. Richard F. Rashid - CMU Computer Science : a 25th anniversary commemorative, Addison-Wesley, c1991

7. Tanenbaum Andrew S., Operating Systems : Design and Implementation, Prentice-Hall, c1987

8. Peterson James Lyle, Abraham Silberschatz - Operating System Concepts, Addison-Wesley, c1983

9. Coulouris George, Dollimore Jean, Kindberg Tim - Distributed Systems Concepts and Design, Addison-Wesley, c2001