ユユユユユ

webエンジニアです

Multi-Level Feedback Queue

OSTEP の第8章で Multi-Level Feedback Queue の理念と動作原理について読んだ。

OS のスケジューリング問題へのアプローチとして1962年に考案されたアルゴリズムである。日本語だと「多段フィードバックキュー」が定訳らしいと wikipedia で知った。

ターンアラウンドタイムとレスポンスタイムというふたつのメトリクスを最適化の対象として意識する。それぞれの定義はこうなる。

  • ターンアラウンドタイム: ジョブが到着してからジョブが完了するまでの時間
  • レスポンスタイム: ジョブが到着してからジョブが最初にスケジュールされるまでの時間

Shortest Jobs First アルゴリズムは、ターンアラウンドタイムをよくするがレスポンスタイムを悪くする。 Round Robin アルゴリズムはその逆に、レスポンスタイムをよくするがターンアラウンドタイムを悪くする。

Multi-Level Feedback Queue とは、それぞれ異なる優先度をもった複数のキューのあいだをジョブに行き来させながら、ふたつのメトリクスを最適化するよううながすものである。任意のジョブがどのくらいの実行時間を持つかはわからないにせよ、ジョブを実行しながら最善の予測をおこなって最適化しようとするアルゴリズムである。

Multi-Level Feedback Queue の仕組みは次の五つのルールに還元される。

  1. 優先度の高いキューからジョブを実行する。
  2. 優先度の等しいキューのジョブは Round Robin で実行する。
  3. 新しいジョブは常に優先度のもっとも高いキューにおかれる。
  4. キューごとに定義された一定の割り当て時間を使い切ると、そのジョブは優先度のひとつ低いキューに移動する。
  5. 一定の時間ごとにすべてのジョブを優先度のもっとも高いキューに移動する。

一般に、 CPU を短く使うジョブは優先度が高く処理されて、素早く終わる。対して CPU を長く使うジョブは優先度の低いキューに到達して、優先度の高いジョブを邪魔しない。 I/O が絡むジョブは、優先度の高いキューにとどまる傾向がありながら、 4. のルールに従って公平に割り当てられる。

5. のルールがうまくできている。これは優先度の高いジョブが大量におかれたときに、優先度の低いジョブがいつまでも CPU を割り当ててもらえない (starvation) という問題を解いている。レスポンスタイムの公平性を守りながら、ターンアラウンドタイムの素早さも守っている。

仕組みとしてはこれに勝るものなしとおもわれるが、難しさはパラメータのチューニングという形でやってくる。すなわち...

  • 優先度の異なるキューをいくつ用意するか
  • キューごとの Round Robin のタイムスロットはどれくらいか
  • キューごとの優先度を下げるまでの割り当て時間はどれくらいか
  • すべてのジョブの優先度を最高にする頻度はどれくらいか

これらが一般化できない問題として残される。もっとも、それ以外の問題は一般化できるという意味でもある。

おもうに、特殊な事象を一般化するのはマクロな科学の産物で、パラメータをチューニングするのはミクロな工学の関心である。

すべてを巨視的に還元するでもなく、すべてを微視的に解消するでもない。工学と科学が重なりあった主題に触れて、おもしろくおもった。