[haizea-commit] r751 - branches/1.1/src/haizea/core/scheduler
haizea-commit at mailman.cs.uchicago.edu
haizea-commit at mailman.cs.uchicago.edu
Sat Jan 9 18:32:29 CST 2010
Author: borja
Date: 2010-01-09 18:32:28 -0600 (Sat, 09 Jan 2010)
New Revision: 751
Modified:
branches/1.1/src/haizea/core/scheduler/lease_scheduler.py
branches/1.1/src/haizea/core/scheduler/vm_scheduler.py
Log:
Beginnings of preemption support in deadline scheduling
Modified: branches/1.1/src/haizea/core/scheduler/lease_scheduler.py
===================================================================
--- branches/1.1/src/haizea/core/scheduler/lease_scheduler.py 2010-01-07 17:52:25 UTC (rev 750)
+++ branches/1.1/src/haizea/core/scheduler/lease_scheduler.py 2010-01-10 00:32:28 UTC (rev 751)
@@ -461,7 +461,7 @@
# We can only reschedule leases in the following four states
if l.get_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
+ # future, we cancel the lease's preparation and
# the last scheduled VM.
vmrr = l.get_last_vmrr()
self.preparation_scheduler.cancel_preparation(l)
@@ -581,7 +581,7 @@
# 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)
+ (vmrr, preemptions) = self.vm_scheduler.schedule(lease, lease.duration.get_remaining_duration(), nexttime, earliest)
## BEGIN NOT-FIT-FOR-PRODUCTION CODE
## Pricing shouldn't live here. Instead, it should happen before a lease is accepted
@@ -610,8 +610,11 @@
# 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)
+ if lease.get_type() == Lease.DEADLINE:
+ self.__preempt_leases_deadline(l, vmrr, preemptions, preemption_time=vmrr.start, nexttime=nexttime)
+ else:
+ for l in preemptions:
+ self.__preempt_lease(l, preemption_time=vmrr.start)
# Schedule lease preparation
is_ready = False
@@ -735,6 +738,98 @@
self.logger.vdebug("Lease after preemption:")
lease.print_contents()
+ def __preempt_leases_deadline(self, lease, vmrr, preempted_leases, preemption_time, nexttime):
+ orig_vmrrs = dict([(l.id,l.vm_rrs[:]) for l in preempted_leases])
+
+ self.slottable.push()
+
+ # Pre-VM RRs (if any)
+ for rr in vmrr.pre_rrs:
+ self.slottable.add_reservation(rr)
+
+ # VM
+ self.slottable.add_reservation(vmrr)
+
+ # Post-VM RRs (if any)
+ for rr in vmrr.post_rrs:
+ self.slottable.add_reservation(rr)
+
+ for preempt_vmrr in [l.get_last_vmrr() for l in preempted_leases]:
+ self.vm_scheduler.cancel_vm(preempt_vmrr)
+
+ feasible = True
+ for lease_to_preempt in preempted_leases:
+ preempt_vmrr = lease_to_preempt.get_last_vmrr()
+ dur = preempt_vmrr.end - preemption_time
+
+ if preempt_vmrr.state == ResourceReservation.STATE_SCHEDULED and preempt_vmrr.start >= preemption_time:
+ self.logger.debug("Lease was set to start in the middle of the preempting lease.")
+ self.preparation_scheduler.cancel_preparation(lease_to_preempt)
+ lease.remove_vmrr(preempt_vmrr)
+ try:
+ (vmrr, preemptions) = self.vm_scheduler.schedule(lease, nexttime, earliest)
+ except:
+ feasible = False
+ break
+ else:
+ can_suspend = self.vm_scheduler.can_suspend_at(lease_to_preempt, preemption_time)
+
+ if not can_suspend:
+ self.logger.debug("Suspending the lease does not meet scheduling threshold.")
+ feasible = False
+ break
+
+ self.vm_scheduler.preempt_vm(preempt_vmrr, preemption_time)
+
+ node_ids = self.slottable.nodes.keys()
+ earliest = {}
+ for node in node_ids:
+ earliest[node] = EarliestStartingTime(preemption_time, EarliestStartingTime.EARLIEST_NOPREPARATION)
+
+ try:
+ (new_vmrr, preemptions) = self.vm_scheduler.schedule(lease_to_preempt, dur, nexttime, earliest, override_state = Lease.STATE_SUSPENDED_PENDING)
+
+ # Add VMRR to lease
+ lease_to_preempt.append_vmrr(new_vmrr)
+
+
+ # Add resource reservations to slottable
+
+ # Pre-VM RRs (if any)
+ for rr in new_vmrr.pre_rrs:
+ self.slottable.add_reservation(rr)
+
+ # VM
+ self.slottable.add_reservation(new_vmrr)
+
+ # Post-VM RRs (if any)
+ for rr in new_vmrr.post_rrs:
+ self.slottable.add_reservation(rr)
+ except:
+ exit()
+ feasible = False
+ break
+
+
+
+ if not feasible:
+ for l in preempted_leases:
+ l.vm_rrs = orig_vmrrs[l.id]
+ self.slottable.pop()
+ else:
+ # Pre-VM RRs (if any)
+ for rr in vmrr.pre_rrs:
+ self.slottable.remove_reservation(rr)
+
+ # VM
+ self.slottable.remove_reservation(vmrr)
+
+ # Post-VM RRs (if any)
+ for rr in vmrr.post_rrs:
+ self.slottable.remove_reservation(rr)
+
+ # commit to slottable
+
def __enqueue(self, lease):
"""Queues a best-effort lease request
Modified: branches/1.1/src/haizea/core/scheduler/vm_scheduler.py
===================================================================
--- branches/1.1/src/haizea/core/scheduler/vm_scheduler.py 2010-01-07 17:52:25 UTC (rev 750)
+++ branches/1.1/src/haizea/core/scheduler/vm_scheduler.py 2010-01-10 00:32:28 UTC (rev 751)
@@ -93,7 +93,7 @@
self.future_leases = set()
- def schedule(self, lease, nexttime, earliest):
+ def schedule(self, lease, duration, nexttime, earliest, override_state = None):
""" The scheduling function
This particular function doesn't do much except call __schedule_asap
@@ -105,13 +105,13 @@
earliest -- The earliest possible starting times on each physical node
"""
if lease.get_type() == Lease.BEST_EFFORT:
- return self.__schedule_asap(lease, nexttime, earliest, allow_in_future = self.can_schedule_in_future())
+ return self.__schedule_asap(lease, duration, nexttime, earliest, allow_in_future = self.can_schedule_in_future())
elif lease.get_type() == Lease.ADVANCE_RESERVATION:
- return self.__schedule_exact(lease, nexttime, earliest)
+ return self.__schedule_exact(lease, duration, nexttime, earliest)
elif lease.get_type() == Lease.IMMEDIATE:
- return self.__schedule_asap(lease, nexttime, earliest, allow_in_future = False)
+ return self.__schedule_asap(lease, duration, nexttime, earliest, allow_in_future = False)
elif lease.get_type() == Lease.DEADLINE:
- return self.__schedule_deadline(lease, nexttime, earliest)
+ return self.__schedule_deadline(lease, duration, nexttime, earliest, override_state)
def estimate_migration_time(self, lease):
@@ -281,7 +281,7 @@
self.__schedule_suspension(vmrr, t)
# Update the VMRR in the slot table
- self.slottable.update_reservation(vmrr, old_start, old_end)
+ #self.slottable.update_reservation(vmrr, old_start, old_end)
# Add the suspension RRs to the VM's post-RRs
for susprr in vmrr.post_rrs:
@@ -340,7 +340,7 @@
return util
- def __schedule_exact(self, lease, nexttime, earliest):
+ def __schedule_exact(self, lease, duration, nexttime, earliest):
""" Schedules VMs that must start at an exact time
This type of lease is "easy" to schedule because we know the exact
@@ -352,7 +352,7 @@
nexttime -- The next time at which the scheduler can allocate resources.
earliest -- The earliest possible starting times on each physical node
"""
-
+
# Determine the start and end time
start = lease.start.requested
end = start + lease.duration.requested
@@ -368,7 +368,7 @@
end,
strictend = True,
allow_preemption = True)
-
+
# If no mapping was found, tell the lease scheduler about it
if mapping == None:
raise NotSchedulableException, "Not enough resources in specified interval"
@@ -388,11 +388,11 @@
# Schedule shutdown for the VM
self.__schedule_shutdown(vmrr)
-
+
return vmrr, preemptions
- def __schedule_asap(self, lease, nexttime, earliest, allow_in_future = None):
+ def __schedule_asap(self, lease, duration, nexttime, earliest, allow_in_future = None, override_state = None):
""" Schedules VMs as soon as possible
This method is a bit more complex that __schedule_exact because
@@ -429,20 +429,23 @@
allowed to schedule the VMs in the future.
"""
-
-
#
# STEP 1: PROLEGOMENA
#
lease_id = lease.id
- remaining_duration = lease.duration.get_remaining_duration()
+ remaining_duration = duration
shutdown_time = lease.estimate_shutdown_time()
+ if override_state != None:
+ state = override_state
+ else:
+ state = lease.get_state()
+
# We might be scheduling a suspended lease. If so, we will
# also have to schedule its resumption. Right now, just
# figure out if this is such a lease.
- mustresume = (lease.get_state() in (Lease.STATE_SUSPENDED_PENDING, Lease.STATE_SUSPENDED_QUEUED, Lease.STATE_SUSPENDED_SCHEDULED))
+ mustresume = (state in (Lease.STATE_SUSPENDED_PENDING, Lease.STATE_SUSPENDED_QUEUED, Lease.STATE_SUSPENDED_SCHEDULED))
# This is the minimum duration that we must be able to schedule.
# See __compute_scheduling_threshold for more details.
@@ -613,16 +616,16 @@
return vmrr, preemptions
- def __schedule_deadline(self, lease, nexttime, earliest):
+ def __schedule_deadline(self, lease, duration, nexttime, earliest, override_state):
for n in earliest:
- earliest[n].time = lease.start.requested
-
- vmrr, preemptions = self.__schedule_asap(lease, nexttime, earliest, allow_in_future = True)
+ earliest[n].time = max(lease.start.requested, earliest[n].time)
- if vmrr.end - vmrr.start != lease.duration.requested or vmrr.end > lease.deadline or len(preemptions)>0:
+ vmrr, preemptions = self.__schedule_asap(lease, duration, nexttime, earliest, allow_in_future = True, override_state=override_state)
+
+ if vmrr.end - vmrr.start != duration or vmrr.end > lease.deadline or len(preemptions)>0:
self.logger.debug("Lease #%i cannot be scheduled before deadline using best-effort." % lease.id)
-
+
self.slottable.push()
future_vmrrs = self.slottable.get_reservations_on_or_after(lease.start.requested)
@@ -650,11 +653,24 @@
for n in earliest:
earliest[n].time = max(lease2.start.requested, nexttime)
self.logger.debug("Rescheduling lease %s" % lease2.id)
- vmrr, preemptions = self.__schedule_asap(lease2, nexttime, earliest, allow_in_future = True)
+ vmrr, preemptions = self.__schedule_asap(lease2, lease2.duration.get_remaining_duration(), nexttime, earliest, allow_in_future = True)
if vmrr.end - vmrr.start != lease2.duration.requested or vmrr.end > lease2.deadline or len(preemptions) != 0:
self.logger.debug("Lease %s could not be rescheduled, undoing changes." % lease2.id)
self.slottable.pop()
+
+ slack = (lease.deadline - lease.start.requested) / lease.duration.requested
+ if slack <= 2.0:
+ try:
+ vmrr, preemptions = self.__schedule_exact(lease, duration, nexttime, earliest)
+ if lease.duration.known != None:
+ print "LEASE %i - %.2f - %i" % (lease.id, slack, lease.duration.known.seconds * lease.numnodes)
+ else:
+ print "LEASE %i - %.2f - %i" % (lease.id, slack, lease.duration.requested.seconds * lease.numnodes)
+ return vmrr, preemptions
+ except:
+ raise NotSchedulableException, "Could not schedule before deadline without making other leases miss deadline"
raise NotSchedulableException, "Could not schedule before deadline without making other leases miss deadline"
+
for rr in vmrr.pre_rrs:
self.slottable.add_reservation(rr)
self.slottable.add_reservation(vmrr)
@@ -961,8 +977,8 @@
vmrr.update_end(susp_start)
# If there are any post RRs, remove them
- for rr in vmrr.post_rrs:
- self.slottable.remove_reservation(rr)
+ #for rr in vmrr.post_rrs:
+ # self.slottable.remove_reservation(rr)
vmrr.post_rrs = []
# Add the suspension RRs to the VM RR
@@ -1214,7 +1230,11 @@
self.resourcepool.verify_suspend(l, rr)
rr.state = ResourceReservation.STATE_DONE
if rr.is_last():
- l.set_state(Lease.STATE_SUSPENDED_PENDING)
+ if l.get_type() == Lease.DEADLINE:
+ l.set_state(Lease.STATE_SUSPENDED_PENDING)
+ l.set_state(Lease.STATE_SUSPENDED_SCHEDULED)
+ else:
+ l.set_state(Lease.STATE_SUSPENDED_PENDING)
l.print_contents()
self.logger.debug("LEASE-%i End of handleEndSuspend" % l.id)
self.logger.info("Lease %i suspended." % (l.id))
More information about the Haizea-commit
mailing list