Scheduling: Highest Response Ratio Next | Baeldung on Computer Science

1. Introduction

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:

$Response\ Ratio = \frac{Waiting\ Time + Execution\ Time}{Execution\ Time}$

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 $w_1=20, w_2=3, w_3=2$ be the waiting times of three processes ( $P_1, P_2, P_3$ , respectively), and let $s_1=10, s_2=1, s_3=2$ be their estimated run times. Their response ratios $r_i=\frac{w_i+s_i}{s_i}$ are:

$\begin{aligned} r_1 &= \frac{20+10}{10} = \frac{30}{10} = 3 \\ r_2 &= \frac{1+1}{1} = \frac{2}{1} = 2 \\ r_3 &= \frac{3+2}{2} = \frac{5}{2} = 2.5 \end{aligned}$

Although $P_2$ and $P_3$ are shorter than $P_1$ , HRRN schedules it for execution because of its long waiting time.

3.2. Characteristics

Let’s rewrite the formula of the response ratio:

$Response\ Ratio = \frac{Waiting\ Time}{Execution\ Time} + \frac{Execution\ Time}{Execution\ Time} = \frac{Waiting\ Time}{Execution\ Time} + 1$

Since the waiting time is at least 0, the ratio is $\geq 1$ .

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 $s_1=s_2=s$ be estimated run times and $w_1$ and $w_2$ the waiting times of $P_1$ and $P_2$ . $P_1$ gets precedence over $P_2$ if:

$1 + \frac{w_1}{s} > 1 + \frac{w_2}{s} \iff w_1 > w_2$

What happens if two processes have different execution estimates ( $s_1 > s_2$ ) but equal waiting times ( $w_1=w_2=2$ )? The shorter one gets precedence:

$s_1 > s_2 \implies 1 + \frac{w}{s_1} < 1 + \frac{w}{s_2}$

4. Example

Let’s go through an example. We have five processes with different times of getting ready and estimated durations:

$\begin{matrix} & Process & Ready\ Time & Execution\ Time \\ & P_1 & 0 & 2 \\ & P_2 & 0 & 3 \cr & P_3 & 1.5 & 5 \cr & P_4 & 3 & 4 \\ & P_5 & 4.5 & 2 \end{matrix}$

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: $P_1$ and $P_2$ . Since they haven’t waited at all, we schedule the shorter, $P_1$ , and let it run until it’s complete:

Now, the CPU time is 2, and we have two processes: $P_2$ and $P_3$ , the latter having arrived while $P_1$ was running. Their waiting times are $w_2 = 2-0=2$ and $w_3=2-1.5=0.5$ . Therefore, their response ratios are:

$\begin{aligned} r_2 &= \frac{2+3}{3} = \frac{5}{3} \approx 1.67 \\ r_3 &= \frac{0.5+5}{5} = \frac{5.5}{5} = 1.1 \end{aligned}$

As a result, we let $P_2$ run on our CPU for three time units:

Now, the CPU time is 5, and $P_4$ and $P_5$ got ready in the meantime. The new waiting times of $P_3$ , $P_4$ , and $P_5$ are:

$w_3 = 5 - 1.5 = 3.5 \qquad w_4 = 5 - 3 = 2 \qquad w_5 = 5 - 4.5 = 0.5$

This gives us the following response ratios:

$\begin{aligned} r_3 &= \frac{3.5+5}{5} = \frac{8.5}{5} = 1.7 \\ r_4 &= \frac{2+4}{4} = \frac{6}{4} = 1.5 \\ r_5 &= \frac{0.5+2}{2} = \frac{2.5}{2} = 1.25 \end{aligned}$

Although $P_4$ and $P_5$ are estimated to take less time than $P_3$ , HRRN schedules $P_3$ because it has the highest response ratio:

After $P_3$ releases the CPU at time 10, the ratios of $P_4$ and $P_5$ are:

$\begin{aligned} r_4 = \frac{(10-3)+4}{4} = \frac{11}{4} = 2.75 \\ r_5 = \frac{(10-4.5)+2}{2} = \frac{7.5}{2} = 3.25 \end{aligned}$

So, $P_5$ gets scheduled, and after it finishes its work, we let $P_4$ run:

In contrast, SJN would last execute $P_3$ . If shorter processes kept coming to the ready pool, SJN would let $P_3$ wait indefinitely to take the CPU.

5. Conclusion

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.

Full Archive

About Baeldung

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex