Reimplement performance interference in opendc-simulator-compute

This change reimplements the performance interference model originally
implemented for the SimpleVirtDriver class, for SimHypervisor.

3 files changed, 146 insertions, 11 deletions

diff --git a/simulator/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/SimHypervisor.kt b/simulator/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/SimHypervisor.kt
index 55eda70f..6087227b 100644
--- a/simulator/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/SimHypervisor.kt
+++ b/simulator/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/SimHypervisor.kt
@@ -30,6 +30,7 @@ import kotlinx.coroutines.intrinsics.startCoroutineCancellable
 import kotlinx.coroutines.selects.SelectClause0
 import kotlinx.coroutines.selects.SelectInstance
 import kotlinx.coroutines.selects.select
+import org.opendc.simulator.compute.interference.PerformanceInterferenceModel
 import org.opendc.simulator.compute.model.ProcessingUnit
 import org.opendc.simulator.compute.workload.SimWorkload
 import java.time.Clock
@@ -69,15 +70,16 @@ public class SimHypervisor(
      *
      * @param model The machine to create.
      */
-    public fun createMachine(model: SimMachineModel): SimMachine {
-        val vmCtx = VmExecutionContext(model)
+    public fun createMachine(model: SimMachineModel, performanceInterferenceModel: PerformanceInterferenceModel? = null): SimMachine {
+        val vm = VmSession(model, performanceInterferenceModel)
+        val vmCtx = VmExecutionContext(vm)
 
         return object : SimMachine {
             override val model: SimMachineModel
                 get() = vmCtx.machine
 
             override val usage: StateFlow<Double>
-                get() = vmCtx.session.usage
+                get() = vm.usage
 
             /**
              * The current active workload.
@@ -187,6 +189,7 @@ public class SimHypervisor(
             val totalAllocatedUsage = maxUsage - availableUsage
             var totalAllocatedBurst = 0L
             availableUsage = totalAllocatedUsage
+            val serverLoad = totalAllocatedUsage / maxUsage
 
             // Divide the requests over the available capacity of the pCPUs fairly
             for (i in pCPUs) {
@@ -232,7 +235,7 @@ public class SimHypervisor(
                 val vm = vmIterator.next()
 
                 // Apply performance interference model
-                val performanceScore = 1.0 // TODO Performance interference
+                val performanceScore = vm.performanceInterferenceModel?.apply(serverLoad) ?: 1.0
                 var hasFinished = false
 
                 for (vcpu in vm.vcpus) {
@@ -330,6 +333,7 @@ public class SimHypervisor(
     @OptIn(InternalCoroutinesApi::class)
     private data class VmSession(
         val model: SimMachineModel,
+        val performanceInterferenceModel: PerformanceInterferenceModel? = null,
         var triggerMode: SimExecutionContext.TriggerMode = SimExecutionContext.TriggerMode.FIRST,
         var merge: (SimExecutionContext.Slice, SimExecutionContext.Slice) -> SimExecutionContext.Slice = { _, r -> r },
         var select: () -> Unit = {}
@@ -491,12 +495,10 @@ public class SimHypervisor(
      * The execution context in which a VM runs.
      *
      */
-    private inner class VmExecutionContext(override val machine: SimMachineModel) :
-        SimExecutionContext,
-        DisposableHandle {
-        private var finalized: Boolean = false
-        private var initialized: Boolean = false
-        val session: VmSession = VmSession(machine)
+    private inner class VmExecutionContext(val session: VmSession) :
+        SimExecutionContext, DisposableHandle {
+        override val machine: SimMachineModel
+            get() = session.model
 
         override val clock: Clock
             get() = this@SimHypervisor.clock
diff --git a/simulator/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/interference/PerformanceInterferenceModel.kt b/simulator/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/interference/PerformanceInterferenceModel.kt
new file mode 100644
index 00000000..4c409887
--- /dev/null
+++ b/simulator/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/interference/PerformanceInterferenceModel.kt
@@ -0,0 +1,134 @@
+/*
+ * Copyright (c) 2020 AtLarge Research
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in all
+ * copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+package org.opendc.simulator.compute.interference
+
+import java.util.*
+import kotlin.random.Random
+
+/**
+ * Meta-data key for the [PerformanceInterferenceModel] of an image.
+ */
+public const val IMAGE_PERF_INTERFERENCE_MODEL: String = "image:performance-interference"
+
+/**
+ * Performance Interference Model describing the variability incurred by different sets of workloads if colocated.
+ *
+ * @param items The [PerformanceInterferenceModel.Item]s that make up this model.
+ */
+public class PerformanceInterferenceModel(
+    public val items: SortedSet<Item>,
+    private val random: Random = Random(0)
+) {
+    private var intersectingItems: List<Item> = emptyList()
+    private val colocatedWorkloads = TreeMap<String, Int>()
+
+    /**
+     * Indicate that a VM has started.
+     */
+    public fun onStart(name: String) {
+        colocatedWorkloads.merge(name, 1, Int::plus)
+        intersectingItems = items.filter { item -> doesMatch(item) }
+    }
+
+    /**
+     * Indicate that a VM has stopped.
+     */
+    public fun onStop(name: String) {
+        colocatedWorkloads.computeIfPresent(name) { _, v -> (v - 1).takeUnless { it == 0 } }
+        intersectingItems = items.filter { item -> doesMatch(item) }
+    }
+
+    /**
+     * Compute the performance interference based on the current server load.
+     */
+    public fun apply(currentServerLoad: Double): Double {
+        if (intersectingItems.isEmpty()) {
+            return 1.0
+        }
+        val score = intersectingItems
+            .firstOrNull { it.minServerLoad <= currentServerLoad }
+
+        // Apply performance penalty to (on average) only one of the VMs
+        return if (score != null && random.nextInt(score.workloadNames.size) == 0) {
+            score.performanceScore
+        } else {
+            1.0
+        }
+    }
+
+    private fun doesMatch(item: Item): Boolean {
+        var count = 0
+        for (
+            name in item.workloadNames.subSet(
+                colocatedWorkloads.firstKey(),
+                colocatedWorkloads.lastKey() + "\u0000"
+            )
+        ) {
+            count += colocatedWorkloads.getOrDefault(name, 0)
+            if (count > 1)
+                return true
+        }
+        return false
+    }
+
+    /**
+     * Model describing how a specific set of workloads causes performance variability for each workload.
+     *
+     * @param workloadNames The names of the workloads that together cause performance variability for each workload in the set.
+     * @param minServerLoad The minimum total server load at which this interference is activated and noticeable.
+     * @param performanceScore The performance score that should be applied to each workload's performance. 1 means no
+     * influence, <1 means that performance degrades, and >1 means that performance improves.
+     */
+    public data class Item(
+        public val workloadNames: SortedSet<String>,
+        public val minServerLoad: Double,
+        public val performanceScore: Double
+    ) : Comparable<Item> {
+        override fun equals(other: Any?): Boolean {
+            if (this === other) return true
+            if (javaClass != other?.javaClass) return false
+
+            other as Item
+
+            if (workloadNames != other.workloadNames) return false
+
+            return true
+        }
+
+        override fun hashCode(): Int = workloadNames.hashCode()
+
+        override fun compareTo(other: Item): Int {
+            var cmp = performanceScore.compareTo(other.performanceScore)
+            if (cmp != 0) {
+                return cmp
+            }
+
+            cmp = minServerLoad.compareTo(other.minServerLoad)
+            if (cmp != 0) {
+                return cmp
+            }
+
+            return hashCode().compareTo(other.hashCode())
+        }
+    }
+}
diff --git a/simulator/opendc-simulator/opendc-simulator-compute/src/test/kotlin/org/opendc/simulator/compute/SimHypervisorTest.kt b/simulator/opendc-simulator/opendc-simulator-compute/src/test/kotlin/org/opendc/simulator/compute/SimHypervisorTest.kt
index b9cd1b06..78bd2940 100644
--- a/simulator/opendc-simulator/opendc-simulator-compute/src/test/kotlin/org/opendc/simulator/compute/SimHypervisorTest.kt
+++ b/simulator/opendc-simulator/opendc-simulator-compute/src/test/kotlin/org/opendc/simulator/compute/SimHypervisorTest.kt
@@ -36,7 +36,6 @@ import org.opendc.simulator.compute.model.ProcessingUnit
 import org.opendc.simulator.compute.workload.SimTraceWorkload
 import org.opendc.simulator.utils.DelayControllerClockAdapter
 import java.time.Clock
-import java.util.*
 
 /**
  * Test suite for the [SimHypervisor] class.