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

0 / 11

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

多段フィードバックキュー（MLFQ）スケジューリングも、MLQと同じく準備キューを複数に分けるが、プロセスがキューの間を移動する。新しいプロセスは最も上のキューから始まり、そのキューのタイムクォンタム内に終わらなければ、OSが実行を止め（プリエンプション）、1つ下のキューに下げる。下のキューほど実行が後回しになる代わりにタイムクォンタムが大きく、最も下のキューはRR方式で実行する。下のキューのプロセスが実行中でも、上のキューに新しいプロセスが来るとOSが実行を止める。

銀行でいえば：窓口は1つで、列が3つある。すべての客はまず「1分の列」に並び、1分で終わらなければ「2分の列」へ、そこでも終わらなければ「4分の列」へ移る。上の列が空いてはじめて下の列の客の番になる。

1 / 11

0ms：P1がキュー0で実行

新しいプロセスはすべて最も上のキュー0に並ぶ。キュー0では一度に1msまでしか実行できない。

2 / 11

1ms：P1がキュー1に下がる

P1はタイムクォンタム1msを使い切っても終わらず（残り4ms）、1つ下のキュー1に下がる。1msに来たP2がキュー0で実行される。

3 / 11

2ms：P2もキュー1に下がる

P2も1ms実行して、2ms残したままキュー1に並ぶ。2msに来たP3がキュー0で実行される。

4 / 11

3ms：P3もキュー1に下がる

P3は7ms残したままキュー1に並ぶ。3msに来たP4がキュー0で実行される。

5 / 11

4ms：キュー0が空になり、キュー1の番

P4も1ms残したままキュー1に並ぶ。キュー0が空になったので、キュー1の先頭のP1が実行される。キュー1では一度に2msまで実行できる。

6 / 11

6ms：P1がキュー2に下がる

P1はタイムクォンタム2msを使い切っても2ms残っているので、最も下のキュー2に下がる。キュー1のP2が実行される。

7 / 11

8ms：P2が完了

P2は残りの2msをタイムクォンタム2ms内に終えた。P3が実行される。

8 / 11

10ms：P3がキュー2に下がる

P3は5ms残したままキュー2に並ぶ。キュー1のP4が実行される。

9 / 11

11ms：P4が終わり、キュー2の番

P4は1msしか残っていなかったので、すぐに終わった。キュー0とキュー1がどちらも空になったので、キュー2のP1が実行される。キュー2では一度に4msまで実行できる。

10 / 11

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

P1は残り2msなので、タイムクォンタム内に終わった。P3は17msにタイムクォンタムを使い切っても、待っているプロセスがないので実行され続ける。

11 / 11

18ms：すべて完了

待ち時間はP1 8ms、P2 4ms、P3 8ms、P4 6msで、平均6.5msだ。実行時間を前もって知らなくても、短いP2・P4はキュー1で終わり、長いP1・P3はキュー2まで下がった。下のキューで長く待ちすぎたプロセスは、上のキューに上げることもある（エージング）。