[haizea-commit] r606 - in branches/TP2.0: src/haizea src/haizea/common src/haizea/core src/haizea/core/scheduler src/haizea/policies tests
haizea-commit at mailman.cs.uchicago.edu
haizea-commit at mailman.cs.uchicago.edu
Wed Jul 15 11:23:40 CDT 2009
Author: borja
Date: 2009-07-15 11:23:35 -0500 (Wed, 15 Jul 2009)
New Revision: 606
Added:
branches/TP2.0/src/haizea/policies/
branches/TP2.0/src/haizea/policies/__init__.py
branches/TP2.0/src/haizea/policies/admission.py
branches/TP2.0/src/haizea/policies/host_selection.py
branches/TP2.0/src/haizea/policies/preemption.py
Modified:
branches/TP2.0/src/haizea/common/utils.py
branches/TP2.0/src/haizea/core/configfile.py
branches/TP2.0/src/haizea/core/leases.py
branches/TP2.0/src/haizea/core/manager.py
branches/TP2.0/src/haizea/core/scheduler/mapper.py
branches/TP2.0/src/haizea/core/scheduler/policy.py
branches/TP2.0/src/haizea/core/scheduler/slottable.py
branches/TP2.0/src/haizea/core/scheduler/vm_scheduler.py
branches/TP2.0/tests/base_config_simulator.conf
Log:
- Added policy engine.
- Mapper is now a pluggable module.
Modified: branches/TP2.0/src/haizea/common/utils.py
===================================================================
--- branches/TP2.0/src/haizea/common/utils.py 2009-07-14 17:09:07 UTC (rev 605)
+++ branches/TP2.0/src/haizea/common/utils.py 2009-07-15 16:23:35 UTC (rev 606)
@@ -96,6 +96,14 @@
else:
return value
+def import_class(fq_name):
+ fq_name = fq_name.split(".")
+ package_name = ".".join(fq_name[:-1])
+ class_name = fq_name[-1]
+ module = __import__(package_name, fromlist=[class_name])
+ exec("cls = module.%s" % class_name)
+ return cls
+
class Singleton(object):
"""
A singleton base class.
Modified: branches/TP2.0/src/haizea/core/configfile.py
===================================================================
--- branches/TP2.0/src/haizea/core/configfile.py 2009-07-14 17:09:07 UTC (rev 605)
+++ branches/TP2.0/src/haizea/core/configfile.py 2009-07-15 16:23:35 UTC (rev 606)
@@ -154,6 +154,42 @@
doc = "The options in this section control how Haizea schedules leases.")
scheduling.options = \
[
+ Option(name = "mapper",
+ getter = "mapper",
+ type = OPTTYPE_STRING,
+ required = False,
+ default = "greedy",
+ doc = """
+ Mapper type
+ """),
+
+ Option(name = "policy-admission",
+ getter = "policy.admission",
+ type = OPTTYPE_STRING,
+ required = False,
+ default = "accept-all",
+ doc = """
+ Lease admission policy
+ """),
+
+ Option(name = "policy-preemption",
+ getter = "policy.preemption",
+ type = OPTTYPE_STRING,
+ required = False,
+ default = "no-preemption",
+ doc = """
+ Lease preemption policy
+ """),
+
+ Option(name = "policy-host-selection",
+ getter = "policy.host-selection",
+ type = OPTTYPE_STRING,
+ required = False,
+ default = "sequential",
+ doc = """
+ Physical host selection policy
+ """),
+
Option(name = "wakeup-interval",
getter = "wakeup-interval",
type = OPTTYPE_TIMEDELTA,
Modified: branches/TP2.0/src/haizea/core/leases.py
===================================================================
--- branches/TP2.0/src/haizea/core/leases.py 2009-07-14 17:09:07 UTC (rev 605)
+++ branches/TP2.0/src/haizea/core/leases.py 2009-07-15 16:23:35 UTC (rev 606)
@@ -510,7 +510,6 @@
for node_set in nodes.node_sets:
capacity = node_set[1]
for resource_type in capacity.get_resource_types():
- print resource_type, resource_types
if resource_type not in resource_types:
# TODO: Raise something more meaningful
raise Exception
Modified: branches/TP2.0/src/haizea/core/manager.py
===================================================================
--- branches/TP2.0/src/haizea/core/manager.py 2009-07-14 17:09:07 UTC (rev 605)
+++ branches/TP2.0/src/haizea/core/manager.py 2009-07-15 16:23:35 UTC (rev 606)
@@ -43,12 +43,14 @@
from haizea.core.scheduler import UnrecoverableError
from haizea.core.scheduler.lease_scheduler import LeaseScheduler
from haizea.core.scheduler.vm_scheduler import VMScheduler
+from haizea.core.scheduler.mapper import class_mappings as mapper_mappings
from haizea.core.scheduler.slottable import SlotTable
-from haizea.core.scheduler.policy import SimplePolicy
+from haizea.core.scheduler.policy import PolicyManager
from haizea.core.scheduler.resourcepool import ResourcePool, ResourcePoolWithReusableImages
from haizea.core.leases import Lease, Site
from haizea.core.rpcserver import RPCServer
-from haizea.common.utils import abstract, round_datetime, Singleton
+from haizea.common.utils import abstract, round_datetime, Singleton, import_class
+from haizea.policies import admission_class_mappings, preemption_class_mappings, host_class_mappings
import operator
import logging
@@ -123,7 +125,6 @@
self.rpc_server = RPCServer(self)
resources = self.config.get("simul.resources")
- print resources
if resources == "in-tracefile":
tracefile = self.config.get("tracefile")
site = Site.from_lwf_file(tracefile)
@@ -154,9 +155,24 @@
rt = slottable.create_resource_tuple_from_capacity(n.capacity)
slottable.add_node(rt)
- # Policy engine
- self.policy = SimplePolicy(slottable)
+ # Policy manager
+ admission = self.config.get("policy.admission")
+ admission = admission_class_mappings.get(admission, admission)
+ admission = import_class(admission)
+ admission = admission(slottable)
+ preemption = self.config.get("policy.preemption")
+ preemption = preemption_class_mappings.get(preemption, preemption)
+ preemption = import_class(preemption)
+ preemption = preemption(slottable)
+
+ host_selection = self.config.get("policy.host-selection")
+ host_selection = host_class_mappings.get(host_selection, host_selection)
+ host_selection = import_class(host_selection)
+ host_selection = host_selection(slottable)
+
+ self.policy = PolicyManager(slottable, admission, preemption, host_selection)
+
# Preparation scheduler
if preparation_type == constants.PREPARATION_UNMANAGED:
preparation_scheduler = UnmanagedPreparationScheduler(slottable, resourcepool, deploy_enact)
@@ -164,7 +180,12 @@
preparation_scheduler = ImageTransferPreparationScheduler(slottable, resourcepool, deploy_enact)
# VM Scheduler
- vm_scheduler = VMScheduler(slottable, resourcepool)
+ mapper = self.config.get("mapper")
+ mapper = mapper_mappings.get(mapper, mapper)
+ mapper = import_class(mapper)
+
+ mapper = mapper(slottable, self.policy)
+ vm_scheduler = VMScheduler(slottable, resourcepool, mapper)
# Lease Scheduler
self.scheduler = LeaseScheduler(vm_scheduler, preparation_scheduler, slottable)
Modified: branches/TP2.0/src/haizea/core/scheduler/mapper.py
===================================================================
--- branches/TP2.0/src/haizea/core/scheduler/mapper.py 2009-07-14 17:09:07 UTC (rev 605)
+++ branches/TP2.0/src/haizea/core/scheduler/mapper.py 2009-07-15 16:23:35 UTC (rev 606)
@@ -21,6 +21,8 @@
import haizea.common.constants as constants
import operator
+class_mappings = {"greedy": "haizea.core.scheduler.mapper.GreedyMapper"}
+
class Mapper(object):
"""Base class for mappers
@@ -40,12 +42,16 @@
def map(self, lease, requested_resources, start, end, strictend, onlynodes = None):
aw = self.slottable.get_availability_window(start, onlynodes)
- pnodes = self.__sort_pnodes(lease, start, aw, onlynodes)
+ if onlynodes == None:
+ onlynodes = aw.get_nodes_at(start)
+
+ pnodes = self.policy.sort_hosts(onlynodes, start, lease)
vnodes = self.__sort_vnodes(requested_resources)
vnodes.reverse()
leases = aw.get_leases_until(end)
mapping = {}
- leases = self.policy.sort_leases(lease, leases)
+ leases = self.policy.sort_leases(lease, leases, start)
+ leases.reverse()
preemptable_leases = leases
preempting = []
done = False
@@ -85,65 +91,14 @@
if len(preemptable_leases) == 0:
done = True
- else:
+ elif not done:
preempting.append(preemptable_leases.pop())
-
+
if len(mapping) != len(requested_resources):
return None, None, None
else:
return mapping, maxend, preempting
-
-
-
- def __sort_pnodes(self, lease, time, aw,onlynodes):
- if onlynodes == None:
- nodes = aw.get_nodes_at(time)
- else:
- nodes = onlynodes
- # Compares node x and node y.
- # Returns "x is ??? than y" (???=BETTER/WORSE/EQUAL)
- def comparenodes(node_x, node_y):
-
- leases_x = aw.get_leases_at(node_x, time)
- leases_y = aw.get_leases_at(node_y, time)
- # 1st: We prefer nodes with fewer leases to preempt
- if len(leases_x) < len(leases_y):
- return constants.BETTER
- elif len(leases_x) > len(leases_y):
- return constants.WORSE
- else:
- # 2nd: we prefer nodes with the highest capacity
- avail_x = aw.get_availability_at(node_x, time)
- avail_y = aw.get_availability_at(node_y, time)
- if avail_x > avail_y:
- return constants.BETTER
- elif avail_x < avail_y:
- return constants.WORSE
- else:
- # 3rd: we prefer nodes where the current capacity
- # doesn't change for the longest time.
- duration_x = aw.get_capacity_interval(node_x, time)
- duration_y = aw.get_capacity_interval(node_y, time)
- if (duration_x == None and duration_y != None) or duration_x > duration_y:
- return constants.BETTER
- elif (duration_x != None and duration_y == None) or duration_x < duration_y:
- return constants.WORSE
- else:
- return constants.EQUAL
- # TODO
- #elif len(node_x.leases) == 0 and len(node_y.leases) == 0:
-
- # preemptable_in_x = [l for l in node_x.leases if policy.can_preempt(lease, l)]
- # preemptable_in_y = [l for l in node_x.leases if policy.can_preempt(lease, l)]
-
- # avail_x = node_x.get_avail_withpreemption(preemptable_in_x)
- # avail_y = node_x.get_avail_withpreemption(preemptable_in_y)
-
- # Order nodes
- nodes.sort(comparenodes)
- return nodes
-
def __sort_vnodes(self, requested_resources):
max_res = self.slottable.create_empty_resource_tuple()
for res in requested_resources.values():
Modified: branches/TP2.0/src/haizea/core/scheduler/policy.py
===================================================================
--- branches/TP2.0/src/haizea/core/scheduler/policy.py 2009-07-14 17:09:07 UTC (rev 605)
+++ branches/TP2.0/src/haizea/core/scheduler/policy.py 2009-07-15 16:23:35 UTC (rev 606)
@@ -18,39 +18,67 @@
from haizea.common.utils import abstract
from haizea.core.leases import Lease
+from mx.DateTime import DateTimeDelta
import operator
-class Policy(object):
+class PolicyManager(object):
"""Base class for policy module
"""
- def __init__(self, slottable):
- self.slottable = slottable
+ def __init__(self, slottable, admission, preemption, host_selection):
+ # Dinamically load policy modules
+ self.admission = admission
+ self.preemption = preemption
+ self.host_selection = host_selection
- def sort_leases(self, preemptor, preemptees):
- leases_score = [(preemptee, self.get_lease_preemptability_score(preemptor,preemptee)) for preemptee in preemptees]
+ def sort_leases(self, preemptor, preemptees, time):
+ leases_score = [(preemptee, self.get_lease_preemptability_score(preemptor,preemptee, time)) for preemptee in preemptees]
leases_score = [(preemptee,score) for preemptee,score in leases_score if score != -1]
- leases_score.sort(key=operator.itemgetter(1))
- return [preempte for preempte,score in leases_score]
+ leases_score.sort(key=operator.itemgetter(1), reverse=True)
+ return [preemptee for preemptee,score in leases_score]
+
+ def sort_hosts(self, nodes, start, lease):
+ nodes_score = [(node, self.get_host_score(node, start, lease)) for node in nodes]
+ nodes_score.sort(key=operator.itemgetter(1), reverse=True)
+ return [node for node,score in nodes_score]
- def get_lease_preemptability_score(self, preemptor, preemptee):
- abstract()
-
def accept_lease(self, lease):
- abstract()
+ return self.admission.accept_lease(lease)
+
+ def get_lease_preemptability_score(self, preemptor, preemptee, time):
+ return self.preemption.get_lease_preemptability_score(preemptor, preemptee, time)
-# def get_host_score(self, node):
-# abstract()
+ def get_host_score(self, node, time, lease):
+ return self.host_selection.get_host_score(node, time, lease)
+
-class SimplePolicy(Policy):
+class LeaseAdmissionPolicyBase(object):
def __init__(self, slottable):
- Policy.__init__(self, slottable)
+ self.slottable = slottable
- def get_lease_preemptability_score(self, preemptor, preemptee):
- if preemptor.get_type() == Lease.ADVANCE_RESERVATION and preemptee.get_type() == Lease.BEST_EFFORT:
- return 1
+ def accept_lease(self, lease):
+ abstract()
+
+
+class PreemptabilityPolicyBase(object):
+ def __init__(self, slottable):
+ self.slottable = slottable
+
+ def get_lease_preemptability_score(self, preemptor, preemptee, time):
+ abstract()
+
+ def _get_aged_score(self, lease, time):
+ horizon = time - DateTimeDelta(31)
+ if lease.submit_time <= horizon:
+ return -1
else:
- return -1
+ seconds = (time - lease.submit_time).seconds
+ horizon_seconds = DateTimeDelta(31).seconds
+ return float(horizon_seconds - seconds) / horizon_seconds
- def accept_lease(self, lease):
- return True
+class HostSelectionPolicyBase(object):
+ def __init__(self, slottable):
+ self.slottable = slottable
+
+ def get_host_score(self, node, time, lease):
+ abstract()
Modified: branches/TP2.0/src/haizea/core/scheduler/slottable.py
===================================================================
--- branches/TP2.0/src/haizea/core/scheduler/slottable.py 2009-07-14 17:09:07 UTC (rev 605)
+++ branches/TP2.0/src/haizea/core/scheduler/slottable.py 2009-07-15 16:23:35 UTC (rev 606)
@@ -686,8 +686,7 @@
pos2 = pos + 1
- print rr.start, rr.end
- print self.cp_list, pos
+
while self.cp_list[pos2] < rr.end:
cp = self.changepoints[self.cp_list[pos2]]
cp.leases.add(lease)
Modified: branches/TP2.0/src/haizea/core/scheduler/vm_scheduler.py
===================================================================
--- branches/TP2.0/src/haizea/core/scheduler/vm_scheduler.py 2009-07-14 17:09:07 UTC (rev 605)
+++ branches/TP2.0/src/haizea/core/scheduler/vm_scheduler.py 2009-07-15 16:23:35 UTC (rev 606)
@@ -35,10 +35,10 @@
policy decisions are factored out into a separate module.
"""
- def __init__(self, slottable, resourcepool):
+ def __init__(self, slottable, resourcepool, mapper):
self.slottable = slottable
self.resourcepool = resourcepool
- self.mapper = GreedyMapper(self.slottable, get_policy())
+ self.mapper = mapper
self.logger = logging.getLogger("VMSCHED")
self.handlers = {}
@@ -92,7 +92,7 @@
end = start + lease.duration.requested
requested_resources = dict([(k,self.slottable.create_resource_tuple_from_capacity(v)) for k,v in lease.requested_resources.items()])
- print requested_resources
+
mapping, actualend, preemptions = self.mapper.map(lease,
requested_resources,
start,
@@ -905,7 +905,7 @@
# Update RAM files
self.resourcepool.remove_ramfile(origin, l.id, vnode)
- self.resourcepool.add_ramfile(dest, l.id, vnode, l.requested_resources.get_by_type(constants.RES_MEM))
+ self.resourcepool.add_ramfile(dest, l.id, vnode, l.requested_resources[vnode].get_quantity(constants.RES_MEM))
rr.state = ResourceReservation.STATE_DONE
l.print_contents()
Added: branches/TP2.0/src/haizea/policies/__init__.py
===================================================================
--- branches/TP2.0/src/haizea/policies/__init__.py (rev 0)
+++ branches/TP2.0/src/haizea/policies/__init__.py 2009-07-15 16:23:35 UTC (rev 606)
@@ -0,0 +1,8 @@
+admission_class_mappings = {"accept-all": "haizea.policies.admission.AcceptAllPolicy",
+ "no-ARs": "haizea.policies.admission.NoARsPolicy"}
+
+preemption_class_mappings = {"no-preemption": "haizea.policies.preemption.NoPreemptionPolicy",
+ "ar-preempts-everything": "haizea.policies.preemption.ARPreemptsEverythingPolicy"}
+
+host_class_mappings = {"sequential": "haizea.policies.host_selection.SequentialPolicy",
+ "greedy": "haizea.policies.host_selection.GreedyPolicy"}
\ No newline at end of file
Added: branches/TP2.0/src/haizea/policies/admission.py
===================================================================
--- branches/TP2.0/src/haizea/policies/admission.py (rev 0)
+++ branches/TP2.0/src/haizea/policies/admission.py 2009-07-15 16:23:35 UTC (rev 606)
@@ -0,0 +1,15 @@
+from haizea.core.scheduler.policy import LeaseAdmissionPolicyBase
+
+class AcceptAllPolicy(LeaseAdmissionPolicyBase):
+ def __init__(self, slottable):
+ LeaseAdmissionPolicyBase.__init__(self, slottable)
+
+ def accept_lease(self, lease):
+ return True
+
+class NoARsPolicy(LeaseAdmissionPolicyBase):
+ def __init__(self, slottable):
+ LeaseAdmissionPolicyBase.__init__(self, slottable)
+
+ def accept_lease(self, lease):
+ return lease.get_type() != Lease.ADVANCE_RESERVATION
\ No newline at end of file
Added: branches/TP2.0/src/haizea/policies/host_selection.py
===================================================================
--- branches/TP2.0/src/haizea/policies/host_selection.py (rev 0)
+++ branches/TP2.0/src/haizea/policies/host_selection.py 2009-07-15 16:23:35 UTC (rev 606)
@@ -0,0 +1,45 @@
+from haizea.core.scheduler.policy import HostSelectionPolicyBase
+
+class SequentialPolicy(HostSelectionPolicyBase):
+ def __init__(self, slottable):
+ HostSelectionPolicyBase.__init__(self, slottable)
+
+ def get_host_score(self, node, time, lease):
+ return 1
+
+
+class GreedyPolicy(HostSelectionPolicyBase):
+ def __init__(self, slottable):
+ HostSelectionPolicyBase.__init__(self, slottable)
+
+ def get_host_score(self, node, time, lease):
+ aw = self.slottable.get_availability_window(time, onlynodes = [node])
+
+ leases_in_node_horizon = 4
+
+ # 1st: We prefer nodes with fewer leases to preempt
+ leases_in_node = len(aw.get_leases_at(node, time))
+ if leases_in_node > leases_in_node_horizon:
+ leases_in_node = leases_in_node_horizon
+
+ # Nodes with fewer leases already scheduled in them get
+ # higher scores
+ leases_in_node = (leases_in_node_horizon - leases_in_node) / float(leases_in_node_horizon)
+ leases_in_node_score = leases_in_node
+
+
+ # 2nd: we prefer nodes with the highest capacity
+ avail = aw.get_availability_at(node, time)
+ # TODO: normalize into a score
+ high_capacity_score = 1.0
+
+ # 3rd: we prefer nodes where the current capacity
+ # doesn't change for the longest time.
+ duration = aw.get_capacity_interval(node, time)
+ if duration == None or duration>=lease.duration.requested:
+ duration_score = 1.0
+ else:
+ duration_score = duration.seconds / float(lease.duration.requested.seconds)
+
+ return 0.5 * leases_in_node_score + 0.25 * high_capacity_score + 0.25 * duration_score
+
\ No newline at end of file
Added: branches/TP2.0/src/haizea/policies/preemption.py
===================================================================
--- branches/TP2.0/src/haizea/policies/preemption.py (rev 0)
+++ branches/TP2.0/src/haizea/policies/preemption.py 2009-07-15 16:23:35 UTC (rev 606)
@@ -0,0 +1,20 @@
+from haizea.core.leases import Lease
+from haizea.core.scheduler.policy import PreemptabilityPolicyBase
+
+
+class NoPreemptionPolicy(PreemptabilityPolicyBase):
+ def __init__(self, slottable):
+ PreemptabilityPolicyBase.__init__(self, slottable)
+
+ def get_lease_preemptability_score(self, preemptor, preemptee, time):
+ return -1
+
+class ARPreemptsEverythingPolicy(PreemptabilityPolicyBase):
+ def __init__(self, slottable):
+ PreemptabilityPolicyBase.__init__(self, slottable)
+
+ def get_lease_preemptability_score(self, preemptor, preemptee, time):
+ if preemptor.get_type() == Lease.ADVANCE_RESERVATION and preemptee.get_type() == Lease.BEST_EFFORT:
+ return self._get_aged_score(preemptee, time)
+ else:
+ return -1
\ No newline at end of file
Modified: branches/TP2.0/tests/base_config_simulator.conf
===================================================================
--- branches/TP2.0/tests/base_config_simulator.conf 2009-07-14 17:09:07 UTC (rev 605)
+++ branches/TP2.0/tests/base_config_simulator.conf 2009-07-15 16:23:35 UTC (rev 606)
@@ -13,6 +13,10 @@
#status-message-interval: 15
[scheduling]
+mapper: greedy
+policy-admission: accept-all
+policy-preemption: ar-preempts-everything
+policy-host-selection: greedy
shutdown-time: 0
suspendresume-exclusion: local
wakeup-interval: 3
More information about the Haizea-commit
mailing list