Round Robin With a Fixed Quantum
One server runs n jobs under round robin with quantum q. Job i arrives at
time a[i] and needs d[i] units of work in total. Work can be split: a job
may run, be set aside, and run again later.
The discipline, with the one ordering question that matters settled explicitly:
there is a single queue. The server always runs the job at its front.
a job runs for min(q, work remaining). Then:
first, every job whose arrival time is <= the new clock joins the BACK
of the queue, in order of arrival and then of index
then, if the job still has work left, IT joins the back, behind those
arrivals
if it has no work left, it departs and its finish time is the new clock
if the queue is empty and jobs remain, the clock jumps to the next arrival.
Print one line per job in the order the jobs finish.
``` n = 3, q = 2, jobs (0,5) (0,3) (0,4)
queue 0 1 2. 0 runs 0-2 (3 left), 1 runs 2-4 (1 left), 2 runs 4-6 (2 left), 0 runs 6-8 (1 left), 1 runs 8-9 and FINISHES, 2 runs 9-11 and FINISHES, 0 runs 11-12 and FINISHES -> 1 9 2 11 0 12 ```
``` n = 2, q = 1, jobs (0,2) (1,1)
job 0 runs 0-1 and has 1 left. The clock is now 1, so job 1 arrives and joins the queue BEFORE job 0 is put back. Queue is 1 then 0. job 1 runs 1-2 and FINISHES, job 0 runs 2-3 and FINISHES. -> 1 2 0 3 ```
## What most people try first
A queue, a quantum, and the preempted job pushed back before the new arrivals
are admitted. It is one line different from the rule above and it gives a
different answer on the second worked example: it produces 0 2 then 1 3
instead. That is why the admission order is written into the statement rather
than left as an implementation detail.
The other common first attempt is to step the clock one unit at a time, which
is correct but spends a steps doing nothing when the first arrival is at
10^9. Advance the clock by a whole slice instead.
## Why the finishing order is well defined
At every moment the server is running at most one job, and a job departs only at the instant its remaining work hits zero. Two jobs can therefore never depart at the same moment, because the departure of the running job is the only event that can end a slice at that instant and only one job is running. So the output order is total and no tie-break is needed for it.
The queue itself needs a tie-break, and the statement gives it: simultaneous arrivals enter in index order, and a preempted job enters behind every arrival admitted at the same clock value.
## Termination
Each slice removes min(q, remaining) units of work from the total, which is at
least 1 because every duration is at least 1 and q is at least 1. The total
work is finite, so the number of slices is at most the sum of all durations and
the loop ends. When the queue empties with jobs still unarrived, the clock jump
makes progress because the next arrival time is strictly greater than the
current clock.
## Overflow
The sum of all durations is at most 10^6 and an arrival is at most 10^9, so
the clock never passes about 1.001 * 10^9. That fits in a signed 32 bit
integer, since INT_MAX is 2147483647. No test here overflows a 32 bit
build, and none is tagged as if it did. The reference solutions still use 64
bit times, which costs nothing and removes the question.
## Cost
O(total work / q + n) slices, each O(1) amortised, and O(n + slices)
memory if the queue is an array with a head index.