Loading learning content...
In our study of CPU scheduling, we've encountered a fundamental tension: algorithms optimized for efficiency often sacrifice fairness.
Shortless Job First (SJF) achieves the theoretical minimum average waiting time—but at a terrible cost. In systems with continuous arrivals of short jobs, long jobs can wait indefinitely. This phenomenon, called starvation or indefinite postponement, represents a critical failure mode that no production system can tolerate.
Consider a web server handling both quick API calls (burst ≈ 10ms) and complex report generations (burst ≈ 5 seconds). Under pure SJF:
This isn't a theoretical concern—it's a system design failure that manifests in production systems daily.
Highest Response Ratio Next (HRRN) elegantly resolves this tension. It maintains much of SJF's efficiency while guaranteeing that no process waits forever. The key insight: priority should depend not just on burst time, but also on how long a process has been waiting.
By the end of this page, you will understand HRRN's core philosophy and response ratio concept, derive and interpret the response ratio formula, trace through HRRN execution with precision, analyze its strengths and weaknesses, and implement HRRN in code. HRRN represents a breakthrough in balancing competing scheduling objectives.
HRRN was developed by Brinch Hansen in 1971 as a solution to SJF's starvation problem. The algorithm introduces a dynamic priority metric called the Response Ratio.
Intuition:
The response ratio answers a simple question: "If we schedule this process now, what will its response ratio be?" The response ratio captures both:
These factors combine to create a balanced priority that automatically favors short jobs while guaranteeing long jobs eventually rise in priority.
Key Properties:
Initially, response ratio depends on burst time: New arrivals have zero waiting time, so their ratio equals 1. Shorter burst times don't affect initial priority.
Over time, waiting dominates: As a process waits, its response ratio grows. Eventually, even a very long job achieves higher priority than newly arrived short jobs.
Short jobs still tend to run first: If two processes have waited the same amount, the shorter one has a higher ratio.
No process waits forever: Since waiting time increases unboundedly while burst time is fixed, every process eventually reaches the highest priority.
HRRN elegantly unifies two seemingly contradictory goals: favoring short jobs (for efficiency) and favoring old jobs (for fairness). The response ratio formula achieves this through a simple ratio that automatically balances both factors based on system state.
The response ratio is defined precisely as:
Response Ratio = (Waiting Time + Burst Time) / Burst Time
Or equivalently:
Response Ratio = 1 + (Waiting Time / Burst Time)
Let's denote:
Then: R = (W + S) / S = 1 + W/S
| Component | Symbol | Meaning | Source |
|---|---|---|---|
| Waiting Time | W | Time in ready queue since arrival | Dynamic (increases over time) |
| Service Time | S | Total CPU burst time needed | Static (fixed at arrival) |
| Response Ratio | R | Dynamic priority for scheduling | Computed at each decision point |
Formula Analysis:
1. Minimum Value: When a process first arrives (W = 0):
2. Growth Rate: For each unit of time waiting:
3. Comparison Dynamics: Compare two processes:
Process A wins despite same wait time—short jobs are still favored.
But now consider:
Process B wins—long wait compensates for long burst.
The response ratio can be interpreted as the ratio of total response time (if scheduled now) to service time. Higher ratios indicate processes that have waited "longer relative to their size"—a fair metric that naturally balances efficiency and equity.
HRRN is a non-preemptive algorithm. Once a process begins execution, it runs to completion without interruption. Scheduling decisions occur only when:
Algorithm Steps:
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
typedef struct { int pid; int arrival_time; int burst_time; int start_time; int completion_time; float response_ratio; // Computed dynamically} Process; /** * Compute response ratio for a process at given time */float compute_response_ratio(Process* p, int current_time) { int waiting_time = current_time - p->arrival_time; // Ensure waiting time is non-negative if (waiting_time < 0) waiting_time = 0; return (float)(waiting_time + p->burst_time) / p->burst_time;} /** * HRRN Scheduling Algorithm */void hrrn_schedule(Process processes[], int n) { int current_time = 0; int completed = 0; int* is_completed = calloc(n, sizeof(int)); // Sort by arrival time for initial processing sort_by_arrival(processes, n); while (completed < n) { // Find all processes that have arrived int best_index = -1; float highest_ratio = -1.0; for (int i = 0; i < n; i++) { if (is_completed[i]) continue; if (processes[i].arrival_time > current_time) continue; // Compute response ratio for this process float ratio = compute_response_ratio(&processes[i], current_time); processes[i].response_ratio = ratio; // Select process with highest response ratio if (ratio > highest_ratio) { highest_ratio = ratio; best_index = i; } } if (best_index == -1) { // No process ready - find next arrival int next_arrival = INT_MAX; for (int i = 0; i < n; i++) { if (!is_completed[i] && processes[i].arrival_time < next_arrival) { next_arrival = processes[i].arrival_time; } } current_time = next_arrival; continue; } // Execute selected process (non-preemptive) Process* selected = &processes[best_index]; selected->start_time = current_time; current_time += selected->burst_time; selected->completion_time = current_time; is_completed[best_index] = 1; completed++; printf("Time %d: Process P%d selected (RR=%.2f)\n", selected->start_time, selected->pid, highest_ratio); } free(is_completed);}Key Implementation Details:
Ratio Computation Timing: Response ratios must be recomputed at every scheduling decision since waiting times change continuously.
Tie-Breaking: When processes have identical ratios, use FCFS (earliest arrival wins) as a deterministic tiebreaker.
Idle Time Handling: If no process has arrived yet, advance time to the next arrival.
No Preemption: Unlike SRTF, arriving processes don't interrupt execution. Decisions happen only at completion points.
A frequent error is computing response ratios once at arrival and caching them. This defeats the entire purpose of HRRN! Response ratios must be recalculated at every scheduling decision point because waiting times continuously change.
Let's trace HRRN execution step-by-step to build deep intuition.
Process Set:
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0 | 3 |
| P2 | 2 | 6 |
| P3 | 4 | 4 |
| P4 | 6 | 5 |
| P5 | 8 | 2 |
Execution Trace:
Decision Point 1: Time 0
Decision Point 2: Time 3
Decision Point 3: Time 9
Decision Point 4: Time 13
Decision Point 5: Time 15
All processes complete at t=20
Gantt Chart:
| P1 | P2 | P3 | P5 | P4 |
0 3 9 13 15 20
Execution Order: P1 → P2 → P3 → P5 → P4
Notice that P5 (burst=2) was selected before P4 (burst=5) at time 13, even though P4 arrived earlier. This is because P5's shorter burst gave it a higher response ratio despite less waiting time.
| Process | Arrival | Burst | Completion | Turnaround | Waiting | Response Ratio (at selection) |
|---|---|---|---|---|---|---|
| P1 | 0 | 3 | 3 | 3 | 0 | 1.00 |
| P2 | 2 | 6 | 9 | 7 | 1 | 1.17 |
| P3 | 4 | 4 | 13 | 9 | 5 | 2.25 |
| P4 | 6 | 5 | 20 | 14 | 9 | 2.40 |
| P5 | 8 | 2 | 15 | 7 | 5 | 3.50 |
| Average | — | — | — | 8.0 | 4.0 | — |
P4 had the longest burst (5) and waited longest (9 time units) but was still scheduled—it wasn't starved! Under pure SJF with continuous short job arrivals, P4 might never run. HRRN guarantees eventual execution through the aging effect of the response ratio.
How does HRRN compare to SJF (non-preemptive) on the same workload?
SJF Execution for Same Process Set:
Decision Point 1 (t=0): P1 runs (only option) Decision Point 2 (t=3): P2 runs (only option) Decision Point 3 (t=9): P3, P4, P5 available → Select P5 (burst=2, shortest) Decision Point 4 (t=11): P3, P4 available → Select P3 (burst=4, shortest) Decision Point 5 (t=15): Select P4 (only remaining)
SJF Gantt Chart:
| P1 | P2 | P5 | P3 | P4 |
0 3 9 11 15 20
| Metric | HRRN | SJF | Winner |
|---|---|---|---|
| P1 Turnaround | 3 | 3 | Tie |
| P2 Turnaround | 7 | 7 | Tie |
| P3 Turnaround | 9 | 11 | HRRN |
| P4 Turnaround | 14 | 14 | Tie |
| P5 Turnaround | 7 | 3 | SJF |
| Avg Turnaround | 8.0 | 7.6 | SJF (marginally) |
| Avg Waiting | 4.0 | 3.6 | SJF (marginally) |
Analysis:
In this example, SJF performs slightly better (3.6 vs 4.0 average waiting). This is expected—SJF is optimal for minimizing average waiting time. HRRN trades some efficiency for:
When Does the Difference Grow?
The gap between SJF and HRRN is typically small for static workloads. The difference becomes dramatic with:
In these scenarios, SJF starves long jobs completely while HRRN guarantees eventual service.
HRRN represents one of the most elegant points on the fairness-efficiency tradeoff curve. It sacrifices minimal efficiency (often within 10% of optimal) while completely eliminating starvation. This makes it valuable in systems where both metrics matter.
Let's formally analyze HRRN's properties to understand what guarantees it provides.
Proof of Starvation Freedom:
Suppose process P has burst time S and is competing against a stream of arriving processes.
At time t, P's response ratio is:
As t → ∞, W_P(t) → ∞ (if P never runs), so R_P(t) → ∞.
For any newly arriving process Q with burst S_Q:
Since R_P(t) can grow arbitrarily large while R_Q = 1 for new arrivals:
Therefore, every process eventually runs. ∎
HRRN can be viewed as a form of dynamic priority scheduling where priorities automatically age. Unlike static priority schemes, no external intervention is needed to prevent starvation—the algorithm's structure inherently guarantees fair service.
While HRRN has elegant theoretical properties, practical deployment raises several considerations.
The Burst Time Estimation Problem:
Like SJF, HRRN requires knowing burst times in advance. In practice, this knowledge isn't available. Solutions include:
Scheduling Overhead:
At each decision point, HRRN must:
For n=1000 processes, this is negligible. For n=100,000, it may become significant. Production schedulers typically limit active jobs or use approximations.
HRRN's non-preemptive nature means a long job blocks all others once started. For interactive systems requiring sub-second response times, HRRN is unsuitable. It's best suited for batch processing, background tasks, or systems where jobs are relatively short.
HRRN's core idea—using waiting time to dynamically adjust priority—has inspired several variants and extensions:
1. Preemptive HRRN
A theoretical variant where response ratios are rechecked periodically, and running processes can be preempted if a ready process's ratio exceeds the running process's. This addresses the long-job-blocking limitation but adds context switch overhead.
2. Multi-Level HRRN
Combine HRRN with queue separation:
3. Weighted HRRN
Extend the formula to include job priority weights:
R = w × (1 + W/S)
Where w is a user-defined weight. Higher-weight jobs get priority boost, but all jobs still benefit from aging.
4. Deadline-Aware HRRN
For soft real-time systems, incorporate deadline urgency:
R = (1 + W/S) × (1 + α/(D - current_time))
Where D is the deadline and α is a tuning parameter. Jobs approaching deadlines get priority boost.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
"""Weighted HRRN Implementation Allows jobs to have different priority weights whilemaintaining the anti-starvation property.""" class WeightedHRRN: def __init__(self): self.ready_queue = [] self.current_time = 0 def add_process(self, pid, burst_time, arrival_time, weight=1.0): """Add a process with optional priority weight.""" self.ready_queue.append({ 'pid': pid, 'burst_time': burst_time, 'arrival_time': arrival_time, 'weight': weight }) def compute_weighted_ratio(self, process): """Compute weighted response ratio.""" waiting_time = self.current_time - process['arrival_time'] if waiting_time < 0: return 0 # Not yet arrived base_ratio = 1 + (waiting_time / process['burst_time']) return process['weight'] * base_ratio def select_next(self): """Select process with highest weighted response ratio.""" ready = [p for p in self.ready_queue if p['arrival_time'] <= self.current_time] if not ready: return None # Compute ratios and find maximum for p in ready: p['current_ratio'] = self.compute_weighted_ratio(p) return max(ready, key=lambda p: p['current_ratio']) def run(self): """Execute weighted HRRN scheduling.""" schedule = [] while self.ready_queue: selected = self.select_next() if selected is None: # Jump to next arrival next_arrival = min(p['arrival_time'] for p in self.ready_queue) self.current_time = next_arrival continue # Execute process start = self.current_time self.current_time += selected['burst_time'] schedule.append({ 'pid': selected['pid'], 'start': start, 'end': self.current_time, 'ratio': selected['current_ratio'] }) self.ready_queue.remove(selected) return scheduleHRRN represents a milestone in scheduling algorithm design—demonstrating that efficiency and fairness need not be mutually exclusive.
What's Next:
We've now seen the response ratio formula and how it operates. The next page dives deeper into the mathematical properties of this formula, exploring its behavior under various workloads, deriving bounds on performance, and understanding the precise conditions under which HRRN approaches optimal.
You now understand HRRN's philosophy, mechanics, and guarantees. You can trace through HRRN execution, compute response ratios, and explain why the algorithm prevents starvation. Next, we'll formalize the response ratio's mathematical properties.