HRRN (Highest Response Ratio Next) Scheduling Algorithm: Prioritizing Processes Based on Response Ratio

Understand the Highest Response Ratio Next (HRRN) scheduling algorithm and how it prioritizes processes based on their response ratio (waiting time + burst time) / burst time. This guide provides a step-by-step example illustrating HRRN scheduling and calculating average waiting time.

HRRN (Highest Response Ratio Next) Scheduling Algorithm Example

Understanding the HRRN Algorithm

The Highest Response Ratio Next (HRRN) scheduling algorithm is a preemptive priority scheduling algorithm that takes into account both waiting time and burst time to prioritize processes. The response ratio (RR) is calculated as: RR = (Waiting Time + Burst Time) / Burst Time. The process with the highest response ratio is selected to run next. This approach aims to balance fairness (giving shorter jobs quicker service) with overall efficiency.

HRRN Example Walkthrough

Let's walk through an example with five processes:

Process ID Arrival Time Burst Time
P0 0 3
P1 2 5
P2 4 4
P3 6 1
P4 8 2
  1. Time 0-3: P0 runs (only process available).
  2. Time 3-8: P1 runs (only process available after P0 completes).
  3. Time 8: All processes are now in the ready queue. We calculate the response ratios:
    • RR(P2) = (8 - 4 + 4) / 4 = 2
    • RR(P3) = (2 + 1) / 1 = 3
    • RR(P4) = (0 + 2) / 2 = 1
  4. Time 8-9: P3 runs (highest RR).
  5. Time 9: We recalculate the response ratios for P2 and P4:
    • RR(P2) = (9 - 4 + 4) / 4 = 2.25
    • RR(P4) = (1 + 2) / 2 = 1.5
  6. Time 9-13: P2 runs (highest RR).
  7. Time 13-15: P4 runs (only remaining process).

Results

Process ID Arrival Time Burst Time Completion Time Turnaround Time Waiting Time
P0 0 3 3 3 0
P1 2 5 8 6 1
P2 4 4 13 9 5
P3 6 1 9 3 2
P4 8 2 15 7 5

Average Waiting Time: (0 + 1 + 5 + 2 + 5) / 5 = 2.6