FOR FREE MATERIALS

Round Robin Algorithm

Round Robin process and examples:

The round-robin (RR) scheduling algorithm is designed especially for timesharing systems and Interactive 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 a 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.

Round Robin Scheduling is very much practical and there is no starvation (no convoy effect) because every process gets CPU for a certain amount of time unit/quantum.

Criteria: TQ (Time Quantum) + AT (Arrival Time)

Mode: Preemptive

Data-structure: Circular Queue 

Example 1: TQ = 2 (Here)

Gantt Chart

Context Switching

Number of Context Switching = 09

Now we calculate Turn Around Time (TAT) and Waiting Time (WT) using the following formula:

TAT = CT - AT,  WT = TAT – BT 

And 

Response Time (RT) = FR (First Response) - AR (Arrival Time)

# If the time quantum is too small, scheduling overhead in the form of context-switch time becomes excessive (high).

# If the time quantum is large then starvation may occur.

So, average time quantum is always better i.e. neither a small time quantum nor a large time quantum.

Example 2: TQ = 8 (Here)

Round Robin Scheduling

Gantt Chart

Context Switching

Number of Context Switching = 06

Now we calculate Turn Around Time (TAT) and Waiting Time (WT) using the following formula:

TAT = CT - AT, WT = TAT – BT 

And 

Response Time (RT) = FR (First Response) - AR (Arrival Time)

From these two examples (1&2) it is clear that 

#  When time quantum increases, context switching decreases, and response time increases.

#  But whenever time quantum decreases, context switching increases and response time decreases.

#  Whenever time quantum is extremely large (TQ = α) then RR ⇒ FCFS 

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, with 5 processes and a time quantum of 20 milliseconds, each process will get up to 20 milliseconds every 100 milliseconds. The performance of the RR algorithm depends heavily on the size of the time quantum.