Simulate Feedback Scheduling on a Uniprocessor
Alternatively, exploiting university course content for code golf reputation
Like round robin scheduling, Feedback Scheduling is a way to schedule ready processes in an operating system. And like round robin scheduling, it runs processes for a certain amount of time (quantum), interrupted after that time (if not yet finished), and then added back to a ready queue for another round.
However, the key difference is that as a process repeatedly goes through the ready queue, it gets a longer quantum1. This can be compared to having multiple ready queues and processors daisy-chained as so:
In the diagram, the first ready queue sends its processes to the first process to run for some time \$k\$. If the process finishes in this time, it is released. Otherwise, it is sent to the second ready queue, which has a quantum of \$2k\$.2 The second ready queue sends its processes to the second processor to run for some time \$2k\$. Once again, if the process finishes in this time, the process is released. Otherwise, it is sent to the third ready queue. This generalises all the way down to the nth ready queue, which has interrupted processes sent back to itself. That is, it gets readded to the nth ready queue in a loop.
As this is a uniprocessor simulation, there's only one processor, so the concept of daisy-chaining multiple processors doesn't really work3. However, this can be simulated by using process priorities. Indeed, a higher priority process would be in one of the higher ready queues (closer to the first ready queue). A lower priority process would be in one of the lower ready queues (closer to the nth ready queue). A process with priority \$n\$ will be executed for \$n k\$, where \$k\$ is the quantum.
The priority only changes how long a process is executed. It does not change the selection order of the ready queue - that's still a first-come first-serve selection method. Processes arrive with a priority of
1, so as to not have any processes running for 0 time units.
Given a list of
[int, int] (both > 0), as well as a base quantum, and a maximum priority, return a list of
int representing the order that processes were executed. Assume that all the processes arrive at the same time.
The list of
[int, int] represents a (simplified) list of processes. The two ints are the process id and service time (the time the process needs to fully run). (The priority is to be handled by the program, as all processes start with priority 1).
[[1, 5], [2, 10], [3, 3], [4, 12]]
Represents the following processes
The base quantum is how long each priority runs, before priority multiplication. The maximum priority represents the priority at which processes loop back into the same quantum.
Using the above process list (
[[1, 5], [2, 10], [3, 3], [4, 12]]), a quantum of
4, and a maximum priority of
4, the process execution order will be:
TODO: Worked example at a time that isn't 11:39pm
- Input can be taken as
list[list[int, int]], int, int,
list[int], list[int], int, int, or some other reasonable input method.
- The processes, quantum and maximum priority can be taken in any order.
- For example:
or any other combination.
- Output can be
str (joined on newlines, or spaces, or any constant delimiter) or some other reasonable output method.
- There will always be at least one process.
- The process ids list will always be a permutation of the range
[1, number of processes].
- The process ids can be 0-indexed if you want it to be for some reason. Using 0-indexing, the ids list will always be a permutation of the range
[0, number of processes].
- The order of the process ids list is important - processes are executed in the order they arrive (in a first come first serve manner). That is how the ready queue in an actual FB simulation works after all (FCFS selection strategy, with pre-emption on time quantums).
This is code-golf, so the shortest answer in each language wins.
- Does the description I've provided make sense? It's not verbatim how FB scheduling works, but it's a simplification to make code golfing it not as tedious as it could be.
- Because I don't have a worked example/test cases yet, some parts might not make sense.
1 Some variants of Feedback Scheduling use constant time slices for all quantums. However, this challenge will assume a variable time quantum, so as to provide fairness to longer processes.
2 The factor of 2 is arbitrary. It could be any integer > 1.
3 At least, not with the simplification provided for this challenge. In practice, it might still work.