RR scheduling, step by step

0 / 10

Round Robin (RR) Scheduling

Processes take turns running a little at a time, in the order they lined up in the ready queue. There is a fixed amount of time a process can run at once, called the time quantum (time slice). When that time is up, the OS stops the process even if it is not finished (preemption), and it goes to the back of the line to wait again.

At a bank: the counter serves each customer for only 2 minutes at a time. A customer who isn't done within 2 minutes goes to the back of the line and waits again.

1 / 10

0ms: P1 starts running

P1 is the only one in line, so it runs right away. But it can run for only 2ms at a time, so at 2ms it is stopped even if it isn't finished.

2 / 10

2ms: P1 uses up its 2ms quantum and goes to the back of the line

P1 ran for 2ms and has 3ms left. Meanwhile, P2 joined the line at 1ms and P3 at 2ms. P2, at the front, runs, and P1 lines up behind P3. Since P3 and P1 both joined the line at 2ms, the newly arrived P3 goes in front.

3 / 10

4ms: P2 also uses up its quantum and goes to the back of the line

P2 is stopped with 1ms left. P4, which arrived at 3ms, is already in line, so P2 lines up behind it. Now it is P3's turn at the front.

4 / 10

6ms: P3 is stopped and P1 runs again

P3 goes to the back of the line with 6ms left. P1 continues from where it stopped earlier.

5 / 10

8ms: P1 is stopped and P4 runs

P1 has 1ms left. P4, which arrived at 3ms, runs for the first time only at 8ms.

6 / 10

10ms: P4 finishes

P4's run time is 2ms, so it finished in one turn. A finished process does not go back to the line. Next is P2.

7 / 10

11ms: P2 finishes

P2 ran only its remaining 1ms and finished. When a process finishes, the next process (P3) starts right away, even if the quantum isn't used up.

8 / 10

13ms: P3 is stopped and P1 runs

P3 lines up again with 4ms left.

9 / 10

14ms: P1 finishes and P3 runs

Now only P3 is in line. Even when its quantum runs out at 16ms, no process is waiting, so P3 keeps running.

10 / 10

18ms: all done

Waiting times are P1 9ms, P2 7ms, P3 8ms and P4 5ms, an average of 7.25ms. That is longer than FCFS (average 5.75ms), but every process had started running by 8ms. In FCFS, P4 first ran only at 16ms. If the quantum is too large, RR is no different from FCFS; if it is too small, switching processes (context switches) happens too often.

Figure showing RR scheduling: four processes take turns running 2ms at a time, a process that has not finished after using its 2ms goes back to the end of the ready queue, and how long each process waited

CPU Scheduling at a glance

Figure showing RR scheduling: four processes take turns running 2ms at a time, a process that has not finished after using its 2ms goes back to the end of the ready queue, and how long each process waited