In this tutorial, we’ll explain the HRRN (Highest response ratio next) scheduling algorithm. It’s a modification of the Shortest-job-next strategy.
2. Shortest Job Next and Starvation
Shortest job next (SJN) schedules processes according to their execution times. When the CPU gets free, this algorithm picks the shortest process to run.
However, it’s a non-preemptive strategy, which means it doesn’t interrupt a process once it starts running. So, it will postpone a long process over and over if shorter processes keep arriving:
This problem is known as starvation, and HRRN solves it successfully.
3. Highest Response Ratio Next
HRRN schedules processes by their response ratios:
where the execution times are estimations. Processes with higher ratios get the CPU before those with lower ratios.
Same as SJN, HRRN is non-preemptive.
3.1. Long Processes Don’t Starve
The longer a process waits to start, the higher its ratio will get. So, short processes won’t be able to starve a long one since its waiting time will eventually make its response ratio the highest in the pool of ready processes.
For instance, let be the waiting times of three processes (, respectively), and let be their estimated run times. Their response ratios are:
Although and are shorter than , HRRN schedules it for execution because of its long waiting time.
Let’s rewrite the formula of the response ratio:
Since the waiting time is at least 0, the ratio is .
It follows that HRRN favors short processes that wait long. However, if a long process has a long waiting time, its ratio will be low. For instance, a process that has been waiting for twenty time units and is estimated to take twenty units to complete will have a ratio of only 2. On the other hand, a shorter process taking five units and waiting for twenty, y will have a ratio of 5.
If two processes take the same time, HRRN prioritizes the one that has waited longer. Let be estimated run times and and the waiting times of and . gets precedence over if:
What happens if two processes have different execution estimates () but equal waiting times ()? The shorter one gets precedence:
Let’s go through an example. We have five processes with different times of getting ready and estimated durations:
We assume that no other processes get ready for execution and that a scheduled process releases the CPU only after it finishes its job, not by getting to the wait state because of an I/O operation or a blocking resource.
So, in the beginning, we have two ready processes at time zero: and . Since they haven’t waited at all, we schedule the shorter, , and let it run until it’s complete:
Now, the CPU time is 2, and we have two processes: and , the latter having arrived while was running. Their waiting times are and . Therefore, their response ratios are:
As a result, we let run on our CPU for three time units:
Now, the CPU time is 5, and and got ready in the meantime. The new waiting times of , , and are:
This gives us the following response ratios:
Although and are estimated to take less time than , HRRN schedules because it has the highest response ratio:
After releases the CPU at time 10, the ratios of and are:
So, gets scheduled, and after it finishes its work, we let run:
In contrast, SJN would last execute . If shorter processes kept coming to the ready pool, SJN would let wait indefinitely to take the CPU.
In this article, we talked about the HRRN (Highest response ratio next) scheduling policy. Since it takes into account how much time a process spends waiting, not just how much it will take to complete, HRRN doesn’t starve long processes. However, it’s a non-preemptive scheduling algorithm.