Overview
Highest Response Ratio Next is a nonpreemptive scheduling rule that balances short-job preference with aging. A job's priority rises as it waits, reducing starvation compared with shortest-job-first.
CoreSource checked
Highest Response Ratio Next
Chooses the ready job with the largest ratio of waiting time plus service time to service time.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Scheduling
- Difficulty
- Intermediate
- Family
- CPU Scheduling
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
non-preemptive schedulingcpu schedulingscheduling
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n log n)
Worst
O(n^2)
Space
O(n)
When to Use
- Use when job durations are known or estimated and starvation should be reduced.
- Use when nonpreemptive dispatch is acceptable.
When Not to Use
- Avoid when hard deadlines or preemption are required.
- Avoid when service-time estimates are too inaccurate to rank jobs reliably.
What It Does
- Computes response ratio for each ready job
- Selects the job with the highest ratio
- Runs the selected job nonpreemptively to completion
Use Cases
- Batch scheduling where both waiting time and job duration matter
- Teaching aging as a starvation-reduction technique
- Comparing nonpreemptive CPU scheduling policies
Inputs
- Ready queue of processes with arrival times, burst estimates, and waiting times
- CPU time-slice or preemption policy
Outputs
- Next scheduled process selection
- Updated waiting, turnaround, and response-time statistics
Pseudocode
- 1.At each dispatch point, collect ready jobs
- 2.For each ready job, compute response ratio
- 3.Choose the job with the highest ratio
- 4.Run it to completion
- 5.Advance time and repeat until all jobs finish
Canonical Example
- Input
- at time 5, A waited 4 with service 4; B waited 2 with service 1
- Output
- run B
- Explanation
- A has ratio 2.0, while B has ratio 3.0, so B is selected.
Implementation Notes
- For each ready job, compute (waiting time + service time) / service time.
- Recompute ratios whenever the scheduler chooses the next job.
- Use deterministic tie-breaking for equal ratios.
Common Pitfalls
- Using arrival time instead of waiting time gives wrong priorities.
- Recomputing ratios only once ignores the aging behavior.
- Treating HRRN as preemptive changes the policy.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow choosing the job with the highest response ratio of waiting and service time on a small non-preemptive scheduling example.
Step 1 of 5: At each dispatch point, collect ready jobs
scheduling-mechanismNotes
HRRN reduces starvation by increasing priority as jobs wait, but it still depends on service-time estimates.
Sources (1)
What each reference supports for this entry.
Operating System Concepts
BookOperating-systems reference for Highest Response Ratio Next scheduling, response-ratio priority, and short-job fairness tradeoffs.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toRound Robin Scheduling
Scheduling · Foundation
HRRN ranks ready jobs by response ratio rather than cycling through fixed time quanta.
Compare with thisRelationships
View full relationship pageAlternative toShortest Job First
HRRN modifies shortest-job-first behavior by raising priority as waiting time grows.
Alternative toRound Robin Scheduling
HRRN ranks ready jobs by response ratio rather than cycling through fixed time quanta.
Related Algorithms
Tags
Scheduling