Highest Response Ratio Next (HRRN)
Highest Response Ratio Next (HRRN) is a non-preemptive scheduling algorithm designed as an improvement over Shortest Job First (SJF). While SJF is optimal for minimizing waiting times, it has a fatal flaw: long jobs can suffer from starvation if short jobs keep arriving.
HRRN solves this by considering both the job's burst time AND how long it has been waiting in the queue. It calculates a 'Response Ratio' for every process in the ready queue, and the CPU is allocated to the process with the highest ratio.
Real-Life Example
Imagine an IT tech support desk. If someone needs a 1-minute password reset (a short job), they usually get priority so they can get out of the way. However, if someone with a massive 2-hour server configuration issue has been sitting in the waiting room all day, the staff will eventually feel bad for them and bump their priority up. In HRRN, the "pity factor" is mathematically calculated—the longer you wait, the higher your response ratio gets until you finally become the top priority!
Example 1: Balancing Short Jobs and Wait Times
Because HRRN relies heavily on Waiting Time, it is best demonstrated with processes that arrive at different times. Let's look at a scenario:
| Process | Arrival Time (ms) | Burst Time (ms) |
|---|---|---|
| P1 | 0 | 3 |
| P2 | 2 | 6 |
| P3 | 4 | 4 |
| P4 | 6 | 5 |
| P5 | 8 | 2 |
Here is how the HRRN algorithm makes its decisions step-by-step:
1. At time 0, only P1 has arrived. It executes until time 3.
2. At time 3, only P2 has arrived (it arrived at 2). It executes until time 9.
3. At time 9, P3, P4, and P5 are all in the ready queue. We must calculate their Response Ratios (RR) using the formula (Wait + Burst) / Burst.
- P3 wait = 9 - 4 = 5. RR = (5 + 4) / 4 = 2.25
- P4 wait = 9 - 6 = 3. RR = (3 + 5) / 5 = 1.60
- P5 wait = 9 - 8 = 1. RR = (1 + 2) / 2 = 1.50
P3 has the highest RR (2.25), so it executes next until time 13.
4. At time 13, P4 and P5 remain. We recalculate their ratios:
- P4 wait = 13 - 6 = 7. RR = (7 + 5) / 5 = 2.40
- P5 wait = 13 - 8 = 5. RR = (5 + 2) / 2 = 3.50
Now, P5 has the highest RR (3.50), so it executes until time 15.
5. P4 is the only one left, executing from 15 to 20.
Here is the Gantt chart:
+----+--------+------+--+-----+
| P1 | P2 | P3 |P5| P4 |
+----+--------+------+--+-----+
0 3 9 13 15 20Let's calculate the Waiting Time (Start Time - Arrival Time):
- P1: 0 - 0 = 0 ms.
- P2: 3 - 2 = 1 ms.
- P3: 9 - 4 = 5 ms.
- P4: 15 - 6 = 9 ms.
- P5: 13 - 8 = 5 ms.
Average Waiting Time = (0 + 1 + 5 + 9 + 5) / 5 = 4 ms.
Let's calculate the Turnaround Time (Completion Time - Arrival Time):
- P1: 3 - 0 = 3 ms.
- P2: 9 - 2 = 7 ms.
- P3: 13 - 4 = 9 ms.
- P4: 20 - 6 = 14 ms.
- P5: 15 - 8 = 7 ms.
Average Turnaround Time = (3 + 7 + 9 + 14 + 7) / 5 = 8 ms.
Example 2: Handling Ties
What happens if two processes have the exact same Response Ratio? The standard protocol is to use First-Come, First-Served (FCFS) to break the tie.
| Process | Arrival Time (ms) | Burst Time (ms) |
|---|---|---|
| P1 | 0 | 5 |
| P2 | 1 | 4 |
| P3 | 3 | 2 |
| P4 | 4 | 3 |
1. At time 0, P1 starts and runs until time 5.
2. At time 5, P2, P3, and P4 are in the queue. Let's check their ratios:
- P2 wait = 5 - 1 = 4. RR = (4 + 4) / 4 = 2.00
- P3 wait = 5 - 3 = 2. RR = (2 + 2) / 2 = 2.00
- P4 wait = 5 - 4 = 1. RR = (1 + 3) / 3 = 1.33
P2 and P3 are tied with a ratio of 2.00. Because P2 arrived first (at 1 ms), it wins the tiebreaker and runs until time 9.
3. At time 9, P3 and P4 remain:
- P3 wait = 9 - 3 = 6. RR = (6 + 2) / 2 = 4.00
- P4 wait = 9 - 4 = 5. RR = (5 + 3) / 3 = 2.66
P3 runs until time 11. Finally, P4 runs from 11 to 14.
Here is the Gantt chart:
+---------+--------+----+-----+
| P1 | P2 | P3 | P4 |
+---------+--------+----+-----+
0 5 9 11 14Let's calculate the Waiting Time (Start Time - Arrival Time):
- P1: 0 - 0 = 0 ms.
- P2: 5 - 1 = 4 ms.
- P3: 9 - 3 = 6 ms.
- P4: 11 - 4 = 7 ms.
Average Waiting Time = (0 + 4 + 6 + 7) / 4 = 4.25 ms.
Let's calculate the Turnaround Time (Completion Time - Arrival Time):
- P1: 5 - 0 = 5 ms.
- P2: 9 - 1 = 8 ms.
- P3: 11 - 3 = 8 ms.
- P4: 14 - 4 = 10 ms.
Average Turnaround Time = (5 + 8 + 8 + 10) / 4 = 7.75 ms.
Advantages of HRRN
- Completely eliminates starvation since long jobs gain priority as they wait.
- Favors shorter jobs, providing excellent throughput similar to SJF.
- Provides a very fair middle-ground between Shortest Job First and First-Come, First-Served.
Disadvantages of HRRN
- Extremely high system overhead because Response Ratios must be dynamically recalculated for every waiting process every single time the CPU becomes free.
- It is non-preemptive, making it totally unsuitable for interactive or time-sharing systems.
- Like SJF, it relies on knowing the burst time of a process in advance, which is practically impossible to predict with 100% accuracy.
Calculate the Response Ratio
Question 1 of 1Test your HRRN math skills with a quick calculation.