CPU scheduling treats with the issues of deciding which of the processes in the ready queue needs to be allocated to the CPU. There are several different CPU scheduling algorithms used nowadays within an operating system.
In this post, we will discuss the Highest Response Ratio Next (HRRN) preemptive Process Scheduling algorithm and also write a program for the Highest Response Ratio Next (HRRN) preemptive Process Scheduling algorithm. In the Highest Response Ratio Next (HRRN) algorithm, the scheduling is done on the basis of an extra parameter called Response Ratio. A Response Ratio is calculated for each of the available jobs and the Job with the highest response ratio is given priority over the others.
Response Ratio is calculated by the given formula:
Response Ratio = (W+S)/S W → Waiting Time S → Service Time or Burst Time
We will use C++ to write this algorithm due to the standard template library support. Hence, we will write the program of the Highest Response Ratio Next algorithm in C++, although, it’s very similar to C.
INPUT:
The first line is the number of processes(nop).
The next nop lines contain three variables: process name(pname), arrival time(atime) and burst time(btime).
OUTPUT:
Print the matrix for process name, arrival time, burst time, completion time, turn around time, waiting time and response time.
Also, print the Gantt chart.
The following is the HRRN Process Scheduling program in C++.
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
char pname[50];
int btime;
int atime;
int wtime;
float rr=0;
}a[50];
void insert(int n){
int i;
for(i=0;i<n;i++){
cin>>a[i].pname;
cin>>a[i].atime;
cin>>a[i].btime;
a[i].rr=0;
a[i].wtime=-a[i].atime;
}
}
bool btimeSort(node a,node b){
return a.btime < b.btime;
}
bool atimeSort(node a,node b){
return a.atime < b.atime;
}
bool rrtimeSort(node a,node b){
return a.rr > b.rr;
}
void disp(int n){
sort(a,a+n,btimeSort);
sort(a,a+n,atimeSort);
int ttime=0,i;
int j,tArray[n];
for(i=0;i<n;i++){
j=i;
while(a[j].atime<=ttime&&j!=n){
j++;
}
for(int q = i;q<j;q++){
a[q].wtime=ttime-a[q].atime;
a[q].rr=(float)(a[q].wtime+a[q].btime)/(float)a[q].btime;
}
sort(a+i,a+j,rrtimeSort);
tArray[i]=ttime;
cout<<endl;
ttime+=a[i].btime;
}
tArray[i] = ttime;
float averageWaitingTime=0;
float averageResponseTime=0;
float averageTAT=0;
cout<<"\n";
cout<<"P.Name AT\tBT\tCT\tTAT\tWT\tRT\n";
for (i=0; i<n; i++){
cout <<'P'<< a[i].pname << "\t";
cout << a[i].atime << "\t";
cout << a[i].btime << "\t";
cout << tArray[i+1] << "\t";
cout << tArray[i]-a[i].atime+a[i].btime << "\t";
averageTAT+=tArray[i]-a[i].atime+a[i].btime;
cout << a[i].wtime << "\t";
averageWaitingTime+=tArray[i]-a[i].atime;
cout << tArray[i]-a[i].atime << "\t";
averageResponseTime+=tArray[i]-a[i].atime;
cout <<"\n";
}
cout<<"\n";
cout<<"\nGantt Chart\n";
for (i=0; i<n; i++){
cout <<"| P"<< a[i].pname << " ";
}
cout<<"\n";
for (i=0; i<n+1; i++){
cout << tArray[i] << "\t";
}
cout<<"\n";
cout<<"Average Response time: "<<(float)averageResponseTime/(float)n<<endl;
cout<<"Average Waiting time: "<<(float)averageWaitingTime/(float)n<<endl;
cout<<"Average TA time: "<<(float)averageTAT/(float)n<<endl;
}
int main(){
int nop,choice,i;
cout<<"Enter number of processes\n";
cin>>nop;
insert(nop);
disp(nop);
return 0;
}
OUTPUT:
Enter number of processes 5 1 0 5 2 1 2 3 2 4 4 3 1 5 4 7 P.Name AT BT CT TAT WT RT P1 0 5 5 5 0 0 P2 1 2 7 6 4 4 P4 3 1 8 5 4 4 P3 2 4 12 10 6 6 P5 4 7 19 15 8 8 Gantt Chart | P1 | P2 | P4 | P3 | P5 0 5 7 8 12 19 Average Response time: 4.4 Average Waiting time: 4.4 Average TA time: 8.2
Other process scheduling algorithms
- SJF (Non-preemptive) Process Scheduling
- HRRN (Preemptive) Process Scheduling
- Round Robin Process Scheduling
- Priority Scheduling (preemptive)
- LRTF Process Scheduling
- SJF (preemptive) Process Scheduling
Let us know in the comments if you are having any questions regarding this Highest Response Ratio Next Processing Scheduling algorithm.
And if you found this post helpful, then please help us by sharing this post with your friends. Thank You
