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

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

設計方針

このアルゴリズムは、以下の設計目標を達成するように設計されています。

短いジョブを優先する: 処理時間が短いジョブを優先的に実行し、システム全体の応答時間を短縮します。
I/Oバウンドなプロセス（対話型プロセス）を優先する: キーボード入力やネットワーク通信など、入出力操作が多いプロセスを優先的に実行し、ユーザーの体感的な応答性を向上させます。
プロセスの性質を迅速に把握し、それに基づいてスケジュールを行う: プロセスの実行パターンを動的に判断し、適切な優先度で処理することで、システム全体の効率を高めます。

詳細

多段フィードバックキューは、複数のFIFO（First-In, First-Out）キューで構成されており、先頭のFIFOキューが最も高い優先度を持ちます。ディスパッチャ（スケジューラ）は、上位のFIFOキューから順に実行可能なプロセスを探し、最初に見つかったプロセスを実行します。プロセスの状態とキューの移動は、以下のように操作されます。

1. 新規プロセスの追加: 新しく生成されたプロセスは、最も優先度の高い先頭のFIFOキューの最後尾に追加されます。
2. キューからの実行: キューの先頭にあるプロセスが取り出され、CPUが割り当てられて実行されます。
3. プロセスの終了: プロセスが終了すると、システムから削除されます。
4. プロセスのブロック: プロセスが自発的に制御を明け渡した場合、またはリソース待ちでブロックする場合、そのキューから一時的に外され、再び実行可能状態になったときに元のキューに戻されます。
5. クォンタムタイムの消費: プロセスが割り当てられたクォンタム（CPU使用時間）を使い切ると、プリエンプト（実行中断）され、1つ下のレベルのキューの最後尾に移動されます。
6. キューの移動: このプロセスは、プロセスが終了するか、または最低レベルのキューに到達するまで繰り返されます。
7. 最低レベルのキュー: 最も優先度の低いキューにあるプロセスは、ラウンドロビン方式で実行されます。

多段フィードバックキューでは、プロセスは特定のレベルのキューで実行される機会は1回のみで（クォンタムを使い切る場合）、すぐに1つ下のレベルのキューに移動します。I/Oバウンドなプロセスは、クォンタムを使い切ることが少ないため、より優先度の高いキューに留まり続けることができます。これにより、I/Oバウンドなプロセスが優先的に処理され、ユーザーの体感的な応答性が向上します。

UNIXの場合

UNIX系オペレーティングシステムでは、多段フィードバックキューが採用されていますが、一般的に以下のような改良が加えられています。

リソース待ちからの復帰: リソース待ちでブロックしていたプロセスが再開する際、以前と同じキューではなく、別のキューに移動します。例えば、ディスクI/O、メモリ、ネットワーク通信など、リソースの種類に応じて戻るキューのレベルを決定します。これにより、CPUバウンドだったプロセスがI/Oバウンドに変化した場合（例：対話型で計算指示を与え、計算終了後に次の指示を待つプログラム）に対応できます。
* 長時間未実行プロセスの救済: 低レベルのキューで実行可能状態でありながら、長期間実行されていないプロセスを、徐々に高いレベルのキューに移動させます。これにより、リソースが不足し、プロセスが実行されない状態（リソーススタベーション）を回避します。

これらの改良により、多段フィードバックキューは、より多様なプロセスに対して効率的なスケジューリングを行うことが可能になっています。

もう一度検索