Click here to Skip to main content
11,706,979 members (52,985 online)
Click here to Skip to main content

Round Robin Scheduling

, 28 Sep 2013 CPOL 195.8K 18.2K 36
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.

You may also be interested in...

Comments and Discussions

 
Questionroudrobin Pin
Member 1021572517-Aug-13 14:00
memberMember 1021572517-Aug-13 14:00 
BugReverse in links!!! Pin
roozevasl19-Jun-13 6:16
memberroozevasl19-Jun-13 6:16 
AnswerRe: Reverse in links!!! Pin
kbsbng28-Sep-13 1:48
memberkbsbng28-Sep-13 1:48 
Questionhelp Pin
Member 958723327-Nov-12 21:34
memberMember 958723327-Nov-12 21:34 
Questionwrong DL Link. Pin
Great Kourosh30-Oct-12 22:29
memberGreat Kourosh30-Oct-12 22:29 
Suggestioncounter example for the simulation program Pin
Deepanwita Basak3-Oct-12 5:52
memberDeepanwita Basak3-Oct-12 5:52 
QuestionThank you! Pin
Donna May11-Oct-11 15:39
memberDonna May11-Oct-11 15:39 
GeneralMultilevel Feedback Queue CPU Scheduling Algorithm Pin
felisardo26-Feb-11 2:43
memberfelisardo26-Feb-11 2:43 
GeneralMy vote of 3 Pin
00120012001220-Dec-10 22:42
member00120012001220-Dec-10 22:42 
GeneralMy vote of 1 Pin
sarmistha prasad20-Dec-10 4:01
membersarmistha prasad20-Dec-10 4:01 
Questionc# code to read data from hash table randomly?? Pin
merryjoy0006-Feb-09 20:13
membermerryjoy0006-Feb-09 20:13 
GeneralRound robin Pin
abhay198317-Sep-08 23:17
memberabhay198317-Sep-08 23:17 
General Pin
_elli_10-Feb-07 13:02
member_elli_10-Feb-07 13:02 
GeneralRe: Pin
kbsbng10-Feb-07 17:27
memberkbsbng10-Feb-07 17:27 
GeneralI find it ironic... Pin
Marc Clifton10-Feb-07 4:01
protectorMarc Clifton10-Feb-07 4:01 
GeneralRe: I find it ironic... Pin
Bassam Saoud10-Feb-07 5:15
memberBassam Saoud10-Feb-07 5:15 
GeneralRe: I find it ironic... Pin
kbsbng10-Feb-07 17:21
memberkbsbng10-Feb-07 17:21 
GeneralRe: I find it ironic... Pin
kbsbng10-Feb-07 22:53
memberkbsbng10-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 | Terms of Use | Mobile
Web02 | 2.8.150819.1 | Last Updated 28 Sep 2013
Article Copyright 2007 by kbsbng
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid