多段フィードバックキュー(Multilevel Feedback Queue)とは、情報工学におけるスケジューリングアルゴリズムの一種である。1962年にフェルナンド・J・コルバトらによって発表された[1]。 以下のような設計目標を満たすように意図されている。 複数のFIFOキューで構成されており、先頭のFIFOが最も優先される。ディスパッチャは上位のFIFOキューから実行可能プロセスを探していき、最初に見つかったプロセスを実行する。多段フィードバックキューは以下のように操作される。 多段フィードバックキューでは、プロセスはあるレベルのキュー上で実行される機会は(クォンタムを使い切るなら)1回しかなく、即座に1つ下のレベルのキューに行くことになる。I/Oバウンドなプロセスはクォンタムを使い切ることが滅多にないので高いレベルのキューに存在し続けることができる。 UNIX系オペレーティングシステムは多段フィードバックキューを採用したが、一般に以下のような改良を施している。
設計方針
短いジョブを優先する。
I/Oバウンドなプロセス(対話型プロセス)を優先する。
プロセスの性質を迅速に把握し、それに基づいてスケジュールを行う。
詳細
新しく生成されたプロセスは先頭のFIFOキューの最後尾に置かれる。
キューの先頭のプロセスから処理され、CPUを割り当てられる。
プロセスが終了すれば、システムから削除される。
プロセスが自発的に制御を明け渡した場合、あるいは何らかのリソース待ちでブロックする場合、このキューから一旦外され、再び実行可能状態になったときに以前と同じレベルのキューに入れられる。
プロセスがクォンタム時間を使い切ると、プリエンプトされて1つ下のレベルのキューの最後尾に繋ぎなおされる。
これがプロセスが終了するか、最低レベルのキューにたどり着くまで続けられる。
最低レベルのキューにあるプロセス群はラウンドロビン方式で処理される。
UNIXの場合
リソース待ちでブロックしたプロセスが起床した際、以前と同じレベルのキューではなく別のキューに置く。例えば、リソースの種類(ディスクI/O、メモリ、通信など)によって戻すキューのレベルを決めておく。これにより、CPUバウンドだったプロセスがI/Oバウンドに変化する可能性に対応する(例えば対話型で計算の指示を与え、計算が終わると次の指示待ちとなるようなプログラム)。
低レベルのキューにあって実行可能でありながら長期間実行されていないプロセスを徐々に高いレベルのキューに移していく。これによりリソーススタベーションを回避する。
脚注^ F. J. Corbato, M. M. Daggett, R. C. Daley, ⇒An Experimental Time-Sharing System (IFIPS 1962年)
表
話
編
歴
オペレーティングシステム
概要
歴史
一覧
カーネル
アーキテクチャ
モノリシックカーネル
マイクロカーネル
エクソカーネル（英語版）
ハイブリッドカーネル（英語版）
コンポーネント
アドレス空間
デバイスドライバ
ローダブル・カーネル・モジュール
マイクロカーネル
プロセス管理
概念
コンテキストスイッチ
割り込み
プロセス間通信
プロセス
プロセス制御ブロック
リアルタイム
スレッド
タイムシェアリング
スケジューリング
アルゴリズム
マルチタスク
多段フィードバックキュー
プリエンプション
ラウンドロビン
メモリ管理と
リソース保護
バスエラー
メモリ保護