Introduction
You open your system in the morning, you open your mailbox, text someone on chat, join your meetings, and have you ever wondered that all this happens at the same time, within some seconds. Let’s examine how the algorithm works. The name of Round Robin Scheduling algorithm comes from the old principle round robin, where the algorithm is designed to get the equal share, maybe time or memory.
This algorithm also offers starvation free execution of processes. Let’s explore the characteristics of a round robin scheduling algorithm.
Characteristics of Round Robin Scheduling Algorithm
- Round robin is a preemptive algorithm.
- Widely used scheduling method in traditional OS.
- Time slice should be minimum, which is assigned for a specific task that needs to be processed. However, it may differ from OS to OS.
- The process that is preempted is added to the end of the queue.
- The CPU is shifted to the next process after fixed interval time, which is called time quantum/time slice.
- It is a real time algorithm which responds to the event within a specific time limit.
- Round robin is a hybrid model which is clock-driven.
- Round robin is one of the oldest, fairest, and easiest algorithms.
Let’s examine the examples and implementation of the round robin scheduling algorithm.
Implementation:
Process | Burst Time | Order | Arrival Time |
P1 | 3 | 1 | 0 |
P2 | 4 | 2 | 0 |
P3 | 3 | 3 | 0 |
Suppose the time quantum is 1 unit.
Order of execution of processes in CPU:
P1 | P2 | P3 | P1 | P2 | P3 | P1 | P2 | P3 | P2 |
0 10
P1 waiting Time: 4 The average waiting time(AWT): (4+6+6)/3 = 5.33
P2 waiting Time: 6
P3 waiting Time: 6
During the process scheduling first P1 enters into the ready queue and is then followed by P2, P3, once a process is executed for a given time period i.e time slice/quantum, it is preempted and other processes in the ready queue execute for the same period of time and this cyclic execution of processes continue until every process completes its burst time/cpu time.
First P1 gets the CPU for a time slice of 1 unit and then moves back to the ready queue, followed by P2 and P3 in a similar manner. The processes execute until they have completed their burst/cpu times.
To implement a round-robin scheduling algorithm, first, we need to understand the completion time, turnaround time, and waiting time.
Completion Time: The time at which the process completes the execution.
Turnaround Time: The time difference between completion and arrival time.
Turnaround time= Completion time- Arrival time
Waiting Time: The time difference between turnaround time and burst time.
Waiting Time= Turnaround time- Burst time
Note: In most cases, we assume arrival time as zero (Same in Blog).
Let’s find the steps to find waiting times for all responses.
1- Create an array rem_bt[] to keep track of remaining burst time of processes. This array is initially a copy of bt[] (burst times array) 2- Create another array wt[] to store waiting times of processes. Initialize this array as 0. 3- Initialize time : t = 0 4- Keep traversing the all processes while all processes are not done. Do following for i'th process if it is not done yet. a- If rem_bt[i] > quantum (i) t = t + quantum (ii) bt_rem[i] -= quantum; c- Else // Last cycle for this process (i) t = t + bt_rem[i]; (ii) wt[i] = t - bt[i] (ii) bt_rem[i] = 0; // This process is over
After finding the waiting time, it is very simple to find the turnaround time.
Turnaround time= Waiting time+Burst time
Now let’s explore the code to understand it in more detail.
C++ Code
// C++ program for implementation of RR scheduling #include<iostream> using namespace std; void findWaitingTime(int processes[], int n, int bt[], int wt[], int quantum) { // burst times. int m_bt[n]; for (int i = 0 ; i < n ; i++) m_bt[i] = bt[i]; int t = 0; // Current time // Keep traversing processes in round-robin manner while (1) { bool done = true; // Traverse all processes one by one repeatedly for (int i = 0 ; i < n; i++) { // If burst time of a process is greater than 0 // then only need to process further if (m_bt[i] > 0) { done = false; // There is a pending process if (m_bt[i] > quantum) { t += quantum; m_bt[i] -= quantum; } // If burst time is smaller than or equal to // quantum. Last cycle for this process else { // Increase the value of t i.e. shows t = t + m_bt[i]; // Waiting time is current time minus time wt[i] = t - bt[i]; // As the process gets fully executed // make its remaining burst time = 0 m_bt[i] = 0; } } } // If all processes are done if (done == true) break; } } // Function to calculate turnaround time void findTurnAroundTime(int processes[], int n, int bt[], int wt[], int tat[]) { // calculating turnaround time by adding // bt[i] + wt[i] for (int i = 0; i < n ; i++) tat[i] = bt[i] + wt[i]; } // Function to calculate average time void findavgTime(int processes[], int n, int bt[], int quantum) { int wt[n], tat[n], total_wt = 0, total_tat = 0; // Function to find waiting time of all processes findWaitingTime(processes, n, bt, wt, quantum); // Function to find turnaround time for all processes findTurnAroundTime(processes, n, bt, wt, tat); // Display processes along with all details cout << "Processes "<< " Burst time " << " Waiting time " << " Turnaround time\n"; // Calculate total waiting time and total turn // around time for (int i=0; i<n; i++) { total_wt = total_wt + wt[i]; total_tat = total_tat + tat[i]; cout << " " << i+1 << "\t\t" << bt[i] <<"\t " << wt[i] <<"\t\t " << tat[i] <<endl; } cout << "Average waiting time = " << (float)total_wt / (float)n; cout << "\nAverage turnaround time = " << (float)total_tat / (float)n; } // Driver code int main() { // process id's int processes[] = { 1, 2, 3}; int n = sizeof processes / sizeof processes[0]; // Burst time of all processes int burst_time[] = {10, 5, 8}; // Time quantum int quantum = 2; findavgTime(processes, n, burst_time, quantum); return 0; }
Output:
Processes Burst time Waiting time Turnaround time 1 10 13 23 2 5 10 15 3 8 13 21 Average waiting time = 12 Average turnaround time = 19.6667
Time Complexity: O(n)
Space Complexity: O(n)
Java Code
// Java program for implementation of RR scheduling public class Main { // Method to find the waiting time for all // processes static void findWaitingTime(int processes[], int n, int bt[], int wt[], int quantum) { // Make a copy of burst times bt[] to store remaining // burst times. int rem_bt[] = new int[n]; for (int i = 0 ; i < n ; i++) rem_bt[i] = bt[i]; int t = 0; // Current time // Keep traversing processes in round-robin manner // until all of them are not done. while(true) { boolean done = true; // Traverse all processes one by one repeatedly for (int i = 0 ; i < n; i++) { // If burst time of a process is greater than 0 // then only need to process further if (rem_bt[i] > 0) { done = false; // There is a pending process if (rem_bt[i] > quantum) { // Increase the value of t i.e. shows // how much time a process has been processed t += quantum; // Decrease the burst_time of current process // by quantum rem_bt[i] -= quantum; } // If burst time is smaller than or equal to // quantum. Last cycle for this process else { // Increase the value of t i.e. shows // how much time a process has been processed t = t + rem_bt[i]; // Waiting time is current time minus time // used by this process wt[i] = t - bt[i]; // As the process gets fully executed // make its remaining burst time = 0 rem_bt[i] = 0; } } } // If all processes are done if (done == true) break; } } // Method to calculate turnaround time static void findTurnAroundTime(int processes[], int n, int bt[], int wt[], int tat[]) { // calculating turnaround time by adding // bt[i] + wt[i] for (int i = 0; i < n ; i++) tat[i] = bt[i] + wt[i]; } // Method to calculate average time static void findavgTime(int processes[], int n, int bt[], int quantum) { int wt[] = new int[n], tat[] = new int[n]; int total_wt = 0, total_tat = 0; // Function to find waiting time of all processes findWaitingTime(processes, n, bt, wt, quantum); // Function to find turnaround time for all processes findTurnAroundTime(processes, n, bt, wt, tat); // Display processes along with all details System.out.println("Processes " + " Burst time + " Waiting time " + " Turnaround time"); // Calculate total waiting time and total turn // around time for (int i=0; i<n; i++) { total_wt = total_wt + wt[i]; total_tat = total_tat + tat[i]; System.out.println(" " + (i+1) + "\t\t" + bt[i] +"\t " + wt[i] +"\t\t " + tat[i]); } System.out.println("Average waiting time = " + (float)total_wt / (float)n); System.out.println("Average turnaround time = " + (float)total_tat / (float)n); } // Driver Method public static void main(String[] args) { // process id's int processes[] = { 1, 2, 3}; int n = processes.length; // Burst time of all processes int burst_time[] = {10, 5, 8}; // Time quantum int quantum = 2; findavgTime(processes, n, burst_time, quantum); } }
Output:
Processes Burst time Waiting time Turnaround time 1 10 13 23 2 5 10 15 3 8 13 21 Average waiting time = 12.0 Average turnaround time = 19.666666
Time Complexity: O(n)
Space Complexity: O(n)
Advantages
- It doesn’t face the issues of starvation or convoy effect.
- If you know the total number of processes on the run queue, then you can also assume the worst-case response time for the same process.
- All the jobs get a fair allocation of CPU.
- It deals with all processes without any priority.
- Allows OS to use the Context switching method to save states of preempted processes.
- This scheduling method does not depend upon burst time. That’s why it is easily implementable on the system.
- Once a process is executed for a specific set of the period, the process is preempted, and another process executes for that given time period.
- It gives the best performance in terms of average response time.
Disadvantages
- Round-robin scheduling doesn’t give special priority to more important tasks.
- Decreases comprehension
- Lower quantum results in higher context switching overhead in the system.
- Finding a correct time quantum is a quite difficult task in this system.
- If the slicing time of the OS is low, the processor output will be reduced.
- This method spends more time on context switching
- Its performance heavily depends on the time quantum.
- Priorities cannot be set for the processes.
Frequently Asked Questions
The real life example of a round robin scheduling algorithm is multitasking.
In Round Robin Scheduling, CPU is assigned to the process on the basis of FCFS for a fixed amount of time. This fixed amount of time is called a time quantum or time slice. After the time quantum expires, the running process is preempted and sent to the ready queue.
Round-robin is one of the algorithms employed by process and network schedulers in computing.
Round-robin scheduling allocates each task an equal share of the CPU time. In its simplest form, tasks are in a circular queue and when a task’s allocated CPU time expires, the task is put to the end of the queue and the new task is taken from the front of the queue.
Key Takeaways
In the above blog we have discussed:
- The name of this algorithm comes from the round-robin principle, where each person gets an equal share of something in turns.
- Round robin is one of the oldest, fairest, and easiest algorithms and widely used scheduling methods in traditional OS.
- Round robin is a preemptive algorithm
- The biggest advantage of the round-robin scheduling method is that If you know the total number of processes on the run queue, then you can also assume the worst-case response time for the same process.
- This method spends more time on context switching.
Read more about search algorithms here, Don’t forget to practice similar problems on CodeStudio as well. If you liked this blog, share it with your friends.
Leave a Reply