[haizea-commit] r611 - in branches/TP2.0/src/haizea: core core/frontends core/scheduler policies
haizea-commit at mailman.cs.uchicago.edu
haizea-commit at mailman.cs.uchicago.edu
Tue Jul 21 08:55:40 CDT 2009
Author: borja
Date: 2009-07-21 08:55:33 -0500 (Tue, 21 Jul 2009)
New Revision: 611
Modified:
branches/TP2.0/src/haizea/core/frontends/tracefile.py
branches/TP2.0/src/haizea/core/leases.py
branches/TP2.0/src/haizea/core/manager.py
branches/TP2.0/src/haizea/core/scheduler/lease_scheduler.py
branches/TP2.0/src/haizea/core/scheduler/vm_scheduler.py
branches/TP2.0/src/haizea/policies/admission.py
Log:
- Finished cleaning up + documenting leases.py
- Cleaned up + documented lease_scheduler.py
- Fixed a few bugs that appeared along the way
Modified: branches/TP2.0/src/haizea/core/frontends/tracefile.py
===================================================================
--- branches/TP2.0/src/haizea/core/frontends/tracefile.py 2009-07-20 16:04:22 UTC (rev 610)
+++ branches/TP2.0/src/haizea/core/frontends/tracefile.py 2009-07-21 13:55:33 UTC (rev 611)
@@ -41,8 +41,7 @@
if tracefile.endswith(".swf"):
self.requests = tracereaders.SWF(tracefile, config)
elif tracefile.endswith(".lwf") or tracefile.endswith(".xml"):
- lease_workload = LeaseWorkload(starttime)
- lease_workload.from_xml_file(tracefile)
+ lease_workload = LeaseWorkload.from_xml_file(tracefile, starttime)
self.requests = lease_workload.get_leases()
if injectfile != None:
Modified: branches/TP2.0/src/haizea/core/leases.py
===================================================================
--- branches/TP2.0/src/haizea/core/leases.py 2009-07-20 16:04:22 UTC (rev 610)
+++ branches/TP2.0/src/haizea/core/leases.py 2009-07-21 13:55:33 UTC (rev 611)
@@ -37,7 +37,7 @@
from haizea.common.utils import StateMachine, round_datetime_delta, get_lease_id, pretty_nodemap, xmlrpc_marshall_singlevalue
from haizea.core.scheduler.slottable import ResourceReservation
-from mx.DateTime import TimeDelta, Parser
+from mx.DateTime import DateTime, TimeDelta, Parser
import logging
import xml.etree.ElementTree as ET
@@ -654,7 +654,7 @@
self.quantity[type] = [0 for i in range(ninstances)]
def get_resource_types(self):
- """Returns the types of resources in this capacity..
+ """Returns the types of resources in this capacity.
"""
return self.quantity.keys()
@@ -814,32 +814,69 @@
class LeaseWorkload(object):
- def __init__(self, inittime, site = None):
- self.inittime = inittime
- self.entries = []
- self.site = site
+ """Reprents a sequence of lease requests.
+
+ A lease workload is a sequence of lease requests with a specific
+ arrival time for each lease. This class is currently only used
+ to load LWF (Lease Workload File) files. See the Haizea documentation
+ for details on the LWF format.
+ """
+ def __init__(self, leases):
+ """Constructor.
- def from_xml_file(self, xml_file):
- self.__from_xml(ET.parse(xml_file).getroot())
+ Arguments:
+ leases -- An ordered list (by arrival time) of leases in the workload
+ """
+ self.leases = leases
+
- def from_xml_string(self, xml):
- self.__from_xml(ET.parsestring(xml))
-
def get_leases(self):
- return self.entries
+ """Returns the leases in the workload.
+
+ """
+ return self.leases
- def __from_xml(self, leaseworkload_element):
- reqs = leaseworkload_element.findall("lease-requests/lease-request")
+ @classmethod
+ def from_xml_file(cls, xml_file, inittime = DateTime(0)):
+ """Constructs a lease workload from an XML file.
+
+ See the Haizea documentation for details on the
+ lease workload XML format.
+
+ Argument:
+ xml_file -- XML file containing the lease in XML format.
+ inittime -- The starting time of the lease workload. All relative
+ times in the XML file will be converted to absolute times by
+ adding them to inittime. If inittime is not specified, it will
+ arbitrarily be 0000/01/01 00:00:00.
+ """
+ return cls.__from_xml_element(ET.parse(xml_file).getroot(), inittime)
+
+ @classmethod
+ def __from_xml_element(cls, element, inittime):
+ """Constructs a lease from an ElementTree element.
+
+ See the Haizea documentation for details on the
+ lease XML format.
+
+ Argument:
+ element -- Element object containing a "<lease-workload>" element.
+ inittime -- The starting time of the lease workload. All relative
+ times in the XML file will be converted to absolute times by
+ adding them to inittime.
+ """
+ reqs = element.findall("lease-requests/lease-request")
+ leases = []
for r in reqs:
lease = r.find("lease")
# Add time lease is submitted
- submittime = self.inittime + Parser.DateTimeDeltaFromString(r.get("arrival"))
+ submittime = inittime + Parser.DateTimeDeltaFromString(r.get("arrival"))
lease.set("submit-time", str(submittime))
# If an exact starting time is specified, add the init time
exact = lease.find("start/exact")
if exact != None:
- start = self.inittime + Parser.DateTimeDeltaFromString(exact.get("time"))
+ start = inittime + Parser.DateTimeDeltaFromString(exact.get("time"))
exact.set("time", str(start))
lease = Lease.from_xml_element(lease)
@@ -848,51 +885,81 @@
if realduration != None:
lease.duration.known = Parser.DateTimeDeltaFromString(realduration.get("time"))
- self.entries.append(lease)
+ leases.append(lease)
+ return cls(leases)
class Site(object):
+ """Represents a site containing machines ("nodes").
+
+ This class is used to load site descriptions in XML format or
+ using a "resources string". Site descriptions can appear in two places:
+ in a LWF file (where the site required for the lease workload is
+ embedded in the LWF file) or in the Haizea configuration file. In both
+ cases, the site description is only used in simulation (in OpenNebula mode,
+ the available nodes and resources are obtained by querying OpenNebula).
+
+ Note that this class is distinct from the ResourcePool class, even though
+ both are used to represent "collections of nodes". The Site class is used
+ purely as a convenient way to load site information from an XML file
+ and to manipulate that information elsewhere in Haizea, while the
+ ResourcePool class is responsible for sending enactment commands
+ to nodes, monitoring nodes, etc.
+ """
def __init__(self, nodes, resource_types, attr_types):
+ """Constructor.
+
+ Arguments:
+ nodes -- A Nodes object
+ resource_types -- A list of valid resource types in this site.
+ attr_types -- A list of valid attribute types in this site
+ """
self.nodes = nodes
self.resource_types = resource_types
self.attr_types = attr_types
- def add_resource(self, name, amounts):
- self.resource_types.append(name)
- self.nodes.add_resource(name, amounts)
-
- def create_empty_resource_quantity(self):
- return Capacity(self.resource_types)
-
- def get_resource_types(self):
- max_ninstances = dict((rt, 1) for rt in self.resource_types)
- for node_set in self.nodes.node_sets:
- capacity = node_set[1]
- for resource_type in capacity.get_resource_types():
- if capacity.ninstances[resource_type] > max_ninstances[resource_type]:
- max_ninstances[resource_type] = capacity.ninstances[resource_type]
-
- max_ninstances = [(rt,max_ninstances[rt]) for rt in self.resource_types]
-
- return max_ninstances
-
@classmethod
def from_xml_file(cls, xml_file):
+ """Constructs a site from an XML file.
+
+ See the Haizea documentation for details on the
+ site XML format.
+
+ Argument:
+ xml_file -- XML file containing the site in XML format.
+ """
return cls.__from_xml_element(ET.parse(xml_file).getroot())
@classmethod
- def from_lwf_file(cls, xml_file):
- return cls.__from_xml_element(ET.parse(xml_file).getroot().find("site"))
+ def from_lwf_file(cls, lwf_file):
+ """Constructs a site from an LWF file.
+ LWF files can have site information embedded in them. This method
+ loads this site information from an LWF file. See the Haizea
+ documentation for details on the LWF format.
+
+ Argument:
+ lwf_file -- LWF file.
+ """
+ return cls.__from_xml_element(ET.parse(lwf_file).getroot().find("site"))
+
@classmethod
- def __from_xml_element(cls, site_element):
- resource_types = site_element.find("resource-types")
+ def __from_xml_element(cls, element):
+ """Constructs a site from an ElementTree element.
+
+ See the Haizea documentation for details on the
+ site XML format.
+
+ Argument:
+ element -- Element object containing a "<site>" element.
+ """
+ resource_types = element.find("resource-types")
resource_types = resource_types.get("names").split()
# TODO: Attributes
attrs = []
- nodes = Nodes.from_xml_element(site_element.find("nodes"))
+ nodes = Nodes.from_xml_element(element.find("nodes"))
# Validate nodes
for node_set in nodes.node_sets:
@@ -906,6 +973,18 @@
@classmethod
def from_resources_string(cls, resource_str):
+ """Constructs a site from a "resources string"
+
+ A "resources string" is a shorthand way of specifying a site
+ with homogeneous resources and no attributes. The format is:
+
+ <numnodes> <resource_type>,<resource_quantity>[;<resource_type>,<resource_quantity>]*
+
+ For example: 4 CPU,100;Memory,1024
+
+ Argument:
+ resource_str -- resources string
+ """
from haizea.core.scheduler.slottable import ResourceTuple
resource_str = resource_str.split(" ")
@@ -926,31 +1005,82 @@
nodes = Nodes([(numnodes,capacity)])
return cls(nodes, res.keys(), [])
+
+ def add_resource(self, name, amounts):
+ """Adds a new resource to all nodes in the site.
+
+ Argument:
+ name -- Name of the resource type
+ amounts -- A list with the amounts of the resource to add to each
+ node. If the resource is single-instance, then this will just
+ be a list with a single element. If multi-instance, each element
+ of the list represent the amount of an instance of the resource.
+ """
+ self.resource_types.append(name)
+ self.nodes.add_resource(name, amounts)
+
+ def get_resource_types(self):
+ """Returns the resource types in this site.
+
+ This method returns a list, each item being a pair with
+ 1. the name of the resource type and 2. the maximum number of
+ instances for that resource type across all nodes.
+
+ """
+ max_ninstances = dict((rt, 1) for rt in self.resource_types)
+ for node_set in self.nodes.node_sets:
+ capacity = node_set[1]
+ for resource_type in capacity.get_resource_types():
+ if capacity.ninstances[resource_type] > max_ninstances[resource_type]:
+ max_ninstances[resource_type] = capacity.ninstances[resource_type]
+
+ max_ninstances = [(rt,max_ninstances[rt]) for rt in self.resource_types]
+ return max_ninstances
+
+
+
class Nodes(object):
+ """Represents a collection of machines ("nodes")
+
+ This class is used to load descriptions of nodes from an XML
+ file. These nodes can appear in two places: in a site description
+ (which, in turn, is loaded by the Site class) or in a lease's
+ resource requirements (describing what nodes, with what resources,
+ are required by the lease).
+
+ Nodes are stored as one or more "node sets". Each node set has nodes
+ with the exact same resources. So, for example, a lease requiring 100
+ nodes (all identical, except 50 have 1024MB of memory and the other 50
+ have 512MB of memory) doesn't need to enumerate all 100 nodes. Instead,
+ it just has to describe the two "node sets" (indicating that there are
+ 50 nodes of one type and 50 of the other). See the Haizea documentation
+ for more details on the XML format.
+
+ Like the Site class, this class is distinct from the ResourcePool class, even
+ though they both represent a "collection of nodes". See the
+ Site class documentation for more details.
+ """
def __init__(self, node_sets):
+ """Constructor.
+
+ Arguments:
+ node_sets -- A list of (n,c) pairs (where n is the number of nodes
+ in the set and c is a Capacity object; all nodes in the set have
+ capacity c).
+ """
self.node_sets = node_sets
- def get_all_nodes(self):
- nodes = {}
- nodenum = 1
- for node_set in self.node_sets:
- numnodes = node_set[0]
- r = node_set[1]
- for i in range(numnodes):
- nodes[nodenum] = r
- nodenum += 1
- return nodes
-
- def add_resource(self, type, amounts):
- for node_set in self.node_sets:
- r = node_set[1]
- r.set_ninstances(type, len(amounts))
- for ninstance, amount in enumerate(amounts):
- r.set_quantity_instance(type, ninstance+1, amount)
-
@classmethod
def from_xml_element(cls, nodes_element):
+ """Constructs a node collection from an ElementTree element.
+
+ See the Haizea documentation for details on the
+ <nodes> XML format.
+
+ Argument:
+ element -- Element object containing a "<nodes>" element.
+ """
nodesets = []
nodesets_elems = nodes_element.findall("node-set")
for nodeset_elem in nodesets_elems:
@@ -973,4 +1103,35 @@
nodesets.append((numnodes,r))
- return cls(nodesets)
\ No newline at end of file
+ return cls(nodesets)
+
+ def get_all_nodes(self):
+ """Returns a dictionary mapping individual nodes to capacities
+
+ """
+ nodes = {}
+ nodenum = 1
+ for node_set in self.node_sets:
+ numnodes = node_set[0]
+ r = node_set[1]
+ for i in range(numnodes):
+ nodes[nodenum] = r
+ nodenum += 1
+ return nodes
+
+ def add_resource(self, name, amounts):
+ """Adds a new resource to all the nodes
+
+ Argument:
+ name -- Name of the resource type
+ amounts -- A list with the amounts of the resource to add to each
+ node. If the resource is single-instance, then this will just
+ be a list with a single element. If multi-instance, each element
+ of the list represent the amount of an instance of the resource.
+ """
+ for node_set in self.node_sets:
+ r = node_set[1]
+ r.set_ninstances(type, len(amounts))
+ for ninstance, amount in enumerate(amounts):
+ r.set_quantity_instance(type, ninstance+1, amount)
+
Modified: branches/TP2.0/src/haizea/core/manager.py
===================================================================
--- branches/TP2.0/src/haizea/core/manager.py 2009-07-20 16:04:22 UTC (rev 610)
+++ branches/TP2.0/src/haizea/core/manager.py 2009-07-21 13:55:33 UTC (rev 611)
@@ -403,7 +403,6 @@
except Exception, exc:
self.__unexpected_exception(exc)
-
def process_starting_reservations(self, time):
"""Process reservations starting/stopping at specified time"""
@@ -426,6 +425,21 @@
except Exception, exc:
self.__unexpected_exception(exc)
+ def get_utilization(self, nowtime):
+ """ Gather utilization information at a given time.
+
+ Each time we process reservations, we report resource utilization
+ to the accounting module. This utilization information shows what
+ portion of the physical resources is used by each type of reservation
+ (e.g., 70% are running a VM, 5% are doing suspensions, etc.) See the
+ accounting module for details on how this data is stored.
+ Currently we only collect utilization from the VM Scheduler
+ (in the future, information may also be gathered from the preparation
+ scheduler).
+ """
+ util = self.scheduler.vm_scheduler.get_utilization(nowtime)
+ self.accounting.append_stat(constants.COUNTER_UTILIZATION, util)
+
def notify_event(self, lease_id, event):
"""Notifies an asynchronous event to Haizea.
@@ -650,6 +664,7 @@
# And one final call to deal with nil-duration reservations
self.manager.process_ending_reservations(self.time)
+
# Print a status message
if self.statusinterval != None and (self.time - prevstatustime).minutes >= self.statusinterval:
self.manager.print_status()
Modified: branches/TP2.0/src/haizea/core/scheduler/lease_scheduler.py
===================================================================
--- branches/TP2.0/src/haizea/core/scheduler/lease_scheduler.py 2009-07-20 16:04:22 UTC (rev 610)
+++ branches/TP2.0/src/haizea/core/scheduler/lease_scheduler.py 2009-07-21 13:55:33 UTC (rev 611)
@@ -20,16 +20,17 @@
"""This module provides the main classes for Haizea's lease scheduler, particularly
the LeaseScheduler class. This module does *not* contain VM scheduling code (i.e.,
the code that decides what physical hosts a VM should be mapped to), which is
-located in the VMScheduler class (in the vm_scheduler module). Lease preparation
-code (e.g., image transfer scheduling) is located in the preparation_schedulers
-package.
+located in the vm_scheduler module. Lease preparation code (e.g., image transfer
+scheduling) is located in the preparation_schedulers package. In fact, the
+main purpose of the lease schedule is to orchestrate these preparation and VM
+schedulers.
This module also includes a Queue class and a LeaseTable class, which are used
by the lease scheduler.
"""
import haizea.common.constants as constants
-from haizea.common.utils import round_datetime, get_config, get_accounting, get_clock
+from haizea.common.utils import round_datetime, get_config, get_accounting, get_clock, get_policy
from haizea.core.leases import Lease
from haizea.core.scheduler import RescheduleLeaseException, NormalEndLeaseException, InconsistentLeaseStateError, EnactmentError, UnrecoverableError, NotSchedulableException, EarliestStartingTime
from haizea.core.scheduler.slottable import ResourceReservation
@@ -53,13 +54,14 @@
The constructor does little more than create the lease scheduler's
attributes. However, it does expect (in the arguments) a fully-constructed
- VMScheduler, PreparationScheduler, and SlotTable (these are currently
+ VMScheduler, PreparationScheduler, SlotTable, and PolicyManager (these are
constructed in the Manager's constructor).
Arguments:
vm_scheduler -- VM scheduler
preparation_scheduler -- Preparation scheduler
slottable -- Slottable
+ policy -- Policy manager
"""
# Logger
@@ -71,9 +73,9 @@
self.slottable = slottable
# Create other data structures
- self.queue = Queue(self)
- self.leases = LeaseTable(self)
- self.completed_leases = LeaseTable(self)
+ self.queue = Queue()
+ self.leases = LeaseTable()
+ self.completed_leases = LeaseTable()
# Handlers are callback functions that get called whenever a type of
# resource reservation starts or ends. Each scheduler publishes the
@@ -94,18 +96,34 @@
def request_lease(self, lease):
"""Requests a leases. This is the entry point of leases into the scheduler.
- Request a lease. At this point, it is simply marked as "Pending" and,
- next time the scheduling function is called, the fate of the
- lease will be determined (right now, AR+IM leases get scheduled
- right away, and best-effort leases get placed on a queue)
+ Request a lease. The decision on whether to accept or reject a
+ lease is deferred to the policy manager (through its admission
+ control policy).
+
+ If the policy determines the lease can be
+ accepted, it is marked as "Pending". This still doesn't
+ guarantee that the lease will be scheduled (e.g., an AR lease
+ could still be rejected if the scheduler determines there are no
+ resources for it; but that is a *scheduling* decision, not a admission
+ control policy decision). The ultimate fate of the lease is determined
+ the next time the scheduling function is called.
+
+ If the policy determines the lease cannot be accepted, it is marked
+ as rejected.
Arguments:
lease -- Lease object. Its state must be STATE_NEW.
"""
- self.logger.info("Lease #%i has been requested and is pending." % lease.id)
+ self.logger.info("Lease #%i has been requested." % lease.id)
lease.print_contents()
lease.set_state(Lease.STATE_PENDING)
- self.leases.add(lease)
+ if get_policy().accept_lease(lease):
+ self.logger.info("Lease #%i has been marked as pending." % lease.id)
+ self.leases.add(lease)
+ else:
+ self.logger.info("Lease #%i has not been accepted" % lease.id)
+ lease.set_state(Lease.STATE_REJECTED)
+ self.completed_leases.add(lease)
def schedule(self, nexttime):
@@ -138,12 +156,12 @@
try:
self.__schedule_lease(lease, nexttime=nexttime)
- self.logger.info("Immediate lease #%i has been accepted." % lease.id)
+ self.logger.info("Immediate lease #%i has been scheduled." % lease.id)
get_accounting().incr_counter(constants.COUNTER_IMACCEPTED, lease.id)
lease.print_contents()
except NotSchedulableException, exc:
get_accounting().incr_counter(constants.COUNTER_IMREJECTED, lease.id)
- self.logger.info("Immediate lease request #%i has been rejected: %s" % (lease.id, exc.message))
+ self.logger.info("Immediate lease request #%i cannot be scheduled: %s" % (lease.id, exc.message))
lease.set_state(Lease.STATE_REJECTED)
self.completed_leases.add(lease)
self.leases.remove(lease)
@@ -155,12 +173,12 @@
try:
self.__schedule_lease(lease, nexttime)
- self.logger.info("AR lease #%i has been accepted." % lease.id)
+ self.logger.info("AR lease #%i has been scheduled." % lease.id)
get_accounting().incr_counter(constants.COUNTER_ARACCEPTED, lease.id)
lease.print_contents()
except NotSchedulableException, exc:
get_accounting().incr_counter(constants.COUNTER_ARREJECTED, lease.id)
- self.logger.info("AR lease request #%i has been rejected: %s" % (lease.id, exc.message))
+ self.logger.info("AR lease request #%i cannot be scheduled: %s" % (lease.id, exc.message))
lease.set_state(Lease.STATE_REJECTED)
self.completed_leases.add(lease)
self.leases.remove(lease)
@@ -170,13 +188,13 @@
def process_starting_reservations(self, nowtime):
- """Processes starting/ending reservations
+ """Processes starting reservations
This method checks the slottable to see if there are any reservations that are
- starting or ending at "nowtime". If so, the appropriate handler is called.
+ starting at "nowtime". If so, the appropriate handler is called.
Arguments:
- nowtime -- Time at which to check for starting/ending reservations.
+ nowtime -- Time at which to check for starting reservations.
"""
# Find starting/ending reservations
@@ -205,24 +223,12 @@
# Other exceptions are not expected, and generally indicate a programming error.
# Thus, they are propagated upwards to the Manager where they will make
# Haizea crash and burn.
-
- # TODO: Move up to manager
- # Each time we process reservations, we report resource utilization to the accounting
- # module. This utilization information shows what portion of the physical resources
- # is used by each type of reservation (e.g., 70% are running a VM, 5% are doing suspensions,
- # etc.) See the get_utilization module for details on how this data is stored.
- # Currently we only collect utilization from the VM Scheduler (in the future,
- # information will also be gathered from the preparation scheduler).
- #util = self.vm_scheduler.get_utilization(nowtime)
- #get_accounting().append_stat(constants.COUNTER_UTILIZATION, util)
-
-
def process_ending_reservations(self, nowtime):
- """Processes starting/ending reservations
+ """Processes ending reservations
This method checks the slottable to see if there are any reservations that are
- starting or ending at "nowtime". If so, the appropriate handler is called.
+ ending at "nowtime". If so, the appropriate handler is called.
Arguments:
nowtime -- Time at which to check for starting/ending reservations.
@@ -274,7 +280,6 @@
# Other exceptions are not expected, and generally indicate a programming error.
# Thus, they are propagated upwards to the Manager where they will make
# Haizea crash and burn.
-
def get_lease_by_id(self, lease_id):
"""Gets a lease with the given ID
@@ -290,7 +295,6 @@
else:
return self.leases.get_lease(lease_id)
-
def cancel_lease(self, lease):
"""Cancels a lease.
@@ -353,7 +357,7 @@
# but allowing Haizea to continue to run normally.
rrs = lease.get_scheduled_reservations()
for r in rrs:
- self.slottable.removeReservation(r)
+ self.slottable.remove_reservation(r)
lease.set_state(Lease.STATE_FAIL)
self.completed_leases.add(lease)
self.leases.remove(lease)
@@ -383,24 +387,54 @@
self.vm_scheduler._handle_unscheduled_end_vm(lease, vmrr)
self._handle_end_lease(lease)
nexttime = get_clock().get_next_schedulable_time()
- # We need to reevaluate the schedule to see if there are any future
- # reservations that we can slide back.
- self.reevaluate_future_leases(vmrr.nodes.values(), nexttime)
+ # We need to reevaluate the schedule to see if there are any
+ # leases scheduled in the future that could be rescheduled
+ # to start earlier
+ self.reevaluate_schedule(nexttime)
- def reevaluate_future_leases(self, nodes, nexttime):
- res = list(self.vm_scheduler.future_reservations) # TODO: get through a function
- for l in res:
- vmrr = l.get_last_vmrr()
- self.vm_scheduler.cancel_vm(vmrr)
- l.remove_vmrr(vmrr)
- # TODO: Clean up (transfers, etc.)
- if l.state in (Lease.STATE_READY, Lease.STATE_SCHEDULED):
- l.state = Lease.STATE_PENDING
- elif l.state == Lease.STATE_SUSPENDED_SCHEDULED:
- l.state = Lease.STATE_SUSPENDED_PENDING
-
- self.__schedule_lease(l, nexttime)
+ def reevaluate_schedule(self, nexttime):
+ """Reevaluates the schedule.
+
+ This method can be called whenever resources are freed up
+ unexpectedly (e.g., a lease than ends earlier than expected))
+ to check if any leases scheduled in the future could be
+ rescheduled to start earlier on the freed up resources.
+
+ Currently, this method only checks if best-effort leases
+ scheduled in the future (using a backfilling algorithm)
+ can be rescheduled
+
+ Arguments:
+ nexttime -- The next time at which the scheduler can allocate resources.
+ """
+ future = self.vm_scheduler.get_future_reschedulable_leases()
+ for l in future:
+ # We can only reschedule leases in the following four states
+ if l.state in (Lease.STATE_PREPARING, Lease.STATE_READY, Lease.STATE_SCHEDULED, Lease.STATE_SUSPENDED_SCHEDULED):
+ # For each reschedulable lease already scheduled in the
+ # future, we cancel the lease's preparantion and
+ # the last scheduled VM.
+ vmrr = l.get_last_vmrr()
+ self.preparation_scheduler.cancel_preparation(l)
+ self.vm_scheduler.cancel_vm(vmrr)
+ l.remove_vmrr(vmrr)
+ if l.state in (Lease.STATE_READY, Lease.STATE_SCHEDULED, Lease.STATE_PREPARING):
+ l.state = Lease.STATE_PENDING
+ elif l.state == Lease.STATE_SUSPENDED_SCHEDULED:
+ l.state = Lease.STATE_SUSPENDED_PENDING
+
+ # At this point, the lease just looks like a regular
+ # pending lease that can be handed off directly to the
+ # __schedule_lease method.
+ # TODO: We should do exception handling here. However,
+ # since we can only reschedule best-effort leases that were
+ # originally schedule in the future, the scheduling function
+ # should always be able to schedule the lease (worst-case
+ # scenario is that it simply replicates the previous schedule)
+ self.__schedule_lease(l, nexttime)
+
+
def is_queue_empty(self):
"""Return True is the queue is empty, False otherwise"""
return self.queue.is_empty()
@@ -418,16 +452,12 @@
it may be possible to schedule leases in the future (using a
backfilling algorithm)
- TODO: Refine the backfilling algorithm, both here and in the VMScheduler.
- Currently, only aggressive backfilling is supported, and somewhat crudely
- (still better than no backfilling at all, though)
-
Arguments:
nexttime -- The next time at which the scheduler can allocate resources.
"""
done = False
- newqueue = Queue(self)
+ newqueue = Queue()
while not done and not self.is_queue_empty():
if not self.vm_scheduler.can_reserve_in_future() and self.slottable.is_full(nexttime, restype = constants.RES_CPU):
self.logger.debug("Used up all future reservations and slot table is full. Skipping rest of queue.")
@@ -455,6 +485,8 @@
def __schedule_lease(self, lease, nexttime):
""" Schedules a lease.
+ This method orchestrates the preparation and VM scheduler to
+ schedule a lease.
Arguments:
lease -- Lease to schedule.
@@ -466,18 +498,27 @@
# Determine earliest start time in each node
if lease_state == Lease.STATE_PENDING or lease_state == Lease.STATE_QUEUED:
- # Figure out earliest start times based on
- # image schedule and reusable images
+ # This lease might require preparation. Ask the preparation
+ # scheduler for the earliest starting time.
earliest = self.preparation_scheduler.find_earliest_starting_times(lease, nexttime)
elif lease_state == Lease.STATE_SUSPENDED_PENDING or lease_state == Lease.STATE_SUSPENDED_QUEUED:
- # Migration
+ # This lease may have to be migrated.
+ # We have to ask both the preparation scheduler and the VM
+ # scheduler what would be the earliest possible starting time
+ # on each node, assuming we have to transfer files between
+ # nodes.
node_ids = self.slottable.nodes.keys()
earliest = {}
if migration == constants.MIGRATE_NO:
+ # If migration is disabled, the earliest starting time
+ # is simply nexttime.
for node in node_ids:
earliest[node] = EarliestStartingTime(nexttime, EarliestStartingTime.EARLIEST_NOPREPARATION)
else:
+ # Otherwise, we ask the preparation scheduler and the VM
+ # scheduler how long it would take them to migrate the
+ # lease state.
prep_migr_time = self.preparation_scheduler.estimate_migration_time(lease)
vm_migr_time = self.vm_scheduler.estimate_migration_time(lease)
for node in node_ids:
@@ -485,17 +526,28 @@
else:
raise InconsistentLeaseStateError(lease, doing = "scheduling a best-effort lease")
+ # Now, we give the lease to the VM scheduler, along with the
+ # earliest possible starting times. If the VM scheduler can
+ # schedule VMs for this lease, it will return a resource reservation
+ # that we can add to the slot table, along with a list of
+ # leases that have to be preempted.
+ # If the VM scheduler can't schedule the VMs, it will throw an
+ # exception (we don't catch it here, and it is just thrown up
+ # to the calling method.
(vmrr, preemptions) = self.vm_scheduler.schedule(lease, nexttime, earliest)
+ # If scheduling the lease involves preempting other leases,
+ # go ahead and preempt them.
if len(preemptions) > 0:
self.logger.info("Must preempt leases %s to make room for lease #%i" % ([l.id for l in preemptions], lease.id))
for l in preemptions:
self.__preempt_lease(l, preemption_time=vmrr.start)
- # Schedule deployment
+ # Schedule lease preparation
is_ready = False
preparation_rrs = []
if lease_state == Lease.STATE_SUSPENDED_QUEUED and migration != constants.MIGRATE_NO:
+ # The lease might require migration
migr_rrs = self.preparation_scheduler.schedule_migration(lease, vmrr, nexttime)
if len(migr_rrs) > 0:
end_migr = migr_rrs[-1].end
@@ -505,13 +557,19 @@
migr_rrs.reverse()
for migr_rr in migr_rrs:
vmrr.pre_rrs.insert(0, migr_rr)
+ if len(migr_rrs) == 0:
+ is_ready = True
+ elif lease_state == Lease.STATE_SUSPENDED_QUEUED and migration == constants.MIGRATE_NO:
+ # No migration means the lease is ready
+ is_ready = True
elif lease_state != Lease.STATE_SUSPENDED_QUEUED:
+ # The lease might require initial preparation
preparation_rrs, is_ready = self.preparation_scheduler.schedule(lease, vmrr, earliest)
# At this point, the lease is feasible.
# Commit changes by adding RRs to lease and to slot table
- # Add deployment RRs (if any) to lease
+ # Add preparation RRs (if any) to lease
for rr in preparation_rrs:
lease.append_preparationrr(rr)
@@ -521,7 +579,7 @@
# Add resource reservations to slottable
- # Deployment RRs (if any)
+ # Preparation RRs (if any)
for rr in preparation_rrs:
self.slottable.add_reservation(rr)
@@ -536,12 +594,15 @@
for rr in vmrr.post_rrs:
self.slottable.add_reservation(rr)
+ # Change lease state
if lease_state == Lease.STATE_PENDING or lease_state == Lease.STATE_QUEUED:
lease.set_state(Lease.STATE_SCHEDULED)
if is_ready:
lease.set_state(Lease.STATE_READY)
elif lease_state == Lease.STATE_SUSPENDED_QUEUED:
lease.set_state(Lease.STATE_SUSPENDED_SCHEDULED)
+ if is_ready:
+ lease.set_state(Lease.STATE_SUSPENDED_READY)
lease.print_contents()
@@ -549,6 +610,10 @@
def __preempt_lease(self, lease, preemption_time):
""" Preempts a lease.
+ This method preempts a lease such that any resources allocated
+ to that lease after a given time are freed up. This may require
+ scheduling the lease to suspend before that time, or cancelling
+ the lease altogether.
Arguments:
lease -- Lease to schedule.
@@ -651,8 +716,7 @@
extra syntactic sugar added for convenience.
"""
- def __init__(self, scheduler):
- self.scheduler = scheduler
+ def __init__(self):
self.__q = []
def is_empty(self):
@@ -690,8 +754,7 @@
extra syntactic sugar added for convenience.
"""
- def __init__(self, scheduler):
- self.scheduler = scheduler
+ def __init__(self):
self.entries = {}
def has_lease(self, lease_id):
Modified: branches/TP2.0/src/haizea/core/scheduler/vm_scheduler.py
===================================================================
--- branches/TP2.0/src/haizea/core/scheduler/vm_scheduler.py 2009-07-20 16:04:22 UTC (rev 610)
+++ branches/TP2.0/src/haizea/core/scheduler/vm_scheduler.py 2009-07-21 13:55:33 UTC (rev 611)
@@ -372,6 +372,8 @@
for susprr in vmrr.post_rrs:
self.slottable.add_reservation(susprr)
+ def get_future_reschedulable_leases(self):
+ return list(self.future_reservations)
def get_utilization(self, time):
# total = self.slottable.get_total_capacity()
@@ -751,6 +753,11 @@
else:
raise InconsistentLeaseStateError(l, doing = "starting a VM")
+ # If this was a future reservation (as determined by backfilling),
+ # remove that status, since the future is now.
+ if rr.backfill_reservation == True:
+ self.future_reservations.remove(l)
+
l.print_contents()
self.logger.debug("LEASE-%i End of handleStartVM" % l.id)
self.logger.info("Started VMs for lease %i on nodes %s" % (l.id, rr.nodes.values()))
@@ -764,9 +771,6 @@
diff = now_time - rr.start
l.duration.accumulate_duration(diff)
rr.state = ResourceReservation.STATE_DONE
-
- if rr.backfill_reservation == True:
- self.future_reservations.remove(l)
self.logger.vdebug("LEASE-%i After:" % l.id)
l.print_contents()
Modified: branches/TP2.0/src/haizea/policies/admission.py
===================================================================
--- branches/TP2.0/src/haizea/policies/admission.py 2009-07-20 16:04:22 UTC (rev 610)
+++ branches/TP2.0/src/haizea/policies/admission.py 2009-07-21 13:55:33 UTC (rev 611)
@@ -1,4 +1,5 @@
from haizea.core.scheduler.policy import LeaseAdmissionPolicyBase
+from haizea.core.leases import Lease
class AcceptAllPolicy(LeaseAdmissionPolicyBase):
def __init__(self, slottable):
More information about the Haizea-commit
mailing list