ラウンドロビンスケジューリングアルゴリズムと例

ラウンドロビンスケジューリングとは何ですか?

このアルゴリズムの名前は、各人が順番に何かを均等に分配するラウンドロビンの原理に由来しています。 これは最も古く、最も単純なスケジューリング アルゴリズムであり、主にマルチタスクに使用されます。

ラウンドロビン方式のスケジューリングでは、準備完了した各タスクは、限られた時間枠内で順番に循環キュー内で実行されます。このアルゴリズムは、プロセスの飢餓状態を回避した実行も実現します。

ラウンドロビンスケジューリングの特徴

ラウンドロビン スケジューリングの重要な特徴は次のとおりです。

• ラウンドロビンは、先制的なアルゴリズムである。
• CPUは、一定の時間間隔（タイムクォンタム／タイムスライスと呼ばれる）が経過すると、次のプロセスに切り替わります。
• プリエンプトされたプロセスはキューの最後に追加されます。
• ラウンドロビン方式は、クロック駆動型のハイブリッドモデルです。
• タイムスライスは最小限に抑えるべきであり、処理が必要な特定のタスクに割り当てられる。ただし、OSによって異なる場合がある。
• これは、特定の時間制限内にイベントに対応するリアルタイムアルゴリズムです。
• ラウンドロビン方式は、最も古く、最も公平で、最も簡単なアルゴリズムの一つです。
• これは、従来のOSで広く用いられているスケジューリング手法である。

ラウンドロビンスケジューリングの例

次の3つのプロセスについて考えてみましょう。

ステップ1） 実行は、バースト時間 1 のプロセス P4 から始まります。ここでは、すべてのプロセスが 2 秒間実行されます。 P2 と P3 はまだ待機キューにあります。

ステップ2） 時刻 2 において、P1 がキューの末尾に追加され、P2 の実行が開始される。

ステップ3） 時刻 4 において、P2 はプリエンプトされ、キューの末尾に追加されます。P3 の実行が開始されます。

ステップ4） 時刻 6 において、P3 はプリエンプトされ、キューの末尾に追加されます。P1 の実行が開始されます。

ステップ5） 時刻 8 において、P1 のバースト時間は 4 であり、実行が完了しました。P2 の実行が開始されます。

ステップ6） P2のバースト時間は3です。すでに2つのインターバルが実行されています。時刻が9の時点で、P2の実行が完了します。その後、P3の実行が開始され、完了するまで続きます。

ステップ7） 上記の例における平均待ち時間を計算してみましょう。

Wait time
P1 = 0 + 4 = 4
P2 = 2 + 4 = 6
P3 = 4 + 3 = 7

ラウンドロビン方式のスケジューリングの利点

ラウンドロビン方式のスケジューリング方法の長所／利点は以下のとおりです。

• 飢餓や輸送隊の影響といった問題に直面しない。
• すべてのジョブに CPU が公平に割り当てられます。
• 優先順位を一切考慮せず、すべてのプロセスを処理します。
• 実行キュー上のプロセスの総数がわかっている場合は、同じプロセスの最悪の場合の応答時間を想定することもできます。
• このスケジューリング方法はバースト時間に依存しないため、システムへの実装が容易です。
• 特定の期間にわたってプロセスが実行されると、そのプロセスはプリエンプトされ、その指定された期間にわたって別のプロセスが実行されます。
• OSがコンテキストスイッチング方式を使用して、プリエンプトされたプロセスの状態を保存できるようにします。
• 平均応答時間の点で最高のパフォーマンスが得られます。

ラウンドロビンスケジューリングの欠点

ラウンドロビン方式のスケジューリングにおける欠点／デメリットは以下のとおりです。

• OSのスライス処理時間が短い場合、プロセッサの出力は低下します。
• この方法は、コンテキスト切り替えに多くの時間を費やします。
• そのパフォーマンスは時間量子に大きく依存します。
• プロセスに優先順位を設定することはできません。
• ラウンドロビン方式のスケジューリングでは、より重要なタスクに特別な優先順位は与えられません。
• 理解度を低下させる。
• タイムクォンタムが短いほど、システムにおけるコンテキストスイッチングのオーバーヘッドが大きくなる。
• このシステムにおいて、適切な時間量子を見つけることは非常に困難な作業である。

最悪の場合の遅延

この用語は、すべてのタスクの実行にかかる最大時間を指します。

• dt = タスクがリストに取り込まれたときの検出時間を示す
• st = あるタスクから別のタスクへの切り替え時間を示す
• et = タスク実行時間を示す

式：

Tworst = {(dti+ sti + eti ), + (dti+ sti + eti )2 +...+ (dti+ sti + eti )N., + (dti+ sti + eti  + eti) N} + tISR
tISR = sum of all execution times

よくあるご質問