Round Robin

Introduction

To solve this problem, we will introduce a new scheduling algorithm, classically referred to as Round-Robin (RR) scheduling“Analysis of a Time-Shared Processor” by Leonard Kleinrock. Naval Research Logistics Quarterly, 11-1, pages 59–73, March 1964. Maybe the first reference to the round-robin scheduling algorithm; certainly one of the first analyses of said approach to scheduling a time-shared system.. The basic idea is simple: instead of running jobs to completion, RR runs a job for a time slice (sometimes called a scheduling quantum) and then switches to the next job in the run queue. It repeatedly does so until the jobs are finished. For this reason, RR is sometimes called time-slicing. Note that the length of a time slice must be a multiple of the timer-interrupt period; thus if the timer interrupts every 10 milliseconds, the time slice could be 10, 20, or any other multiple of 10 ms.

To understand RR in more detail, let’s look at an example. Assume three jobs $A$, $B$, and $C$ arrive at the same time in the system, and that they each wish to run for 5 seconds. An SJF scheduler runs each job to completion before running another (as seen in the figure below).

In contrast, RR with a time-slice of 1 second would cycle through the jobs quickly. Check out the figure below: