Chapter 14 of 38

Round Robin Scheduling

Imagine five friends sharing one game controller. If the first person plays until they finish the whole game, the others wait for hours. So they agree on a rule: everyone plays for 10 minutes, then passes the controller to the next person, and the line keeps going round and round. Nobody waits too long, and everyone makes progress.

That rule is Round Robin (RR) scheduling, and it is the heart of every time-sharing operating system.

Round Robin scheduling gives each ready process the CPU for at most one fixed time slice, called the time quantum. If the process has not finished when its quantum expires, it is preempted and placed at the back of the ready queue.

RR is basically FCFS plus a timer. It fixes FCFS's convoy effect without needing to know burst times (which SJF needs) and without letting anyone starve (which Priority Scheduling allows). In exchange, it pays for many more context switches, and the choice of quantum becomes the most important design decision.


How Round Robin Works

The ready queue is a circular FIFO queue. The scheduler repeats these steps:

  1. Take the process at the head of the ready queue.

  2. Set a timer to interrupt after one quantum q, and dispatch the process.

  3. One of two things happens:

    • The burst finishes (or the process blocks for I/O) before the quantum ends. The process leaves the CPU voluntarily and the scheduler picks the next one immediately. The unused part of the quantum is not carried forward.

    • The timer interrupt fires. The OS saves the process's state, puts it at the tail of the ready queue, and picks the next one.

          ┌──────────────── preempted (quantum expired) ───────────────┐
          ↓                                                            │
New → [ tail ... ready queue ... head ] → CPU (runs ≤ q) ──────────────┘
                                             │
                                             └→ finished / blocked for I/O

RR is preemptive, but the preemption comes from the clock, not from a "better" process arriving.

An Important Tie Rule

What if a new process arrives at exactly the same moment that the running process's quantum expires? Who goes into the queue first?

Standard convention (used in this chapter and in most exam solutions): newly arrived processes are added to the ready queue first, and then the preempted process is added behind them.

The reasoning is that the new process was "waiting at the door" before the running one was sent back. Some textbooks use the opposite order. If a question states a rule, follow it; if not, use this one and write it down in your answer.


Example 1: All Processes Arrive at Time 0

Quantum q = 3.

Process

Arrival Time

Burst Time

P1

0

10

P2

0

4

P3

0

7

Step-by-step trace

Time  Runs  For  Remaining after    Ready queue after
----  ----  ---  ---------------    -----------------
 0    P1    3    P1 = 7             P2, P3, P1
 3    P2    3    P2 = 1             P3, P1, P2
 6    P3    3    P3 = 4             P1, P2, P3
 9    P1    3    P1 = 4             P2, P3, P1
12    P2    1    P2 = 0 (done)      P3, P1
13    P3    3    P3 = 1             P1, P3
16    P1    3    P1 = 1             P3, P1
19    P3    1    P3 = 0 (done)      P1
20    P1    1    P1 = 0 (done)      -
|  P1  |  P2  |  P3  |  P1  |  P2  |  P3  |  P1  |  P3  |  P1  |
0      3      6      9      12     13     16     19     20     21

Process

BT

CT

TAT

WT

RT

P1

10

21

21

11

0

P2

4

13

13

9

3

P3

7

20

20

13

6

Average TAT = 54 / 3 = 18
Average WT  = 33 / 3 = 11
Average RT  = 9 / 3  = 3

Notice the pattern of response times: 0, 3, 6. With n processes, everyone gets a first turn within (n - 1) × q. That predictable, quick first response is what makes RR feel "interactive".

Also notice that P2 needed only 1 unit in its second turn at time 12, so it gave up the CPU early and P3 started at 13, not 15.


Example 2: Different Arrival Times

Quantum q = 2.

Process

Arrival Time

Burst Time

P1

0

5

P2

1

3

P3

2

1

P4

3

2

P5

4

3

The secret to solving RR correctly is to write down the ready queue after every step. Most mistakes come from putting processes into the queue in the wrong order.

Step-by-step trace

t = 0  : queue = [P1]
         P1 runs 0-2 (rem 3)
         arrivals during/at end: P2 (1), P3 (2)  → queue = [P2, P3]
         then P1 goes to the tail                 → queue = [P2, P3, P1]

t = 2  : P2 runs 2-4 (rem 1)
         arrivals: P4 (3), P5 (4)                 → queue = [P3, P1, P4, P5]
         then P2 goes to the tail                 → queue = [P3, P1, P4, P5, P2]
         (P5 arrived exactly at 4, so it goes BEFORE P2: our tie rule)

t = 4  : P3 runs 4-5, needs only 1 → done       → queue = [P1, P4, P5, P2]

t = 5  : P1 runs 5-7 (rem 1)                    → queue = [P4, P5, P2, P1]

t = 7  : P4 runs 7-9 (rem 0) → done             → queue = [P5, P2, P1]

t = 9  : P5 runs 9-11 (rem 1)                   → queue = [P2, P1, P5]

t = 11 : P2 runs 11-12 → done                    → queue = [P1, P5]

t = 12 : P1 runs 12-13 → done                    → queue = [P5]

t = 13 : P5 runs 13-14 → done                    → queue = []
|  P1  |  P2  |  P3  |  P1  |  P4  |  P5  |  P2  |  P1  |  P5  |
0      2      4      5      7      9      11     12     13     14

Process

AT

BT

CT

TAT

WT

RT

P1

0

5

13

13

8

0

P2

1

3

12

11

8

1

P3

2

1

5

3

2

2

P4

3

2

9

6

4

4

P5

4

3

14

10

7

5

Average TAT = 43 / 5 = 8.6
Average WT  = 29 / 5 = 5.8
Average RT  = 12 / 5 = 2.4
Context switches between processes = 8

What If We Used the Opposite Tie Rule?

If the preempted process were re-queued before processes arriving at that same instant, P1 would go ahead of P3 at time 2, and P2 ahead of P5 at time 4. The schedule becomes:

|  P1  |  P2  |  P1  |  P3  |  P4  |  P2  |  P5  |  P1  |  P5  |
0      2      4      6      7      9      10     12     13     14

The individual times change (for example, P3 now finishes at 7 instead of 5, and the average response time becomes 15 / 5 = 3.0). In this particular case the average waiting time happens to stay 5.8, but in general it can change too. This is why stating your convention matters.


Round Robin in C

This program simulates RR with a circular queue, using the tie rule above (admit new arrivals first, then re-queue the preempted process). It uses the data from Example 2.

#include <stdio.h>

#define N 5
#define QUANTUM 2

/* A simple circular FIFO queue of process indexes. */
static int queue[N + 1], head = 0, tail = 0;   /* holds at most N items */
static void enqueue(int x) { queue[tail] = x; tail = (tail + 1) % (N + 1); }
static int  dequeue(void)  { int x = queue[head]; head = (head + 1) % (N + 1); return x; }
static int  empty(void)    { return head == tail; }

int main(void) {
    const char *name[N] = {"P1", "P2", "P3", "P4", "P5"};
    int at[N] = {0, 1, 2, 3, 4};     /* must be sorted by arrival */
    int bt[N] = {5, 3, 1, 2, 3};
    int rem[N], ct[N], first[N];

    for (int i = 0; i < N; i++) { rem[i] = bt[i]; first[i] = -1; }

    int time = 0, next = 0, done = 0;

    /* Admit every process that has arrived by 'time'. */
    #define ADMIT() while (next < N && at[next] <= time) enqueue(next++)

    ADMIT();
    printf("Gantt:");
    while (done < N) {
        if (empty()) {                       /* CPU idle */
            printf(" [%d]IDLE", time);
            time = at[next];
            ADMIT();
            continue;
        }
        int p = dequeue();
        int run = rem[p] < QUANTUM ? rem[p] : QUANTUM;

        printf(" [%d]%s", time, name[p]);
        if (first[p] == -1) first[p] = time;
        time += run;
        rem[p] -= run;

        ADMIT();              /* arrivals first ...                  */
        if (rem[p] > 0)
            enqueue(p);       /* ... then the preempted process      */
        else {
            ct[p] = time;
            done++;
        }
    }
    printf(" [%d]\n\n", time);

    double s_tat = 0, s_wt = 0, s_rt = 0;
    printf("Proc  AT  BT  CT  TAT  WT  RT\n");
    for (int i = 0; i < N; i++) {
        int tat = ct[i] - at[i], wt = tat - bt[i], rt = first[i] - at[i];
        s_tat += tat; s_wt += wt; s_rt += rt;
        printf("%-4s %3d %3d %3d %4d %3d %3d\n",
               name[i], at[i], bt[i], ct[i], tat, wt, rt);
    }
    printf("\nAverage TAT = %.2f\nAverage WT  = %.2f\nAverage RT  = %.2f\n",
           s_tat / N, s_wt / N, s_rt / N);
    return 0;
}

Output:

Gantt: [0]P1 [2]P2 [4]P3 [5]P1 [7]P4 [9]P5 [11]P2 [12]P1 [13]P5 [14]

Proc  AT  BT  CT  TAT  WT  RT
P1     0   5  13   13   8   0
P2     1   3  12   11   8   1
P3     2   1   5    3   2   2
P4     3   2   9    6   4   4
P5     4   3  14   10   7   5

Average TAT = 8.60
Average WT  = 5.80
Average RT  = 2.40

The two lines that implement the tie rule are ADMIT(); followed by enqueue(p);. Swap them and you get the opposite convention. The queue array has N + 1 slots because a circular queue that uses head == tail for "empty" must keep one slot unused.


Choosing the Time Quantum

The quantum controls everything about RR's behaviour. There are two extremes:

Quantum

Behaviour

Very large (larger than every burst)

No process is ever preempted by the timer. RR becomes FCFS, with its convoy effect.

Very small (close to the context-switch time)

Each of n processes seems to run on its own CPU at 1/n speed (called processor sharing), but most CPU time is wasted on context switches.

Same Processes, Different Quanta

Here is Example 2 solved with several quanta (switch cost ignored):

q

Avg TAT

Avg WT

Avg RT

Context switches

1

8.0

5.2

1.2

13

2

8.6

5.8

2.4

8

3

7.4

4.6

3.4

5

4

8.4

5.6

3.8

5

5 or more

7.4

4.6

4.6

4 (same as FCFS)

Three lessons from this table:

  • Smaller quantum → better response time (1.2 at q = 1 vs 4.6 at q = 5).

  • Smaller quantum → many more context switches (13 vs 4).

  • Turnaround time does not improve steadily as the quantum grows. It went 8.0, 8.6, 7.4, 8.4, 7.4. It depends on how bursts happen to line up with the quantum.

The same effect appears in Example 1 (P1 = 10, P2 = 4, P3 = 7): the average TAT is 16.67 at q = 2, 18.0 at q = 3, and 16.0 at q = 4. Bigger is not always better, and smaller is not always better.

The Rule of Thumb

Choose the quantum so that most CPU bursts (a common guideline is about 80%) finish within one quantum, while the quantum stays much larger than the context-switch time.

Then short interactive bursts finish in a single turn (fast response), while only long CPU-bound bursts get cycled. Typical time slices in real systems are in the range of a few milliseconds to around 100 milliseconds, while a context switch costs on the order of microseconds.

The Cost of Context Switches

If every switch costs s time units and each quantum is q, then in the worst case (every process uses its full quantum):

CPU efficiency = q / (q + s)

q = 4 ms,  s = 1 ms   → 4 / 5     = 80%   (20% wasted!)
q = 20 ms, s = 1 ms   → 20 / 21   ≈ 95.2%
q = 100 ms, s = 1 ms  → 100 / 101 ≈ 99.0%

Let's redo Example 2 (q = 2) with a context switch of 1 unit between different processes:

| P1 | CS | P2 | CS | P3 | CS | P1 | CS | P4 | CS | P5 | CS | P2 | CS | P1 | CS | P5 |
0    2    3    5    6    7    8    10   11   13   14   16   17   18   19   20   21   22
CT:  P1 = 20, P2 = 18, P3 = 7, P4 = 13, P5 = 22
Average TAT = 70 / 5 = 14.0     (was 8.6 without overhead)
Average WT  = 56 / 5 = 11.2     (was 5.8)
CPU utilization = 14 / 22 ≈ 63.64%

Eight switches added 8 units of pure overhead to 14 units of real work. That is why the quantum must be large compared to the switch time.

A Guaranteed Bound on Waiting

With n processes in the ready queue and quantum q, a process that has just been preempted waits at most

(n - 1) × q

before it runs again (plus switch overhead). For example, with 5 processes and q = 20 ms, no process waits more than 80 ms for its next turn. This bound is why RR has no starvation, and why users feel the system responding to them even when many programs are running.


Round Robin in Real Systems

  • Linux SCHED_RR: a real-time policy that uses preemptive priority between levels and Round Robin among threads of the same priority. Its default time slice is visible in /proc/sys/kernel/sched_rr_timeslice_ms, which shows 100 (milliseconds) on a stock Ubuntu WSL2 kernel. A program can query it with sched_rr_get_interval().

  • Normal Linux processes do not use a fixed quantum. The fair scheduler (EEVDF since Linux 6.6, CFS before it) divides CPU time in proportion to weights derived from nice values. You can think of it as a weighted, smarter descendant of Round Robin.

  • Multilevel feedback queues (next chapter) use RR inside each level, with different quanta per level.

  • Outside the CPU: RR is used to share network links between flows, to distribute requests across servers in load balancers ("round-robin DNS"), and in tournament scheduling.


Advantages and Disadvantages

Advantages

Disadvantages

Fair: every process gets an equal share of CPU turns

Many context switches, especially with a small quantum

No starvation; waiting bounded by (n - 1) × q

Performance depends heavily on the quantum

Good response time, ideal for time-sharing and interactive systems

Average turnaround and waiting time often worse than SJF/SRTF

Does not need burst-time knowledge

No notion of priority or importance in its pure form

Simple to implement with a circular queue and a timer

If all bursts are equal and long, everyone finishes late (all processes finish near the end)

The last point deserves a quick example: three processes of 10 units each with q = 1 finish at times 28, 29 and 30 (average TAT 29). FCFS would finish them at 10, 20 and 30 (average 20). When jobs are similar and long, RR's fairness actually hurts turnaround.


Common Mistakes

  • Adding the preempted process before new arrivals when the question expects the standard rule (or vice versa). Always state the rule you use.

  • Forgetting processes that arrived during a quantum. At t = 4 in Example 2, P4 arrived at 3 while P2 was running. It must already be in the queue.

  • Charging a full quantum when the burst is shorter. A process with 1 unit left uses 1 unit, and the next process starts immediately.

  • Putting a finished process back in the queue. Once its remaining time is 0, it leaves for good.

  • Using RT as WT. In RR, a process waits many times. Use WT = TAT - BT.

  • Thinking a smaller quantum always gives better turnaround. It improves response time, but turnaround can go up or down.


Interview Questions

What happens in Round Robin when the quantum is very large?

No process is preempted by the timer, so RR behaves exactly like FCFS.

What happens when the quantum is very small?

Response time improves, but context-switch overhead dominates and useful CPU work drops sharply.

Can Round Robin cause starvation?

No. Every process gets a turn within (n - 1) × q time units after being preempted.

How should the time quantum be chosen?

Large compared to the context-switch time, and long enough that most CPU bursts (roughly 80%) complete within one quantum.

Why is RR good for time-sharing systems?

It gives every user frequent, predictable turns on the CPU, so the system feels responsive even with many active programs.

Is RR preemptive? What triggers preemption?

Yes. Preemption is triggered by the timer interrupt when the quantum expires, not by the arrival of a higher-priority or shorter process.

With 4 processes and q = 50 ms, what is the longest a process waits between turns?

(4 - 1) × 50 = 150 ms, ignoring context-switch time.


The Main Idea

Round Robin lets every ready process run for at most one time quantum, then sends it to the back of the queue.

Take head of the ready queue
      ↓
Run for min(quantum, remaining time)
      ↓
Add new arrivals to the queue
      ↓
Not finished? → back to the tail
      ↓
Repeat

Key facts:

Type         → Preemptive (timer-based)
Starvation   → No, wait ≤ (n - 1) × q
q very large → becomes FCFS
q very small → processor sharing, heavy switch overhead
Efficiency   → q / (q + s)
Good for     → Time-sharing, interactive systems

Round Robin trades a little efficiency for a lot of fairness and responsiveness, and the quantum decides how good that trade is.

RR treats every process the same, and Priority Scheduling treats them very differently. In the next chapter, Multilevel Queue & Feedback Queue Scheduling, we combine the two: several queues with different priorities, Round Robin inside each, and processes that move between queues based on how they behave.