diff options
10 files changed, 113 insertions, 34 deletions
diff --git a/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimAbstractResourceAggregator.kt b/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimAbstractResourceAggregator.kt index 84217278..8a24b3e7 100644 --- a/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimAbstractResourceAggregator.kt +++ b/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimAbstractResourceAggregator.kt @@ -116,8 +116,8 @@ public abstract class SimAbstractResourceAggregator( updateCounters(ctx, work) } - override fun getRemainingWork(ctx: SimResourceControllableContext, work: Double, speed: Double, duration: Long): Double { - return _inputConsumers.sumOf { it.remainingWork } + override fun getConsumedWork(ctx: SimResourceControllableContext, work: Double, speed: Double, duration: Long): Double { + return work - _inputConsumers.sumOf { it.remainingWork } } } } diff --git a/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimResourceDistributor.kt b/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimResourceDistributor.kt index 6bfbfc99..f384582f 100644 --- a/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimResourceDistributor.kt +++ b/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimResourceDistributor.kt @@ -22,6 +22,8 @@ package org.opendc.simulator.resources +import org.opendc.simulator.resources.interference.InterferenceKey + /** * A [SimResourceDistributor] distributes the capacity of some resource over multiple resource consumers. */ @@ -33,6 +35,8 @@ public interface SimResourceDistributor : SimResourceConsumer { /** * Create a new output for the distributor. + * + * @param key The key of the interference member to which the output belongs. */ - public fun newOutput(): SimResourceCloseableProvider + public fun newOutput(key: InterferenceKey? = null): SimResourceCloseableProvider } diff --git a/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimResourceDistributorMaxMin.kt b/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimResourceDistributorMaxMin.kt index d8fc8cb6..398797cf 100644 --- a/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimResourceDistributorMaxMin.kt +++ b/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimResourceDistributorMaxMin.kt @@ -22,15 +22,21 @@ package org.opendc.simulator.resources -import kotlin.math.max +import org.opendc.simulator.resources.interference.InterferenceDomain +import org.opendc.simulator.resources.interference.InterferenceKey import kotlin.math.min /** * A [SimResourceDistributor] that distributes the capacity of a resource over consumers using max-min fair sharing. + * + * @param interpreter The interpreter for managing the resource contexts. + * @param parent The parent resource system of the distributor. + * @param interferenceDomain The interference domain of the distributor. */ public class SimResourceDistributorMaxMin( private val interpreter: SimResourceInterpreter, - private val parent: SimResourceSystem? = null + private val parent: SimResourceSystem? = null, + private val interferenceDomain: InterferenceDomain? = null ) : SimResourceDistributor { override val outputs: Set<SimResourceCloseableProvider> get() = _outputs @@ -56,9 +62,14 @@ public class SimResourceDistributorMaxMin( */ private var totalAllocatedSpeed = 0.0 + /** + * The total requested speed for the output resources. + */ + private var totalRequestedSpeed = 0.0 + /* SimResourceDistributor */ - override fun newOutput(): SimResourceCloseableProvider { - val provider = Output(ctx?.capacity ?: 0.0) + override fun newOutput(key: InterferenceKey?): SimResourceCloseableProvider { + val provider = Output(ctx?.capacity ?: 0.0, key) _outputs.add(provider) return provider } @@ -148,6 +159,7 @@ public class SimResourceDistributorMaxMin( assert(deadline >= interpreter.clock.millis()) { "Deadline already passed" } this.totalRequestedWork = totalRequestedWork + this.totalRequestedSpeed = totalRequestedSpeed this.totalAllocatedSpeed = capacity - availableSpeed val totalAllocatedWork = min( totalRequestedWork, @@ -169,7 +181,7 @@ public class SimResourceDistributorMaxMin( /** * An internal [SimResourceProvider] implementation for switch outputs. */ - private inner class Output(capacity: Double) : + private inner class Output(capacity: Double, private val key: InterferenceKey?) : SimAbstractResourceProvider(interpreter, parent, capacity), SimResourceCloseableProvider, SimResourceProviderLogic, @@ -216,7 +228,6 @@ public class SimResourceDistributorMaxMin( check(!isClosed) { "Cannot re-use closed output" } activeOutputs += this - interpreter.batch { ctx.start() // Interrupt the input to re-schedule the resources @@ -262,19 +273,22 @@ public class SimResourceDistributorMaxMin( lastCommandTimestamp = ctx.clock.millis() } - override fun getRemainingWork(ctx: SimResourceControllableContext, work: Double, speed: Double, duration: Long): Double { + override fun getConsumedWork(ctx: SimResourceControllableContext, work: Double, speed: Double, duration: Long): Double { val totalRemainingWork = this@SimResourceDistributorMaxMin.ctx?.remainingWork ?: 0.0 - return if (work > 0.0) { - // Compute the fraction of compute time allocated to the output - val fraction = actualSpeed / totalAllocatedSpeed + // Compute the fraction of compute time allocated to the output + val fraction = actualSpeed / totalAllocatedSpeed - // Compute the work that was actually granted to the output. - val processingAvailable = max(0.0, totalRequestedWork - totalRemainingWork) * fraction - max(0.0, work - processingAvailable) + // Compute the performance penalty due to resource interference + val perfScore = if (interferenceDomain != null) { + val load = totalAllocatedSpeed / requireNotNull(this@SimResourceDistributorMaxMin.ctx).capacity + interferenceDomain.apply(key, load) } else { - 0.0 + 1.0 } + + // Compute the work that was actually granted to the output. + return (totalRequestedWork - totalRemainingWork) * fraction * perfScore } /* Comparable */ diff --git a/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimResourceProviderLogic.kt b/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimResourceProviderLogic.kt index 5231ecf5..17045557 100644 --- a/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimResourceProviderLogic.kt +++ b/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimResourceProviderLogic.kt @@ -22,8 +22,6 @@ package org.opendc.simulator.resources -import kotlin.math.max - /** * The logic of a resource provider. */ @@ -63,19 +61,18 @@ public interface SimResourceProviderLogic { public fun onFinish(ctx: SimResourceControllableContext) /** - * Get the remaining work to process after a resource consumption. + * Compute the amount of work that was consumed over the specified [duration]. * - * @param work The size of the resource consumption. - * @param speed The speed of consumption. + * @param work The total size of the resource consumption. + * @param speed The speed of the resource provider. * @param duration The duration from the start of the consumption until now. - * @return The amount of work remaining. + * @return The amount of work that was consumed by the resource provider. */ - public fun getRemainingWork(ctx: SimResourceControllableContext, work: Double, speed: Double, duration: Long): Double { + public fun getConsumedWork(ctx: SimResourceControllableContext, work: Double, speed: Double, duration: Long): Double { return if (duration > 0L) { - val processed = duration / 1000.0 * speed - max(0.0, work - processed) + return (duration / 1000.0) * speed } else { - 0.0 + work } } } diff --git a/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimResourceSwitch.kt b/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimResourceSwitch.kt index f6e7b22f..d2aab634 100644 --- a/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimResourceSwitch.kt +++ b/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimResourceSwitch.kt @@ -22,6 +22,8 @@ package org.opendc.simulator.resources +import org.opendc.simulator.resources.interference.InterferenceKey + /** * A [SimResourceSwitch] enables switching of capacity of multiple resources between multiple consumers. */ @@ -43,8 +45,10 @@ public interface SimResourceSwitch : AutoCloseable { /** * Create a new output on the switch. + * + * @param key The key of the interference member to which the output belongs. */ - public fun newOutput(): SimResourceCloseableProvider + public fun newOutput(key: InterferenceKey? = null): SimResourceCloseableProvider /** * Add the specified [input] to the switch. diff --git a/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimResourceSwitchExclusive.kt b/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimResourceSwitchExclusive.kt index 4ff741ed..fbb541e5 100644 --- a/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimResourceSwitchExclusive.kt +++ b/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimResourceSwitchExclusive.kt @@ -22,6 +22,7 @@ package org.opendc.simulator.resources +import org.opendc.simulator.resources.interference.InterferenceKey import java.util.ArrayDeque /** @@ -61,7 +62,10 @@ public class SimResourceSwitchExclusive : SimResourceSwitch { override fun toString(): String = "SimResourceCounters[demand=$demand,actual=$actual,overcommit=$overcommit]" } - override fun newOutput(): SimResourceCloseableProvider { + /** + * Add an output to the switch. + */ + override fun newOutput(key: InterferenceKey?): SimResourceCloseableProvider { check(!isClosed) { "Switch has been closed" } check(availableResources.isNotEmpty()) { "No capacity to serve request" } val forwarder = availableResources.poll() diff --git a/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimResourceSwitchMaxMin.kt b/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimResourceSwitchMaxMin.kt index 50d58798..ceb5a1a4 100644 --- a/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimResourceSwitchMaxMin.kt +++ b/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/SimResourceSwitchMaxMin.kt @@ -22,13 +22,21 @@ package org.opendc.simulator.resources +import org.opendc.simulator.resources.interference.InterferenceDomain +import org.opendc.simulator.resources.interference.InterferenceKey + /** * A [SimResourceSwitch] implementation that switches resource consumptions over the available resources using max-min * fair sharing. + * + * @param interpreter The interpreter for managing the resource contexts. + * @param parent The parent resource system of the switch. + * @param interferenceDomain The interference domain of the switch. */ public class SimResourceSwitchMaxMin( interpreter: SimResourceInterpreter, - parent: SimResourceSystem? = null + parent: SimResourceSystem? = null, + interferenceDomain: InterferenceDomain? = null ) : SimResourceSwitch { /** * The output resource providers to which resource consumers can be attached. @@ -61,7 +69,7 @@ public class SimResourceSwitchMaxMin( /** * The distributor to distribute the aggregated resources. */ - private val distributor = SimResourceDistributorMaxMin(interpreter, parent) + private val distributor = SimResourceDistributorMaxMin(interpreter, parent, interferenceDomain) init { aggregator.startConsumer(distributor) @@ -70,10 +78,10 @@ public class SimResourceSwitchMaxMin( /** * Add an output to the switch. */ - override fun newOutput(): SimResourceCloseableProvider { + override fun newOutput(key: InterferenceKey?): SimResourceCloseableProvider { check(!isClosed) { "Switch has been closed" } - return distributor.newOutput() + return distributor.newOutput(key) } /** diff --git a/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/impl/SimResourceContextImpl.kt b/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/impl/SimResourceContextImpl.kt index 90c7bc75..98fad068 100644 --- a/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/impl/SimResourceContextImpl.kt +++ b/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/impl/SimResourceContextImpl.kt @@ -24,6 +24,7 @@ package org.opendc.simulator.resources.impl import org.opendc.simulator.resources.* import java.time.Clock +import kotlin.math.max import kotlin.math.min /** @@ -318,7 +319,7 @@ internal class SimResourceContextImpl( */ private fun computeRemainingWork(now: Long): Double { return if (_work > 0.0) - logic.getRemainingWork(this, _work, speed, now - _timestamp) + max(0.0, _work - logic.getConsumedWork(this, _work, speed, now - _timestamp)) else 0.0 } diff --git a/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/interference/InterferenceDomain.kt b/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/interference/InterferenceDomain.kt new file mode 100644 index 00000000..1066777f --- /dev/null +++ b/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/interference/InterferenceDomain.kt @@ -0,0 +1,19 @@ +package org.opendc.simulator.resources.interference + +import org.opendc.simulator.resources.SimResourceConsumer + +/** + * An interference domain represents a system of resources where [resource consumers][SimResourceConsumer] may incur + * performance variability due to operating on the same resources and therefore causing interference. + */ +public interface InterferenceDomain { + /** + * Compute the performance score of a participant in this interference domain. + * + * @param key The participant to obtain the score of or `null` if the participant has no key. + * @param load The overall load on the interference domain. + * @return A score representing the performance score to be applied to the resource consumer, with 1 + * meaning no influence, <1 means that performance degrades, and >1 means that performance improves. + */ + public fun apply(key: InterferenceKey?, load: Double): Double +} diff --git a/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/interference/InterferenceKey.kt b/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/interference/InterferenceKey.kt new file mode 100644 index 00000000..8b12e7b4 --- /dev/null +++ b/opendc-simulator/opendc-simulator-resources/src/main/kotlin/org/opendc/simulator/resources/interference/InterferenceKey.kt @@ -0,0 +1,28 @@ +/* + * 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.resources.interference + +/** + * A key that uniquely identifies a participant of an interference domain. + */ +public interface InterferenceKey |