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?
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.
- 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.
here while calculating waiting time above, we are getting it as 5 for process3 which is actually how much process3 waited till time unit 9 as it has already arrived at 4, therefore it is 9-4=5 and same for process4 and process5 that how much they waited till time unit 9 as they have already arrived at 6 & 8 , which is 9-6=3, 9-8=1 respectively.
and further same while calculating response ratio again for process4 and process5. which is how much process4 and process5 waited till time unit 13 i.e. 13-6=7, 13-8=5 respectively.
the highest response ratio next therefore does not suffer from starvation, as the process waiting for longer period of time will even compete with the processes arriving and having shorter service time and each and every process will get a chance to get the CPU processing.
I found this psuedocode from another website on how to step through the process of HRRN.
Steps for HRRN:
- First, loop queue to find the highest ratio.
- calculate each ratio and compare to the highest ratio
- if response ratio is greater than highest ratio then update
- If the element is at the start of the queue, dequeue it and set the list to it's next element.
- Go back to the start of the queue and find the element before the dequeued element.
- Assign prev next to dequeued process next.
- Return the highest ratio element in the list
- Repeat once the running process has completed the job or is pre-emptied.