patternMinor
Highest Response Ratio Next (Scheduling Algorithm)
Viewed 0 times
schedulingresponsenextalgorithmhighestratio
Problem
In CPU scheduling HRRN(Highest Response Ratio Next) algorithm chooses the next process to be scheduled using the formula (W+S)/S where W-> waiting time &
S->Service Time. Can someone share their intuition behind this formula? How does this calculate Highest Response Ratio?
S->Service Time. Can someone share their intuition behind this formula? How does this calculate Highest Response Ratio?
Solution
It's a variation on Shortest Job Next (SJN) and is an attempt to avoid the starvation problems for estimated long running jobs on busy systems with many short running jobs.
When a job has just hit the scheduling queue it's wait time is zero and it's priority is 1. As the wait time increases it's priority is increased by a factor weighted by it's ESTIMATED* run time. Consider 2 processes, one with an estimated run time of 5, the other with 10. Assuming they are placed in the run queue at the same time, both will have an initial priority of 1.
Process A (s=5) priority = 1 + 0/5 = 1
Process B (S=10) priority = 1 + 0/10 = 1
As the processes wait, their priority increases proportional to their expected run time, let's say both have waited an interval of 10:
Process A (S=5) priority = 1 + 10/5 = 3
Process B (S=10) priority = 1 + 10/10 = 2
As you can see the priorities of each process increase, but at different rates. After the initial scheduling interval, process A is going to be picked to run before process B. Once a process is picked to run, its wait time is reset to 0.
Let's assume that process A was picked to run after the previous wait period, but process B had to wait another 10 intervals, and process A became computable again. The new priorities would be:
Process A (S=5) = 1 + 0/5 = 1
Process B (S=10) = 1 + 20/10 = 3
Assuming other processes with higher priority blocked both processes for another interval of 10 the new priorities become:
Process A = 1 + 10/5 = 3
Process B = 1 + 30/10 = 4
And again both wait 10:
Process A = 1 + 20/5 = 5
Process B = 1 + 40/10 = 5
At this point both processes again have equal priority and either COULD be picked, but on a busy system it's not guaranteed. If they wait again the new priorities would become:
Process A = 1 + 30 / 5 = 7
Process B = 1 + 50/10 = 6
Again process A becomes the higher priority, but B is still increasing it's priority. A will be picked first and it's wait again reset to 0, but since B is still accumulating wait time it's priority will keep increasing until it becomes the highest priority on the system and all other processes will have to wait for it to run.
Opinion time:
This seems like a better algorithm than straight SJN, but in practice it could still provide unsatisfactory perceived user response on a busy general purpose system. Users would perceive a "bursty" system which sometimes gave quick answers, but with long pauses. I prefer preemptive style scheduling for interactive systems. For non-interactive systems, this may provide better overall throughput since it reduces expensive context switches.
When a job has just hit the scheduling queue it's wait time is zero and it's priority is 1. As the wait time increases it's priority is increased by a factor weighted by it's ESTIMATED* run time. Consider 2 processes, one with an estimated run time of 5, the other with 10. Assuming they are placed in the run queue at the same time, both will have an initial priority of 1.
Process A (s=5) priority = 1 + 0/5 = 1
Process B (S=10) priority = 1 + 0/10 = 1
As the processes wait, their priority increases proportional to their expected run time, let's say both have waited an interval of 10:
Process A (S=5) priority = 1 + 10/5 = 3
Process B (S=10) priority = 1 + 10/10 = 2
As you can see the priorities of each process increase, but at different rates. After the initial scheduling interval, process A is going to be picked to run before process B. Once a process is picked to run, its wait time is reset to 0.
Let's assume that process A was picked to run after the previous wait period, but process B had to wait another 10 intervals, and process A became computable again. The new priorities would be:
Process A (S=5) = 1 + 0/5 = 1
Process B (S=10) = 1 + 20/10 = 3
Assuming other processes with higher priority blocked both processes for another interval of 10 the new priorities become:
Process A = 1 + 10/5 = 3
Process B = 1 + 30/10 = 4
And again both wait 10:
Process A = 1 + 20/5 = 5
Process B = 1 + 40/10 = 5
At this point both processes again have equal priority and either COULD be picked, but on a busy system it's not guaranteed. If they wait again the new priorities would become:
Process A = 1 + 30 / 5 = 7
Process B = 1 + 50/10 = 6
Again process A becomes the higher priority, but B is still increasing it's priority. A will be picked first and it's wait again reset to 0, but since B is still accumulating wait time it's priority will keep increasing until it becomes the highest priority on the system and all other processes will have to wait for it to run.
Opinion time:
This seems like a better algorithm than straight SJN, but in practice it could still provide unsatisfactory perceived user response on a busy general purpose system. Users would perceive a "bursty" system which sometimes gave quick answers, but with long pauses. I prefer preemptive style scheduling for interactive systems. For non-interactive systems, this may provide better overall throughput since it reduces expensive context switches.
- Note that these are all ESTIMATED run times either based on a default initial value or on the average of the previous estimate and the actual last run time. This leads to a scheduling problem if the estimate is wildly inaccurate or has a series of short run times followed by a very long run.
Context
StackExchange Computer Science Q#52257, answer score: 4
Revisions (0)
No revisions yet.