多段フィードバックキュー（MLFQ）

MLFQ はプロセスの最近の動作から優先度を調整する。本課では新しい仕事を最上位へ入れ、量子を使い切って CPU 作業が残れば一段下げる。I/O で待機して戻ると最上位へ入れる。バーストの長さを先に知らず、短い仕事や対話的な仕事へ早い応答を与えられる。

新着は速い窓口で試し、長ければ長い時間枠の列へ移し、資料を取りに離れて戻れば速い列へ入れるイメージだ。12 tick ごとに低い列の待機者を上へ戻し、古い判断を残し続けない。同じ負荷の Round Robin と比較する。

仕組み

既定は Q0 の量子 2、Q1 は 4、Q2 は 8。常に最高の非空キューの先頭を選ぶ。

1. 新着は Q0 へ入る。
2. 量子を使い切って現在の CPU バーストが残れば一段降格し、最下位ならそこに留まる。
3. バーストを終えて I/O へ進む場合は、量子との同時終了でも降格しない。I/O 完了後はこのモデルでは必ず Q0 へ戻る。
4. より高い優先度の仕事が準備できると、低位の実行者をプリエンプトし、元キューの末尾へ戻す。
5. 12 tick ごとに Q1、Q2 で実行待ちの仕事を Q0 へ昇格する。実行中の仕事は対象外だが、新しい上位集団にすぐ中断され得る。

Round Robin の基準は FIFO 一列、量子 3。新着は末尾、先頭が実行し、量子後も CPU 作業があれば末尾へ回る。一列の比較でフィードバックの効果を切り出す。

同 tick は到着、I/O 完了、昇格の順に処理し、その後でプリエンプトや再キューを行う。同時到着は量子切れの仕事より前に並ぶ。

ステップ実行

固定負荷は P1 が t=0 に到着して CPU 5、I/O 4、CPU 3。P2 は t=1、CPU 4。P3 は t=2、CPU 2、I/O 3、CPU 4。P4 は t=4、CPU 3。

既定 MLFQ、量子 2/4/8、昇格周期 12：

1. P1 は 0–2 を実行して Q1 へ降格する。同刻の P3 は先に Q0 へ入る。P2 は 2–4 を走り、降格する。
2. P3 は 4–6 で最初の CPU バーストを完了し、9 まで I/O へ進む。降格しない。P4 は 6–8 で作業が残り、降格する。
3. Q0 が空なので P1 は Q1 から 8–9 を走る。9 に P3 が I/O から Q0 へ戻り、P1 を Q1 末尾へ押し戻す。
4. P3 は 9–11 で Q0 量子を使い、残りがあるので Q1 へ降格。P2 が Q1 から 11–12 を走る。
5. t=12 に Q1 で待つ P4、P1、P3 を順に Q0 へ上げる。実行中 P2 は昇格せず、上位の準備で中断して Q1 へ戻る。
6. P4 は 12–13 で完了し、ターンアラウンド 9。P1 は 13–15 でバーストと量子が同時に終わり、降格せず 19 まで I/O。P3 は 15–17 で完了し、ターンアラウンド 15。
7. P2 は Q1 の 17–18 で完了し、ターンアラウンド 17。18–19 は準備済み仕事がなくアイドル。
8. P1 は 19 に Q0 へ戻り、19–21 の後で降格し、Q1 の 21–22 で完了。ターンアラウンド 22。

Round Robin、量子 3：

1. P1 は 0–3 を走り、P2 と P3 が並ぶ。P1 を戻すと列は P2、P3、P1。
2. P2 は 3–6 を走り、4 に P4 が到着する。P2 は一 tick 残して末尾へ。
3. P3 は 6–8 で最初のバーストを終え、11 まで I/O。P1 は 8–10 で最初の 5 tick を終え、14 まで I/O。
4. P4 は 10–13 で完了し、その途中の 11 に P3 が再入列する。P2 は 13–14 で完了し、同刻に P1 の I/O も終わる。
5. P3 は 14–17 で一 tick 残し、P1 は 17–20 で完了、P3 は 20–21 で完了する。アイドルなしで 21 に終える。

輪番のターンアラウンドは P1–P4 順に 20、13、19、9、応答時間は 0、2、4、6。MLFQ の応答は 0、1、2、2 に縮むが、P1 のターンアラウンドは 22、全体も一 tick 遅く終わる。

プロセス色は到着から完了まで共通だ。現在のカードをリングで示し、量子メーターは今の量子で使った tick だけ伸びる。降格は一棚下へ動き、12 の昇格は三枚を同時に上げる。ガント図は再生中は最近の窓、終了時は全体と指標表を見せる。

バーストの予知が不要な理由

全ジョブが同時に利用可能で長さが既知なら、短い順は平均ターンアラウンドを最小化する。到着がずれる場合はそのまま適用できず、実カーネルも未来の作業量を推定する必要がある。MLFQ は最近の CPU 使用を代用し、量子を使い切って作業が残れば下げ、I/O から戻れば上へ置く。

短い Q0 量子によって、応答は輪番の 0、2、4、6 から 0、1、2、2 へ変わる。代価は優先順位、横取り、I/O 時刻の変化で、P1 は二 tick 遅く終わる。このトレースの P1 の降格は二回であり、ほかの中断やバースト終了まで降格と数えてはいけない。

高位の到着が続くと低位が飢餓になり得るため、周期的昇格で待機者を競争へ戻す。古い優先度が効き続ける時間を制限する仕組みであり、無限に増える任意の負荷に固定の完了時刻を保証するものではない。

境界ケース

• バーストと量子が同時に終われば完了を先に扱う。t=15 の P1 は I/O へ行き、降格しない。P4 は 13 に量子前で完了し、再キューしない。
• 到着と期限切れが同時なら新着を先に入れる。MLFQ の 2 では P3、輪番の 3 では P2、P3、P1 の並びになる。
• 昇格は実行者を除く。12 の P2 は Q1 のまま中断され、17 まで再開しない。
• アイドルも出力だ。18–19 は P1 の I/O だけなので、IDLE を描いて次イベントへ時刻を進める。

よくある間違い

• ガント図を方針そのものと思う。図は結果であり、各選択を生んだ規則を追う。
• I/O が降格の原因だと思う。このモデルは量子を消費して CPU 作業が残ると降格し、I/O 完了は Q0 へ戻る。
• 全指標で輪番に勝つと期待する。本例は応答が速くても P1 の完了と全体終了は遅い。
• 高位の横取りを忘れる。Q1 の P1 は 8–9 の一 tick で、戻った P3 に中断される。
• キュー階層を永久の属性と読む。最近の動作への推測であり、昇格が待機者の古い判断を戻す。

モデルの範囲

単一 CPU、整数 tick、固定バースト、I/O 復帰は Q0、切替費用ゼロ。割り込み遅延、ロック、アフィニティー、nice、実用の公平性会計は省く。実 MLFQ の変種は累積割当量など別の規則も使うため、ここでの各規則を全 MLFQ の定義としない。