Highest Response Ratio Next (HRRN) scheduling is a non-preemptive discipline, in which the priority of each job is dependent on its estimated run time, and also the amount of time it has spent waiting. Jobs gain higher priority the longer they wait, which prevents indefinite postponement (process starvation).

It selects a process with the largest ratio of waiting time over service time. This guarantees that a process does not starve due to its requirements.

In fact, the jobs that have spent a long time waiting compete against those estimated to have short run times.

Priority = (waiting time + estimated runtime) / estimated runtime

                                            (Or)

Response Ratio = (waiting time + service time) / service time

Advantages

  • Improves upon SPF scheduling
  • Still non-preemptive
  • Considers how long process has been waiting
  • Prevents indefinite postponement

Disadvantages

  • Does not support external priority system. Processes are scheduled by using internal priority system

Example:

Q1. Consider the Processes with following Arrival time, Burst Time and priorities

Process Arrival Time Burst Time Priority
P1 0 7 3(high)
P2 2 4 1(low)
P3 3 4 2
Solution: HRRN

At time 0 only process p1 is available, so p1 is considered for execution

Since it is Non-preemptive, it executes process p1 completely. It takes 7 ms to complete process p1 execution.

Now, among p2 and p3 the process with highest response ratio is chosen for execution.

Response Ration for P2  = (5+4)/4 = 2.25

Response Ration for P3  = (4+4)/4 = 2

As process p2 is having highest response ratio than that of p3. Process p2 will be considered for execution and then followed by P3.

Average Waiting Time  =  0+(7-2) +(11-3) / 3  = 4.33

Average Turunaround Time  = 7 + (11-2) +(15-3) /3  = 9.33

Q2. Consider the Processes with following Arrival time, Burst Time and priorities 

Process Arrival Time Burst Time
P1 0 3
P2 2 6
P3 4 4
P4 6 5
P5 8 2
  • At time 0 only process p1 is available, so p1 is considered for execution
  • At time 3 only process p2 is available, so p2 is considered for execution
  • Since at time 9 all process has arrived so we have to calculate Response Ratio for these process
P1 P2

3             9           13

Response Ratio for P3 = (5 + 4)/4 = 2.25

Response Ratio for P4 = (3 + 5)/5 = 1.6

Response Ratio for P5 = (1+2)/2 = 1.5

P1 P2 P3

3                    9                     13                   15

Response Ratio for P4= (7+ 5)/5= 2.4

Response Ratio for P5 = (5+2)/2 = 3.5

P1 P2 P3 P5 P4

                       3                     9                     13                   15                 20