Round Robin Scheduling Algorithm

This algorithm works on the principle of round-robin, where an equal share of an object is given to each person in turns. Mostly used for multitasking, this is the oldest and simplest scheduling algorithm that offers starvation-free execution. Each ready task has to run turn by turn in a cyclic queue for a limited time period in round-robin (RR).

Example of Round Robin Algorithm

Following are three processes with their burst time:

Step 1: Process P1 executes first. Every process executes for 2 seconds so processes P2 and P3 are in the waiting queue.

Step 2: At time = 2, P2 starts executing and P1 is added to the end of the Queue.

Step 3: At time = 4, P3 starts executing and P2 is added at the end of the queue.

Step 4: At time = 6, P1 starts executing and P3 is added at the end of the queue.

Step 5: At time = 8, As P1 has a burst time of 4 it completes execution and P2 starts execution.

Step 6: With a burst time of 3, process P2 executes for 2 intervals. At time = 9, P2 completes execution and P3 starts execution till completion.

Step 7: Average waiting time is:
Waiting time
P1 = 0 + 4 = 4
P2 = 2 + 4 = 6
P3 = 4 + 3 = 7

Characteristics of Round Robin Scheduling

Following are some important characteristics of RR:

• A preemptive scheduling algorithm.
• CPU shifts to the next process after a fixed time interval known as time quantum or time-slice.
• Preempted processes are added to the end of the queue.
• A hybrid and clock-driven model.
• Time slice is usually the minimum but differs from OS to OS.
• A real time algorithm that responds to an event within a specific time limit.
• Oldest, fairest, and easiest algorithm.
• Widely used in traditional OS.

Advantages of Round Robin Algorithm

Following are the advantages of RR:

• No issues of starvation or convoy effect.
• Every job gets a fair allocation of CPU.
• No priority scheduling is involved.
• Total number of processes on the run queue helps assume the worst-case response time for a process.
• Doesn’t depend on burst time and is easily implementable.
• When a process executes for a specific time, it is preempted, and another process takes its place executing for that same time period.
• Context switching helps save states of preempted processes.
• Best performance in terms of average response time.

Disadvantages of Round Robin Algorithm

Following are the disadvantages of RR:

• Low slicing time reduces processor output.
• Spends more time on context switching.
• Performance depends on time quantum.
• Processes don’t have priorities.
• No special priority to more important tasks.
• Decreases comprehension.
• Higher context switching overhead due to lower time quantum.
• Difficult to find a correct time quantum.

Worst Case Latency

Worst Case Latency is the maximum time taken for execution of all tasks. Following is the formula for worst-case latency is:
Tworst = {(dti + sti + eti), + (dti + sti + eti)2 +…+ (dti + sti + eti)N., + (dti + sti + eti + eti)N} + tISR

t,SR = sum of all execution times
dt = Detection time when a task enters the list
st = Time required to switch from one task to another
et = Execution time of task

Summary

Round Robin process scheduling algorithm works on the principle of round-robin, where an equal share of an object is given to each person in turns. Oldest, fairest, and easiest scheduling algorithms. It spends a lot of time on context switching. Worst-case latency is the maximum time taken for the execution of all the tasks in the OS.