Highest Response Ratio Next (HRRN) scheduling, explained

Highest Response Ratio Next tries to get the benefits of SJF without its main problem. For every waiting process it calculates a response ratio and runs the one with the highest value.

The ratio is (waiting time + burst time) divided by burst time. A short job has a high ratio, and the longer any process waits, the higher its ratio grows.

How it works

• When the CPU is free, work out the response ratio for every waiting process.
• Pick the process with the highest ratio.
• Run it until it finishes. This version cannot be interrupted.
• Repeat until all processes are done.

A small example

Four processes, A to D:

Arrival times: 0 2 4 5
Burst times:   7 4 1 4

When A finishes at time 7, the ratios are B: (5 + 4) / 4 = 2.25, C: (3 + 1) / 1 = 4 and D: (2 + 4) / 4 = 1.5. So C runs first. The average waiting time is:

4.0 time units

If B and D keep waiting, their ratios keep growing until they win.

What to know about its cost

• It is non-preemptive.
• It needs the burst times, like SJF.
• It avoids starvation, because waiting always raises the ratio.

Where it works well

• Good average waiting time.
• Long processes eventually get their turn.

Where it struggles

• It must calculate a ratio for every waiting process at every decision.
• It needs burst times in advance.

Try it yourself

Open the CPU Scheduling experiment, enter the processes from this post, choose Highest Response Ratio Next and step through the Gantt chart. Then try the other algorithms on the same processes and compare the averages.

Open the CPU Scheduling experiment