多段フィードバックキュー

多段フィードバックキュー(Multilevel Feedback Queue)とは、情報工学におけるスケジューリングアルゴリズムの一種である。1962年にフェルナンド・J・コルバトらによって発表された。

設計方針

以下のような設計目標を満たすように意図されている。

1. 短いジョブを優先する。
2. I/Oバウンドなプロセス(対話型プロセス)を優先する。
3. プロセスの性質を迅速に把握し、それに基づいてスケジュールを行う。

詳細

複数のFIFOキューで構成されており、先頭のFIFOが最も優先される。ディスパッチャは上位のFIFOキューから実行可能プロセスを探していき、最初に見つかったプロセスを実行する。多段フィードバックキューは以下のように操作される。

1. 新しく生成されたプロセスは先頭のFIFOキューの最後尾に置かれる。
2. キューの先頭のプロセスから処理され、CPUを割り当てられる。
3. プロセスが終了すれば、システムから削除される。
4. プロセスが自発的に制御を明け渡した場合、あるいは何らかのリソース待ちでブロックする場合、このキューから一旦外され、再び実行可能状態になったときに以前と同じレベルのキューに入れられる。
5. プロセスがクォンタム時間を使い切ると、プリエンプトされて1つ下のレベルのキューの最後尾に繋ぎなおされる。
6. これがプロセスが終了するか、最低レベルのキューにたどり着くまで続けられる。

• 最低レベルのキューにあるプロセス群はラウンドロビン方式で処理される。

多段フィードバックキューでは、プロセスはあるレベルのキュー上で実行される機会は(クォンタムを使い切るなら)1回しかなく、即座に1つ下のレベルのキューに行くことになる。I/Oバウンドなプロセスはクォンタムを使い切ることが滅多にないので高いレベルのキューに存在し続けることができる。

UNIXの場合

UNIX系オペレーティングシステムは多段フィードバックキューを採用したが、一般に以下のような改良を施している。

• リソース待ちでブロックしたプロセスが起床した際、以前と同じレベルのキューではなく別のキューに置く。例えば、リソースの種類(ディスクI/O、メモリ、通信など)によって戻すキューのレベルを決めておく。これにより、CPUバウンドだったプロセスがI/Oバウンドに変化する可能性に対応する(例えば対話型で計算の指示を与え、計算が終わると次の指示待ちとなるようなプログラム)。
• 低レベルのキューにあって実行可能でありながら長期間実行されていないプロセスを徐々に高いレベルのキューに移していく。これによりリソーススタベーションを回避する。

脚注