Loading article…
コンピュータサイエンスにおいて、マルチレベルフィードバックキューはスケジューリングアルゴリズムです。スケジューリングアルゴリズムは、中央処理装置（CPU）をビジー状態に保つために、常に何らかのプロセスを実行するように設計されています。 [1]マルチレベルフィードバックキューは、次の設計要件を備えた標準アルゴリズムを拡張します。
- プロセッサの必要性に基づいて、プロセスを複数の準備キューに分割します。
- CPU バーストが短いプロセスを優先します。
- I/Oバーストの高いプロセスを優先します。(I/O バウンド プロセスは、他のプロセスに CPU 時間を割り当てるために待機キューでスリープします。)
マルチレベルフィードバックキューは、フェルナンド・J・コルバト（1962年）によって初めて開発されました。[2]この功績により、計算機協会はコルバトにチューリング賞を授与しました。[3]
プロセススケジューリング
マルチレベルキューアルゴリズムはプロセスを最初のキュー割り当てに永続的に割り当てたままにするのに対し、マルチレベルフィードバックキューはプロセスをキュー間でシフトします。[4]このシフトは、前のタイムスライスのCPUバーストに依存します。[5]
- プロセスが CPU 時間を過度に使用すると、優先度の低いキューに移動されます。
- プロセスが I/O バウンドまたは対話型プロセスである場合、そのプロセスは優先度の高いキューに移動されます。
- プロセスが低優先度のキューで長時間待機し、リソースが不足している場合は、高優先度のキューに移されます。
アルゴリズム
複数のFIFOキューが使用され、操作は次のようになります。
- 新しいプロセスは、最上位FIFOキューの末尾 (末尾) に挿入されます。
- ある段階で、プロセスはキューの先頭に到達し、CPU が割り当てられます。
- プロセスが指定されたキューのタイムスライス内に完了すると、システムから終了します。
- プロセスが自発的に CPU の制御を放棄すると、キュー ネットワークから離脱し、プロセスが再び準備完了になると、以前に放棄した同じキューの末尾に挿入されます。
- プロセスがすべての量子時間を使用した場合、そのプロセスはプリエンプトされ、次の下位レベルのキューの末尾に挿入されます。この次の下位レベルのキューには、前の上位レベルのキューよりも大きな量子時間が割り当てられます。
- このスキームは、プロセスが完了するか、ベースレベルのキューに到達するまで継続されます。
- ベースレベルキューでは、プロセスは完了してシステムから出るまでラウンドロビン方式で循環します。ベースレベルキュー内のプロセスは先着順でスケジュールすることもできます。[6]
- オプションとして、プロセスが I/O をブロックする場合、そのプロセスは1 レベル昇格され、次の上位のキューの最後に配置されます。これにより、I/O にバインドされたプロセスがスケジューラによって優先され、プロセスがベース レベルのキューを回避できるようになります。
スケジューリングでは、スケジューラは常に最上位レベルのキューの先頭からプロセスを取得します。最上位レベルのキューが空になった場合にのみ、スケジューラは次の下位レベルのキューからプロセスを取得します。後続の下位レベルのキューでプロセスを取得する場合も同じポリシーが実装されています。一方、プロセスが上位レベルのキューのいずれかに入ると、下位レベルのキューのプロセスをプリエンプトします。
また、新しいプロセスは常に最上位レベルのキューの末尾に挿入され、短時間で完了すると想定されます。時間のかかるプロセスは、時間消費と対話レベルに基づいて自動的に下位レベルのキューに送られます。マルチレベル フィードバック キューでは、プロセスは下位レベルのキューに強制的に送られる前に、特定のキュー レベルで完了するチャンスが 1 回だけ与えられます。
スケジュールパラメータ
一般的に、マルチレベルフィードバックキュースケジューラは以下のパラメータによって定義される。[6]
- キューの数。
- 各キューのスケジューリング アルゴリズムは FIFO と異なる場合があります。
- プロセスをより高い優先度のキューに昇格させるタイミングを決定するために使用される方法。
- プロセスを優先度の低いキューに降格するタイミングを決定するために使用される方法。
- プロセスがサービスを必要とするときに、そのプロセスがどのキューに入るかを決定するために使用される方法。
外部リンク
- マルチレベルフィードバックキュースケジューラ — Solaris 2.6 タイムシェアリング
- タイムシェアリングシステムにおける混合スケジューリング規律のプロセッサ共有キューイングモデル
参照
参考文献
- ^ Silberschatz, Abraham (1994).オペレーティングシステムの概念、第 4 版。Addison-Wesley。p. 131。ISBN 978-0-201-50480-4。
- ^ Corbató, Fernando J.; Merwin-Daggett, Marjorie; Daley, Robert C. (1962)。「実験的なタイムシェアリングシステム」。1962年 5 月 1 日から 3 日にかけて開催された春季合同コンピュータ会議 - AIEE-IRE '62 (春季) の議事録。p. 335。doi :10.1145/1460833.1460871。S2CID 14363753 。
- ^ Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014). 「マルチレベルフィードバックキュー」。オペレーティングシステム: 3 つの簡単な部分(PDF)。Arpaci-Dusseau の本。
- ^ Silberschatz, Abraham (1994).オペレーティングシステムの概念、第 4 版。Addison-Wesley。p. 147。ISBN 978-0-201-50480-4。
- ^ Silberschatz, Abraham (1994).オペレーティングシステムの概念、第 4 版。Addison-Wesley。p. 148。ISBN 978-0-201-50480-4。
- ^ ab シルバーシャッツ、アブラハム、ガルビン、ピーター・ベア、ガニエ、グレッグ (2008)。オペレーティングシステムの概念(第 8 版)。ホーボーケン、ニュージャージー: ワイリー。p. 198。ISBN 978-0470128725。