orca.policy.core
Class BrokerWorstFitPolicyPlugin

java.lang.Object
  orca.shirako.core.Policy
      orca.shirako.core.BrokerPolicy
          orca.policy.core.BrokerBasePolicyPlugin
              orca.policy.core.BrokerSimplePolicyPlugin
                  orca.policy.core.BrokerPriorityPolicyPlugin
                      orca.policy.core.BrokerWorstFitPolicyPlugin

All Implemented Interfaces:

IBrokerPolicy, IClientPolicy, IInitialize, IPolicy, IRecover, ISerialize, IServerPolicy

Direct Known Subclasses:

BrokerQueuedWorstFitPolicyPlugin

public class BrokerWorstFitPolicyPlugin
extends BrokerPriorityPolicyPlugin

The AgentWorstFitPolicyPlugin performs a worst fit allocation algorithm over an inventory of machines. It gives priority to extending reservations. It also gives priority based on preset priorities of request types.

Author:

grit

Field Summary

protected int	allocated Used to count how many requests have been successfully allocated
static int	Dimensions
protected int	failed Used to count how many requests have failed
protected LogicalInventory	inventory Holds a set of logical machines it has from tickets - it represents the agent's holdings
static java.lang.String	PropertyForceNewId Used for testing to force an id switch
static java.lang.String	PropertyIDList Properties appended to each donated reservation to indicate the ids used for nodes provided by this reservation
static java.lang.String	PropertyIDs Saves list of machine ids for recovery

Fields inherited from class orca.policy.core.BrokerPriorityPolicyPlugin

PropertyRequestTypeCount, PropertyRequestTypeName, PropertyRequestTypePriority, requestTypePriorities

Fields inherited from class orca.policy.core.BrokerSimplePolicyPlugin

ADVANCE_TIME, CALL_INTERVAL, CLOCK_SKEW, lastAllocation, ready, REQUEST_TYPE

Fields inherited from class orca.policy.core.BrokerBasePolicyPlugin

calendar, PropertyDiscoverTypes, PropertyTypeCount, PropertyTypeDescriptionPrefix, PropertyTypeNamePrefix, requireApproval

Fields inherited from class orca.shirako.core.BrokerPolicy

recoverer

Fields inherited from class orca.shirako.core.Policy

actor, clock, guid, logger, PropertyGuid

Constructor Summary

BrokerWorstFitPolicyPlugin()

Method Summary

void	allocate(long cycle) Allows additional configuration of priority between multiple types of requests as specified in REQUEST_TYPE.
void	allocate(ReservationSet requests, long startCycle) Allocate requests.
protected boolean	canResize(BrokerReservation r, long[] available) Determine if this request can be resized.
protected long	checkRequestEndTime(long[] maxResources, long start, long end, BrokerReservation r) Determine if the new growth affects the endtime of the request - would only affect the endtime
void	configure(java.util.Properties p) Do any configuration items that should occur
protected ResourceTable	constructTable(long start, long end) Constructs a table of available resources for the given interval
void	donate(ReservationClient r) Convert incoming ticket information into the agent's machine representation and add it to its logical inventory.
protected void	extendTicket(BrokerReservation r, ResourceTable table, long start, long end) Extend a ticket.
AllotmentTable	findAllotment(ResourceEntry request, ResourceTable table, int unitsNeeded, AllotmentTable allotment, int minIndex, BrokerReservation r, int extendedUnits) Recursively determines the machines and number of units per machine that will be allocated to a request
void	finish(long cycle) Clean inventory Informs the mapper that all processing for the specified cycle is complete.
protected java.util.Vector<ID>	getIdentifiers(java.util.Properties p) Obtains the identifiers from a properties list
protected java.util.ArrayList<ID>	getIDList(ReservationClient r)
protected java.util.ArrayList<ID>	getIDList(java.lang.String str)
protected java.lang.String	getIDString(java.util.ArrayList<ID> list)
LogicalInventory	getLogicalInventory()
MachineState	getLogicalMachine(ID machineId)
protected long[]	getMax(ResourceSet set) Obtains the upper bound on resource dimensions
protected long[]	getMin(ResourceSet set) Obtains the lower bound on resource dimensions
protected long[]	getShares(ResourceSet set) Returns the current resource shares held by this resource set
protected long[]	growResources(AllotmentTable allotment, ResourceEntry minRequest, long[] maxRequest, BrokerReservation r) Determines how far we can grow the minimum request, but not exceed the maximum request
protected void	issueTicket(BrokerReservation r, AllotmentTable allotment, long[] maxResources, long start, long end) Reserves the allotment being allocated to the ticket from the agent's inventory and creates the ticket to be given to the request.
protected AllotmentTable	rebuildAllotment(ResourceTable machines, java.util.Vector<ID> ids, long start, long end) Rebuilds the allotment table for the reservation represented by the given ids
protected void	release(BrokerReservation r) Release resources associated with a client reservation.
protected void	releaseNotApproved(BrokerReservation r) Release the resources for a reservation that is not approved.
protected void	releaseResources(ResourceSet set, Term t) Releases the resources assigned to this reservation
protected void	removeIds(java.util.Vector<ID> ids, int count) Removes count identifiers from the specified list
void	reset(java.util.Properties p) De-serializes the object from the given properties list.
void	revisit(ResourceReservation reservation) Informs the mapper about a reservation.
java.util.Properties	save() Serializes the object into a properties list.
void	save(java.util.Properties p) Serializes the object into the given properties list.
protected void	storeIDList(ReservationClient r, java.util.ArrayList<ID> list)
protected boolean	ticket(BrokerReservation r, ResourceTable table, long start, long end) Issue a new ticket to a request. This is the first request for a ticket We try to satisfy the request for the lower bound of requested resources per dimension.

Methods inherited from class orca.policy.core.BrokerPriorityPolicyPlugin

addRequestType

Methods inherited from class orca.policy.core.BrokerSimplePolicyPlugin

allocateExtending, allocateNewBids, bind, calculateAvailable, createSourceHashtable, extend, extractTicket, formulateBids, getAllocation, getApprovedTerm, getNextAllocation, getRenew, getStartForAllocation, prepare, processRenewing, query, satisfyAllocation, switchSource, verifyWantedResources

Methods inherited from class orca.policy.core.BrokerBasePolicyPlugin

addForApproval, addForApprovalCalendar, addToCalendar, approve, checkPending, close, closed, count, getClosing, getForApproval, initialize, notApprove, release, remove, removeForApproval, revisitClient, revisitServer

Methods inherited from class orca.shirako.core.BrokerPolicy

demand, getHoldings, getHoldings, getRedeeming, prepareExtend, prepareReserve, reset, revisit, ticketSatisfies, updateTicketComplete

Methods inherited from class orca.shirako.core.Policy

error, extend, getGuid, internalError, logError, logWarn, setActor, setLogger

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface orca.shirako.api.IPolicy

extend, getGuid, setActor, setLogger

Methods inherited from interface orca.shirako.api.IPolicy

extend, getGuid, setActor, setLogger

Field Detail

PropertyIDList

public static final java.lang.String PropertyIDList

Properties appended to each donated reservation to indicate the ids used for nodes provided by this reservation

See Also:

Constant Field Values

PropertyForceNewId

public static java.lang.String PropertyForceNewId

Used for testing to force an id switch

PropertyIDs

public static java.lang.String PropertyIDs

Saves list of machine ids for recovery

Dimensions

public static int Dimensions

inventory

protected LogicalInventory inventory

Holds a set of logical machines it has from tickets - it represents the agent's holdings

failed

protected int failed

Used to count how many requests have failed

allocated

protected int allocated

Used to count how many requests have been successfully allocated

Constructor Detail

BrokerWorstFitPolicyPlugin

public BrokerWorstFitPolicyPlugin()

Method Detail

donate

public void donate(ReservationClient r)
            throws java.lang.Exception

Convert incoming ticket information into the agent's machine representation and add it to its logical inventory.
Accepts ticketed resources to be used for allocation of client requests. The policy should add the resources represented by this reservation to its inventory. This method is invoked with the kernel lock on.

Note: This method will be invoked only for resources not directly requested by the policy. For example, exported resources claimed manually by an administrator. The policy is itself responsible to "donate" resources to its inventory when resources it requests become available.

Specified by:

donate in interface IServerPolicy

Overrides:

donate in class BrokerBasePolicyPlugin

Throws:

java.lang.Exception

allocate

public void allocate(long cycle)
              throws java.lang.Exception

Allows additional configuration of priority between multiple types of requests as specified in REQUEST_TYPE. For example, requests for "master" nodes may be given priority over "worker" requests.
Run an allocation of requests against all sources, given a set of pending bids by using FCFS giving extends priority. This simple policy runs through the bids in iterator order, and give every request min(requested,available) until we run out. It gives priority to extending requests compared to new requests. Assumes that there is only 1 source reservation per type. Makes the assumption that we allocate resources sequentially in time, so there are never less resources available in the future.
Allocates resources to all clients who have requested them. This method is called by the policy once per cycle. The method should determine whether to perform resource allocation on the given cycle and what requests to consider in that process. This method is invoked with the kernel lock on.

Specified by:

allocate in interface IServerPolicy

Overrides:

allocate in class BrokerPriorityPolicyPlugin

Parameters:

cycle - the cycle for this allocation

Throws:

java.lang.Exception

getIdentifiers

protected java.util.Vector<ID> getIdentifiers(java.util.Properties p)
                                       throws java.lang.Exception

Obtains the identifiers from a properties list

Parameters:

p - the properties

Returns:

a set of ids

Throws:

java.lang.Exception

removeIds

protected void removeIds(java.util.Vector<ID> ids,
                         int count)
                  throws java.lang.Exception

Removes count identifiers from the specified list

Parameters:

ids - set of ids

count - number of ids to remove

Throws:

java.lang.Exception

constructTable

protected ResourceTable constructTable(long start,
                                       long end)

Constructs a table of available resources for the given interval

Parameters:

start - start of the requested ticket

end - end of the requested ticket

Returns:

a table representing the available machines and their resources for the specified time period

rebuildAllotment

protected AllotmentTable rebuildAllotment(ResourceTable machines,
                                          java.util.Vector<ID> ids,
                                          long start,
                                          long end)

Rebuilds the allotment table for the reservation represented by the given ids

Parameters:

machines - set of the machines

ids - the ids of machines from which to rebuild allotment table

start - start of the requested ticket

end - end of the requested ticket

Returns:

an allotment table

getMax

protected long[] getMax(ResourceSet set)
                 throws java.lang.Exception

Obtains the upper bound on resource dimensions

Parameters:

set - contains the properties

Returns:

the maximum available over all resources

Throws:

java.lang.Exception

getMin

protected long[] getMin(ResourceSet set)
                 throws java.lang.Exception

Obtains the lower bound on resource dimensions

Parameters:

set - contains the properties

Returns:

the minimum available over all resources

Throws:

java.lang.Exception

getShares

protected long[] getShares(ResourceSet set)
                    throws java.lang.Exception

Returns the current resource shares held by this resource set

Parameters:

set - resource set

Returns:

Throws:

java.lang.Exception

issueTicket

protected void issueTicket(BrokerReservation r,
                           AllotmentTable allotment,
                           long[] maxResources,
                           long start,
                           long end)
                    throws java.lang.Exception

Reserves the allotment being allocated to the ticket from the agent's inventory and creates the ticket to be given to the request.

Parameters:

r - request

allotment - what is being given to the request

maxResources - resources being allocated to the ticket

start - when the ticket will start

end - when the ticket will end

Throws:

java.lang.Exception

canResize

protected boolean canResize(BrokerReservation r,
                            long[] available)
                     throws java.lang.Exception

Determine if this request can be resized. Max becomes the min amount

Parameters:

r - request

available - the resources that are available for this request

Returns:

true if the all the minimum resources requested by the request is less than what's available; false otherwise.

Throws:

java.lang.Exception

extendTicket

protected void extendTicket(BrokerReservation r,
                            ResourceTable table,
                            long start,
                            long end)
                     throws java.lang.Exception

Extend a ticket. Agent tries to minimize the number of id changes that are made to this request by first seeing if it can satisfy the request with the previously assigned logical machines. If not, then it performs the same algorithm as a new ticket request.
Extends are tricky. Currently we are not allowed to change identifiers. First, we shrink the reservation (if necessary) Second, we try to resize. We compute how much space we have left on each logical node this reservation is currently assigned to. If this space is not within the resource requirements of the reservation we will fail it. This is somewhat conservative: if we have multiple nodes hosted on the same logical node, we may be able to scrub more free space and actually satisfy the resizing part. Finally, if we need to add nodes, we try to allocate them.

Parameters:

r - the request

table - the available machines from the logical inventory

start - requested restart

end - requested end

Throws:

java.lang.Exception

ticket

protected boolean ticket(BrokerReservation r,
                         ResourceTable table,
                         long start,
                         long end)
                  throws java.lang.Exception

Issue a new ticket to a request.
This is the first request for a ticket We try to satisfy the request for the lower bound of requested resources per dimension. If this succeeds, we find the maximum amount by which we can grow each of the pre-allocated nodes. We compute the final allocation and commit it to the inventory. Finally, we issue a ticket will all required properties.

Parameters:

r - the request

table - the available machines from the logical inventory

start - requested start

end - requested end

Returns:

true if ticket successfully completed, false otherwise

Throws:

java.lang.Exception

growResources

protected long[] growResources(AllotmentTable allotment,
                               ResourceEntry minRequest,
                               long[] maxRequest,
                               BrokerReservation r)

Determines how far we can grow the minimum request, but not exceed the maximum request

Parameters:

allotment - the current allotment

minRequest - the minimum request

maxRequest - the maximum a request may grow to

r - the request

Returns:

the new resource vector with possibly more resources than the minimum request

checkRequestEndTime

protected long checkRequestEndTime(long[] maxResources,
                                   long start,
                                   long end,
                                   BrokerReservation r)
                            throws java.lang.Exception

Determine if the new growth affects the endtime of the request - would only affect the endtime

Parameters:

maxResources - current resource vector for the request

start - when the lease will begin

end - when the lease will end

r - the request

Returns:

the new endtime

Throws:

java.lang.Exception

allocate

public void allocate(ReservationSet requests,
                     long startCycle)
              throws java.lang.Exception

Allocate requests. Iterate through all the requests, create a table representing the available resources for the duration of the request, and determine if it is a new request or an extend request.

Parameters:

requests -

Throws:

java.lang.Exception

findAllotment

public AllotmentTable findAllotment(ResourceEntry request,
                                    ResourceTable table,
                                    int unitsNeeded,
                                    AllotmentTable allotment,
                                    int minIndex,
                                    BrokerReservation r,
                                    int extendedUnits)
                             throws java.lang.Exception

Recursively determines the machines and number of units per machine that will be allocated to a request

Parameters:

request - the request's resources

table - the resources from the logical inventory available for this request

unitsNeeded - number of units needed to successfully satisfy this request

allotment - what has been allocated to this request

minIndex - how far the search should continue

r - the request

extendedUnits - additional units that have already been extended - only for extendTicket

Returns:

the allotment for this request

Throws:

java.lang.Exception

finish

public void finish(long cycle)

Clean inventory
Informs the mapper that all processing for the specified cycle is complete. The mapper can safely discard any state associated with the cycle or any previous cycles. This method is invoked with the kernel lock on.

Note: The cycle number parameter is redundant and is passed for convenience. The policy can always obtain the cycle number by calling IActor.getCurrentCycle().

Specified by:

finish in interface IPolicy

Overrides:

finish in class BrokerBasePolicyPlugin

Parameters:

cycle - the cycle number that has just passed

release

protected void release(BrokerReservation r)

Description copied from class: BrokerBasePolicyPlugin

Release resources associated with a client reservation.

Overrides:

release in class BrokerBasePolicyPlugin

Parameters:

r - client reservation

releaseNotApproved

protected void releaseNotApproved(BrokerReservation r)

Description copied from class: BrokerBasePolicyPlugin

Release the resources for a reservation that is not approved.

Overrides:

releaseNotApproved in class BrokerBasePolicyPlugin

releaseResources

protected void releaseResources(ResourceSet set,
                                Term t)

Releases the resources assigned to this reservation

Parameters:

r -

configure

public void configure(java.util.Properties p)
               throws java.lang.Exception

Do any configuration items that should occur

Overrides:

configure in class BrokerPriorityPolicyPlugin

Parameters:

p - properties

Throws:

java.lang.Exception

save

public java.util.Properties save()
                          throws java.lang.Exception

Description copied from interface: ISerialize

Serializes the object into a properties list.

Specified by:

save in interface ISerialize

Overrides:

save in class Policy

Returns:

properties list representing this object

Throws:

java.lang.Exception

save

public void save(java.util.Properties p)
          throws java.lang.Exception

Description copied from interface: ISerialize

Serializes the object into the given properties list.

Specified by:

save in interface ISerialize

Overrides:

save in class Policy

Parameters:

p - properties list to serialize the object into

Throws:

java.lang.Exception

storeIDList

protected void storeIDList(ReservationClient r,
                           java.util.ArrayList<ID> list)

getIDString

protected java.lang.String getIDString(java.util.ArrayList<ID> list)

getIDList

protected java.util.ArrayList<ID> getIDList(ReservationClient r)

getIDList

protected java.util.ArrayList<ID> getIDList(java.lang.String str)

reset

public void reset(java.util.Properties p)
           throws java.lang.Exception

Description copied from interface: ISerialize

De-serializes the object from the given properties list.

Specified by:

reset in interface ISerialize

Overrides:

reset in class Policy

Parameters:

p - properties list containing the serialized version of the object

Throws:

java.lang.Exception

revisit

public void revisit(ResourceReservation reservation)
             throws java.lang.Exception

Description copied from interface: IPolicy

Informs the mapper about a reservation. Called during recovery/startup. The mapper must re-establish any state required for the management of the reservation.

Specified by:

revisit in interface IPolicy

Overrides:

revisit in class BrokerBasePolicyPlugin

Throws:

java.lang.Exception

getLogicalInventory

public LogicalInventory getLogicalInventory()

getLogicalMachine

public MachineState getLogicalMachine(ID machineId)