MLQ（Multi-Level Queue）スケジューリング

0 / 8

MLQ（Multi-Level Queue）スケジューリング

多段キュー（MLQ）スケジューリングでは、準備キューを複数に分け、プロセスを性質（システム、対話型、バッチ処理など）に応じて1つのキューに固定して入れる。上のキューが空になってはじめて下のキューが実行され、下のキューのプロセスが実行中でも、上のキューにプロセスが来るとOSが実行を止める（プリエンプション）。一度入ったキューは変わらない。

銀行でいえば：窓口は1つだが、VIPの列と一般の列が別にある。VIPの列が空になってはじめて一般の客に対応し、一般の客はVIPの列に移れない。

1 / 8

0ms：バッチ処理キューのP1を実行

P1はバッチ処理のプロセスなので、バッチ処理キューに並ぶ。上の2つのキューが空なので、すぐ実行される。

2 / 8

1ms：対話型のP2が来て、P1が止められる

P2は対話型プロセスキューに並ぶ。対話型キューはバッチ処理キューより上なので、OSがP1を止めてP2を実行する。P1は4ms残したまま自分のキュー（バッチ処理）に戻る。

3 / 8

2ms：P3はバッチ処理キューに並ぶ

P3もバッチ処理のプロセスなので、バッチ処理キューに並ぶ。上のキューのP2が実行中なので待つ。

4 / 8

3ms：システムのP4が来て、P2が止められる

最も上のシステムプロセスキューが最優先だ。OSがP2を止めてP4を実行する。P2は1ms残したまま自分のキュー（対話型）に戻る。

5 / 8

5ms：P4が終わり、P2を実行

システムキューが空になったので、その次の対話型キューのP2が続けて実行される。

6 / 8

6ms：上の2つのキューが空になり、バッチ処理キューの番

P2が終わり、上の2つのキューがどちらも空になった。そこでようやくバッチ処理キューのP1が、止まったところから続けて実行される。

7 / 8

10ms：P1が終わり、P3を実行

P3は2msから10msまで待った。上のキューにプロセスが次々に入ってくると、下のキューはいつまでも待たされうる（飢餓状態）。キューを移れないので、長く待っても上に上がれない。

8 / 8

18ms：すべて完了

待ち時間はP1 5ms、P2 2ms、P3 8ms、P4 0msで、平均3.75msだ。上のキューのP4・P2は短く、下のキューのP1・P3は長く待った。