マルチレベルフィードバックキュー（MLFQ）とは？適応型CPUスケジューリングアルゴリズムを徹底解説

MLFQとは

マルチレベルフィードバックキュー（MLFQ：Multilevel Feedback Queue）は、複数のレディーキューを持ち、各キューに異なる優先度とタイムクォンタム（時間割り当て量）を設定するCPUスケジューリングアルゴリズムです。新規プロセスは最上位のキューから実行を開始し、その後の動作に応じてキュー間で昇格・降格が行われます。この適応型の設計により、対話型プロセスとCPU集中型プロセスの双方のニーズをバランスよく満たすことができます。

キュー構成の例

• キュー0（最優先）：タイムクォンタム＝1。新規プロセスはここから開始する
• キュー1（中優先度）：タイムクォンタム＝2。キュー0で時間を使い切ったプロセスが降格してくる
• キュー2（最下位）：FCFS（先着順）方式。長時間のCPU処理が必要なプロセスが最終的に到達する

プロセス移動のルール

• 新規プロセスは必ずキュー0から開始する
• タイムクォンタム内に処理が完了しなかった場合、次に低い優先度のキューへ降格する
• エージング（aging）機構により、長時間待機したプロセスは上位キューへ昇格し、スタベーション（飢餓状態）を防止する

MLFQの仕組み

MLFQは以下の基本原則に基づいて動作します。

• 優先度ベースのスケジューリング：常に優先度の高いキューから順に実行される
• 可変タイムクォンタム：優先度の高いキューほど短いタイムスライスが割り当てられる
• 動的な優先度調整：プロセスの実際の動作（CPU使用時間やI/O待ちなど）に基づいてキュー間を移動する
• エージング機構：長期間待たされているプロセスを昇格させ、スタベーションを防止する

実行例

以下の3つのプロセスを例に考えてみましょう。

条件は、キュー0のタイムクォンタム＝1、キュー1のタイムクォンタム＝2、キュー2はFCFS方式とします。

実行タイムライン

このように、新しく到着したプロセスはまず最上位キューで短いタイムスライスを与えられ、より多くのCPU時間を必要とするプロセスは徐々に下位のキューへ降格していきます。短い対話型処理を素早く捌きつつ、CPU集中型の処理にも継続的にCPU時間を与えられる点がMLFQの大きな特徴です。

主なユースケース

• 対話型アプリケーション：Webブラウザ、テキストエディタ、GUIアプリケーションなど、ユーザー操作への迅速な応答が求められる環境
• タイムシェアリングシステム：対話型処理とバッチ処理が共存するマルチユーザーシステム
• リアルタイムシステム：重要タスクと非重要タスクに異なる優先度を与える必要があるシステム
• ゲームアプリケーション：音声やネットワーク通信などのバックグラウンド処理を管理しつつ、入力への高い応答性を維持する必要があるゲーム

メリット

• 応答時間の向上：短いプロセスは高優先度キューで素早く処理される
• 動的な優先度調整：プロセスの動作パターンに自動的に適応する
• スタベーションの防止：エージング機構により、長時間待機したプロセスも最終的にCPU時間を確保できる
• 良好なスループット：対話型処理とバッチ処理のニーズを効果的にバランスさせる
• 柔軟なチューニング：ワークロードに応じてタイムクォンタムやキュー数を調整可能

デメリット

• 実装の複雑さ：異なるポリシーを持つ複数のキューを管理する必要があり、システム全体が複雑になる
• オーバーヘッドの増加：キュー間の移動判定や優先度の再計算など、スケジューラ自体の処理コストが増大する
• パラメータ調整の難易度：キュー数やタイムクォンタムの設定次第で性能が大きく変わり、最適化には経験と検証が必要
• 悪用への対策が必要：プロセスが意図的にI/O待ちを発生させて高優先度を維持するといった「スケジューラのゲーム化」を防ぐ仕組みが求められる

まとめ

MLFQは、プロセスの振る舞いを観察しながら優先度を動的に調整することで、応答性とスループットの両立を実現する洗練されたスケジューリング手法です。実装の複雑さやオーバーヘッドという課題はあるものの、対話型処理とバッチ処理が混在する現代のOS環境において非常に有効なアルゴリズムであり、多くの実用的なシステムで採用されています。