From 1fc201745b1984db492350ab5b4e11d2a3363aa5 Mon Sep 17 00:00:00 2001 From: Sacheendra Talluri Date: Thu, 16 Jan 2025 15:53:15 +0100 Subject: Add support for schedulers which can receive task state change updates (#290) * Change scheduler API to include task removal and add tests * Check if memorizing schduler works with the whole system * Spotless apply * Expand function name and improve documentation --- .../compute/simulator/service/ComputeService.java | 54 +++++++++------------- .../opendc/compute/simulator/service/HostView.java | 16 +++++++ .../compute/simulator/service/ServiceTask.java | 7 +-- 3 files changed, 42 insertions(+), 35 deletions(-) (limited to 'opendc-compute/opendc-compute-simulator/src/main/java/org') diff --git a/opendc-compute/opendc-compute-simulator/src/main/java/org/opendc/compute/simulator/service/ComputeService.java b/opendc-compute/opendc-compute-simulator/src/main/java/org/opendc/compute/simulator/service/ComputeService.java index c7478c84..6fa6af60 100644 --- a/opendc-compute/opendc-compute-simulator/src/main/java/org/opendc/compute/simulator/service/ComputeService.java +++ b/opendc-compute/opendc-compute-simulator/src/main/java/org/opendc/compute/simulator/service/ComputeService.java @@ -31,6 +31,7 @@ import java.util.Collections; import java.util.Deque; import java.util.HashMap; import java.util.HashSet; +import java.util.Iterator; import java.util.List; import java.util.Map; import java.util.Objects; @@ -49,6 +50,9 @@ import org.opendc.compute.simulator.host.HostModel; import org.opendc.compute.simulator.host.HostState; import org.opendc.compute.simulator.host.SimHost; import org.opendc.compute.simulator.scheduler.ComputeScheduler; +import org.opendc.compute.simulator.scheduler.SchedulingRequest; +import org.opendc.compute.simulator.scheduler.SchedulingResult; +import org.opendc.compute.simulator.scheduler.SchedulingResultType; import org.opendc.compute.simulator.telemetry.ComputeMetricReader; import org.opendc.compute.simulator.telemetry.SchedulerStats; import org.opendc.simulator.compute.power.SimPowerSource; @@ -204,6 +208,7 @@ public final class ComputeService implements AutoCloseable { } if (task.getState() == TaskState.COMPLETED || task.getState() == TaskState.TERMINATED) { + scheduler.removeTask(task, hv); setTaskToBeRemoved(task); } @@ -430,38 +435,37 @@ public final class ComputeService implements AutoCloseable { private void doSchedule() { // reorder tasks - while (!taskQueue.isEmpty()) { - SchedulingRequest request = taskQueue.peek(); - - if (request.isCancelled) { - taskQueue.poll(); - tasksPending--; - continue; + for (Iterator iterator = taskQueue.iterator(); + iterator.hasNext(); + iterator = taskQueue.iterator()) { + final SchedulingResult result = scheduler.select(iterator); + if (result.getResultType() == SchedulingResultType.EMPTY) { + break; } - - final ServiceTask task = request.task; + final HostView hv = result.getHost(); + final SchedulingRequest req = result.getReq(); + final ServiceTask task = req.getTask(); + final ServiceFlavor flavor = task.getFlavor(); if (task.getNumFailures() >= maxNumFailures) { LOGGER.warn("task {} has been terminated because it failed {} times", task, task.getNumFailures()); - taskQueue.poll(); + taskQueue.remove(req); tasksPending--; tasksTerminated++; task.setState(TaskState.TERMINATED); + scheduler.removeTask(task, hv); this.setTaskToBeRemoved(task); continue; } - final ServiceFlavor flavor = task.getFlavor(); - final HostView hv = scheduler.select(request.task); - - if (hv == null || !hv.getHost().canFit(task)) { + if (result.getResultType() == SchedulingResultType.FAILURE) { LOGGER.trace("Task {} selected for scheduling but no capacity available for it at the moment", task); if (flavor.getMemorySize() > maxMemory || flavor.getCoreCount() > maxCores) { // Remove the incoming image - taskQueue.poll(); + taskQueue.remove(req); tasksPending--; tasksTerminated++; @@ -472,6 +476,7 @@ public final class ComputeService implements AutoCloseable { this.setTaskToBeRemoved(task); continue; } else { + // VM fits, but we don't have enough capacity break; } } @@ -479,7 +484,7 @@ public final class ComputeService implements AutoCloseable { SimHost host = hv.getHost(); // Remove request from queue - taskQueue.poll(); + taskQueue.remove(req); tasksPending--; LOGGER.info("Assigned task {} to host {}", task, host); @@ -488,7 +493,6 @@ public final class ComputeService implements AutoCloseable { task.host = host; host.spawn(task); - // host.start(task); tasksActive++; attemptsSuccess++; @@ -500,6 +504,7 @@ public final class ComputeService implements AutoCloseable { activeTasks.put(task, host); } catch (Exception cause) { LOGGER.error("Failed to deploy VM", cause); + scheduler.removeTask(task, hv); attemptsFailure++; } } @@ -679,19 +684,4 @@ public final class ComputeService implements AutoCloseable { internalTask.start(); } } - - /** - * A request to schedule a {@link ServiceTask} onto one of the {@link SimHost}s. - */ - static class SchedulingRequest { - final ServiceTask task; - final long submitTime; - - boolean isCancelled; - - SchedulingRequest(ServiceTask task, long submitTime) { - this.task = task; - this.submitTime = submitTime; - } - } } diff --git a/opendc-compute/opendc-compute-simulator/src/main/java/org/opendc/compute/simulator/service/HostView.java b/opendc-compute/opendc-compute-simulator/src/main/java/org/opendc/compute/simulator/service/HostView.java index f4aa9c70..7c548add 100644 --- a/opendc-compute/opendc-compute-simulator/src/main/java/org/opendc/compute/simulator/service/HostView.java +++ b/opendc-compute/opendc-compute-simulator/src/main/java/org/opendc/compute/simulator/service/HostView.java @@ -33,6 +33,22 @@ public class HostView { long availableMemory; int provisionedCores; + /** + * Scheduler bookkeeping + * Use by schedulers which use a priority queue data structure + * to keep track of the order of hosts to scheduler tasks on. + * {@link MemorizingScheduler} for example. + * MemorizingScheduler has an array of lists + * The 0th index of the array has a list of hosts with 0 tasks, + * 1st index of the array has hosts with 1 task, and so on. + * The priorityIndex points to the index of this the list this host + * belongs to in the array. + * The listIndex is the position of this host in the list. + */ + public int priorityIndex; + + public int listIndex; + /** * Construct a {@link HostView} instance. * diff --git a/opendc-compute/opendc-compute-simulator/src/main/java/org/opendc/compute/simulator/service/ServiceTask.java b/opendc-compute/opendc-compute-simulator/src/main/java/org/opendc/compute/simulator/service/ServiceTask.java index f39142eb..06d6535d 100644 --- a/opendc-compute/opendc-compute-simulator/src/main/java/org/opendc/compute/simulator/service/ServiceTask.java +++ b/opendc-compute/opendc-compute-simulator/src/main/java/org/opendc/compute/simulator/service/ServiceTask.java @@ -34,6 +34,7 @@ import org.jetbrains.annotations.Nullable; import org.opendc.compute.api.TaskState; import org.opendc.compute.simulator.TaskWatcher; import org.opendc.compute.simulator.host.SimHost; +import org.opendc.compute.simulator.scheduler.SchedulingRequest; import org.opendc.simulator.compute.workload.Workload; import org.slf4j.Logger; import org.slf4j.LoggerFactory; @@ -59,7 +60,7 @@ public class ServiceTask { Instant createdAt; Instant finishedAt; SimHost host = null; - private ComputeService.SchedulingRequest request = null; + private SchedulingRequest request = null; private int numFailures = 0; @@ -221,10 +222,10 @@ public class ServiceTask { * Cancel the provisioning request if active. */ private void cancelProvisioningRequest() { - final ComputeService.SchedulingRequest request = this.request; + final SchedulingRequest request = this.request; if (request != null) { this.request = null; - request.isCancelled = true; + request.setCancelled(true); } } } -- cgit v1.2.3