Click here to Skip to main content
Click here to Skip to main content

Round Robin Scheduling

, 28 Sep 2013
Rate this:
Please Sign up or sign in to vote.
Finding scheduling order, average turn-around and wait time for round-robin scheduling
Sample image

Introduction

Round-robin scheduling algorithm is one of the simplest scheduling algorithms. It is designed especially for time-sharing systems. The ready queue is treated as a circular queue. The algorithm assigns a time slice (also called time quantum) to each process in the ready queue in order, handling all processes without priority. A maximum of one time slice is allocated at once. If the remaining request is less than a time slice, only the remaining request time is allocated. Round-robin scheduling is both simple and easy to implement. It is also starvation-free.

The project may be used to find the scheduling order, the average turn-around time and average wait time when round-robin scheduling is applied.

About the Code

The code is very simple. The design consists of a class roundrobin. This class consists of functions:

  1. read()

    This function is used to read the input to an object of this class. The inputs required are:

    1. n: The number of processes
    2. a[]: The arrival times of processes
    3. rq[]: The request times of processes
    4. q: The time quantum
  2. calc()

    This function is used to calculate:

    1. t[]: The turnaround time of each process
    2. w[]: The wait time of each process
    3. order: The scheduling order
  3. display()

    This function does two tasks:

    1. Calculates tav and wav, the average turn-around time and average wait time respectively, from t[] and w[] respectively
    2. Displays the scheduling order and the average turn-around and average wait time

The Code

Here is the main part of the code present in the calc() function:

for(i=0;j<n;i=(i+1)%n)//while there are uncompleted processes
 {
  if(r[i]>0&&sp>=a[i])	//find the next uncompleted process 
			//which has already or just arrived
  {
   f=true;
   if(r[i]<=q)	//if the process requests for time less than the quantum
    time=r[i];	//time to be alloted in this turn is the complete requested time
   else time=q;	//else, it is the quantum time
   //schedule the process
   t[i]+=time,r[i]-=time,order.push_back(i+1);
   if(r[i]==0) j++;	//if the process has got completed, increment j
   for(k=0;k<n;k++)	//for each arrived processes incompleted after this scheduling
    if(r[k]!=0&&k!=i&&a[k]<sp+time)
     if(!(a[k]<=sp))	//if they arrived while scheduling this process
      w[k]+=sp+time-a[k],t[i]+=sp+time-a[k];
    else
      w[k]+=time,t[k]+=time;//add time to their wait times and turn-around times
   sp+=time;
   continue;
  }
  if(i==n-1)
  {
   if(!f)
   //now there are no more arrived processes to be scheduled
   //so change sp to the arrival time of next arriving process
   {
    int it;
    int diff=0;//diff between present time spent and arrivaltime of next arriving process
    for(it=0;it<n;it++)
     if(sp<a[it])//if process has'nt yet arrived
     {
      if(diff==0) diff=a[it]-sp;
      else if(diff>a[it]-sp) diff=a[it]-sp;
     }
    sp+=diff;
   }
   f=false;
  }
 }
  • The code uses for loop which terminates when all processes have completed.
  • j is used to count the number of processes completed.
  • i is used to consider a process for scheduling in the circular-queue fashion.
  • The array r[] is used to keep note of the remaining request of each process.
  • sp gives the time spent till the given instant.

History

Initially, the project was designed assuming all processes arrive on time. Then the code is much simpler. We need not use variable sp in the above code. Also, the if(i==n-1){...} block is not necessary.

Bibliography

  1. Round-robin scheduling
  2. Silberschatz, Galvin and Gagne; Operating System Concepts; Sixth Edition; Wiley

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

kbsbng
Technical Lead Yahoo!
India India
I've studied info. sc. engg. from Sir MVIT, Bangalore.
 
I'm interested in programming.
 
Some of my technical blogs:
 
http://perl-blog.kbsbng.com/
http://java-blog.kbsbng.com/
 
I also enjoy writing some webpages such as http://sites.google.com/site/plantencyclopedia/
 
More about me at http://www.kbsbng.com and http://blog.kbsbng.com.
Follow on   Twitter   Google+

Comments and Discussions

 
Questionroudrobin PinmemberMember 1021572517-Aug-13 14:00 
BugReverse in links!!! Pinmemberroozevasl19-Jun-13 6:16 
AnswerRe: Reverse in links!!! Pinmemberkbsbng28-Sep-13 1:48 
Questionhelp PinmemberMember 958723327-Nov-12 21:34 
Questionwrong DL Link. PinmemberGreat Kourosh30-Oct-12 22:29 
Suggestioncounter example for the simulation program PinmemberDeepanwita Basak3-Oct-12 5:52 
QuestionThank you! PinmemberDonna May11-Oct-11 15:39 
GeneralMultilevel Feedback Queue CPU Scheduling Algorithm Pinmemberfelisardo26-Feb-11 2:43 
GeneralMy vote of 3 Pinmember00120012001220-Dec-10 22:42 
GeneralMy vote of 1 Pinmembersarmistha prasad20-Dec-10 4:01 
Questionc# code to read data from hash table randomly?? Pinmembermerryjoy0006-Feb-09 20:13 
GeneralRound robin Pinmemberabhay198317-Sep-08 23:17 
General Pinmember_elli_10-Feb-07 13:02 
GeneralRe: Pinmemberkbsbng10-Feb-07 17:27 
GeneralI find it ironic... PinprotectorMarc Clifton10-Feb-07 4:01 
GeneralRe: I find it ironic... PinmemberBassam Saoud10-Feb-07 5:15 
GeneralRe: I find it ironic... Pinmemberkbsbng10-Feb-07 17:21 
GeneralRe: I find it ironic... Pinmemberkbsbng10-Feb-07 22:53 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web03 | 2.8.140821.2 | Last Updated 28 Sep 2013
Article Copyright 2007 by kbsbng
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid