15,511,353 members
Articles / Programming Languages / C++
Article
Posted 9 Feb 2007

288K views
37 bookmarked

# Round Robin Scheduling

Rate me:
Finding scheduling order, average turn-around and wait time for round-robin scheduling

## 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.

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()`

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:

C++
```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

Written By
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.

 First Prev Next
 how to calculate the CPU utilization Member 1216695826-Nov-15 7:33 Member 12166958 26-Nov-15 7:33
 roudrobin Member 1021572517-Aug-13 15:00 Member 10215725 17-Aug-13 15:00
 Reverse in links!!! roozevasl19-Jun-13 7:16 roozevasl 19-Jun-13 7:16
 Re: Reverse in links!!! kbsbng28-Sep-13 2:48 kbsbng 28-Sep-13 2:48
 help Member 958723327-Nov-12 22:34 Member 9587233 27-Nov-12 22:34
 wrong DL Link. Great Kourosh30-Oct-12 23:29 Great Kourosh 30-Oct-12 23:29
 counter example for the simulation program Deepanwita Basak3-Oct-12 6:52 Deepanwita Basak 3-Oct-12 6:52
 Thank you! Donna May11-Oct-11 16:39 Donna May 11-Oct-11 16:39
 Multilevel Feedback Queue CPU Scheduling Algorithm felisardo26-Feb-11 3:43 felisardo 26-Feb-11 3:43
 My vote of 3 00120012001220-Dec-10 23:42 001200120012 20-Dec-10 23:42