最も高い回答率

最高応答率次（HRRN）スケジューリングは、非プリエンプティブな手法です。これは、プロセス不足の問題を軽減するために、最短ジョブ次または最短ジョブ先（SJNまたはSJF）の修正としてブリンチ・ハンセンによって開発されました。HRRNでは、次のジョブは推定実行時間が最も短いジョブではなく、次のように定義される応答率が最も高いジョブです。

${\displaystyle 応答\ 比率 = {\frac {これまでのプロセスの待機時間\ + 推定実行時間}{推定実行時間}} = 1 + {\frac {これまでのプロセスの待機時間\ {推定実行時間}}}$

つまり、長時間待機しているジョブは、実行時間が短いと推定されるジョブと競合します。上記の応答率の式からわかるように、プロセスの待機時間が長くなると、その応答率も高くなり、待機時間が長いプロセスが次に実行されます。したがって、このアルゴリズムは、SJN スケジューリング アルゴリズムに存在する飢餓問題を解決します。

リンク リスト Q が与えられた場合、キュー内の各比率を比較して、Q を反復処理して最高比率を見つけます。要素 N の比率が最高比率の要素 M よりも大きい場合は、要素 M を要素 N に置き換えて、リスト内の最高比率の要素にします。リストの末尾に達したら、最高比率の要素をキューから取り出します。要素がリストの先頭にある場合は、キューから取り出してリストを次の要素に設定し、その要素を返します。それ以外の場合は、N の隣接要素が、次の隣接要素と前の隣接要素として互いを識別するように再割り当てされ、N の結果が返されます。

• 残り時間最短

• William Stallings:オペレーティングシステム: 内部と設計原則。第 4 版、Prentice-Hall、2001 年、ISBN  0-13-031999-6。