Round Robin is a CPU scheduling algorithm where each process is assigned a fixed time slot in a cyclic way.
- It is simple, easy to implement, and starvation-free as all processes get fair share of CPU.
- One of the most commonly used technique in CPU scheduling as a core.
- It is preemptive as processes are assigned CPU only for a fixed slice of time at most.
- The disadvantage of it is more overhead of context switching.
Illustration:
How to compute below times in Round Robin using a program?
In this tutorial you will learn about round robin scheduling program in C. Process scheduling is an important component for process management. In a multi-user and a time-sharing system, response time is one of the most important objective to be accomplished. There are many scheduling algorithms in C for process management such as: 1. Question-1 Explain Round Robin scheduling algorithms with illustration. Selection Criteria: Each selected process is assigned a time interval, called time quantum or time slice. Process is allowed to run only for this time interval. Here, two things are possible: First, Process is either blocked or terminated before the quantum has elapsed.
- Completion Time: Time at which process completes its execution.
- Turn Around Time: Time Difference between completion time and arrival time. Turn Around Time = Completion Time – Arrival Time
- Waiting Time(W.T): Time Difference between turn around time and burst time.
Waiting Time = Turn Around Time – Burst Time
In this post, we have assumed arrival times as 0, so turn around and completion times are same.
The tricky part is to compute waiting times. Once waiting times are computed, turn around times can be quickly computed.
Steps to find waiting times of all processes:
Once we have waiting times, we can compute turn around time tat[i] of a process as sum of waiting and burst times, i.e., wt[i] + bt[i]
Below is implementation of above steps.
C/C++
// C++ program for implementation of RR scheduling using namespace std; // Function to find the waiting time for all void findWaitingTime( int processes[], int n, { // Make a copy of burst times bt[] to store remaining int rem_bt[n]; rem_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 { // then only need to process further { { // how much time a process has been processed // by quantum } // If burst time is smaller than or equal to else // Increase the value of t i.e. shows t = t + rem_bt[i]; // Waiting time is current time minus time wt[i] = t - bt[i]; // As the process gets fully executed rem_bt[i] = 0; } if (done true ) } void findTurnAroundTime( int processes[], int n, { // bt[i] + wt[i] tat[i] = bt[i] + wt[i]; void findavgTime( int processes[], int n, int bt[], { // Function to find waiting time of all processes // Function to find turn around time for all processes cout << 'Processes ' << ' Burst time ' // around time { total_tat = total_tat + tat[i]; << wt[i] << 'tt ' << tat[i] <<endl; << ( float )total_wt / ( float )n; << ( float )total_tat / ( float )n; int main() // process id's int n = sizeof processes / sizeof processes[0]; // Burst time of all processes int quantum = 2; return 0; |
Java
// Java program for implementation of RR scheduling public class GFG // Method to find the waiting time for all static void findWaitingTime( int processes[], int n, { // Make a copy of burst times bt[] to store remaining int rem_bt[] = new int [n]; rem_bt[i] = bt[i]; int t = 0 ; // Current time // Keep traversing processes in round robin manner while ( true ) boolean done = true ; // Traverse all processes one by one repeatedly { // then only need to process further { { // how much time a process has been processed // by quantum } // If burst time is smaller than or equal to else // Increase the value of t i.e. shows t = t + rem_bt[i]; // Waiting time is current time minus time wt[i] = t - bt[i]; // As the process gets fully executed rem_bt[i] = 0 ; } if (done true ) } static void findTurnAroundTime( int processes[], int n, { // bt[i] + wt[i] tat[i] = bt[i] + wt[i]; static void findavgTime( int processes[], int n, int bt[], { int total_wt = 0 , total_tat = 0 ; // Function to find waiting time of all processes // Function to find turn around time for all processes System.out.println( 'Processes ' + ' Burst time ' + // around time { total_tat = total_tat + tat[i]; System.out.println( ' ' + (i+ 1 ) + 'tt' + bt[i] + 't ' + } System.out.println( 'Average waiting time = ' + System.out.println( 'Average turn around time = ' + } // Driver Method { int processes[] = { 1 , 2 , 3 }; int burst_time[] = { 10 , 5 , 8 }; // Time quantum findavgTime(processes, n, burst_time, quantum); } |
Python3
# RR scheduling # Function to find the waiting time def findWaitingTime(processes, n, bt, rem_bt = [ 0 ] * n # Copy the burst time into rt[] rem_bt[i] = bt[i] # robin manner until all of them are while ( 1 ): # one repeatedly # than 0 then only need to process further done = False # There is a pending process if (rem_bt[i] > quantum) : # Increase the value of t i.e. shows t + = quantum # Decrease the burst_time of current rem_bt[i] - = quantum # If burst time is smaller than or equal else : # Increase the value of t i.e. shows t = t + rem_bt[i] # Waiting time is current time minus wt[i] = t - bt[i] # As the process gets fully executed rem_bt[i] = 0 # If all processes are done break # Function to calculate turn around time def findTurnAroundTime(processes, n, bt, wt, tat): # Calculating turnaround time tat[i] = bt[i] + wt[i] # and turn-around times. wt = [ 0 ] * n # of all processes wt, quantum) # Function to find turn around time findTurnAroundTime(processes, n, bt, print ( 'Processes Burst Time Waiting' , total_wt = 0 for i in range (n): total_wt = total_wt + wt[i] print ( ' ' , i + 1 , 'tt' , bt[i], print ( 'nAverage waiting time = %.5f ' % (total_wt / n) ) print ( 'Average turn around time = %.5f ' % (total_tat / n)) # Driver code proc = [ 1 , 2 , 3 ] burst_time = [ 10 , 5 , 8 ] # Time quantum findavgTime(proc, n, burst_time, quantum) # This code is contributed by |
C#
// scheduling // for all processes int n, int []bt, int []wt, int quantum) // store remaining burst times. rem_bt[i] = bt[i]; int t = 0; // Current time // Keep traversing processes in round // not done. { // one repeatedly { // is greater than 0 then only if (rem_bt[i] > 0) done = false ; if (rem_bt[i] > quantum) // Increase the value of t i.e. // has been processed // current process by quantum } // If burst time is smaller than // for this process { // Increase the value of t i.e. // has been processed // time minus time used by wt[i] = t - bt[i]; // As the process gets fully // burst time = 0 } } // If all processes are done break ; } // Method to calculate turn around time int n, int []bt, int []wt, int []tat) // calculating turnaround time by adding for ( int i = 0; i < n ; i++) } // Method to calculate average time int []bt, int quantum) int []wt = new int [n]; int total_wt = 0, total_tat = 0; // Function to find waiting time of findWaitingTime(processes, n, bt, wt, quantum); // Function to find turn around time findTurnAroundTime(processes, n, bt, wt, tat); // Display processes along with Console.WriteLine( 'Processes ' + ' Burst time ' + // around time { total_tat = total_tat + tat[i]; + 't ' + wt[i] + 'tt ' + tat[i]); ( float )total_wt / ( float )n); ( float )total_tat / ( float )n); public static void Main() // process id's int n = processes.Length; // Burst time of all processes int quantum = 2; } |
Output:
This article is contributed by Sahil Chhabra. If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to [email protected]. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Recommended Posts:
I have been working on a Round Robin Scheduling Program. My inputs are:
Time Slice is 3 units!My output must be:
But I am not getting the correct results(WT & FT) for Process 1, 4 & 5. Here's my code, can anyone please help me fix it and get the above results?
Thank You
trollstertrollster2,36755 gold badges2828 silver badges5757 bronze badges
5 Answers
I'm sure there are many bugs (starting with not caring if the user wants to enter 11 or more processes even though your array of processes is limited to 10).
However; I spent 10 minutes trying to decipher your code and still don't really know what it thinks it's doing - there's no comments at all and the variable names and function names don't help (e.g.
no
is not a boolean 'yes/no' variable, checkprocess()
doesn't check one process but checks all processes to see if all processes have finished, etc). Mostly, if I were being paid to fix this code I'd simple throw it out and rewrite it from scratch to save time. I thought about rewriting it from scratch and just posting the resulting code; but that's not going to help you with your homework.My advice is, rewrite it from scratch instead of fixing it.
It should have a global
currently_running_process
variable, a global current_time
variable, one function to increase the current time, and one function for the scheduler itself.The function to increase the current time would:
- for each process on the scheduler's linked list, increase the waiting time
- do
current_time++
- find any processes that should be started (
current_time arrival_time
) and append any started processes to the end of the scheduler's linked list
The scheduler function should:
- remove the first process from the scheduler's linked list
- determine how much time that process should use (the time slice length or the process' remaining time, whichever is lower)
- subtract that amount of time from the process' remaining time
- call the
increase_time()
function in a loop, until that amount of time has passed - if the process' remaining time is not zero; put the process back onto the end of the linked list
- if the process` remaining time was zero, check if the scheduler's linked list is empty and exit the program if it is
Note: I'd start with
current_time = -1;
and call the function to increase the current time once before calling the scheduler function; so that any processes with arrival_time 0
would be added to the scheduler's linked list before the scheduler starts working (and so that the scheduler function doesn't see an empty list as soon as it's started).BrendanBrendan
kanikakanika
You can use queue for doing the same, i am pasting a link which is written in ANSI CPP You can check this link for more info. I was having same problem like you had but the code on the link helped me a lot it also contains many other Scheduling program but i extracted only round robin from it. click here to see the code for round robin Scheduling
ROHIT PATELROHIT PATEL
Artjom B.53.8k1818 gold badges8787 silver badges160160 bronze badges
user3832997user3832997
This code will read data from file whose format should have one process info in a single line, arrival time, burst time, spaced, and file should terminate with -1. File name and time slice must be passed in command arguments. Like:
The code is in C and variable names are self-descriptive.
Khurram RazaKhurram Raza
protected by eyllanescApr 6 '18 at 19:26
Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).
Would you like to answer one of these unanswered questions instead?
Would you like to answer one of these unanswered questions instead?