调度：最高响应比优先

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:

P1 gets scheduled first

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:

P2 gets scheduled

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:

P3 gets scheduled

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:

P4 and P4 get scheduled

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.

Persistence

REST

Security