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

3 files changed, 42 insertions, 35 deletions

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<SchedulingRequest> 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
@@ -34,6 +34,22 @@ public class HostView {
     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.
      *
      * @param host The host to create a view of.
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);
         }
     }
 }