Operating Systems | Scheduling Algorithms : Round Robin


Round Robin

Features :

  • Most popular algorithm of all
  • Practically implementable
  • Implementable with basic data structures like queue
  • Extremely lesser starvation
  • Optimum efficiency can be set by controlling time quantum

The round robin algorithm will continuously switch between processes if a process in CPU (under execution) exceeds a time limit set by OS called time quantum.

Flow Chart :

  • Scheduler allocated process to for execution.
  • CPU starts monitoring the execution time right after from allocation.
  • If the process completes its execution before exceeding time quantum, OS forwards the process to termination state.
  • else, the processes gets preempted once the time quantum limit exceeded and if the process finished at this moment, OS moves the process to termination state, else it moves to ready queue and iterates over the whole process listed above.

Example : Consider the following table of processes and calculate completion time, turn around time and waiting time using Round Robin algorithm.

    Assumptions:

  • Time quantum = 2unit
  • Preemptive algorithm.
  • No I/O request will be there from any process.
  • Arrival time is relative to CPU on time.
Process AT BT
P1 0 2
P2 1 2
P3 2 4
P4 3 1
P5 4 2



Scheduler has to move new process from the frond on the ready queue,when either the current running process get terminates with out exceeding time quantum or the process reached the limit of time quantum. In second case if the process did not processed completely it has to enqueue again at the back of ready queue.

Execution of the set of given in above example can be depicted as follows:

Process Number AT BT CT TAT WT
1 0 2 2 2 0
2 1 2 4 3 1
3 2 4 11 9 5
4 3 1 7 4 3
4 5 2 9 4 2



By observing the nature of representations it can be found out that as the length of time quantum increases frequency of context switching decreases. A decrements in time quantum reduces the time gap between switching of processes, so there will be a smaller response time and lesser starvation. Algorithm with infinite time quantum is what we call FCFS algorithm.

Comments