Round Robin Scheduling Algorithm

Round Robin

In round robin scheduling, each ready job only executes turn-by-turn in a cyclic queue for a discrete window of time. Additionally, the method allows processes to run without starvation.

  • It is always pre-emptive algorithm
  • It is a hybrid paradigm that is time-driven.
  • It is used in time sharing systems
  • Similar to FCFS with time quantum(TQ)
  • It is a real-time algorithm that replies to the event in a predetermined amount of time.
  • One of the oldest, fairest, and simplest algorithms is round robin.
  • a common scheduling technique in conventional operating systems.

After a predetermined amount of time, or “time quantum” or “time slice,” the CPU switches to the following process.

  • The preempted process gets moved to the back of the queue.
  • A time slice that is given to a particular task that needs to be processed should be as short as possible. It might, however, vary from one OS to another.

Example of Round-robin Scheduling
Consider the following five processes with the arrival time and length of CPU Burst given in ms. Find the average waiting time with time quantum is 3?

ProcessArrival TimeBurst Time
P108
P252
P317
P463
P585

Solution

Step 1: Let TQ = 3

Step 2: First CPU allocated to given process where process have minimum arrival time. Here P1 process have 0 arrival time. So you can add P1 process from Ready Queue to Gantt Chart.

Step 3: Burst Time for process P1 is 8. But Time Quantum is 3. So remaining value(8-3 = 5) assigned to P1 process and added P1 Process into the ready queue.

Step 4: Now check the next process which have next minimum time. Here P3 process have 1 arrival time. So you can add P3 process from Ready queue to Gantt chart

Step 5: Similarly we have to allocate CPU to all process and add process from Ready Queue to Gantt Chart.

Round Robin Ready Queue
Round Robin

             (Gantt chart)

ProcessArrival Time (AT)Burst Time (BT)Completion Time (CT)Turn Around Time
TAT = CT-AT
Waiting Time WT = TAT-BTResponse Time
RT = ST-AT
(Start Time-Arrival Time)
P108 5 22222140
P25211644
P317 4 12322152
P46314855
P585 22517129

In the above table, we can find the waiting time for the process P1, P2, P3, P4 and P5.          

Waiting Time for P1 => 14

Waiting Time for P2 => 4

Waiting Time for P3 => 15

Waiting Time for P4 => 5

Waiting Time for P5 => 12

Average Waiting Time(AWT) =(14+4+15+5+12)/5

= 50/5

= 10 ms

Advantage of Round-robin Scheduling Algorithm

  • It is not affected by convoy effect or famine.
  • A specific time quantum is allocated to various tasks when round-robin scheduling is used.
  • Once a process has run for a particular amount of time, it is preempted and another process runs for that time period instead.
  • In terms of average response time, it performs best.
  • Fairness exists because each process receives an equal share of the CPU.
  • The freshly generated process is now added to the ready queue’s end.
  • Each task is assigned a time slot or quantum by a round-robin scheduler, which typically uses time-sharing.

Disadvantages of Round-robin Scheduling Algorithm

  • The output of the CPU will be decreased if the OS’s slicing time is short.
  • This approach spends more time transferring between contexts.
  • More significant jobs are not given a higher priority when round-robin scheduling is used.
  • Context switching overhead in the system increases as time quantum decreases.
  • Finding the right time quantum in this system is a very challenging issue.
  • Low throughput is present.
  • If quantum time for scheduling is smaller, the Gantt chart appears to be overly large.
  • Small quantum scheduling takes a lot of time.
Leave a Reply 0

Your email address will not be published. Required fields are marked *


Exit mobile version