(ref.doc)Emerald

Fine-Grained Mobility in the Emerald System
by Eric Jul, Henry Levy, Norman Hutchinson, and Andrew Black
in ACM Transactions on Computer Systems, Vol 6, No 1, February 1988

These notes range from simple repetition of interesting or major
points, to comments, sometimes with critics. They are presented in
sequential order, closely following the text itself.

[Abstract, p 109 ] Emerald is presented as an `object-based' system
and not an `object-oriented' one. What is the difference? In an
object-based system, an object is a support for the implementation
more than a conceptual tool. There is usually no inheritance: an
object definition is always instantiable (although here, polymorphism
is supported through the concept of abstract types: see 2.2 Types in
Emerald, p 113). The system may be distributed, but the objects
themselves are not: an object belongs to only one process (here:
resides on one node) at a time.

[1. Introduction, p 110] Emerald is based on the assumption, common in
the Unix world (because of both the architecture of the machines on
which it usually runs, having numerous registers, and the existence of
global data), that processes are necessarily heavy. Thus, the
fine-grained mobility is justified here by the existence of pure data
objects.

[2. Overview of Emerald, p 112] An interesting example of one of the
common justifications for creating a new language: a progress in the
compiler technology makes a potential new compiler able to use
efficiently an information that the semantics of the existing
languages do not allow it to get.

[2.2 Types in Emerald, p 114] The abstract types in Emerald do not
bind explicitly to language modules (classes).
`Conceptually, each object carries its own code': at first thought,
this sounds like a major difference with the conceptual framework of
C++! But then, one speaks of shared `concrete type objects',
immutable, implemented as relocatable code objects, dynamically
linkable. Well, this is very close to the class implementation (with
the restriction that there is no class/static data, and no provision
for code sharing between implementations of classes in deep
inheritance trees?).

[2.3 Primitives for mobility, p 115] Attachment is an interesting
concept, but a dangerous one, precisely because of its transitivity.
It is not said whether it is a hint to the compiler (as the move
primitive) or whether it is stronger, nor whether it is static or
dynamic, nor whether it can be undone, either explicitly, or not, for
instance out-going from a scope.

[2.4 Parameter passing, p 115] The problems raised in the other
systems reviewed all disappear when applying a separation between the
interface and the implementation, i.e.  systematically access objects
through handles: there may as well be handles, independently on
whether the objects are local or remote to the function invoked. The
handle is then close to what is called here: `the invocation record'.

[2.4 Parameter passing, p 116] `call-by-visit' and `call-by- move'
both very seducing.

[2.5 Processes, Objects and Mobility, p 116] Powerful model for
processes, with a stack analogy. Useful formalization of the processes
through `activation records', close to transactions.

[3. Implementing Mobility in Emerald, p 118] `Object IDs' evoked, but
not developed. Source of bottle-necks in distributed systems.

[3.1 Object Implementation and Addressing, p 118] `Shared memory',
`Protection is guaranteed by the compiler': typical move of expensive
checking from run-time to compile-time, made possible through static
typing. Memory protection is usually provided very efficiently at
run-time by the hardware, but at the cost of heavy context switching
between processes. This cost can be eliminated if the language may
guarantee that there is no violation of the limits of the memory
spaces. This is an advantage of having multi-processing addressed by
the language conceptual model. In Emerald (as there must probably be
anyway), there are still some `run-time checks' inserted in the code,
but under the responsibility of the compiler.

[3.1 Object Implementation and Addressing, p 119] Three kinds of
objects: global, local and direct. The difference between on the one
hand global, and on the other local and direct objects is conceptual:
it is a question of scope. This between on the one hand global and
local, and on the other direct is of implementation: direct objects
are implemented as part of the representation of their enclosing
object.

Object descriptor: one for every global object, on every node where
the object is referenced. Small imprecision in the text: the `G bit'
indicates that the object is global (instead of whether it is local or
global), and that the structure is thus an `object descriptor' (not
needed for local objects, as they are visible only within the scope of
their enclosing object, and reside on the same node as it).

The `object data area' for local objects has also a `G bit',
indicating that the object is local, but the `R bit' is useless, since
the local object is always resident on the only node where is may be
referred to: this where its enclosing object resides.

Object descriptors act as `smart pointers'. The price is only one
systematic additional indirection.

[3.2 Finding Objects, p 120] Bright idea: keeping all the nodes
up-to-date is unnecessarily expensive, keeping track of the objects'
locations through pathes of `forwarding addresses', these being
updated only when proved to be out-of-date, provides the same service
in a globally less expensive way. This is an application of the
principle of `delayed update'. The response time to an arbitrary
request becomes less deterministic, but the global performance
improves. Conflicting `forwarding addresses' are resolved with the
help of a time-stamp mechanism (a counter: but how is the wrapping
handled?).

[3.2 Finding Objects, p 120] The existence of a `unique network-wide
Object Identifier' is a necessity, but a challenge in itself. If
objects are to be created dynamically, object id servers will be
needed to maintain the id database, which may prove to be bottlenecks
to the whole system. The traditional answer is then to define naming
hierarchies, and thus to distribute the responsibility for the naming
to domain servers.  At least these domains cannot in a system like
Emerald be location based. The existence of such domains allows for
the use of relative names, at the expense of a communication need to
fully resolve the identifications. Aliasing facilities may also be
considered, with a penalty in raising consistency management problems.

[3.2 Finding Objects, p 120] Latency problem in the alternative scheme
of updating all forwarding addresses.

[3.2 Finding Objects, p 120] Other justification: the disputable `what
you pay is what you get' principle.

[3.2 Finding Objects, p 121] Complex two-phase broadcast protocol in
case there is no progress in the search for the current address at any
step. This procedure is very heavy.  Efficiency relies on the
optimistic assumption that objects are available, or at least
correctly located in some accessible nodes.

[3.3 Finding and Translating Pointers, p 121] What is called here
`direct memory addresses', is actually one-level indirection. Time
efficiency is considered here, where `cost' or `price' are mentioned.
Again, justification by the `what you pay is what you get' principle.

[3.3 Finding and Translating Pointers, p 121-122] The example given in
figures 4 and 5 is not totally clear: one understands that the
template entries contain a count which is not explicited in the
example, and a static type identifier for the members (1: monitor, 2:
pointer, 4: data?), the use of which is not clear (and questionable:
`data' is no strong type, and does not provide a basis for an
extendible scheme?); the role of the `myself' pointer in the `Object
Data Area' to the `Object Descriptor' is not obvious. The embedding of
a monitor inside every object is interesting, as it stresses the
nature of every object as a shared resource. It does however only
provide a quite primitive scheme for the access of resources: locking
for access, with queuing the requests. This is insufficient to
prevent, or help to resolve dead-locks... This is inadequate for long
transactions, and unnecessarily tough to rule non- conflicting
accesses.

[3.3 Finding and Translating Pointers, p 123] There are templates also
for activation-records. These are not presented in more detail and
some points remain unclear: what are the `registers' (the processor
registers, as explained later [3.4.3])?

[3.4 Moving Objects, p 123] Copy of code is not always necessary.

[3.4.1 Moving Data Objects, p 123] Details unclear to me: why are the
forwarding address and the address of the object's descriptor on the
source node sent (if the data itself is sent)?

[3.4.2 Moving Process Activation Records, p 123] Again, not fully
understood. Why would the overhead of linking the activation record to
the object at invocation time, and unlinking at exit time from
invocation be so high? Relatively to what? Is there a relation between
the linked list of activation records and the queue in the monitors,
as defined earlier? What is done of the activation records once they
have been invoked (marked as discardable for the garbage collector, I
presume)?  When is it `necessary' (always when an object is moved?) to
break a stack into parts? How is such a fragmented stack being
searched? What is the relation between the order in the list of
activation records for a given object, and the order in a process
stack?

[3.4.3 Handling Processor Registers, p 124] The complexity rises, and
the solutions chosen feel less sophisticated: all the processor
registers are sent?! Anyway, it feels not mandatory to understand such
technical points on the basis of this description.

[3.5 Garbage Collection, p 126] `any object based system': a disputed
issue, garbage collection is not provided with C++. And it is not
strictly speaking bound to object orientation, although Meyer
considers it a criterium for defining an object-oriented language...

Object mobility doesn't add to the complexity of determining whether
or not an object is being referred to, with comparison to any
distributed object system: the problem comes from the possible
existence of moving references. Garbage objects do not move.

Two-level collection: node-level and distributed. Only the second
requires collaboration from the various nodes. Basic scheme: `mark and
sweep'. `RefGivenOut' bit set for objects referred to externally.

`Mark and sweep' scheme: objects are marked white. Reachable objects
are marked grey. Grey object are scanned to mark grey the objects they
refer to; when this is done for one object, it is marked as black.
Remaining white objects are garbage.

The distributed collector works only with the objects which have the
RefGivenOut bit set, which are ignored by the node-local collector.

Distributed collection is performed in parallel on all nodes. Moving
objects are dealt with immediately. Problem with objects on
non-reachable nodes overcome: not all nodes need to be up
simultaneously.

In Emerald, garbage collection may be performed in parallel with other
processing, at a high initial cost, which can be delayed by `freezing'
the objects concerned until they are actually used, before what they
need to be processed by the collector.

[4. Performance, p 128] The testing network is made of only 4 nodes.
The mobility is evaluated by comparing two implementations of a mail
system driven by a synthetic workload, the one using mobility, the
other not. The results show that mobility reduced the time used by
22%, and the number of network packets by 34%.

[5. Summary, p 131] Good conclusion, clear: recall of the goals, of
the main achievements, and mention of the problems met.