Problem: Round-Robin Scheduling

Let’s look at a classic queue problem: scheduling tasks on a single CPU.

Assume time starts at 0 and switching between tasks takes no time.

This is a real scheduling policy, and operating systems use it. Your computer looks like it runs many programs at once, but a CPU core runs one thing at a time. What happens is that the operating system gives each program a small slice of time, then moves on to the next one. It cycles through them fast enough that all of them seem to make progress together. Round-robin is the simplest version of this idea, and the “line” that tasks wait in is a queue.

Let’s trace a small example: burstTimes = [9, 2, 7] and quantum = 4. In the diagrams below, each entry shows a task and its remaining time, so T0:9 means task 0 with 9 units left. All three tasks start in line:

┌──────┬──────┬──────┐
│ T0:9 │ T1:2 │ T2:7 │
└──────┴──────┴──────┘
    ▲             ▲
  front         back

Task 0 runs from time 0 to time 4, using up 4 of its 9 units. It is not done (5 remain), so it goes to the back of the queue:

┌──────┬──────┬──────┐
│ T1:2 │ T2:7 │ T0:5 │
└──────┴──────┴──────┘
    ▲             ▲
  front         back

Task 1 runs from time 4 to time 6. It only needed 2 units, so it finishes at time 6, before using its full quantum. It leaves the queue and does not come back:

┌──────┬──────┐
│ T2:7 │ T0:5 │
└──────┴──────┘
    ▲      ▲
  front  back

The next two turns repeat the same pattern, so I will describe them without drawing the queue. Task 2 runs from time 6 to time 10, with 3 units remaining, and goes to the back. Task 0 runs again from time 10 to time 14, with 1 unit remaining, and goes to the back. Then task 2 runs from time 14 to time 17 and finishes. It needed only 3 of its 4 allowed units. Only task 0 is left:

┌──────┐
│ T0:1 │
└──────┘
    ▲
front, back

Task 0 runs from time 17 to time 18 and finishes. The queue is now empty:

(empty queue — every task has finished)

The answer is [18, 6, 17]. It shows the completion times of the tasks in order: task 0 finishes at time 18, task 1 finishes at time 6, and task 2 finishes at time 17.

Notice that task 1, which is second in the array and has the shortest burst time (2), finished first, even though task 0 was ahead of it in the queue. With round-robin, the short tasks do not have to wait for a long task to finish before they get to run.

The signature of the method in Java might look like this:

public static int[] completionTimes(int[] burstTimes, int quantum) {
  // Your implementation goes here
}

Let’s think of some special or edge cases as well:

  • If burstTimes is empty, there is nothing to schedule, and the result is an empty array.
  • If every burst time is at most quantum, no task is ever sent to the back. The tasks run one after another, in order.
  • A task that finishes exactly at the end of its quantum is done. It must not be sent to the back of the queue with 0 remaining units.