マルチレベル フィードバック キュー (MLFQ):適応型 CPU スケジューリング アルゴリズム

マルチレベル フィードバック キュー (MLFQ) は、それぞれが異なる優先レベルとタイム クォンタム値を持つ複数のレディ キューを維持する CPU スケジューリング アルゴリズムです。新しいプロセスは最も優先度の高いキューから開始され、その動作に基づいてキュー間で昇格または降格されることがあります。この適応的なアプローチにより、インタラクティブなプロセスと CPU 負荷の高いプロセスの両方のニーズのバランスがとれます。

マルチレベル フィードバック キューの構造 キュー 0 (最高優先度) タイム クォンタム:1 キュー 1 (中優先度) タイム クォンタム:2 キュー 2 (最低優先度) FCFS CPU 新しいプロセス 時間が経過すると降格 エージング:待機後に昇格 プロセス移動ルール ?新しいプロセスはキュー 0 で開始されますか?タイムクォンタムが期限切れになったら?次に下のキューに移動しますか?老化メカニズムが飢餓を防ぐ

MLFQ の仕組み

このアルゴリズムは、次の重要な原則に従って動作します。

• 優先度ベースのスケジューリング 優先度の高いキューが最初に処理されます

• 可変タイム クォンタム 優先度の高いキューほどタイム スライスが短くなります

• 動的優先度調整 プロセスは動作に基づいてキュー間を移動します

• 老化メカニズム 長時間待機するプロセスを促進することで飢餓を防ぐ

例

次の特性を持つ 3 つのプロセスを考えてみましょう。

プロセス 到着時刻 バースト時間 初期キュー P108キュー0P214キュー0P322キュー0

キュー 0 のタイム クォンタム =1、キュー 1 のタイム クォンタム =2、およびキュー 2 の FCFS 使用:

MLFQ 実行タイムライン P1 P2 P3 P2 P1 P2 P1 (キュー 2 - FCFS) 0 1 2 3 4 6 8 14 Q0 Q0 Q0 Q1 Q1 Q1 Q2

使用例

MLFQ は、次のシナリオで特に効果的です。

• インタラクティブなアプリケーション Web ブラウザ、テキスト エディタ、および GUI アプリケーションは、ユーザー インタラクションに対する応答時間が速いというメリットを享受できます

• タイムシェアリング システム インタラクティブ プロセスとバッチ プロセスの両方が共存するマルチユーザー システム

• リアルタイム システム 重要なタスクと重要でないタスクに異なる優先レベルを必要とするシステム

• ゲーム アプリケーション ゲームでは、オーディオやネットワークなどのバックグラウンド タスクを管理しながら、応答性の高い入力処理が必要です

利点

• 応答時間の向上 短いプロセスは優先度の高いキューですぐに注目を集めます

• 動的な優先度調整 プロセスの動作パターンに自動的に適応します

• Starvation Aging メカニズムを防止し、長時間待機しているプロセスが最終的に CPU 時間を確保できるようにします

• 優れたスループット インタラクティブ処理とバッチ処理のニーズを効果的にバランスさせます

• 柔軟な構成 特定のワークロードに合わせて時間量とキューの数を調整できます。

欠点

• 実装の複雑さ 異なるポリシーを使用して複数のキューを管理すると、システムの複雑さが増大します。

• オーバーヘッドが大きい&マイナス