What is Round Robin Scheduling in OS?

What is Round Robin Scheduling in OS?

The Round robin scheduling algorithm is one of the CPU scheduling algorithms in which every process gets a fixed amount of time quantum to execute the process.

In this algorithm, every process gets executed cyclically. This means that processes that have their burst time remaining after the expiration of the time quantum are sent back to the ready state and wait for their next turn to complete the execution until it terminates. This processing is done in FIFO order which suggests that processes are executed on a first-come, first-serve basis.

How does the Round Robin Algorithm Work?

1. All the processes are added to the ready queue.
2. At first, The burst time of every process is compared to the time quantum of the CPU.
3. If the burst time of the process is less than or equal to the time quantum in the round-robin scheduling algorithm, the process is executed to its burst time.
4. If the burst time of the process is greater than the time quantum, the process is executed up to the time quantum (TQ).
5. When the time quantum expires, it checks if the process is executed completely or not.
6. On completion, the process terminates. Otherwise, it goes back again to the ready state.

Consider the below flow diagram for a better understanding of Round Robin scheduling algorithm:

Characteristics of Round Robin Scheduling in OS

• Round robin scheduling in os is clock-driven (Hybrid model).
• It is a Preemptive type of CPU scheduling algorithm in OS.
• The round-robin algorithm generally focuses on the Time Sharing technique.
• Round robin Scheduling is the simplest and one of the oldest algorithms.
• This algorithm is a real-time algorithm as it responds to an event within a specific time limit.
• Round robin is a widely used algorithm in traditional OS.

Example of Round Robin Scheduling Algorithm

Consider the following 6 processes: P1, P2, P3, P4, P5, and P6 with their arrival time and burst time as given below:

Q. What are the average waiting and turnaround times for the round-robin scheduling algorithm (RR) with a time quantum of 4 units?

Ready Queue:

At first, In the ready queue, process P1 will be executed for a time slice of 4 units. Since there are no processes initially, Process P1, with a burst time of 5 units, will be the only process in the ready queue.

Ready Queue:

Along with the execution of P1, four more processes, P2, P3, P4, and P5, arrive in the ready queue. P1 will be added to the ready queue due to the remaining 1 unit.

Ready Queue:

During the execution of P2, P6 arrived in the ready queue. Since P2 has not been completed, P2 will be added to the ready queue.

Ready Queue:

Similarly, P3 and P4 have been completed, but P5 has a remaining burst time of 1 unit. Hence it will be added back to the queue.

Ready Queue:

The next processes, P6 and P2, will be executed. Only P5 will be left with 1 unit of burst time.

GANTT Chart:

The Gantt chart will look like this:

As we know,

Turn Around Time = Completion Time - Arrival Time
Waiting Time = Turn Around Time - Burst Time

Avg Waiting Time = (11+5+8+6+16+12)/6 = 68/6 = 11.33 units.

Implementation of Round Robin Algorithm in C++

Output:

Average Turn Around Time = 15.33 Average Waiting Time = 11.33

• Code Explanation:
  • Initialize a FIFO queue to implement this algorithm and push the first process into the queue.
  • We will use an array to check whether the process is in the queue.
  • Keep track of the time using a variable - current_time
  • If the process gets CPU for the first time, record its start time as current_time.
  • Give the quantum unit of time to the process in the front of the queue and pop this process from the queue.
  • If the burst time of this process becomes 0, calculate the Completion Time, Turn Around Time, and Waiting Time for it.
  • If some process had arrived when this process was executing, insert them into the queue.
  • If the current process has burst time remaining, push the process into the queue again.
  • If the queue is empty, pick the first process from the list that is not completed.
  • Keep doing this till all processes are completed.

Advantages of Round Robin in OS

1. This round-robin algorithm offers starvation-free execution of processes.
2. Each process gets equal priority and fair allocation of CPU.
3. Round Robin scheduling algorithm enables the Context switching method to save the states of preempted processes.
4. It is easily implementable on the system because round-robin scheduling in os doesn’t depend upon burst time.

Disadvantages of Round Robin in OS

1. The waiting and response times are higher due to the short time slot.
2. Lower time quantum results in higher context switching.
3. We cannot set any special priority for the processes.