Round Robin Algorithm with implementation in Java

(269 Views)


Round Robin is a very popular CPU scheduling algorithm. A CPU scheduling algorithm is nothing but an algorithm which schedules the processes based on their arrival time, burst time and CPU's time quantum. Arrival time of a process, as the name signifies, is the time at which the process came for scheduling. Burst time of a process is the time required for it to complete. And time quantum is the time limit which is set by the cpu, one process can run for at max t units of time or time quantum.

Why do we need scheduling algorithm anyway ?

We do multi tasking on our machines, we download a movie from the internet, play music, and do programming, all at the same time. But our computer don't have many cores, to take multiple requests. Our CPU uses context-switching to overcome the problem of lack of processing cores / processors. It might seem to us that all the processes are executing in parallel, but they are not. CPU's scheduling algorithm runs one process for some time, halts it, and runs other process for some time. This context switching is so fast that it seems that all the processes are running in parallel.

You might wonder that why don't we have multiple processors. Well we can have multiple processors, but it would be waste of money and most of the time our processors would be in idle condition.

Round robin scheduling algorithm

Multiple processes come to the CPU for scheduling, these processes have their arrival time and burst time. The processes are entertained on the basis of their arrival time, i.e, the process which has less arrival time means that the process came early and should be processed first as per first come first serve rule.

Consider these processes:

Round Robin Algorithm

Now we have something called the "Ready queue" and "Running queue" in which processes are added. When Arrival time of CPU matches the CPU time, the process is ready to be processed and hence, added to the ready queue. For example, process p1 has arrival time 0, So currently our ready queue will have process p0.
Lets set the time quantum to 2 units.
After 2 units of time, process p2 will arrive and then it will be added to the ready queue
Ready queue is used to see the processes which have arrived, and processing is done in the "running queue".

Algorithm for Round Robin
After 2 units of time, process p2 and p3 will be ready for processing, so we can add them to ready queue. And since p1 is processed for 2 time quantums, its burst time will be reduced to 3.
Round Robin Pseudocode
Notice that p1 is not yet complete, so we need to add it to ready queue again.
After 2 more time units, p2 will stop executing and p3 will come into running queue.
Round Robin Algorithm in Java
Now its p3's turn to execute. Since burst time of p3 is 2, it will completely execute, and will not be added to the ready queue again.
Java Program for demonstrating round robin algorithm

There's one more point to notice, process p4 has burst time of 1 units. So execution will happen for 1 unit, not 2 units which is the CPU's burst time.
In this way, all the processes execute until they have their burst time of 0 units.

Through this algorithm, we usually calculate the average waiting time and average turn-around time. Turn around time is Time Difference between completion time and arrival time. And waiting time is Time Difference between turn around time and burst time.

Pseudocode

  • Create an array of arrival time ar_time[] which keeps track of arrival time of process Pi
  • Create another array of burst time br_time[] which keeps track of remaining burst time
  • Initialize CPU time to 0; t = 0
  • Repeat these steps until ready queue is empty
    • if br_time[i] > quantum, t = t + quantum, br_time[i] -= quantum
    • else t = t + br_time[i], br_time = 0

Java Code

import java.io.*; class round{ public static void main(String args[])throws IOException{ DataInputStream in=new DataInputStream(System.in); int i,j,k,q,sum=0; System.out.println("Enter number of process:"); int n=Integer.parseInt(in.readLine()); int bt[]=new int[n]; int wt[]=new int[n]; int tat[]=new int[n]; int a[]=new int[n]; System.out.println("Enter brust Time:"); for(i=0;i<n;i++){ System.out.println("Enter brust Time for "+(i+1)); bt[i]=Integer.parseInt(in.readLine()); } System.out.println("Enter Time quantum:"); q=Integer.parseInt(in.readLine()); for(i=0;i<n;i++) a[i]=bt[i]; for(i=0;i<n;i++) wt[i]=0; do{ for(i=0;i<n;i++){ if(bt[i]>q){ bt[i]-=q; for(j=0;j<n;j++){ if((j!=i)&&(bt[j]!=0)) wt[j]+=q; } } else{ for(j=0;j<n;j++){ if((j!=i)&&(bt[j]!=0)) wt[j]+=bt[i]; } bt[i]=0; } } sum=0; for(k=0;k<n;k++) sum=sum+bt[k]; } while(sum!=0); for(i=0;i<n;i++) tat[i]=wt[i]+a[i]; System.out.println("process\t\tBT\tWT\tTAT"); for(i=0;i<n;i++){ System.out.println("process"+(i+1)+"\t"+a[i]+"\t"+wt[i]+"\t"+tat[i]); } float avg_wt=0; float avg_tat=0; for(j=0;j<n;j++){ avg_wt+=wt[j]; } for(j=0;j<n;j++){ avg_tat+=tat[j]; } System.out.println("average waiting time "+(avg_wt/n)+"\n Average turn around time"+(avg_tat/n)); } }

Solution Worked 0 UpvotesUpvote

        

Solution Didn't Worked 0 DownvotesDownvote



Comments



Search