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

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

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

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

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

次の3つのプロセスを検討してください

プロセスキュー	バースト時間
P1	4
P2	3
P3	5

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

ステップ 2) 時間 =2 で、P1 がキューの最後に追加され、P2 が実行を開始します。

ステップ3） time=4 で、P2 がプリエンプトされ、キューの最後に追加されます。 P3 が実行を開始します。

ステップ4） time=6 で、P3 がプリエンプトされ、キューの最後に追加されます。 P1 が実行を開始します。

ステップ5） time=8 では、P1 のバースト時間は 4 です。実行が完了しています。 P2 が実行を開始します

ステップ6） P2 のバースト時間は 3 です。すでに 2 インターバルにわたって実行されています。 time=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	
t,SR = sum of all execution times

要約

• このアルゴリズムの名前は、各人が順番に何かを均等に分配するラウンドロビンの原理に由来しています。
• ラウンドロビンは、最も古く、公平で、簡単なアルゴリズムの1つであり、従来のスケジューリング方法で広く使用されている。 OS.
• ラウンドロビンは先制アルゴリズムです
• ラウンドロビン スケジューリング方法の最大の利点は、実行キュー上のプロセスの総数がわかっている場合、同じプロセスの最悪の場合の応答時間も想定できることです。
• この方法ではコンテキストの切り替えに時間がかかります
• 最悪の場合の遅延は、すべてのタスクの実行にかかる最大時間を表す用語です。