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.
Now it's time to take a look at an example for the same:
Here, we have several processes with different burst and arraival times, and a Gantt chart to represent CPU allocation time.
The Gantt Chart according to HRRN will be:
Explanation
Given below is the explanation of the above example
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.
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
In the table given below, we will calculate turn around time, waiting time, and completion time for all the Processes.
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
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[10];
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[0].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
Advantages of HRNN Scheduling
The advantages of the HRNN scheduling algorithm are as follows:
Disadvantages of HRNN Scheduling
The disadvantages of the HRNN scheduling algorithm are as follows:
10 videos|99 docs|33 tests
|
|
Explore Courses for Computer Science Engineering (CSE) exam
|