From e56967a29ac2b2d26cc085b1f3e27096dad6a170 Mon Sep 17 00:00:00 2001 From: Fabian Mastenbroek Date: Thu, 24 Jun 2021 12:54:52 +0200 Subject: simulator: Re-implement performance interference model This change updates reimplements the performance interference model to work on top of the universal resource model in `opendc-simulator-resources`. This enables us to model interference and performance variability of other resources such as disk or network in the future. --- .../interference/PerformanceInterferenceModel.kt | 134 ---------------- .../compute/kernel/SimAbstractHypervisor.kt | 30 ++-- .../compute/kernel/SimFairShareHypervisor.kt | 12 +- .../kernel/SimFairShareHypervisorProvider.kt | 12 +- .../simulator/compute/kernel/SimHypervisor.kt | 10 +- .../compute/kernel/SimHypervisorProvider.kt | 4 + .../compute/kernel/SimSpaceSharedHypervisor.kt | 2 +- .../kernel/SimSpaceSharedHypervisorProvider.kt | 4 + .../kernel/interference/VmInterferenceDomain.kt | 43 ++++++ .../kernel/interference/VmInterferenceGroup.kt | 44 ++++++ .../kernel/interference/VmInterferenceModel.kt | 170 +++++++++++++++++++++ .../org/opendc/simulator/compute/SimMachineTest.kt | 12 +- .../simulator/compute/kernel/SimHypervisorTest.kt | 61 ++++++++ 13 files changed, 371 insertions(+), 167 deletions(-) delete mode 100644 opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/interference/PerformanceInterferenceModel.kt create mode 100644 opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/interference/VmInterferenceDomain.kt create mode 100644 opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/interference/VmInterferenceGroup.kt create mode 100644 opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/interference/VmInterferenceModel.kt (limited to 'opendc-simulator/opendc-simulator-compute') diff --git a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/interference/PerformanceInterferenceModel.kt b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/interference/PerformanceInterferenceModel.kt deleted file mode 100644 index 4c409887..00000000 --- a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/interference/PerformanceInterferenceModel.kt +++ /dev/null @@ -1,134 +0,0 @@ -/* - * 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, - private val random: Random = Random(0) -) { - private var intersectingItems: List = emptyList() - private val colocatedWorkloads = TreeMap() - - /** - * 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, - public val minServerLoad: Double, - public val performanceScore: Double - ) : Comparable { - 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/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimAbstractHypervisor.kt b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimAbstractHypervisor.kt index fb46dab4..d287312f 100644 --- a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimAbstractHypervisor.kt +++ b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimAbstractHypervisor.kt @@ -23,9 +23,9 @@ package org.opendc.simulator.compute.kernel import org.opendc.simulator.compute.* -import org.opendc.simulator.compute.interference.PerformanceInterferenceModel import org.opendc.simulator.compute.kernel.cpufreq.ScalingGovernor import org.opendc.simulator.compute.kernel.cpufreq.ScalingPolicy +import org.opendc.simulator.compute.kernel.interference.VmInterferenceDomain import org.opendc.simulator.compute.model.MachineModel import org.opendc.simulator.compute.model.ProcessingUnit import org.opendc.simulator.resources.* @@ -39,7 +39,8 @@ import org.opendc.simulator.resources.SimResourceSwitch */ public abstract class SimAbstractHypervisor( private val interpreter: SimResourceInterpreter, - private val scalingGovernor: ScalingGovernor? + private val scalingGovernor: ScalingGovernor? = null, + protected val interferenceDomain: VmInterferenceDomain? = null ) : SimHypervisor { /** * The machine on which the hypervisor runs. @@ -87,12 +88,9 @@ public abstract class SimAbstractHypervisor( return canFit(model, switch) } - override fun createMachine( - model: MachineModel, - performanceInterferenceModel: PerformanceInterferenceModel? - ): SimMachine { + override fun createMachine(model: MachineModel, interferenceId: String?): SimMachine { require(canFit(model)) { "Machine does not fit" } - val vm = VirtualMachine(model, performanceInterferenceModel) + val vm = VirtualMachine(model, interferenceId) _vms.add(vm) return vm } @@ -116,17 +114,18 @@ public abstract class SimAbstractHypervisor( /** * A virtual machine running on the hypervisor. * - * @property model The machine model of the virtual machine. - * @property performanceInterferenceModel The performance interference model to utilize. + * @param model The machine model of the virtual machine. */ - private inner class VirtualMachine( - model: MachineModel, - val performanceInterferenceModel: PerformanceInterferenceModel? = null, - ) : SimAbstractMachine(interpreter, parent = null, model) { + private inner class VirtualMachine(model: MachineModel, interferenceId: String? = null) : SimAbstractMachine(interpreter, parent = null, model) { + /** + * The interference key of this virtual machine. + */ + private val interferenceKey = interferenceId?.let { interferenceDomain?.join(interferenceId) } + /** * The vCPUs of the machine. */ - override val cpus = model.cpus.map { VCpu(switch.newOutput(), it) } + override val cpus = model.cpus.map { VCpu(switch.newOutput(interferenceKey), it) } override fun close() { super.close() @@ -136,6 +135,9 @@ public abstract class SimAbstractHypervisor( } _vms.remove(this) + if (interferenceKey != null) { + interferenceDomain?.leave(interferenceKey) + } } } diff --git a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimFairShareHypervisor.kt b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimFairShareHypervisor.kt index 2ce51ea6..17130d34 100644 --- a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimFairShareHypervisor.kt +++ b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimFairShareHypervisor.kt @@ -22,8 +22,10 @@ package org.opendc.simulator.compute.kernel +import org.opendc.simulator.compute.SimMachine import org.opendc.simulator.compute.SimMachineContext import org.opendc.simulator.compute.kernel.cpufreq.ScalingGovernor +import org.opendc.simulator.compute.kernel.interference.VmInterferenceDomain import org.opendc.simulator.compute.model.MachineModel import org.opendc.simulator.compute.workload.SimWorkload import org.opendc.simulator.resources.SimResourceInterpreter @@ -32,20 +34,22 @@ import org.opendc.simulator.resources.SimResourceSwitchMaxMin import org.opendc.simulator.resources.SimResourceSystem /** - * A [SimHypervisor] that distributes the computing requirements of multiple [SimWorkload] on a single - * [SimBareMetalMachine] concurrently using weighted fair sharing. + * A [SimHypervisor] that distributes the computing requirements of multiple [SimWorkload]s on a single [SimMachine] + * concurrently using weighted fair sharing. * * @param interpreter The interpreter to manage the machine's resources. * @param parent The parent simulation system. * @param scalingGovernor The CPU frequency scaling governor to use for the hypervisor. + * @param interferenceDomain The resource interference domain to which the hypervisor belongs. * @param listener The hypervisor listener to use. */ public class SimFairShareHypervisor( private val interpreter: SimResourceInterpreter, private val parent: SimResourceSystem? = null, scalingGovernor: ScalingGovernor? = null, + interferenceDomain: VmInterferenceDomain? = null, private val listener: SimHypervisor.Listener? = null -) : SimAbstractHypervisor(interpreter, scalingGovernor) { +) : SimAbstractHypervisor(interpreter, scalingGovernor, interferenceDomain) { override fun canFit(model: MachineModel, switch: SimResourceSwitch): Boolean = true @@ -54,7 +58,7 @@ public class SimFairShareHypervisor( } private inner class SwitchSystem(private val ctx: SimMachineContext) : SimResourceSystem { - val switch = SimResourceSwitchMaxMin(interpreter, this) + val switch = SimResourceSwitchMaxMin(interpreter, this, interferenceDomain) override val parent: SimResourceSystem? = this@SimFairShareHypervisor.parent diff --git a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimFairShareHypervisorProvider.kt b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimFairShareHypervisorProvider.kt index 542cd0d2..8d0592ec 100644 --- a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimFairShareHypervisorProvider.kt +++ b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimFairShareHypervisorProvider.kt @@ -22,6 +22,8 @@ package org.opendc.simulator.compute.kernel +import org.opendc.simulator.compute.kernel.cpufreq.ScalingGovernor +import org.opendc.simulator.compute.kernel.interference.VmInterferenceDomain import org.opendc.simulator.resources.SimResourceInterpreter import org.opendc.simulator.resources.SimResourceSystem @@ -34,6 +36,14 @@ public class SimFairShareHypervisorProvider : SimHypervisorProvider { override fun create( interpreter: SimResourceInterpreter, parent: SimResourceSystem?, + scalingGovernor: ScalingGovernor?, + interferenceDomain: VmInterferenceDomain?, listener: SimHypervisor.Listener? - ): SimHypervisor = SimFairShareHypervisor(interpreter, parent, listener = listener) + ): SimHypervisor = SimFairShareHypervisor( + interpreter, + parent, + scalingGovernor = scalingGovernor, + interferenceDomain = interferenceDomain, + listener = listener + ) } diff --git a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimHypervisor.kt b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimHypervisor.kt index 40402f5c..e398ab36 100644 --- a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimHypervisor.kt +++ b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimHypervisor.kt @@ -23,13 +23,12 @@ package org.opendc.simulator.compute.kernel import org.opendc.simulator.compute.SimMachine -import org.opendc.simulator.compute.interference.PerformanceInterferenceModel import org.opendc.simulator.compute.model.MachineModel import org.opendc.simulator.compute.workload.SimWorkload /** * A SimHypervisor facilitates the execution of multiple concurrent [SimWorkload]s, while acting as a single workload - * to a [SimBareMetalMachine]. + * to another [SimMachine]. */ public interface SimHypervisor : SimWorkload { /** @@ -46,12 +45,9 @@ public interface SimHypervisor : SimWorkload { * Create a [SimMachine] instance on which users may run a [SimWorkload]. * * @param model The machine to create. - * @param performanceInterferenceModel The performance interference model to use. + * @param interferenceId An identifier for the interference model. */ - public fun createMachine( - model: MachineModel, - performanceInterferenceModel: PerformanceInterferenceModel? = null - ): SimMachine + public fun createMachine(model: MachineModel, interferenceId: String? = null): SimMachine /** * Event listener for hypervisor events. diff --git a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimHypervisorProvider.kt b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimHypervisorProvider.kt index cafd1ffc..b307a34d 100644 --- a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimHypervisorProvider.kt +++ b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimHypervisorProvider.kt @@ -22,6 +22,8 @@ package org.opendc.simulator.compute.kernel +import org.opendc.simulator.compute.kernel.cpufreq.ScalingGovernor +import org.opendc.simulator.compute.kernel.interference.VmInterferenceDomain import org.opendc.simulator.resources.SimResourceInterpreter import org.opendc.simulator.resources.SimResourceSystem @@ -43,6 +45,8 @@ public interface SimHypervisorProvider { public fun create( interpreter: SimResourceInterpreter, parent: SimResourceSystem? = null, + scalingGovernor: ScalingGovernor? = null, + interferenceDomain: VmInterferenceDomain? = null, listener: SimHypervisor.Listener? = null ): SimHypervisor } diff --git a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimSpaceSharedHypervisor.kt b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimSpaceSharedHypervisor.kt index 3ceebb9a..ac1c0250 100644 --- a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimSpaceSharedHypervisor.kt +++ b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimSpaceSharedHypervisor.kt @@ -31,7 +31,7 @@ import org.opendc.simulator.resources.SimResourceSwitchExclusive /** * A [SimHypervisor] that allocates its sub-resources exclusively for the virtual machine that it hosts. */ -public class SimSpaceSharedHypervisor(interpreter: SimResourceInterpreter) : SimAbstractHypervisor(interpreter, null) { +public class SimSpaceSharedHypervisor(interpreter: SimResourceInterpreter) : SimAbstractHypervisor(interpreter) { override fun canFit(model: MachineModel, switch: SimResourceSwitch): Boolean { return switch.inputs.size - switch.outputs.size >= model.cpus.size } diff --git a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimSpaceSharedHypervisorProvider.kt b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimSpaceSharedHypervisorProvider.kt index fb47d9e5..3906cb9a 100644 --- a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimSpaceSharedHypervisorProvider.kt +++ b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimSpaceSharedHypervisorProvider.kt @@ -22,6 +22,8 @@ package org.opendc.simulator.compute.kernel +import org.opendc.simulator.compute.kernel.cpufreq.ScalingGovernor +import org.opendc.simulator.compute.kernel.interference.VmInterferenceDomain import org.opendc.simulator.resources.SimResourceInterpreter import org.opendc.simulator.resources.SimResourceSystem @@ -34,6 +36,8 @@ public class SimSpaceSharedHypervisorProvider : SimHypervisorProvider { override fun create( interpreter: SimResourceInterpreter, parent: SimResourceSystem?, + scalingGovernor: ScalingGovernor?, + interferenceDomain: VmInterferenceDomain?, listener: SimHypervisor.Listener? ): SimHypervisor = SimSpaceSharedHypervisor(interpreter) } diff --git a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/interference/VmInterferenceDomain.kt b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/interference/VmInterferenceDomain.kt new file mode 100644 index 00000000..1801fcd0 --- /dev/null +++ b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/interference/VmInterferenceDomain.kt @@ -0,0 +1,43 @@ +/* + * Copyright (c) 2021 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.kernel.interference + +import org.opendc.simulator.resources.interference.InterferenceDomain +import org.opendc.simulator.resources.interference.InterferenceKey + +/** + * The interference domain of a hypervisor. + */ +public interface VmInterferenceDomain : InterferenceDomain { + /** + * Join this interference domain. + * + * @param id The identifier of the virtual machine. + */ + public fun join(id: String): InterferenceKey + + /** + * Leave this interference domain. + */ + public fun leave(key: InterferenceKey) +} diff --git a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/interference/VmInterferenceGroup.kt b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/interference/VmInterferenceGroup.kt new file mode 100644 index 00000000..708ddede --- /dev/null +++ b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/interference/VmInterferenceGroup.kt @@ -0,0 +1,44 @@ +/* + * Copyright (c) 2021 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.kernel.interference + +/** + * A group of virtual machines that together can interfere when operating on the same resources, causing performance + * variability. + */ +public data class VmInterferenceGroup( + /** + * The minimum load of the host before the interference occurs. + */ + public val targetLoad: Double, + + /** + * A score in [0, 1] representing the performance variability as a result of resource interference. + */ + public val score: Double, + + /** + * The members of this interference group. + */ + public val members: Set +) diff --git a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/interference/VmInterferenceModel.kt b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/interference/VmInterferenceModel.kt new file mode 100644 index 00000000..c2e00c8e --- /dev/null +++ b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/interference/VmInterferenceModel.kt @@ -0,0 +1,170 @@ +/* + * Copyright (c) 2021 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.kernel.interference + +import org.opendc.simulator.resources.interference.InterferenceKey +import java.util.* + +/** + * An interference model that models the resource interference between virtual machines on a host. + * + * @param groups The groups of virtual machines that interfere with each other. + * @param random The [Random] instance to select the affected virtual machines. + */ +public class VmInterferenceModel( + private val groups: List, + private val random: Random = Random(0) +) { + /** + * Construct a new [VmInterferenceDomain]. + */ + public fun newDomain(): VmInterferenceDomain = object : VmInterferenceDomain { + /** + * The stateful groups of this domain. + */ + private val groups = this@VmInterferenceModel.groups.map { GroupContext(it) } + + /** + * The set of keys active in this domain. + */ + private val keys = mutableSetOf() + + override fun join(id: String): InterferenceKey { + val key = InterferenceKeyImpl(id, groups.filter { id in it }.sortedBy { it.group.targetLoad }) + keys += key + return key + } + + override fun leave(key: InterferenceKey) { + if (key is InterferenceKeyImpl) { + keys -= key + key.leave() + } + } + + override fun apply(key: InterferenceKey?, load: Double): Double { + if (key == null || key !is InterferenceKeyImpl) { + return 1.0 + } + + val ctx = key.findGroup(load) + val group = ctx?.group + + // Apply performance penalty to (on average) only one of the VMs + return if (group != null && random.nextInt(group.members.size) == 0) { + group.score + } else { + 1.0 + } + } + + override fun toString(): String = "VmInterferenceDomain" + } + + /** + * An interference key. + * + * @param id The identifier of the member. + * @param groups The groups to which the key belongs. + */ + private inner class InterferenceKeyImpl(val id: String, private val groups: List) : InterferenceKey { + init { + for (group in groups) { + group.join(this) + } + } + + /** + * Find the active group that applies for the interference member. + */ + fun findGroup(load: Double): GroupContext? { + // Find the first active group whose target load is lower than the current load + val index = groups.binarySearchBy(load) { it.group.targetLoad } + val target = if (index >= 0) index else -(index + 1) + + // Check whether there are active groups ahead of the index + for (i in target until groups.size) { + val group = groups[i] + if (group.group.targetLoad > load) { + break + } else if (group.isActive) { + return group + } + } + + // Check whether there are active groups before the index + for (i in (target - 1) downTo 0) { + val group = groups[i] + if (group.isActive) { + return group + } + } + + return null + } + + /** + * Leave all the groups. + */ + fun leave() { + for (group in groups) { + group.leave(this) + } + } + } + + /** + * A group context is used to track the active keys per interference group. + */ + private inner class GroupContext(val group: VmInterferenceGroup) { + /** + * The active keys that are part of this group. + */ + private val keys = mutableSetOf() + + /** + * A flag to indicate that the group is active. + */ + val isActive + get() = keys.size > 1 + + /** + * Determine whether the specified [id] is part of this group. + */ + operator fun contains(id: String): Boolean = id in group.members + + /** + * Join this group with the specified [key]. + */ + fun join(key: InterferenceKeyImpl) { + keys += key + } + + /** + * Leave this group with the specified [key]. + */ + fun leave(key: InterferenceKeyImpl) { + keys -= key + } + } +} diff --git a/opendc-simulator/opendc-simulator-compute/src/test/kotlin/org/opendc/simulator/compute/SimMachineTest.kt b/opendc-simulator/opendc-simulator-compute/src/test/kotlin/org/opendc/simulator/compute/SimMachineTest.kt index 892d5223..a6d955ca 100644 --- a/opendc-simulator/opendc-simulator-compute/src/test/kotlin/org/opendc/simulator/compute/SimMachineTest.kt +++ b/opendc-simulator/opendc-simulator-compute/src/test/kotlin/org/opendc/simulator/compute/SimMachineTest.kt @@ -24,12 +24,9 @@ package org.opendc.simulator.compute import kotlinx.coroutines.* import kotlinx.coroutines.flow.toList +import org.junit.jupiter.api.* import org.junit.jupiter.api.Assertions.assertArrayEquals import org.junit.jupiter.api.Assertions.assertEquals -import org.junit.jupiter.api.BeforeEach -import org.junit.jupiter.api.Test -import org.junit.jupiter.api.assertDoesNotThrow -import org.junit.jupiter.api.assertThrows import org.opendc.simulator.compute.device.SimNetworkAdapter import org.opendc.simulator.compute.model.* import org.opendc.simulator.compute.power.ConstantPowerModel @@ -157,8 +154,10 @@ class SimMachineTest { try { coroutineScope { launch { machine.run(SimFlopsWorkload(2_000, utilization = 1.0)) } - assertEquals(100.0, machine.psu.powerDraw) - assertEquals(100.0, source.powerDraw) + assertAll( + { assertEquals(100.0, machine.psu.powerDraw) }, + { assertEquals(100.0, source.powerDraw) } + ) } } finally { machine.close() @@ -284,6 +283,7 @@ class SimMachineTest { } } + @Test fun testDiskWriteUsage() = runBlockingSimulation { val interpreter = SimResourceInterpreter(coroutineContext, clock) val machine = SimBareMetalMachine( diff --git a/opendc-simulator/opendc-simulator-compute/src/test/kotlin/org/opendc/simulator/compute/kernel/SimHypervisorTest.kt b/opendc-simulator/opendc-simulator-compute/src/test/kotlin/org/opendc/simulator/compute/kernel/SimHypervisorTest.kt index 71d48a31..a61cba8d 100644 --- a/opendc-simulator/opendc-simulator-compute/src/test/kotlin/org/opendc/simulator/compute/kernel/SimHypervisorTest.kt +++ b/opendc-simulator/opendc-simulator-compute/src/test/kotlin/org/opendc/simulator/compute/kernel/SimHypervisorTest.kt @@ -34,6 +34,8 @@ import org.junit.jupiter.api.assertAll import org.junit.jupiter.api.assertDoesNotThrow import org.opendc.simulator.compute.SimBareMetalMachine import org.opendc.simulator.compute.kernel.cpufreq.PerformanceScalingGovernor +import org.opendc.simulator.compute.kernel.interference.VmInterferenceGroup +import org.opendc.simulator.compute.kernel.interference.VmInterferenceModel import org.opendc.simulator.compute.model.MachineModel import org.opendc.simulator.compute.model.MemoryUnit import org.opendc.simulator.compute.model.ProcessingNode @@ -223,4 +225,63 @@ internal class SimHypervisorTest { machine.close() } + + @Test + fun testInterference() = runBlockingSimulation { + val cpuNode = ProcessingNode("Intel", "Xeon", "amd64", 2) + val model = MachineModel( + cpus = List(cpuNode.coreCount) { ProcessingUnit(cpuNode, it, 3200.0) }, + memory = List(4) { MemoryUnit("Crucial", "MTA18ASF4G72AZ-3G2B1", 3200.0, 32_000) } + ) + + val groups = listOf( + VmInterferenceGroup(targetLoad = 0.0, score = 0.9, members = setOf("a", "b")), + VmInterferenceGroup(targetLoad = 0.0, score = 0.6, members = setOf("a", "c")), + VmInterferenceGroup(targetLoad = 0.1, score = 0.8, members = setOf("a", "n")) + ) + val interferenceModel = VmInterferenceModel(groups) + + val platform = SimResourceInterpreter(coroutineContext, clock) + val machine = SimBareMetalMachine( + platform, model, SimplePowerDriver(ConstantPowerModel(0.0)) + ) + val hypervisor = SimFairShareHypervisor(platform, interferenceDomain = interferenceModel.newDomain()) + + val duration = 5 * 60L + val workloadA = + SimTraceWorkload( + sequenceOf( + SimTraceWorkload.Fragment(duration * 1000, 0.0, 1), + SimTraceWorkload.Fragment(duration * 1000, 28.0, 1), + SimTraceWorkload.Fragment(duration * 1000, 3500.0, 1), + SimTraceWorkload.Fragment(duration * 1000, 183.0, 1) + ), + ) + val workloadB = + SimTraceWorkload( + sequenceOf( + SimTraceWorkload.Fragment(duration * 1000, 0.0, 1), + SimTraceWorkload.Fragment(duration * 1000, 28.0, 1), + SimTraceWorkload.Fragment(duration * 1000, 3100.0, 1), + SimTraceWorkload.Fragment(duration * 1000, 73.0, 1) + ) + ) + + launch { + machine.run(hypervisor) + } + + coroutineScope { + launch { + val vm = hypervisor.createMachine(model, "a") + vm.run(workloadA) + vm.close() + } + val vm = hypervisor.createMachine(model, "b") + vm.run(workloadB) + vm.close() + } + + machine.close() + } } -- cgit v1.2.3