# Round robin scheduling algorithm with Example

Round robin  is the  scheduling algorithm used by the CPU during execution of the process . Round robin is designed specifically for time sharing systems . It is similar to first come first serve scheduling algorithm but the preemption  is the added functionality to switch between the processes .

A small unit of time also known as time slice or quantum is set/defined . The ready queue works like circular queue .All processes in this algorithm are kept in the circular queue also known as ready queue .  Each New process is added to the tail of the ready/circular queue .
By using this algorithm , CPU makes sure, time slices ( any natural number ) are assigned  to each process in equal portions and in circular order , dealing with all process without any priority .

It is also known as cyclic executive .

The main advantage of round robin algorithm over first come first serve algorithm is that it is  starvation free  . Every process will be executed by CPU for fixed interval of time (which is set as time slice ) . So in this way no process left waiting for its turn to be executed by the CPU .

Round robin algorithm is simple and easy to implement . The  name round robin comes from the principle known as round robin in which every person takes equal share of something in turn .

Pseudo Code :

* CPU scheduler picks the process from the circular/ready queue , set a timer to interrupt it after 1 time slice    / quantum  and dispatches it .

*  If  process has burst time less than 1 time slice/quantum

>  Process will leave the CPU after the completion
>  CPU will proceed with the next process in the ready queue / circular queue .

else If process has burst time longer than 1 time slice/quantum

>  Timer will be stopped . It cause interruption to the OS .
>   Executed process is then placed at the tail of the circular / ready  querue by applying  the context                   switch
>  CPU scheduler then proceeds by selecting the next process in the ready queue .

Here , User can calculate the average turnaround time and average waiting time along with the starting and finishing time of each process

Turnaround time   :   Its the total time taken by the process between starting and the completion

Waiting time         :   Its the time for which process is ready to run but not executed by CPU scheduler

for example ,
we have three processes

Burst time             Waiting time         Turnaround time

P1                          24                           6                           30

P2                          3                             4                            7

P3                          3                             7                           10

So here we can see the turnaround time for the process 1 is 30 while 7 and 10 for 2nd and 3rd process

A Gantt chart is a chart which shows the start and finish times of  all the processes .

Gantt chart for the round robin algorithm  is

|-----------|-----------|----------|------------|------------|------------|------------|---------------|
|    P1           |      P2          |     P3         |    P1              |    P1              |  P1                 |       P1            |     P1                  |
|-----------|-----------|----------|------------|------------|------------|------------|---------------|
0                  4                   7                 10                  14                   18                     22                     26                              30

Read Also :     Shortest Remaining Time Scheduling Algorithm with Example

The major features of the Round Robin algorithm is that

* Throughput is low as the large process is holding up the Central processing unit for execution .

* The main advantage of Round robin is to remove starvation  . As long as all processes completes the execution then we  dont have any trouble, But the problem starts when any of the process fails to complete . The incomplete   execution of any process leads to starvation .

* Queuing is done without using any prioritization of the processes.

Code :

```import java.util.List;

public class RoundRobin {

int [] temp;
int [] tempWaitinTime;
int commBT, k, tq;
int[][] d;
int btcache;

void start( ){
for (int i = 0; i < d.length; i++) {
int bt  = d[i][1];
if( bt > 0){
if( bt <= tq){
temp[i] = btcache+bt;
btcache = temp[i];
k += bt;
bt -= bt;

}
else{
temp[i] = btcache+tq;
btcache = temp[i];
bt -= tq;
k += tq;
}

d[i][1] = bt;

}
}
if( k!= commBT)
start();
}

private void display(List<Job> jobList) {
float avgTurnArroundTime = 0;
float avgWaitigTime = 0;
int c = 1;
System.out.println("============================================ ");
System.out.println("Process ID | Turnaround time | Waiting time ");
System.out.println("============================================ ");
Object[] job = jobList.toArray();
for (int i : temp) {
Job job1 = (Job) job[c-1];
System.out.println( "    " + c + "       |     " + i +"           |   "+(i-job1.getCpuTime()));
System.out.println("----------------------------------------");
avgTurnArroundTime += i;
avgWaitigTime += (i-job1.getCpuTime());
c++;
}
System.out.println("===============================================");
System.out.println( "Avg waiting time = " + avgWaitigTime/temp.length);
System.out.println("===============================================");
System.out.println( "Avg turn round time = " + avgTurnArroundTime/temp.length);
System.out.println("===============================================");
}
public void run(List<Job> jobList, int quantum) {

int pcount = jobList.size();
d = new int[pcount][2];

temp = new int[pcount];
int count = 0;
for(Job job:jobList){
d[count][0] = count;

int m = job.getCpuTime();
d[count][1] = m;

commBT += m;
count++;
}

tq = quantum;
start();
display(jobList);

}
}

AllocationStrategy.java

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.Queue;

/* implement this class for all three strategies */

public abstract class AllocationStrategy {
protected List<Job> Jobs;
protected ArrayList<Job> Queue;

public AllocationStrategy(List<Job> jobs) {
super();
Jobs = jobs;
}

public abstract void run();
// update current job by 1 tick
// check if the job queue might need to be changed.
// check for jobs to add to the queue
}

Job.java

public class Job {
private int id, submitTime, CPUTime, CPUTimeLeft;

private int startTime = 0, endTime = 0;

public int ProcessCompletionTime;
public int processArrivalTime;
public int waitingTime;
public int turnAroundTime;
private JobFinishEvent evt;

private int arrivalTime,cpuTime,processId;

public Job(int id, int submitTime, int CPUTime, JobFinishEvent evt) {
super();
this.id = id;
this.submitTime = submitTime;
this.CPUTime = CPUTime;
this.CPUTimeLeft = CPUTime;
this.evt = evt;
}

public Job(int processId, int arrivalTime, int cpuTime) {

this.processId = processId;
this.arrivalTime = arrivalTime;
this.cpuTime = cpuTime;

}

public void start(int sysTime) {
startTime = sysTime;
}

public void tick(int sysTime) {
CPUTimeLeft --;
if (CPUTimeLeft <= 0){
endTime = sysTime;
evt.onFinish(this);
}

}

public int getId() {
return id;
}

public void setId(int id) {
this.id = id;
}

public int getSubmitTime() {
return submitTime;
}

public void setSubmitTime(int submitTime) {
this.submitTime = submitTime;
}

public int getCPUTime() {
return CPUTime;
}

public void setCPUTime(int cPUTime) {
CPUTime = cPUTime;
}

public int getCPUTimeLeft() {
return CPUTimeLeft;
}

public void setCPUTimeLeft(int cPUTimeLeft) {
CPUTimeLeft = cPUTimeLeft;
}

public int getStartTime() {
return startTime;
}

public void setStartTime(int startTime) {
this.startTime = startTime;
}

public int getEndTime() {
return endTime;
}

public void setEndTime(int endTime) {
this.endTime = endTime;
}

public int getArrivalTime() {
return arrivalTime;
}

public void setArrivalTime(int arrivalTime) {
this.arrivalTime = arrivalTime;
}

public int getCpuTime() {
return cpuTime;
}

public void setCpuTime(int cpuTime) {
this.cpuTime = cpuTime;
}

public int getProcessId() {
return processId;
}

public void setProcessId(int processId) {
this.processId = processId;
}

}

JobFinishEvent.java

public interface JobFinishEvent {
public void onFinish(Job j);
}

Question1.java

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Question1 {

public static void main(String[] args) {
// Process command line arguments

Scanner sc = new Scanner(System.in);
Scanner sc1 = new Scanner(System.in);
Scanner sc2 = new Scanner(System.in);

String filename ;
String allocationStrategy;
int quantum=20;

/*filename = args[0];
allocationStrategy = args[1];*/

filename = "testing.txt";
allocationStrategy = "FCFS";

//filename = sc.nextLine();

if(args.length==3){
quantum = new Integer(args[2]);
}

try {

String sCurrentLine;

//System.out.println("processId  arrivalTime  cpuTime");

List<Job> jobList = new ArrayList<Job>();
while ((sCurrentLine = br.readLine()) != null) {

String a[] = sCurrentLine.split(",");
int processId = new Integer(a[0]);
int arrivalTime = new Integer(a[1]);
int cpuTime = new Integer(a[2]);

Job job = new Job(processId,arrivalTime,cpuTime);

//System.out.println(processId+" "+ arrivalTime+" " + cpuTime);
}

if("FCFS".equalsIgnoreCase(allocationStrategy)){

FirstComeFirstServed firstComeFirstServed = new FirstComeFirstServed(jobList);
firstComeFirstServed.run(jobList);

}else if("SRT".equalsIgnoreCase(allocationStrategy)){

ShortestRemainingTime shortestRemainingTime = new ShortestRemainingTime(jobList);
shortestRemainingTime.run(jobList);

}else if("RR".equalsIgnoreCase(allocationStrategy)){

RoundRobin roundRobin = new RoundRobin();
roundRobin.run(jobList,quantum);

}

} catch (IOException e) {
e.printStackTrace();
} finally {
try {
if (br != null)br.close();
} catch (IOException ex) {
ex.printStackTrace();
}
}

JobFinishEvent callback = new JobFinishEvent() {
@Override
public void onFinish(Job j) {
// this will be called when a job is finished.
}
};

ArrayList jobs = new ArrayList();
RoundRobin rr = new RoundRobin(jobs);
rr.run();
*/
}

}
```