Round Robin Scheduling

Round Robin (RR) scheduling algorithm is designed especially for time sharing systems. It is similar to FCFS scheduling but preemption is added to enable the system to switch between processes. A small unit of time called time quantum or time slice is defined. A time quantum is generally from 10 to 100 milliseconds in length. The ready queue is treated as a circular queue. The CPU scheduler goes around the ready queue, allocating the CPU to each process for a time interval of up to 1-time quantum.

The process may have a CPU burst less than 1-time quantum. In this case, the process itself will release the CPU voluntarily. The scheduler will then proceed to the next process in the ready queue. Otherwise, if the CPU burst of the currently running process is longer than 1-time quantum, the timer will go off and will cause an interrupt to the OS. A context switch will be executed, and the process will be put at the tail of the ready queue. The CPU scheduler will then select the next process in the ready queue.

The average waiting time under the RR policy is often long.

Q1. Consider the following set of processes that arrive at time 0, with the length of the CPU burst given in milliseconds.

Example 1: Quantum time = 4

The Gantt chart is:

The process P1 gets the first 4 milliseconds. Since it requires another 20 milliseconds, it is preempted after the first-time quantum, and the CPU is given to the next process in the queue, process P2. Process P2 does not need 4 milliseconds, so it quits before its time quantum expires. The CPU is then given to the next process, process P3. Once each process has received 1-time quantum time, the CPU is returned to the process for an additional time quantum.

• Average time: = (P1 + P2 + P3) / 3

=    [ (10 – 4) + 4 + 7] / 3

=    17 / 3

=    5.66 milliseconds

Example 2: quantum = 20

Gantt chart

Average Waiting Time:

= (P1 + P2 + P3 + P4) / 4

= [{0 + (77 – 20) + (121 – 97)} + 20 + {37 + (97-57) + (134 – 117)} + {57 + (117 – 77)}] / 4

= (81+20+94+97) / 4

= 73 milliseconds

If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units. Each process must wait no longer than (n – 1) x q time units until its next time quantum. For example, there are 5 processes and a time quantum of 20 milliseconds, each process will get up to 20 milliseconds every 100 milliseconds.

Q2. Consider the following set of processes that arrive at given time, with the length of the CPU burst given in milliseconds. Calculate AWT, ATAT,

TQ= 2

Queue

Gantt Chart

0       2        4        6        8        9        11      13      15      17      18      19      21