diff options
10 files changed, 257 insertions, 84 deletions
diff --git a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/Experiment.kt b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/Experiment.kt deleted file mode 100644 index a4f947c8..00000000 --- a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/Experiment.kt +++ /dev/null @@ -1,34 +0,0 @@ -/* - * MIT License - * - * Copyright (c) 2017 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 nl.atlarge.opendc.experiment - -/** - * A simulation of multiple simultaneous workloads running on top of a topology. - * - * @param id The unique identifier of the experiment. - * @param name The name of the experiment. - * @author Fabian Mastenbroek (f.s.mastenbroek@student.tudelft.nl) - */ -data class Experiment(val id: Int, val name: String) diff --git a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/ExperimentRunner.kt b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/ExperimentRunner.kt deleted file mode 100644 index e53c6e08..00000000 --- a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/ExperimentRunner.kt +++ /dev/null @@ -1,39 +0,0 @@ -/* - * MIT License - * - * Copyright (c) 2017 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 nl.atlarge.opendc.experiment - -/** - * An [ExperimentRunner] is responsible for executing an [Experiment]. - * - * @author Fabian Mastenbroek (f.s.mastenbroek@student.tudelft.nl) - */ -interface ExperimentRunner { - /** - * Run the given [Experiment] using this runner. - * - * @param experiment The experiment to run. - */ - fun run(experiment: Experiment) -} diff --git a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/scheduler/FifoScheduler.kt b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/scheduler/FifoScheduler.kt new file mode 100644 index 00000000..cc196a00 --- /dev/null +++ b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/scheduler/FifoScheduler.kt @@ -0,0 +1,101 @@ +/* + * MIT License + * + * Copyright (c) 2017 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 nl.atlarge.opendc.scheduler + +import nl.atlarge.opendc.kernel.Context +import nl.atlarge.opendc.topology.Entity +import nl.atlarge.opendc.topology.machine.Machine +import nl.atlarge.opendc.workload.Task +import java.util.* + +/** + * A [Scheduler] that distributes work according to the first-in-first-out principle. + * + * @author Fabian Mastenbroek (f.s.mastenbroek@student.tudelft.nl) + */ +class FifoScheduler : Scheduler { + /** + * The set of machines the scheduler knows of. + */ + val machines: MutableSet<Machine> = HashSet() + + /** + * The queue of [Task]s that need to be scheduled. + */ + val queue: Queue<Task> = ArrayDeque() + + /** + * (Re)schedule the tasks submitted to the scheduler over the specified set of machines. + */ + override suspend fun <E : Entity<*>> Context<E>.schedule() { + if (queue.isEmpty()) { + return + } + + machines + .filter { it.state.status == Machine.Status.IDLE } + .forEach { + while (queue.isNotEmpty()) { + val task = queue.poll() + + // TODO What to do with tasks that are not ready yet to be processed + if (!task.isReady()) { + submit(task) + continue + } + + it.send(task) + break + } + } + } + + /** + * Submit a [Task] to this scheduler. + * + * @param task The task to submit to the scheduler. + */ + override fun submit(task: Task) { + queue.add(task) + } + + /** + * Register a [Machine] to this scheduler. + * + * @param machine The machine to register. + */ + override fun register(machine: Machine) { + machines.add(machine) + } + + /** + * Deregister a [Machine] from this scheduler. + * + * @param machine The machine to deregister. + */ + override fun deregister(machine: Machine) { + machines.remove(machine) + } +} diff --git a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/Scheduler.kt b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/scheduler/Scheduler.kt index 28aa84e7..8c96341a 100644 --- a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/Scheduler.kt +++ b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/scheduler/Scheduler.kt @@ -22,21 +22,45 @@ * SOFTWARE. */ -package nl.atlarge.opendc.experiment +package nl.atlarge.opendc.scheduler +import nl.atlarge.opendc.kernel.Context import nl.atlarge.opendc.topology.Entity +import nl.atlarge.opendc.topology.machine.Machine +import nl.atlarge.opendc.workload.Task /** * A task scheduler that is coupled to an [Entity] in the topology of the cloud network. * * @author Fabian Mastenbroek (f.s.mastenbroek@student.tudelft.nl) */ -interface Scheduler<in E : Entity<*>> { +interface Scheduler { /** - * Schedule the given jobs for the given entity. + * (Re)schedule the tasks submitted to the scheduler over the specified set of machines. * - * @param entity The entity in the cloud network topology representing the entity. - * @param jobs The jobs that have been submitted to the cloud network. + * This method should be invoked at some interval to allow the scheduler to reschedule existing tasks and schedule + * new tasks. */ - fun schedule(entity: E, jobs: Set<Job>) + suspend fun <E: Entity<*>> Context<E>.schedule() + + /** + * Submit a [Task] to this scheduler. + * + * @param task The task to submit to the scheduler. + */ + fun submit(task: Task) + + /** + * Register a [Machine] to this scheduler. + * + * @param machine The machine to register. + */ + fun register(machine: Machine) + + /** + * Deregister a [Machine] from this scheduler. + * + * @param machine The machine to deregister. + */ + fun deregister(machine: Machine) } diff --git a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/scheduler/SrtfScheduler.kt b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/scheduler/SrtfScheduler.kt new file mode 100644 index 00000000..ce80ddc3 --- /dev/null +++ b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/scheduler/SrtfScheduler.kt @@ -0,0 +1,106 @@ +/* + * MIT License + * + * Copyright (c) 2017 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 nl.atlarge.opendc.scheduler + +import nl.atlarge.opendc.kernel.Context +import nl.atlarge.opendc.topology.Entity +import nl.atlarge.opendc.topology.machine.Machine +import nl.atlarge.opendc.workload.Task +import java.util.* + +/** + * A [Scheduler] that distributes work according to the shortest job first policy. + * + * @author Fabian Mastenbroek (f.s.mastenbroek@student.tudelft.nl) + */ +class SrtfScheduler : Scheduler { + /** + * The set of machines the scheduler knows of. + */ + val machines: MutableSet<Machine> = HashSet() + + /** + * The set of [Task]s that need to be scheduled. + */ + val tasks: MutableSet<Task> = HashSet() + + /** + * (Re)schedule the tasks submitted to the scheduler over the specified set of machines. + */ + override suspend fun <E : Entity<*>> Context<E>.schedule() { + if (tasks.isEmpty()) { + return + } + + val iterator = tasks.sortedBy { it.remaining }.iterator() + + machines + .filter { it.state.status == Machine.Status.IDLE } + .forEach { + while (iterator.hasNext()) { + val task = iterator.next() + + // TODO What to do with tasks that are not ready yet to be processed + if (!task.isReady()) { + submit(task) + continue + } else if (task.finished) { + tasks.remove(task) + continue + } + + it.send(task) + break + } + } + } + + /** + * Submit a [Task] to this scheduler. + * + * @param task The task to submit to the scheduler. + */ + override fun submit(task: Task) { + tasks.add(task) + } + + /** + * Register a [Machine] to this scheduler. + * + * @param machine The machine to register. + */ + override fun register(machine: Machine) { + machines.add(machine) + } + + /** + * Deregister a [Machine] from this scheduler. + * + * @param machine The machine to deregister. + */ + override fun deregister(machine: Machine) { + machines.remove(machine) + } +} diff --git a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/topology/container/Datacenter.kt b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/topology/container/Datacenter.kt index b995732a..4136c03c 100644 --- a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/topology/container/Datacenter.kt +++ b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/topology/container/Datacenter.kt @@ -32,5 +32,8 @@ import nl.atlarge.opendc.topology.Entity * @author Fabian Mastenbroek (f.s.mastenbroek@student.tudelft.nl) */ class Datacenter : Entity<Unit> { + /** + * The initial state of the entity. + */ override val initialState = Unit } diff --git a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/topology/container/Room.kt b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/topology/container/Room.kt index 3b338899..109a5629 100644 --- a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/topology/container/Room.kt +++ b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/topology/container/Room.kt @@ -31,4 +31,9 @@ import nl.atlarge.opendc.topology.Entity * * @author Fabian Mastenbroek (f.s.mastenbroek@student.tudelft.nl) */ -interface Room : Entity<Unit> +class Room : Entity<Unit> { + /** + * The initial state of the entity. + */ + override val initialState = Unit +} diff --git a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/Job.kt b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/workload/Job.kt index 8c41735d..6dbbf327 100644 --- a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/Job.kt +++ b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/workload/Job.kt @@ -22,7 +22,7 @@ * SOFTWARE. */ -package nl.atlarge.opendc.experiment +package nl.atlarge.opendc.workload /** * A job that is submitted to a cloud network, which consists of one or multiple [Task]s. diff --git a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/Task.kt b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/workload/Task.kt index ec2eb2fa..9a8c84e6 100644 --- a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/Task.kt +++ b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/workload/Task.kt @@ -22,7 +22,7 @@ * SOFTWARE. */ -package nl.atlarge.opendc.experiment +package nl.atlarge.opendc.workload /** * A task represents some computation that is part of a [Job]. @@ -47,6 +47,13 @@ data class Task( private set /** + * Determine whether the task is ready to be processed. + * + * @return `true` if the task is ready to be processed, `false` otherwise. + */ + fun isReady() = dependencies.all { it.finished } + + /** * Consume the given amount of flops of this task. * * @param flops The total amount of flops to consume. diff --git a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/User.kt b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/workload/User.kt index bb87a167..d0e90851 100644 --- a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/User.kt +++ b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/workload/User.kt @@ -22,14 +22,14 @@ * SOFTWARE. */ -package nl.atlarge.opendc.experiment +package nl.atlarge.opendc.workload import nl.atlarge.opendc.topology.Topology /** * A user of a cloud network that provides [Job]s for the simulation. * - * <p>Each [User] in a simulation has its own logical view of the cloud network which is used to route its jobs in the + * Each [User] in a simulation has its own logical view of the cloud network which is used to route its jobs in the * physical network. * * @param id The unique identifier of the user. |