Dark Mode On/Off

# Highest Response Ratio Next (HRRN) Scheduling

HRRN(Highest Response Ratio Next )Scheduling is a non-preemptive scheduling algorithm in the operating system. It is one of the optimal algorithms used for scheduling.

As HRRN is a non-preemptive scheduling algorithm so in case if there is any process that is currently in execution with the CPU and during its execution, if any new process arrives in the memory with burst time smaller than the currently running process then at that time the currently running process will not be put in the ready queue & complete its execution without any interruption.

HRRN is basically the modification of Shortest Job Next(SJN) in order to reduce the problem of starvation.

In the HRRN scheduling algorithm, the CPU is assigned to the next process that has the highest response ratio and not to the process having less burst time.

Now, let us first take a look at how to calculate the Response ratio.

Response Ratio = (W+S)/S

Where,

W=It indicates the Waiting Time.

S=It indicates the Service time that is Burst Time.

## Algorithm of HRNN

• In the HRNN scheduling algorithm, once a process is selected for execution will run until its completion.

• The first step is to calculate the waiting time for all the processes. Waiting time simply means the sum of the time spent waiting in the ready queue by processes.

• Processes get scheduled each time for execution in order to find the response ratio for each available process.

• Then after the process having the highest response ratio is executed first by the processor.

• In a case, if two processes have the same response ratio then the tie is broken using the FCFS scheduling algorithm.

Now it's time to take a look at an example for the same:

## HRRN Scheduling Example

Here, we have several processes with different burst and arraival times, and a Gantt chart to represent CPU allocation time.   ### Explanation

Given below is the explanation of the above example

• At time=0 there is no process available in the ready queue, so from 0 to 1 CPU is idle. Thus 0 to 1 is considered as CPU idle time.

• At time=1, only the process P1 is available in the ready queue. So, process P1 executes till its completion.

• After process P1, at time=4 only process P2 arrived, so the process P2 gets executed because the operating system did not have any other option.

• At time=10, the processes P3, P4, and P5 were in the ready queue. So in order to schedule the next process after P2, we need to calculate the response ratio.

• In this step, we are going to calculate the response ratio for P3, P4, and P5.

Response Ratio = W+S/S

RR(P3) = [(10-5) +8]/8

= 1.625

RR(P4) = [(10-7) +4]/4

= 1.75

RR(P5) = [(10-8) +5]/5

= 1.4

From the above results, it is clear that Process P4 has the Highest Response ratio, so the Process P4 is schedule after P2.

• At time t=10, execute process P4 due to its large value of Response ratio.

• Now in the ready queue, we have two processes P3 and P5, after the execution of P4 let us calculate the response ratio of P3 and P5

RR (P3) = [(14-5) +8]/8

=2.125

RR (P5) = [(14-8) +5]/5

=2.2

From the above results,it is clear that Process P5 has the Highest Response ratio, so the Process P5 is schedule after P4

• At t=14, process P5 is executed.

• After the complete execution of P5, P3 is in the ready queue so at time t=19 P3 gets executed.

In the table given below, we will calculate turn around time, waiting time, and completion time for all the Processes.

Process Arrival Time Burst Time Completion time

Turn around Time

Turn Around Time = Completion Time – Arrival Time

Waiting Time

Waiting Time = Turn Around Time – Burst Time

P1 1 3 4 4-1=3 3-3=0
P2 3 6 10 10-3=7 7-6=1
P3 5 8 27 27-5=22 22-8=14
P4 7 4 14 14-7=7 7-4=3
P5 8 5 19 19-8=11 11-5=6

Average waiting time is calculated by adding the waiting time of all processes and then dividing them by no. of processes.

average waiting time = waiting time of all processes/ no.of processes

average waiting time=0+1+14+3+6/5=24/5 = 4.8ms

## HRRN Scheduling Example in C Language

Given below is the C program for HRRN Scheduling:

``````// C program for the Highest Response Ratio Next (HRRN) Scheduling
#include <stdio.h>

// This structure defines the details of the process
struct process {
char name;
int at, bt, ct, wt, tt;
int complete;
float ntt;
} p;

int m;

//The Sorting of Processes by Arrival Time
void sortByArrival()
{
struct process temp;
int i, j;

// Selection Sort applied
for (i = 0; i < m - 1; i++) {
for (j = i + 1; j < m; j++) {

// This condition is used to Check for the lesser arrival time
if (p[i].at > p[j].at) {

// Swaping of earlier process to front
temp = p[i];
p[i] = p[j];
p[j] = temp;
}
}
}
}

void main()
{
int i, j, t, sum_bt = 0;
char c;
float avgwt = 0, avgtt = 0;
m = 5;

// the predefined arrival times
int arriv[] = { 1, 3, 5, 7, 8 };

// the predefined burst times
int burst[] = { 3, 7, 8, 4, 2};

// Initialize the structure variables
for (i = 0, c = 'A'; i < m; i++, c++) {
p[i].name = c;
p[i].at = arriv[i];
p[i].bt = burst[i];

// Variable for Completion status
// for Pending = 0
// for Completed = 1
p[i].complete = 0;

// the Variable for the sum of all Burst Times
sum_bt += p[i].bt;
}

// Let us Sort the structure by the arrival times
sortByArrival();
printf("\nName\tArrival Time\tBurst Time\tWaiting Time");
printf("\tTurnAround Time\t Normalized TT");
for (t = p.at; t < sum_bt;) {

// Now Set the lower limit to response ratio
float hrr = -9999;

//The Response Ratio Variable
float temp;

// Variable used to store the next processs selected
int loc;
for (i = 0; i < m; i++) {

// Check if the process has arrived and is Incomplete
if (p[i].at <= t && p[i].complete != 1) {

// Calculating the Response Ratio
temp = (p[i].bt + (t - p[i].at)) / p[i].bt;

// Checking for the Highest Response Ratio
if (hrr < temp) {

// Storing the Response Ratio
hrr = temp;

// Storing the  Location
loc = i;
}
}
}

// Updating the time value
t += p[loc].bt;

// Calculation of the waiting time
p[loc].wt = t - p[loc].at - p[loc].bt;

// Calculation of the Turn Around Time
p[loc].tt = t - p[loc].at;

// Sum of Turn Around Time for the average
avgtt += p[loc].tt;

// Calculation of the Normalized Turn Around Time
p[loc].ntt = ((float)p[loc].tt / p[loc].bt);

// Updating  the Completion Status
p[loc].complete = 1;

// Sum of the Waiting Time to calculate the average
avgwt += p[loc].wt;
printf("\n%c\t\t%d\t\t", p[loc].name, p[loc].at);
printf("%d\t\t%d\t\t", p[loc].bt, p[loc].wt);
printf("%d\t\t%f", p[loc].tt, p[loc].ntt);
}
printf("\nThe Average waiting time:%f\n", avgwt / m);
printf("The Average Turn Around time:%f\n", avgtt / m);
} ``````

### Output The advantages of the HRNN scheduling algorithm are as follows:

1. HRRN Scheduling algorithm gives better performance than the shortest job first Scheduling.

2. With this algorithm, there is a reduction in waiting time for longer jobs and also it encourages shorter jobs.

3. With this algorithm, the throughput increases.