From 90e0d1d8c6ab94e020dd4cb4831a369b270a69b7 Mon Sep 17 00:00:00 2001 From: Fabian Mastenbroek Date: Wed, 20 Sep 2017 00:37:13 +0200 Subject: Implement standard task schedulers This change implements default tasks scheduling algorithms like FIFO or SRTF and adds them to to the standard library. --- .../nl/atlarge/opendc/experiment/Experiment.kt | 34 ------- .../atlarge/opendc/experiment/ExperimentRunner.kt | 39 -------- .../kotlin/nl/atlarge/opendc/experiment/Job.kt | 36 ------- .../nl/atlarge/opendc/experiment/Scheduler.kt | 42 -------- .../kotlin/nl/atlarge/opendc/experiment/Task.kt | 64 ------------- .../kotlin/nl/atlarge/opendc/experiment/User.kt | 40 -------- .../nl/atlarge/opendc/scheduler/FifoScheduler.kt | 101 ++++++++++++++++++++ .../nl/atlarge/opendc/scheduler/Scheduler.kt | 66 +++++++++++++ .../nl/atlarge/opendc/scheduler/SrtfScheduler.kt | 106 +++++++++++++++++++++ .../opendc/topology/container/Datacenter.kt | 3 + .../nl/atlarge/opendc/topology/container/Room.kt | 7 +- .../main/kotlin/nl/atlarge/opendc/workload/Job.kt | 36 +++++++ .../main/kotlin/nl/atlarge/opendc/workload/Task.kt | 71 ++++++++++++++ .../main/kotlin/nl/atlarge/opendc/workload/User.kt | 40 ++++++++ 14 files changed, 429 insertions(+), 256 deletions(-) delete mode 100644 opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/Experiment.kt delete mode 100644 opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/ExperimentRunner.kt delete mode 100644 opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/Job.kt delete mode 100644 opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/Scheduler.kt delete mode 100644 opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/Task.kt delete mode 100644 opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/User.kt create mode 100644 opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/scheduler/FifoScheduler.kt create mode 100644 opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/scheduler/Scheduler.kt create mode 100644 opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/scheduler/SrtfScheduler.kt create mode 100644 opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/workload/Job.kt create mode 100644 opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/workload/Task.kt create mode 100644 opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/workload/User.kt 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/experiment/Job.kt b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/Job.kt deleted file mode 100644 index 8c41735d..00000000 --- a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/Job.kt +++ /dev/null @@ -1,36 +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 job that is submitted to a cloud network, which consists of one or multiple [Task]s. - * - * @param id The unique identifier of this job. - * @param name The name of this job. - * @param owner The user to which the job belongs. - * @param tasks The tasks of which the job consists. - * @author Fabian Mastenbroek (f.s.mastenbroek@student.tudelft.nl) - */ -data class Job(val id: Int, val name: String, val owner: User, val tasks: Collection) diff --git a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/Scheduler.kt b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/Scheduler.kt deleted file mode 100644 index 28aa84e7..00000000 --- a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/Scheduler.kt +++ /dev/null @@ -1,42 +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 - -import nl.atlarge.opendc.topology.Entity - -/** - * 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> { - /** - * Schedule the given jobs for the given entity. - * - * @param entity The entity in the cloud network topology representing the entity. - * @param jobs The jobs that have been submitted to the cloud network. - */ - fun schedule(entity: E, jobs: Set) -} diff --git a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/Task.kt b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/Task.kt deleted file mode 100644 index ec2eb2fa..00000000 --- a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/Task.kt +++ /dev/null @@ -1,64 +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 task represents some computation that is part of a [Job]. - * - * @author Fabian Mastenbroek (f.s.mastenbroek@student.tudelft.nl) - */ -data class Task( - val id: Int, - val dependencies: Set, - val flops: Long -) { - /** - * The remaining amount of flops to compute. - */ - var remaining: Long = flops - private set - - /** - * A flag to indicate whether the task is finished. - */ - var finished: Boolean = false - private set - - /** - * Consume the given amount of flops of this task. - * - * @param flops The total amount of flops to consume. - */ - fun consume(flops: Long) { - if (finished) - return - if (remaining <= flops) { - finished = true - remaining = 0 - } else { - remaining -= flops - } - } -} diff --git a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/User.kt b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/User.kt deleted file mode 100644 index bb87a167..00000000 --- a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/experiment/User.kt +++ /dev/null @@ -1,40 +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 - -import nl.atlarge.opendc.topology.Topology - -/** - * A user of a cloud network that provides [Job]s for the simulation. - * - *

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. - * @param name The name of the user. - * @param view The view of the user on the topology. - * @author Fabian Mastenbroek (f.s.mastenbroek@student.tudelft.nl) - */ -data class User(val id: Int, val name: String, val view: Topology) 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 = HashSet() + + /** + * The queue of [Task]s that need to be scheduled. + */ + val queue: Queue = ArrayDeque() + + /** + * (Re)schedule the tasks submitted to the scheduler over the specified set of machines. + */ + override suspend fun > Context.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/scheduler/Scheduler.kt b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/scheduler/Scheduler.kt new file mode 100644 index 00000000..8c96341a --- /dev/null +++ b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/scheduler/Scheduler.kt @@ -0,0 +1,66 @@ +/* + * 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 + +/** + * 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 { + /** + * (Re)schedule the tasks submitted to the scheduler over the specified set of machines. + * + * This method should be invoked at some interval to allow the scheduler to reschedule existing tasks and schedule + * new tasks. + */ + suspend fun > Context.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 = HashSet() + + /** + * The set of [Task]s that need to be scheduled. + */ + val tasks: MutableSet = HashSet() + + /** + * (Re)schedule the tasks submitted to the scheduler over the specified set of machines. + */ + override suspend fun > Context.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 { + /** + * 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 +class Room : Entity { + /** + * The initial state of the entity. + */ + override val initialState = Unit +} diff --git a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/workload/Job.kt b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/workload/Job.kt new file mode 100644 index 00000000..6dbbf327 --- /dev/null +++ b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/workload/Job.kt @@ -0,0 +1,36 @@ +/* + * 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.workload + +/** + * A job that is submitted to a cloud network, which consists of one or multiple [Task]s. + * + * @param id The unique identifier of this job. + * @param name The name of this job. + * @param owner The user to which the job belongs. + * @param tasks The tasks of which the job consists. + * @author Fabian Mastenbroek (f.s.mastenbroek@student.tudelft.nl) + */ +data class Job(val id: Int, val name: String, val owner: User, val tasks: Collection) diff --git a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/workload/Task.kt b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/workload/Task.kt new file mode 100644 index 00000000..9a8c84e6 --- /dev/null +++ b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/workload/Task.kt @@ -0,0 +1,71 @@ +/* + * 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.workload + +/** + * A task represents some computation that is part of a [Job]. + * + * @author Fabian Mastenbroek (f.s.mastenbroek@student.tudelft.nl) + */ +data class Task( + val id: Int, + val dependencies: Set, + val flops: Long +) { + /** + * The remaining amount of flops to compute. + */ + var remaining: Long = flops + private set + + /** + * A flag to indicate whether the task is finished. + */ + var finished: Boolean = false + 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. + */ + fun consume(flops: Long) { + if (finished) + return + if (remaining <= flops) { + finished = true + remaining = 0 + } else { + remaining -= flops + } + } +} diff --git a/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/workload/User.kt b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/workload/User.kt new file mode 100644 index 00000000..d0e90851 --- /dev/null +++ b/opendc-stdlib/src/main/kotlin/nl/atlarge/opendc/workload/User.kt @@ -0,0 +1,40 @@ +/* + * 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.workload + +import nl.atlarge.opendc.topology.Topology + +/** + * A user of a cloud network that provides [Job]s for the simulation. + * + * 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. + * @param name The name of the user. + * @param view The view of the user on the topology. + * @author Fabian Mastenbroek (f.s.mastenbroek@student.tudelft.nl) + */ +data class User(val id: Int, val name: String, val view: Topology) -- cgit v1.2.3