Anonymous user menu

Example explaining concept of Round Robin Scheduling Algorit

Example explaining concept of Round Robin Scheduling Algorithm.


RR is most confusing and important scheduling algorithm for GATE. Here I wil try to put it in a simple manner,so that you can easily get and remember it for long time. I will take example of a Hypothetical Bank,where all rules are same except Cash Deposit and Withdrawal. Some terms are Cashier=CPU, Cash Amount= Burst Time/CPU time, Customer= Process.Assuming only 1 cashier in bank,as we study single cpu system.This example is for understanding the concept.Please try to visualize it.

Each customer (process ) comes to system( bank) in order to deposit (process) some amount. Now the bank manager (OS) decides that no customer (process) will starve ( waiting in queue for indefinite time) and each customer  (process ) must get chance to deposit its amount.For this, he creates some rules ( together called as algorithm)

1. There will be a queue ( Ready queue RQ) . Whoever wants to deposit its cash, must stand in queue first. By analogy, if there is a process ,which wants to execute, it must be in queue.

2. There will be a certain amount "A "( time quantum T) ,fixed by Manager (OS), which is the maximum amount,a customer (process ) can deposit at a time. If total amount( CPU time) of customer (process) is greater than A (TQ), then customer  (process ) will leave cashier counter(CPU) and again stand in Queue (RQ) and wait for its turn.However, if total amount is less than A, then after deposit, customer (process ) will leave cashier counter (CPU) and get out of bank immediately and next customer  (process ) from queue (RQ) will deposit his amount next from that point of time.

3.  For getting into queue (RQ), There can be 3 cases

A) If only single customer (process ) is there, then he simply stand in queue (RQ) ,does not matter,whether he already deposited any amount or not( executed on CPU or not)

B) If there are 2 customers  (processes ),coming to join queue (RQ)  at the same time, one already deposited some amount,old, and another is just arriving at the bank,new, then to ensure  that each customer  (process ) get chance, new customer  ( new process ) is given priority ie new customer  (new process )will enter into queue  (RQ) before old customer.

C) If there are 2 or more customers  (processes ) and all are new , all trying to joining queue  (RQ) at the same time, then their passbook is checked and older one is given priority over younger one. Example old customer(lower process id) is using bank from 1991(ID ) while new one is using from 1998, then 1991(ID ) is less than 1998(ID ) , 1991 guy is senior customer of bank so given priority over new one with year time stamp as 1998. In case of processes, if Arrival of 2 or more new processes are same, generally Process with lower process id is given preference and it will join  (RQ)  before higher process id.

Now staff ( scheduler) will call the first customer(process ) from queue   (RQ) and send him to cashier counter(CPU).  As soon as cashier gets free( Either Maximum amount reached "TQ expires"   or total amount of customer is deposited and it left the system ) , staff wil call new customer from queue and send him to cashier. This process executes,until all customers are deposited their amount. 

The most important part is joining the queue. I hope you can make analogy now and easily get the concept.

Please let me know if theres anything wrong or unclear.

Parimal Andhalkar @parimal_andhalkar
10 Nov 2014 08:44 pm