round robin scheduling

• Download source code - 74.8 Kb
• Download source code - 1.9 Kb

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:

a. n: The number of processes,

b. a[]: The arrival times of processes,

c. rq[]: The request times of processes and

d. q: The time quantum.

2. calc():

This function is used to calculate:

a. t[]: The turnaround time of each process,

b. w[]: The wait time of each process and

c. order: The scheduling order.

3. display():

This function does two tasks:

a. Calculates tav and wav, the average turn-around time and average wait time respectively, from t[] and w[] respectively;

b. Displays the scheduling order and the average turn-around and average wait time.

How the code does

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 at 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