Home       Trees       Indices       Help   
Package haizea :: Package core :: Package scheduler :: Module slottable :: Class SlotTable
[hide private]
[frames] | no frames]

Class SlotTable

source code

Slot table

The slot table is one of the main data structures in Haizea (if not *the* main one). It tracks the capacity of the physical nodes on which leases can be scheduled, contains the resource reservations of all the leases, and allows efficient access to them.

However, the information in the slot table is stored in a somewhat 'raw' format (a collection of ResourceReservations) which can be hard to use directly. So, one of the responsabilities of the slot table is to efficiently generate "availability windows", which are a more convenient abstraction over available resources. See AvailabilityWindow for more details. When writing a custom mapper, most read-only interactions with the slot table should be through availability windows, which can be obtained through the get_availability_window method of SlotTable.

The slot table also depends on classes Node and KeyValueWrapper.

Since querying resource reservations is the most frequent operation in Haizea, the slot table tries to optimize access to them as much as possible. In particular, we will often need to quickly access reservations starting or ending at a specific time (or in an interval of time). The current slot table implementation stores the RRs in two ordered lists: one by starting time and another by ending time. Access is done by binary search in O(log n) time using the bisect module. Insertion and removal require O(n) time, since lists are implemented internally as arrays in CPython. We could improve these times in the future by using a tree structure (which Python doesn't have natively, so we'd have to include our own tree implementation), although slot table accesses far outweight insertion and removal operations.

Instance Methods [hide private]
 
__init__(self, resource_types)
Constructor		 source code
 
add_node(self, node_id, resourcetuple)
Add a new physical node to the slot table		 source code
ResourceTuple
create_empty_resource_tuple(self)
Create an empty resource tuple		 source code
ResourceTuple
create_resource_tuple_from_capacity(self, capacity)
Converts a Capacity object to a ResourceTuple		 source code
AvailabilityWindow
get_availability_window(self, start)
Creates an availability window starting at a given time.		 source code
dict
get_availability(self, time, min_capacity=None)
Computes the available resources on all nodes at a given time.		 source code
bool
is_empty(self)
Determines if the slot table is empty (has no reservations)		 source code
bool
is_full(self, time, restype)
Determines if a resource type is "full" at a specified time.		 source code
int
get_total_capacity(self, restype)
Determines the aggregate capacity of a given resource type across all nodes.		 source code
 
add_reservation(self, rr)
Adds a ResourceReservation to the slot table.		 source code
 
update_reservation(self, rr, old_start, old_end)
Update a ResourceReservation to the slot table.		 source code
 
remove_reservation(self, rr)
Remove a ResourceReservation from the slot table.		 source code
list of ResourceReservations
get_reservations_at(self, time)
Get all reservations at a specified time		 source code
list of ResourceReservations
get_reservations_starting_between(self, start, end)
Get all reservations starting in a specified interval.		 source code
list of ResourceReservations
get_reservations_ending_between(self, start, end)
Get all reservations ending in a specified interval.		 source code
list of ResourceReservations
get_reservations_starting_after(self, start)
Get all reservations starting after (but not on) a specified time		 source code
list of ResourceReservations
get_reservations_ending_after(self, end)
Get all reservations ending after (but not on) a specified time		 source code
list of ResourceReservations
get_reservations_starting_on_or_after(self, start)
Get all reservations starting on or after a specified time		 source code
list of ResourceReservations
get_reservations_ending_on_or_after(self, end)
Get all reservations ending on or after a specified time		 source code
list of ResourceReservations
get_reservations_starting_at(self, time)
Get all reservations starting at a specified time		 source code
list of ResourceReservations
get_reservations_ending_at(self, time)
Get all reservations ending at a specified time		 source code
list of ResourceReservations
get_reservations_after(self, time)
Get all reservations that take place after (but not on) a specified time.		 source code
list of ResourceReservations
get_reservations_on_or_after(self, time)
Get all reservations that take place on or after a specified time.		 source code
list of DateTimes
get_changepoints_after(self, after, until=None, nodes=None)
Get all the changepoints after a given time.		 source code
DateTime
get_next_changepoint(self, time)
Get the first changepoint after a given time.		 source code
DateTime
get_next_premature_end(self, after)
Get the first premature end time after a given time.		 source code
list of ResourceReservations
get_prematurely_ending_res(self, time)
Gets all the ResourceReservations that are set to end prematurely at a given time.		 source code
 
__remove_reservation(self, rr, start=None, end=None)
Remove a ResourceReservation from the slot table.		 source code
 
__get_availability_cache_miss(self, time)
Computes availability at a given time, and caches it.		 source code
 
__get_aw_cache_miss(self, time)
Computes availability window at a given time, and caches it.		 source code
 
__dirty(self)
Empties the caches.		 source code
 
__get_reservation_index(self, rlist, rr, time)
Find the index of a resource reservation in one of the internal reservation lists		 source code
(bool,
sanity_check(self)
Verifies the slot table is consistent.		 source code

Inherited from object: __delattr__, __format__, __getattribute__, __hash__, __new__, __reduce__, __reduce_ex__, __repr__, __setattr__, __sizeof__, __str__, __subclasshook__

Properties [hide private]

Inherited from object: __class__

Method Details [hide private]

__init__(self, resource_types)
(Constructor)

source code 

Constructor

The slot table will be initially empty, without any physical nodes. These have to be added with add_node.

Parameters:
  • resource_types (dict) - A dictionary mapping resource types to ResourceTuple.SINGLE_INSTANCE or ResourceTuple.MULTI_INSTANCE (depending on whether the resource is single- or multi-instance)
Overrides: object.__init__

add_node(self, node_id, resourcetuple)

source code 

Add a new physical node to the slot table

Parameters:
  • node_id (int) - Resource type
  • resourcetuple (ResourceTuple) - Resource type

create_empty_resource_tuple(self)

source code 

Create an empty resource tuple

Returns: ResourceTuple
Empty resource tuple, single-instance resources set to zero, multi-instance resources set to zero instances.

create_resource_tuple_from_capacity(self, capacity)

source code 

Converts a Capacity object to a ResourceTuple

Parameters:
  • capacity (Capacity) - Resource capacity
Returns: ResourceTuple
Resource tuple

get_availability_window(self, start)

source code 

Creates an availability window starting at a given time.

Parameters:
  • start (DateTime) - Start of availability window.
Returns: AvailabilityWindow
Availability window

get_availability(self, time, min_capacity=None)

source code 

Computes the available resources on all nodes at a given time.

Parameters:
  • time (DateTime) - Time at which to determine availability.
  • min_capacity (ResourceTuple) - If not None, only include the nodes that have at least this minimum capacity.
Returns: dict
A dictionary mapping physical node id to a Node object (which contains the available capacity of that physical node at the specified time)

is_empty(self)

source code 

Determines if the slot table is empty (has no reservations)

Returns: bool
True if there are no reservations, False otherwise.

is_full(self, time, restype)

source code 

Determines if a resource type is "full" at a specified time.

A resource type is considered to be "full" if its available capacity is zero in all the physical nodes in the slot table.

Parameters:
  • time (DateTime) - time at which to check for fullness.
  • restype (str) - Resource type
Returns: bool
True if the resource type is full, False otherwise.

get_total_capacity(self, restype)

source code 

Determines the aggregate capacity of a given resource type across all nodes.

Parameters:
  • restype (str) - Resource type
Returns: int
Total capacity

add_reservation(self, rr)

source code 

Adds a ResourceReservation to the slot table.

Parameters:

update_reservation(self, rr, old_start, old_end)

source code 

Update a ResourceReservation to the slot table.

Since the start and end time are used to index the reservations, the old times have to be provided so we can find the old reservation and make the changes.

Parameters:
  • rr (ResourceReservation) - Resource reservation with updated values (including potentially new start and/or end times)
  • old_start (DateTime) - Start time of reservation before update.
  • old_end (DateTime) - End time of reservation before update.

remove_reservation(self, rr)

source code 

Remove a ResourceReservation from the slot table.

Parameters:

get_reservations_at(self, time)

source code 

Get all reservations at a specified time

Parameters:
  • time (DateTime) - Time
Returns: list of ResourceReservations
Resource reservations

get_reservations_starting_between(self, start, end)

source code 

Get all reservations starting in a specified interval.

The interval is closed: it includes the starting time and the ending time.

Parameters:
  • start (DateTime) - Start of interval
  • end (DateTime) - End of interval
Returns: list of ResourceReservations
Resource reservations

get_reservations_ending_between(self, start, end)

source code 

Get all reservations ending in a specified interval.

The interval is closed: it includes the starting time and the ending time.

Parameters:
  • start (DateTime) - Start of interval
  • end (DateTime) - End of interval
Returns: list of ResourceReservations
Resource reservations

get_reservations_starting_after(self, start)

source code 

Get all reservations starting after (but not on) a specified time

Parameters:
  • start (DateTime) - Time
Returns: list of ResourceReservations
Resource reservations

get_reservations_ending_after(self, end)

source code 

Get all reservations ending after (but not on) a specified time

Parameters:
  • end (DateTime) - Time
Returns: list of ResourceReservations
Resource reservations

get_reservations_starting_on_or_after(self, start)

source code 

Get all reservations starting on or after a specified time

Parameters:
  • start (DateTime) - Time
Returns: list of ResourceReservations
Resource reservations

get_reservations_ending_on_or_after(self, end)

source code 

Get all reservations ending on or after a specified time

Parameters:
  • end (DateTime) - Time
Returns: list of ResourceReservations
Resource reservations

get_reservations_starting_at(self, time)

source code 

Get all reservations starting at a specified time

Parameters:
  • time (DateTime) - Time
Returns: list of ResourceReservations
Resource reservations

get_reservations_ending_at(self, time)

source code 

Get all reservations ending at a specified time

Parameters:
  • time (DateTime) - Time
Returns: list of ResourceReservations
Resource reservations

get_reservations_after(self, time)

source code 

Get all reservations that take place after (but not on) a specified time. i.e., all reservations starting or ending after that time.

Parameters:
  • time (DateTime) - Time
Returns: list of ResourceReservations
Resource reservations

get_reservations_on_or_after(self, time)

source code 

Get all reservations that take place on or after a specified time. i.e., all reservations starting or ending after that time.

Parameters:
  • time (DateTime) - Time
Returns: list of ResourceReservations
Resource reservations

get_changepoints_after(self, after, until=None, nodes=None)

source code 

Get all the changepoints after a given time.

A changepoint is any time anything is scheduled to change in the slottable (a reservation starting or ending).

Parameters:
  • after (DateTime) - Time
  • until (DateTime) - If not None, only include changepoints until this time.
  • nodes (list of ints) - If not None, only include changepoints affecting these nodes.
Returns: list of DateTimes
Changepoints

get_next_changepoint(self, time)

source code 

Get the first changepoint after a given time.

Parameters:
  • time (DateTime) - Time
Returns: DateTime
Changepoints

get_next_premature_end(self, after)

source code 

Get the first premature end time after a given time. ONLY FOR SIMULATION.

In simulation, some reservations can end prematurely, and this information is stored in the slot table (in real life, this information is not known a priori).

Parameters:
  • after (DateTime) - Time
Returns: DateTime
Next premature end

get_prematurely_ending_res(self, time)

source code 

Gets all the ResourceReservations that are set to end prematurely at a given time. ONLY FOR SIMULATION

Parameters:
  • time (DateTime) - Time
Returns: list of ResourceReservations
Resource reservations

__remove_reservation(self, rr, start=None, end=None)

source code 

Remove a ResourceReservation from the slot table.

Parameters:
  • rr (ResourceReservation) - Resource reservation
  • start (DateTime) - Start time under which the reservation is indexed, in cases where the RR has changed (this parameter is only used when calling this method from update_reservation)
  • end (DateTime) - Same as start, but for the end time for the RR.

__get_availability_cache_miss(self, time)

source code 

Computes availability at a given time, and caches it.

Called when get_availability can't use availabilities in the cache.

Parameters:
  • time (DateTime) - Time at which to determine availability.

__get_aw_cache_miss(self, time)

source code 

Computes availability window at a given time, and caches it.

Called when get_availability_window can't use the cached availability window.

Parameters:
  • time (DateTime) - Start of availability window.

__dirty(self)

source code 

Empties the caches.

Should be called whenever the caches become dirty (e.g., when a reservation is added to the slot table).

__get_reservation_index(self, rlist, rr, time)

source code 

Find the index of a resource reservation in one of the internal reservation lists

Parameters:

sanity_check(self)

source code 

Verifies the slot table is consistent. Used by unit tests.

Returns: (bool,
Returns a tuple, the first item being True if the slot table is in a consistent state, and False otherwise. If the slot table is not in a consistent state, the remaining values in the tuple are the offending node, the offending changepoint, and the available resources in the node at the changepoint.

   Home       Trees       Indices       Help   
Generated by Epydoc 3.0.1 on Thu Dec 17 10:59:22 2009 http://epydoc.sourceforge.net