This is one of the oldest, simplest, and widely used algorithm. It is a preemptive algorithm, primarily used in time-sharing systems where the primary requirement is to provide reasonably good response times and in general to share the system fairly among all system users. RR scheduling is similar to FCFS scheduling, but preemption is added to switch between processes. Here, the CPU time is divided into time slices ( A small unit of time ), each process is allocated a small time slice while it is running. A time quantum is generally from 10 to 100 ms. In this algorithm the CPU switches between the processes. When the time slice is expired, the CPU switches to another job.
No process can run for more than one time slice when there are other processes waiting in the ready queue. If a process needs more CPU time to complete after exhausting one time slice, it goes to the end of the ready queue to await the next allocation.
If the process has a CPU burst time of less than one-time slice then the process releases the CPU voluntarily. The scheduler will then proceed to the next process in the ready queue.
Consider the three processes P1, P2, P3 which require the following CPU time.
Process CPU time
Assume that the time slice is of 5ms. Then the Gantt chart is as follows.
P1 gets the first 5ms, still, it requires another 20ms, it is preempted after the first time slice and the CPU is given to the next process i.e. P2. Since P2 just needs 5ms, it terminates as the time slice expires. The CPU is then given to the next process P3. once each process has received a one-time slice, the CPU is then returned to P1 for an additional time slice.
Waiting time for P1 = 0 + 10 =10
Waiting time for P2 = 5
Waiting time for P3 = 10
Avg. waiting time = 10 + 5 +10/3 = 25/3 = 8.33ms.
Turn around time for P1 = 35 – 0 =35
Turn around time for P2 = 10 – 0 = 10
Turn around time for P3 = 15 – 0 = 15
Avg. turn around time = 60/3 = 20ms.
Therefore as we have seen, compared to the FCFS algorithm, the avg. waiting time and turn around time is comparatively less since the time quantum is involved. The performance of the RR scheduling depends very much on the time quantum.
The time slice must be very moderate, neither small nor too frequent, or too large since if the time quantum is small, the context switch required will be much more, whereas if the time quantum is too large, RR becomes an FCFS scheduling algorithm.