12.0 Core objects in action

System level services such as object creation and binding are supported by a cooperating set of core objects. Before examining the interfaces and designs of the individual system-level Legion objects involved in these services, it would be useful to have a high-level understanding of the roles these objects play and their interrelationships.

To this end, this section describes how Legion implements a simplified RPC-style interaction between two Legion objects. The description introduces the basic functionality that Legion core objects must support, but does not describe them in detail, nor does it discuss what alternative policies and implementations are allowed by the architecture and object model. These discussions are deferred until section 13.

Suppose that Legion object Foo wishes to invoke member function func() on Legion object Bar (Figure 27).

The typical chain of events consists of several steps: Foo must learn Bar's LOID, get a binding for this LOID, and create or activate Bar.

Figure 27: A simple RPC-style interaction between two Legion objects.

12.1 Determining LOIDs

The programmer, in writing Foo's source code, should be sure that func() is invoked on object Bar. E.g., an MPL programmer would include the following line in the program, where return_value is the same type of variable that func() returns (in this case an integer).

return_value = Bar.func(7);

The compiler generates code to organize the integer argument, constructing a simple macro data-flow program graph [36] representing the function call, then translating the graph into a Legion message, and retrieving the return value and placing it in the return_value variable.

The compiler must associate the context name "Bar" with the appropriate Legion object in order to send a message to Bar, which means that the compiler must know Bar's LOID. One possible approach is to statically translate the programmer-specified name for Bar into a context name that the compiler can use to identify the object. This context name can then be resolved to determine Bar's LOID, either within the compiler or within the object being created (with potentially different results in each case). The runtime library provides routines for using Legion context objects to resolve context names to LOIDs. This assumes that Bar already exists, but an alternative scenario might require that Foo create a new object, in which case the object creation mechanism would return the new object's LOID to Foo. In any event, we can assume that the caller can learn Bar's LOID.

12.2 The binding mechanism

Foo must bind Bar's LOID to Foo's current OA in order to carry out necessary low-level communications for method invocation. This is the binding mechanism, and is depicted in Figure 28.

Figure 28: Potential steps in the Legion binding and class-of mechanisms.

Possible steps in the binding process: Caller needs to bind Callee's LOID to a current OA in order to communicate with Callee. If Caller has previously communicated with Callee, Caller may already have a cached binding for Callee (a). Otherwise, it may need to consult a binding agent (b). The binding agent may have a cached binding for Callee (c), or may need to consult Callee's class, CalleeClass, for the binding (d). In that case, the binding agent needs CalleeClass's binding. If not, it may need to consult CalleeClass's metaclass (e), which means that it must know the metaclass's binding. This recursion is guaranteed to terminate at LegionClass (f), the root of the binding tree. Eventually, the binding agent returns Callee's binding (g) and Caller can send messages directly to Callee (h).

If Foo has previously communicated with Bar, it may already have a cached binding for Bar, so first it checks its binding cache (step 1). Otherwise, it has to consult a binding agent (step 2). The binding agent checks its binding cache (step 3). If this fails, the binding agent must consult Bar's class, BarClass (step 4). However, to do this the binding agent needs BarClass's binding. If it doesn't know BarClass's binding, it must consult BarClassMetaclass (step 5), which means that it must know the metaclass's binding. This recursion is guaranteed to terminate, eventually, at LegionClass (step 6), the root of the binding tree. Eventually, the binding agent will return Bar's binding to Foo (step 7) and Foo can send messages directly to Bar (step 8).

12.2.1 Binding caches

As noted above, if Foo has communicated with Bar prior to the current method invocation, Foo may already have a binding for Bar stored in its local binding cache, maintained within Foo's address space (Figure 28, step 1). Binding caches contain bindings collected during repeated execution of the binding mechanism and take advantage of the fact that once Foo invokes a method on Bar, Foo is likely to invoke other methods on Bar in the near future. Once Foo has cached Bar's binding it just reuses it, instead of seeking the binding over and over again. If Bar is deactivated or migrates to a new OA after its binding is cached in Foo, of course, the cached binding is stale and Foo must obtain the up-to-date OA. Detecting stale bindings and obtaining current OAs is discussed in section 12.4.

12.2.2 Binding agents

If Foo does not have a cached binding for Bar, Foo contacts its binding agent (Figure 28, step 2), which finds and returns bindings for its clients. Multiple objects can use the same binding agent, allowing shared caching of the results of time-consuming binding requests. If the binding agent does not have a cached binding for Bar, it asks Bar's class, BarClass (Figure 28, step 4). First, the binding agent must know BarClass's Legion name -- i.e., its LOID. If it doesn't know, it executes the class-of mechanism, described in section 12.3.

Now that it knows BarClass's name, it must know where it is. The binding agent must therefore get BarClass's binding. It may need to contact BarClass's class, BarClassMetaclass. This may continue through a chain of metaclasses. The binding and class-of mechanisms are recursive, however, and the class-of hierarchy is rooted at LegionClass. The mechanism is guaranteed to terminate.

12.3 The class-of mechanism

If a binding agent or calling object needs to contact an object's class, it must know the class's LOID. This is accomplished through the class-of mechanism, which maps an object's LOID to its class's LOID.

As with bindings, objects and binding agents maintain class-of caches. If Bar is not itself a class object, objects that need to contact BarClass can exploit the fact that A) BarClass's LOID and Bar's LOID contain the same class identifier and B) a class object's LOID contains an empty instance number (as mentioned in section 9.1). Thus, the binding agent can search through its binding cache for a LOID with these characteristics and assume that any such LOID is that of BarClass. As with bindings, binding agents provide a shared caching mechanism for its clients.

If the desired class-of result is not cached locally or in the binding agent, the class-of caller (here Foo's binding agent) must consult the comprehensive and logically-global Legion class map. The class map is maintained by the LegionClass object, which is located at a well-known and unchanging object address. In practice, LegionClass is distributed over multiple cooperating processes and the class map is highly replicated.

12.4 The rebinding mechanism

If Bar is a valid object (i.e. Bar maps to the LOID of an object that was created and has not yet been destroyed), Foo will be able to obtain a binding. However, as noted earlier, bindings (whether they come from binding caches, binding agents or class objects) can become stale: Bar's binding might contain an outdated object address. When this happens, Foo discovers that the binding is stale (typically by noticing repeated failed attempts to communicate with Bar at its old address) and invokes the rebinding mechanism.

The rebinding mechanism mirrors the regular binding mechanism, but it uses the stale object address to ensure that the same binding is not returned. Foo checks its binding cache for Bar's LOID: if the only binding in the cache is the one that contains the stale object address, that binding is removed from the cache and the binding agent is consulted. The stale object address is passed as a parameter to the binding agent. The binding agent may attempt to verify that the binding is stale or may immediately defer to BarClass. In any event, BarClass will serve as the ultimate authority for locating its instances.

12.5 Object activation

In sections 12.2 and 12.4, we based our discussion of the binding process on the fundamental assumption that classes could always return a valid object address for their instances. However inert objects are stored at an OPA, an object persistent address. If Bar is inert when Foo invokes func(), all cached bindings for Bar will be stale. The binding process will require a call to BarClass to obtain a new binding for Bar. BarClass recognizes that Bar is inert and employs the object activation mechanism to move Bar into the active state. BarClass must activate Bar in order obtain a valid binding to return to either Foo or a binding agent operating on Foo's behalf. Figure 29 depicts the object activation process.

Before Bar can be activated, BarClass must determine where it should be placed. The placement process is performed by the class object itself or by an external agent. This may involve consulting an external scheduler (step 1) to choose a host and vault. BarClass must then get Bar's OPA (and thus learn where Bar's inert state is located) from Bar's vault (step 2). BarClass sends an activation request to the desired host (step 3) specifying Bar's LOID, implementation, and OPA. To create a process for Bar, the host must obtain the specified implementation (see section 12.5.1, below), using a shared implementation cache object (step 4). Having downloaded the implementation, the host starts a process for Bar and returns the new binding to BarClass.

BarClass has complete freedom in selecting an appropriate host for its instances. A very conservative and simple class object might place all of its instances on its own host but typically a class object will employ more elaborate and flexible placement policies, often using external scheduling agents. This allows a simple, generic class object implementation to be combined with any number of separately defined scheduling policies. It also supports the dynamic replacement of a class object's scheduling policy. The placement process returns the chosen host object's LOID.

Figure 29: The Legion object activation mechanism.

CalleeClass must first decide where to place the activated Callee. This may involve an external scheduler (a), to choose a host and vault. CalleeClass must then get Callee's OPA (and thus find where Callee's inert state is located) from Callee's vault (b). Finally, CalleeClass sends an activation request to the desired host (c) specifying the Callee's LOID, implementation, and OPA. To creat a process for Callee, the host must obtain the specified implementation, using a shared implementation cache object (d). Having downloaded the implementation, the host starts a process for Callee and returns the binding to CalleeClass.

When an external scheduling agent is used, as in Figure 29, it may implement any specialized placement policy appropriate for the class. For example, it may use specialized policies appropriate for a 2D finite difference class in an ocean model, or for a class designed for objects that execute only on machines local to an organization and use only those resources not currently supporting interactive sessions. The agent will typically interact with other information providers (objects that gather and dynamically update information about which hosts are available, their type and attributes, their current load, and so on). Note, though, that the placement process is guided by a set of restrictions determined by the class, such as a list of acceptable object implementations. For more details on the scheduling model see Karpovich [19]. For more information on application specific scheduling agents see Berman [3].

The class must ensure that the instance will be able to access its OPR when it runs on that host: the instance must have access to the vault object that manages its OPR. Not all vaults are accessible from all hosts, so before a class activates an instance it must verify that the vault holding the instance's OPR is compatible with the intended host (indicated by the host and vault objects' attributes [see section 10.0]). If a class needs to execute an instance on a host that is incompatible with the instance's vault, the instance's OPR must move to a compatible vault before the object can be started.

Once this is settled, the class object invokes the host object's startObject() method. Parameters to this method specify the LOID and OPA of the object to be started and the LOID of the implementation object (see sections 12.5.1 and 13.5) to be used.

Note, however, that the startObject() method may not succeed. The host object is free to refuse the activation request for policy or security reasons (e.g., only privileged users can use that particular resource or a host might decide that its load is too high to accept new object activations). The host may have simply crashed and will, at least temporarily, be unable to service the request. If the startObject() invocation fails, the class object must make another placement selection, possibly re-invoking the external scheduling agent.

12.5.1 Implementation objects

Once a host accepts an instantiation request, it must obtain appropriate executable code. When startObject() is invoked on a host, the class passes the appropriate implementation object's LOID so that the host can retrieve appropriate executable code. Legion objects that contain executable code for other objects are called implementation objects. Typically, an implementation object contains a binary executable file, although the model explicitly allows shell scripts and interpreted code, such as Java bytecode or Perl. Each class maintains a list of the implementation objects that are suitable for its instances. Several different implementation objects might be maintained by one class to support the use of multiple platforms -- a class can have implementation objects for different architectures, for different operating systems, for different memory requirements, etc.

12.5.2 Implementation caches

To service a startObject() request, the host object must find or make a local copy of the executable code contained within the specified implementation object. A simple host object could retrieve, via the member functions of implementation objects, the executable code on every startObject() invocation. However, retrieving executable code can be expensive, in both communication time and local storage space. Thus, groups of host objects typically share an external implementation cache, a Legion object that downloads executable code on behalf of a set of host objects and caches copies of the executables to save storage space and communication time. To use an implementation cache, the host object sends the cache object the desired implementation object's LOID. The cache object responds with the name of a local file that contains the cached executable code: the host need not be aware of whether the cache retrieved the executable in response to this request, or used an existing local copy. (Please see section 10.0 in the System Administrator Manual for more discussion of the implementation model.)

12.5.3 Running objects

Once the implementation is locally available, the host object can execute it. How an executable is used depends on its type and the host object's characteristics. E.g., if the implementation consists of native executable code the host runs the executable as a normal process; if the host is a normal Unix workstation it uses the fork() and exec() system calls. If the implementation is Java byte code the host executes it within a Java Virtual Machine. Or, if the host represents a workstation farm that is managed by a queueing system such as Condor [22] or LoadLeveler [17], the host starts the object through the batch system's particular interface.

Once the host activates the object, the host object passes the newly started object its LOID and new OPA. The host object determines the activated object's local OA, and returns it to the calling class object. The class marks the instance as active, records the instance's OA, and can once again return accurate bindings for the instance.

The binding and activation processes described in this section can be time consuming. In practice, aggressive caching of bindings and object executables helps bypass much of the mechanism and its cost. The benefits of this design include flexibility and the convenient transparent binary migration, one-step system-wide binary replacement for objects, object-local policy autonomy, licensing and proxies, user-definable scheduling policies, user-definable persistent storage, and more.

Directory of Legion 1.8 Manuals
[Home] [General] [Documentation] [Software]
[Testbeds] [Et Cetera] [Map/Search]

Free JavaScripts provided by The JavaScript Source