From 52d35cd82905612f0ef9f7b7d88611300fb48ebe Mon Sep 17 00:00:00 2001 From: Fabian Mastenbroek Date: Fri, 18 Feb 2022 14:08:18 +0100 Subject: refactor(utils): Rename utils module to common module This change adds a new module, opendc-common, that contains functionality that is shared across OpenDC's modules. We move the existing utils module into this new module. --- .../main/kotlin/org/opendc/common/util/Pacer.kt | 92 ++++++++ .../org/opendc/common/util/TimerScheduler.kt | 239 +++++++++++++++++++++ .../kotlin/org/opendc/common/util/PacerTest.kt | 127 +++++++++++ .../org/opendc/common/util/TimerSchedulerTest.kt | 139 ++++++++++++ 4 files changed, 597 insertions(+) create mode 100644 opendc-common/src/main/kotlin/org/opendc/common/util/Pacer.kt create mode 100644 opendc-common/src/main/kotlin/org/opendc/common/util/TimerScheduler.kt create mode 100644 opendc-common/src/test/kotlin/org/opendc/common/util/PacerTest.kt create mode 100644 opendc-common/src/test/kotlin/org/opendc/common/util/TimerSchedulerTest.kt (limited to 'opendc-common/src') diff --git a/opendc-common/src/main/kotlin/org/opendc/common/util/Pacer.kt b/opendc-common/src/main/kotlin/org/opendc/common/util/Pacer.kt new file mode 100644 index 00000000..8ccff6c3 --- /dev/null +++ b/opendc-common/src/main/kotlin/org/opendc/common/util/Pacer.kt @@ -0,0 +1,92 @@ +/* + * Copyright (c) 2022 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.common.util + +import kotlinx.coroutines.* +import java.lang.Runnable +import java.time.Clock +import kotlin.coroutines.ContinuationInterceptor +import kotlin.coroutines.CoroutineContext + +/** + * Helper class to pace the incoming scheduling requests. + * + * @param context The [CoroutineContext] in which the pacer runs. + * @param clock The virtual simulation clock. + * @param quantum The scheduling quantum. + * @param process The process to invoke for the incoming requests. + */ +public class Pacer( + private val context: CoroutineContext, + private val clock: Clock, + private val quantum: Long, + private val process: (Long) -> Unit +) { + /** + * The [Delay] instance that provides scheduled execution of [Runnable]s. + */ + @OptIn(InternalCoroutinesApi::class) + private val delay = + requireNotNull(context[ContinuationInterceptor] as? Delay) { "Invalid CoroutineDispatcher: no delay implementation" } + + /** + * The current [DisposableHandle] representing the pending scheduling cycle. + */ + private var handle: DisposableHandle? = null + + /** + * Determine whether a scheduling cycle is pending. + */ + public val isPending: Boolean get() = handle != null + + /** + * Enqueue a new scheduling cycle. + */ + public fun enqueue() { + if (handle != null) { + return + } + + val quantum = quantum + val now = clock.millis() + + // We assume that the scheduler runs at a fixed slot every time quantum (e.g t=0, t=60, t=120). + // We calculate here the delay until the next scheduling slot. + val timeUntilNextSlot = quantum - (now % quantum) + + @OptIn(InternalCoroutinesApi::class) + handle = delay.invokeOnTimeout(timeUntilNextSlot, { + process(now + timeUntilNextSlot) + handle = null + }, context) + } + + /** + * Cancel the currently pending scheduling cycle. + */ + public fun cancel() { + val handle = handle ?: return + this.handle = null + handle.dispose() + } +} diff --git a/opendc-common/src/main/kotlin/org/opendc/common/util/TimerScheduler.kt b/opendc-common/src/main/kotlin/org/opendc/common/util/TimerScheduler.kt new file mode 100644 index 00000000..86314411 --- /dev/null +++ b/opendc-common/src/main/kotlin/org/opendc/common/util/TimerScheduler.kt @@ -0,0 +1,239 @@ +/* + * Copyright (c) 2022 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.common.util + +import kotlinx.coroutines.* +import kotlinx.coroutines.channels.Channel +import kotlinx.coroutines.selects.select +import java.time.Clock +import java.util.* +import kotlin.coroutines.CoroutineContext +import kotlin.math.max + +/** + * A TimerScheduler facilitates scheduled execution of future tasks. + * + * @param context The [CoroutineContext] to run the tasks with. + * @param clock The clock to keep track of the time. + */ +@OptIn(ExperimentalCoroutinesApi::class) +public class TimerScheduler(context: CoroutineContext, private val clock: Clock) : AutoCloseable { + /** + * The scope in which the scheduler runs. + */ + private val scope = CoroutineScope(context + Job()) + + /** + * A priority queue containing the tasks to be scheduled in the future. + */ + private val queue = PriorityQueue() + + /** + * A map that keeps track of the timers. + */ + private val timers = mutableMapOf() + + /** + * The channel to communicate with the scheduling job. + */ + private val channel = Channel(Channel.CONFLATED) + + /** + * A flag to indicate that the scheduler is active. + */ + private var isActive = true + + init { + scope.launch { + val timers = timers + val queue = queue + val clock = clock + val job = requireNotNull(coroutineContext[Job]) + val exceptionHandler = coroutineContext[CoroutineExceptionHandler] + var next: Long? = channel.receive() + + while (true) { + next = select { + channel.onReceive { it } + + val delay = next?.let { max(0L, it - clock.millis()) } ?: return@select + + onTimeout(delay) { + while (queue.isNotEmpty() && job.isActive) { + val timer = queue.peek() + val timestamp = clock.millis() + + assert(timer.timestamp >= timestamp) { "Found task in the past" } + + if (timer.timestamp > timestamp && !timer.isCancelled) { + // Schedule a task for the next event to occur. + return@onTimeout timer.timestamp + } + + queue.poll() + + if (!timer.isCancelled) { + timers.remove(timer.key) + try { + timer() + } catch (e: Throwable) { + exceptionHandler?.handleException(coroutineContext, e) + } + } + } + + null + } + } + } + } + } + + /** + * Stop the scheduler. + */ + override fun close() { + isActive = false + cancelAll() + scope.cancel() + } + + /** + * Cancel a timer with a given key. + * + * If canceling a timer that was already canceled, or key never was used to start + * a timer this operation will do nothing. + * + * @param key The key of the timer to cancel. + */ + public fun cancel(key: T) { + if (!isActive) { + return + } + + val timer = timers.remove(key) + + // Mark the timer as cancelled + timer?.isCancelled = true + + // Optimization: check whether we are the head of the queue + val queue = queue + val channel = channel + val peek = queue.peek() + if (peek == timer) { + queue.poll() + + if (queue.isNotEmpty()) { + channel.trySend(peek.timestamp) + } else { + channel.trySend(null) + } + } + } + + /** + * Cancel all timers. + */ + public fun cancelAll() { + queue.clear() + timers.clear() + } + + /** + * Check if a timer with a given key is active. + * + * @param key The key to check if active. + * @return `true` if the timer with the specified [key] is active, `false` otherwise. + */ + public fun isTimerActive(key: T): Boolean = key in timers + + /** + * Start a timer that will invoke the specified [block] after [delay]. + * + * Each timer has a key and if a new timer with same key is started the previous is cancelled. + * + * @param key The key of the timer to start. + * @param delay The delay before invoking the block. + * @param block The block to invoke. + */ + public fun startSingleTimer(key: T, delay: Long, block: () -> Unit) { + startSingleTimerTo(key, clock.millis() + delay, block) + } + + /** + * Start a timer that will invoke the specified [block] at [timestamp]. + * + * Each timer has a key and if a new timer with same key is started the previous is cancelled. + * + * @param key The key of the timer to start. + * @param timestamp The timestamp at which to invoke the block. + * @param block The block to invoke. + */ + public fun startSingleTimerTo(key: T, timestamp: Long, block: () -> Unit) { + val now = clock.millis() + val queue = queue + val channel = channel + + require(timestamp >= now) { "Timestamp must be in the future" } + check(isActive) { "Timer is stopped" } + + timers.compute(key) { _, old -> + if (old != null && old.timestamp == timestamp) { + // Fast-path: timer for the same timestamp already exists + old + } else { + // Slow-path: cancel old timer and replace it with new timer + val timer = Timer(key, timestamp, block) + + old?.isCancelled = true + queue.add(timer) + + // Check if we need to push the interruption forward + // Note that we check by timer reference + if (queue.peek() === timer) { + channel.trySend(timer.timestamp) + } + + timer + } + } + } + + /** + * A task that is scheduled to run in the future. + */ + private inner class Timer(val key: T, val timestamp: Long, val block: () -> Unit) : Comparable { + /** + * A flag to indicate that the task has been cancelled. + */ + @JvmField + var isCancelled: Boolean = false + + /** + * Run the task. + */ + operator fun invoke(): Unit = block() + + override fun compareTo(other: Timer): Int = timestamp.compareTo(other.timestamp) + } +} diff --git a/opendc-common/src/test/kotlin/org/opendc/common/util/PacerTest.kt b/opendc-common/src/test/kotlin/org/opendc/common/util/PacerTest.kt new file mode 100644 index 00000000..1cd435f6 --- /dev/null +++ b/opendc-common/src/test/kotlin/org/opendc/common/util/PacerTest.kt @@ -0,0 +1,127 @@ +/* + * Copyright (c) 2022 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.common.util + +import kotlinx.coroutines.delay +import org.junit.jupiter.api.Assertions.* +import org.junit.jupiter.api.Test +import org.junit.jupiter.api.assertThrows +import org.opendc.simulator.core.runBlockingSimulation +import java.time.Clock +import kotlin.coroutines.EmptyCoroutineContext + +/** + * Test suite for the [Pacer] class. + */ +class PacerTest { + @Test + fun testEmptyContext() { + assertThrows { Pacer(EmptyCoroutineContext, Clock.systemUTC(), 100) {} } + } + + @Test + fun testSingleEnqueue() { + var count = 0 + + runBlockingSimulation { + val pacer = Pacer(coroutineContext, clock, quantum = 100) { + count++ + } + + pacer.enqueue() + } + + assertEquals(1, count) { "Process should execute once" } + } + + @Test + fun testCascade() { + var count = 0 + + runBlockingSimulation { + val pacer = Pacer(coroutineContext, clock, quantum = 100) { + count++ + } + + pacer.enqueue() + pacer.enqueue() + + assertTrue(pacer.isPending) + } + + assertEquals(1, count) { "Process should execute once" } + } + + @Test + fun testCancel() { + var count = 0 + + runBlockingSimulation { + val pacer = Pacer(coroutineContext, clock, quantum = 100) { + count++ + } + + pacer.enqueue() + pacer.cancel() + + assertFalse(pacer.isPending) + } + + assertEquals(0, count) { "Process should never execute " } + } + + @Test + fun testCancelWithoutPending() { + var count = 0 + + runBlockingSimulation { + val pacer = Pacer(coroutineContext, clock, quantum = 100) { + count++ + } + + assertFalse(pacer.isPending) + assertDoesNotThrow { pacer.cancel() } + + pacer.enqueue() + } + + assertEquals(1, count) { "Process should execute once" } + } + + @Test + fun testSubsequent() { + var count = 0 + + runBlockingSimulation { + val pacer = Pacer(coroutineContext, clock, quantum = 100) { + count++ + } + + pacer.enqueue() + delay(100) + pacer.enqueue() + } + + assertEquals(2, count) { "Process should execute twice" } + } +} diff --git a/opendc-common/src/test/kotlin/org/opendc/common/util/TimerSchedulerTest.kt b/opendc-common/src/test/kotlin/org/opendc/common/util/TimerSchedulerTest.kt new file mode 100644 index 00000000..89b0cbe9 --- /dev/null +++ b/opendc-common/src/test/kotlin/org/opendc/common/util/TimerSchedulerTest.kt @@ -0,0 +1,139 @@ +/* + * Copyright (c) 2022 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.common.util + +import kotlinx.coroutines.ExperimentalCoroutinesApi +import org.junit.jupiter.api.Assertions.* +import org.junit.jupiter.api.Test +import org.junit.jupiter.api.assertThrows +import org.opendc.simulator.core.runBlockingSimulation + +/** + * A test suite for the [TimerScheduler] class. + */ +@OptIn(ExperimentalCoroutinesApi::class) +internal class TimerSchedulerTest { + @Test + fun testBasicTimer() { + runBlockingSimulation { + val scheduler = TimerScheduler(coroutineContext, clock) + + scheduler.startSingleTimer(0, 1000) { + scheduler.close() + assertEquals(1000, clock.millis()) + } + } + } + + @Test + fun testCancelNonExisting() { + runBlockingSimulation { + val scheduler = TimerScheduler(coroutineContext, clock) + + scheduler.cancel(1) + scheduler.close() + } + } + + @Test + fun testCancelExisting() { + runBlockingSimulation { + val scheduler = TimerScheduler(coroutineContext, clock) + + scheduler.startSingleTimer(0, 1000) { + assertFalse(false) + } + + scheduler.startSingleTimer(1, 100) { + scheduler.cancel(0) + scheduler.close() + + assertEquals(100, clock.millis()) + } + } + } + + @Test + fun testCancelAll() { + runBlockingSimulation { + val scheduler = TimerScheduler(coroutineContext, clock) + + scheduler.startSingleTimer(0, 1000) { + assertFalse(false) + } + + scheduler.startSingleTimer(1, 100) { + assertFalse(false) + } + + scheduler.close() + } + } + + @Test + fun testOverride() { + runBlockingSimulation { + val scheduler = TimerScheduler(coroutineContext, clock) + + scheduler.startSingleTimer(0, 1000) { + assertFalse(false) + } + + scheduler.startSingleTimer(0, 200) { + scheduler.close() + + assertEquals(200, clock.millis()) + } + } + } + + @Test + fun testStopped() { + runBlockingSimulation { + val scheduler = TimerScheduler(coroutineContext, clock) + + scheduler.close() + + assertThrows { + scheduler.startSingleTimer(1, 100) { + assertFalse(false) + } + } + } + } + + @Test + fun testNegativeDelay() { + runBlockingSimulation { + val scheduler = TimerScheduler(coroutineContext, clock) + + assertThrows { + scheduler.startSingleTimer(1, -1) { + assertFalse(false) + } + } + + scheduler.close() + } + } +} -- cgit v1.2.3 From 0711d4c1d6afb41ca31afbf8bd6253921d57eeb4 Mon Sep 17 00:00:00 2001 From: Fabian Mastenbroek Date: Fri, 18 Feb 2022 14:45:05 +0100 Subject: perf(common): Optimize TimerScheduler This change updates the TimerScheduler implementation to directly use the Delay object instead of running the timers inside a coroutine. Constructing the coroutine is more expensive, so we prefer running in a Runnable. --- .../org/opendc/common/util/TimerScheduler.kt | 239 ++++++++++----------- .../org/opendc/common/util/TimerSchedulerTest.kt | 46 ++-- 2 files changed, 134 insertions(+), 151 deletions(-) (limited to 'opendc-common/src') diff --git a/opendc-common/src/main/kotlin/org/opendc/common/util/TimerScheduler.kt b/opendc-common/src/main/kotlin/org/opendc/common/util/TimerScheduler.kt index 86314411..bec2c9f1 100644 --- a/opendc-common/src/main/kotlin/org/opendc/common/util/TimerScheduler.kt +++ b/opendc-common/src/main/kotlin/org/opendc/common/util/TimerScheduler.kt @@ -23,12 +23,10 @@ package org.opendc.common.util import kotlinx.coroutines.* -import kotlinx.coroutines.channels.Channel -import kotlinx.coroutines.selects.select import java.time.Clock import java.util.* +import kotlin.coroutines.ContinuationInterceptor import kotlin.coroutines.CoroutineContext -import kotlin.math.max /** * A TimerScheduler facilitates scheduled execution of future tasks. @@ -37,86 +35,83 @@ import kotlin.math.max * @param clock The clock to keep track of the time. */ @OptIn(ExperimentalCoroutinesApi::class) -public class TimerScheduler(context: CoroutineContext, private val clock: Clock) : AutoCloseable { +public class TimerScheduler(private val context: CoroutineContext, private val clock: Clock) { /** - * The scope in which the scheduler runs. + * The [Delay] instance that provides scheduled execution of [Runnable]s. */ - private val scope = CoroutineScope(context + Job()) + @OptIn(InternalCoroutinesApi::class) + private val delay = + requireNotNull(context[ContinuationInterceptor] as? Delay) { "Invalid CoroutineDispatcher: no delay implementation" } + + /** + * The stack of the invocations to occur in the future. + */ + private val invocations = ArrayDeque() /** * A priority queue containing the tasks to be scheduled in the future. */ - private val queue = PriorityQueue() + private val queue = PriorityQueue>() /** * A map that keeps track of the timers. */ - private val timers = mutableMapOf() + private val timers = mutableMapOf>() /** - * The channel to communicate with the scheduling job. + * Start a timer that will invoke the specified [block] after [delay]. + * + * Each timer has a key and if a new timer with same key is started the previous is cancelled. + * + * @param key The key of the timer to start. + * @param delay The delay before invoking the block. + * @param block The block to invoke. */ - private val channel = Channel(Channel.CONFLATED) + public fun startSingleTimer(key: T, delay: Long, block: () -> Unit) { + startSingleTimerTo(key, clock.millis() + delay, block) + } /** - * A flag to indicate that the scheduler is active. + * Start a timer that will invoke the specified [block] at [timestamp]. + * + * Each timer has a key and if a new timer with same key is started the previous is cancelled. + * + * @param key The key of the timer to start. + * @param timestamp The timestamp at which to invoke the block. + * @param block The block to invoke. */ - private var isActive = true - - init { - scope.launch { - val timers = timers - val queue = queue - val clock = clock - val job = requireNotNull(coroutineContext[Job]) - val exceptionHandler = coroutineContext[CoroutineExceptionHandler] - var next: Long? = channel.receive() - - while (true) { - next = select { - channel.onReceive { it } - - val delay = next?.let { max(0L, it - clock.millis()) } ?: return@select - - onTimeout(delay) { - while (queue.isNotEmpty() && job.isActive) { - val timer = queue.peek() - val timestamp = clock.millis() - - assert(timer.timestamp >= timestamp) { "Found task in the past" } - - if (timer.timestamp > timestamp && !timer.isCancelled) { - // Schedule a task for the next event to occur. - return@onTimeout timer.timestamp - } - - queue.poll() - - if (!timer.isCancelled) { - timers.remove(timer.key) - try { - timer() - } catch (e: Throwable) { - exceptionHandler?.handleException(coroutineContext, e) - } - } - } - - null - } - } + public fun startSingleTimerTo(key: T, timestamp: Long, block: () -> Unit) { + val now = clock.millis() + val queue = queue + val invocations = invocations + + require(timestamp >= now) { "Timestamp must be in the future" } + + timers.compute(key) { _, old -> + if (old != null && old.timestamp == timestamp) { + // Fast-path: timer for the same timestamp already exists + old.block = block + old + } else { + // Slow-path: cancel old timer and replace it with new timer + val timer = Timer(key, timestamp, block) + + old?.isCancelled = true + queue.add(timer) + trySchedule(now, invocations, timestamp) + + timer } } } /** - * Stop the scheduler. + * Check if a timer with a given key is active. + * + * @param key The key to check if active. + * @return `true` if the timer with the specified [key] is active, `false` otherwise. */ - override fun close() { - isActive = false - cancelAll() - scope.cancel() - } + public fun isTimerActive(key: T): Boolean = key in timers /** * Cancel a timer with a given key. @@ -127,28 +122,10 @@ public class TimerScheduler(context: CoroutineContext, private val clock: Clo * @param key The key of the timer to cancel. */ public fun cancel(key: T) { - if (!isActive) { - return - } - val timer = timers.remove(key) // Mark the timer as cancelled timer?.isCancelled = true - - // Optimization: check whether we are the head of the queue - val queue = queue - val channel = channel - val peek = queue.peek() - if (peek == timer) { - queue.poll() - - if (queue.isNotEmpty()) { - channel.trySend(peek.timestamp) - } else { - channel.trySend(null) - } - } } /** @@ -157,64 +134,60 @@ public class TimerScheduler(context: CoroutineContext, private val clock: Clo public fun cancelAll() { queue.clear() timers.clear() - } - /** - * Check if a timer with a given key is active. - * - * @param key The key to check if active. - * @return `true` if the timer with the specified [key] is active, `false` otherwise. - */ - public fun isTimerActive(key: T): Boolean = key in timers + // Cancel all pending invocations + for (invocation in invocations) { + invocation.cancel() + } + invocations.clear() + } /** - * Start a timer that will invoke the specified [block] after [delay]. - * - * Each timer has a key and if a new timer with same key is started the previous is cancelled. + * Try to schedule an engine invocation at the specified [target]. * - * @param key The key of the timer to start. - * @param delay The delay before invoking the block. - * @param block The block to invoke. + * @param now The current virtual timestamp. + * @param target The virtual timestamp at which the engine invocation should happen. + * @param scheduled The queue of scheduled invocations. */ - public fun startSingleTimer(key: T, delay: Long, block: () -> Unit) { - startSingleTimerTo(key, clock.millis() + delay, block) + private fun trySchedule(now: Long, scheduled: ArrayDeque, target: Long) { + val head = scheduled.peek() + + // Only schedule a new scheduler invocation in case the target is earlier than all other pending + // scheduler invocations + if (head == null || target < head.timestamp) { + @OptIn(InternalCoroutinesApi::class) + val handle = delay.invokeOnTimeout(target - now, ::doRunTimers, context) + scheduled.addFirst(Invocation(target, handle)) + } } /** - * Start a timer that will invoke the specified [block] at [timestamp]. - * - * Each timer has a key and if a new timer with same key is started the previous is cancelled. - * - * @param key The key of the timer to start. - * @param timestamp The timestamp at which to invoke the block. - * @param block The block to invoke. + * This method is invoked when the earliest timer expires. */ - public fun startSingleTimerTo(key: T, timestamp: Long, block: () -> Unit) { - val now = clock.millis() - val queue = queue - val channel = channel + private fun doRunTimers() { + val invocations = invocations + val invocation = checkNotNull(invocations.poll()) // Clear invocation from future invocation queue + val now = invocation.timestamp - require(timestamp >= now) { "Timestamp must be in the future" } - check(isActive) { "Timer is stopped" } + while (queue.isNotEmpty()) { + val timer = queue.peek() - timers.compute(key) { _, old -> - if (old != null && old.timestamp == timestamp) { - // Fast-path: timer for the same timestamp already exists - old - } else { - // Slow-path: cancel old timer and replace it with new timer - val timer = Timer(key, timestamp, block) + val timestamp = timer.timestamp + val isCancelled = timer.isCancelled - old?.isCancelled = true - queue.add(timer) + assert(timestamp >= now) { "Found task in the past" } - // Check if we need to push the interruption forward - // Note that we check by timer reference - if (queue.peek() === timer) { - channel.trySend(timer.timestamp) - } + if (timestamp > now && !isCancelled) { + // Schedule a task for the next event to occur. + trySchedule(now, invocations, timestamp) + break + } - timer + queue.poll() + + if (!isCancelled) { + timers.remove(timer.key) + timer() } } } @@ -222,7 +195,7 @@ public class TimerScheduler(context: CoroutineContext, private val clock: Clo /** * A task that is scheduled to run in the future. */ - private inner class Timer(val key: T, val timestamp: Long, val block: () -> Unit) : Comparable { + private class Timer(val key: T, val timestamp: Long, var block: () -> Unit) : Comparable> { /** * A flag to indicate that the task has been cancelled. */ @@ -234,6 +207,22 @@ public class TimerScheduler(context: CoroutineContext, private val clock: Clo */ operator fun invoke(): Unit = block() - override fun compareTo(other: Timer): Int = timestamp.compareTo(other.timestamp) + override fun compareTo(other: Timer): Int = timestamp.compareTo(other.timestamp) + } + + /** + * A future engine invocation. + * + * This class is used to keep track of the future engine invocations created using the [Delay] instance. In case + * the invocation is not needed anymore, it can be cancelled via [cancel]. + */ + private class Invocation( + @JvmField val timestamp: Long, + @JvmField val handle: DisposableHandle + ) { + /** + * Cancel the engine invocation. + */ + fun cancel() = handle.dispose() } } diff --git a/opendc-common/src/test/kotlin/org/opendc/common/util/TimerSchedulerTest.kt b/opendc-common/src/test/kotlin/org/opendc/common/util/TimerSchedulerTest.kt index 89b0cbe9..01f61f92 100644 --- a/opendc-common/src/test/kotlin/org/opendc/common/util/TimerSchedulerTest.kt +++ b/opendc-common/src/test/kotlin/org/opendc/common/util/TimerSchedulerTest.kt @@ -27,21 +27,30 @@ import org.junit.jupiter.api.Assertions.* import org.junit.jupiter.api.Test import org.junit.jupiter.api.assertThrows import org.opendc.simulator.core.runBlockingSimulation +import java.time.Clock +import kotlin.coroutines.EmptyCoroutineContext /** * A test suite for the [TimerScheduler] class. */ @OptIn(ExperimentalCoroutinesApi::class) internal class TimerSchedulerTest { + @Test + fun testEmptyContext() { + assertThrows { TimerScheduler(EmptyCoroutineContext, Clock.systemUTC()) } + } + @Test fun testBasicTimer() { runBlockingSimulation { val scheduler = TimerScheduler(coroutineContext, clock) scheduler.startSingleTimer(0, 1000) { - scheduler.close() assertEquals(1000, clock.millis()) } + + assertTrue(scheduler.isTimerActive(0)) + assertFalse(scheduler.isTimerActive(1)) } } @@ -51,7 +60,6 @@ internal class TimerSchedulerTest { val scheduler = TimerScheduler(coroutineContext, clock) scheduler.cancel(1) - scheduler.close() } } @@ -61,12 +69,11 @@ internal class TimerSchedulerTest { val scheduler = TimerScheduler(coroutineContext, clock) scheduler.startSingleTimer(0, 1000) { - assertFalse(false) + fail() } scheduler.startSingleTimer(1, 100) { scheduler.cancel(0) - scheduler.close() assertEquals(100, clock.millis()) } @@ -78,15 +85,9 @@ internal class TimerSchedulerTest { runBlockingSimulation { val scheduler = TimerScheduler(coroutineContext, clock) - scheduler.startSingleTimer(0, 1000) { - assertFalse(false) - } - - scheduler.startSingleTimer(1, 100) { - assertFalse(false) - } - - scheduler.close() + scheduler.startSingleTimer(0, 1000) { fail() } + scheduler.startSingleTimer(1, 100) { fail() } + scheduler.cancelAll() } } @@ -95,12 +96,9 @@ internal class TimerSchedulerTest { runBlockingSimulation { val scheduler = TimerScheduler(coroutineContext, clock) - scheduler.startSingleTimer(0, 1000) { - assertFalse(false) - } + scheduler.startSingleTimer(0, 1000) { fail() } scheduler.startSingleTimer(0, 200) { - scheduler.close() assertEquals(200, clock.millis()) } @@ -108,16 +106,14 @@ internal class TimerSchedulerTest { } @Test - fun testStopped() { + fun testOverrideBlock() { runBlockingSimulation { val scheduler = TimerScheduler(coroutineContext, clock) - scheduler.close() + scheduler.startSingleTimer(0, 1000) { fail() } - assertThrows { - scheduler.startSingleTimer(1, 100) { - assertFalse(false) - } + scheduler.startSingleTimer(0, 1000) { + assertEquals(1000, clock.millis()) } } } @@ -129,11 +125,9 @@ internal class TimerSchedulerTest { assertThrows { scheduler.startSingleTimer(1, -1) { - assertFalse(false) + fail() } } - - scheduler.close() } } } -- cgit v1.2.3