Resource allocation is a negotiation process between resources and objects. Legion encompasses a variety of resources, including hosts, networks, vaults, and I/O devices such as printers and sensors. To accomplish tasks, users will require allocations of time on some or all of these resources and must be able to control placement of their objects' active and persistent states: otherwise, Legion will not be a suitable platform for certain types of applications. Administrators, on the other hand, must regulate usage of and control access to their resources, as well as enforce local policies of usage, security, etc. Different applications may require certain levels and types of parallelism, storage and memory space, I/O support, communication, and communication topology. A single generic resource scheduling arrangement is simply not feasible under these conditions, and in order to give equal power to resource providers and consumers both parties must be able to arrive at an arrangement.
Application- and object-specific allocation of resources is therefore crucial to achieving both user and administrator goals, and Legion supports the development and use of allocation algorithms tailored to objects or applications. This way, the resource objects embody the resource provider's interests, and each provider can create his or her own flavors of resource objects, or use existing implementations. Class objects will enforce policies for their instances, and both parties can export interfaces to facilitate negotiations. This placement philosophy allows the tailoring of each allocation decision to the application, so as to better match actual application run-time behavior and application-specific knowledge.
In the allocation of resources for a specific task there are three steps: decision, enactment, and monitoring. In the allocation decision stage the task's characteristics, requirements, and run-time behavior; the resource's properties and policies; and users' preferences must all be considered. Legion provides an information infrastructure and a resource negotiation framework for this decision-making process. The allocation decision includes target hosts and storage space with assorted host objects and vaults. At the enactment stage, the allocation coordinator sends an activation request, including the desired host-vault mapping for the object, to the class object which will carry out the request. The class object checks that the placement is acceptable and then coordinates with the host object and vault to create and start the new object. The monitoring stage ensures that the new object is operating correctly and that it is using the correct allocation of resources. An object-mandatory interface includes functions to establish and remove triggers that will monitor object status.
There are three special objects involved in Legion resource management; the Collector, the Scheduler, and the Enactor. The Collection acts as a database of resource information, constantly monitoring the system's host and vault objects to determine what resources are in use and what are available for what kind of tasks. The Scheduler determines possible schedules of resource use for specific tasks and makes policy decisions as to where the tasks should be placed. The Enactor negotiates with resources to carry out those schedules and acquires reservation tokens from successful negotiations. Figure 19 shows how these objects are placed in the Legion object model.
Suppose, for example, that a user wants ClassFoo to start instance Foo on another host. The user sends a call (Figure 20, step 1) to the Scheduler.1 The Scheduler then consults the Collection to determine what resources are available and appropriate for Foo (step 2) and builds a sample schedule or series of schedules (step 3). It then sends a sample schedule to the Enactor (step 4). The Enactor contacts each resource on the schedule and requests an allocation of time (step 5). Once it has contacted each resource and reserved the necessary time it confirms the schedule with the Scheduler, and then contacts ClassFoo and tells it to begin Foo on the appropriate resources (step 6). ClassFoo contacts the resource(s) and sends the order to create Foo (step 7).
Before the Scheduler approaches the Collection it needs to know Foo's specific needs: computing time, any dependency graphs, special requirements, etc. The Scheduler either explicitly knows this information., if it class-specific, or it can obtain descriptive information from the class through the attributes interface. With this information, it can ask the Collection for the correct kinds of resources. If the Scheduler has requested an SPARC, for example, the Collection determines which SPARCs are accessible, available, and have the proper amount of free space. Note that individual resources may limit outside usage to certain types of users, objects, hosts, etc., so the Collection stores information regarding which resources accept instances of ClassFoo, on its particular host, started by a particular user.
The Collection returns a list of matching resources to the Scheduler. The Scheduler builds a set of possible schedules, prioritizes them, and sends an ordered list of schedules off to the Enactor. (Note that this can vary, depending on the individual Scheduler. The Scheduler might send only one or several possible schedules.)
When the Enactor is ready to request reservations of time and space on the appropriate resources it methodically goes down its list and approaches each one individually. If any resources refuses the Enactor's request, the Enactor either starts on the next one or informs the Scheduler that it needs a new schedule. In Figure 20, host object Beta and vault object Beta are the only resources required, so the Enactor approaches each one with the make_reservation() function (this function asks for an instant reservation). It requests reservation for the host and the vault separately. Host object Beta then decides whether or not to accept the reservation. Note that Beta is free to refuse the reservation at any point during this procedure, regardless of its normal policies towards the user and the user's host, if previous reservations or internal considerations require a cancellation. If it refuses, the Enactor tells the Scheduler that the schedule is not possible, and requests another schedule, or, if the Scheduler has sent a list of schedules, the Enactor moves down to the next schedule. If this happens after other hosts objects on the failed schedule have been contacted and have agreed to make reservations, the Enactor contacts them again to release its reservations. The prototype Enactor allows schedule expression as a difference set from the previous schedule. This system is intended to avoid "reservation thrashing," i.e., repetitive reservations when an Enactor releases a reservation and immediately re-reserves the resource as part of a new schedule. In this case, however, host object Beta decides to allow a reservation and sends the Enactor a reservation token. The Enactor then contacts vault object Beta. Once all resources on a schedule have been contacted and have sent in reservation tokens, the Enactor notifies the Scheduler that the task can be completed.
The Scheduler then tells the Enactor to contact ClassFoo. The Enactor sends a call to create_instance(reserved host object name, reservation token) to ClassFoo, which in turn sends a start_object(reservation token) call to host object Beta and the name of the vault Beta should use.
Both ClassFoo and the resource have veto power at all times. This allows Legion to handle denial or failure at any point during the reservation process. Any party can refuse to talk to another, in which case the Enactor must ask the Scheduler for another schedule and try again. A reserved resource can also override the start_object() call. The two parties remain autonomous during this entire procedure, and are not obligated to honor each other's commitments.
Depending on the individual resource, the reservation tokens may have a time-out period after which the reservation is invalid. The token guarantees that a block of time and space will remain open for a specific period, beginning with the creation of the token. Note that the token may expire by the time Class Foo is ready to use it.
A system may have multiple Schedulers, for different processes, problems, levels of granularity, etc. For information on writing your own Scheduler, or using multiple Schedulers, please contact the Legion Research Group.
1. ClassFoo can also have an associated external scheduler so that a user could call the class and the class would then call its scheduler. Back