到着時間が異なるプロセスに対応するラウンドロビンスケジューリングの徹底解説

ラウンドロビン(Round Robin、RR)は、各プロセスに「クォンタム(タイムスライス)」と呼ばれる固定の実行時間を順番に割り当てる、プリエンプティブ(強制的に割り込み可能な)CPUスケジューリングアルゴリズムです。全プロセスの到着時刻がゼロであることを前提とする標準的なラウンドロビンとは異なり、この記事で扱うバリアントは、プロセスがそれぞれ異なる時刻に到着するケースに対応します。レディキュー(実行待ち行列)が動的に変化するため、スケジューリングはより複雑になります。

プリエンプティブなスケジューリングでは、実行中のプロセスは割り込まれてレディキューの末尾へ戻されることがあります。ラウンドロビンは各プロセスに均等なCPU時間を与えることで公平性を確保し、スタベーション(特定のプロセスが永遠に実行されない状態)を防ぎながら、対話型システムに求められる良好な応答時間を維持します。

到着時間が異なる場合のラウンドロビンの動作

プロセスの到着時刻が異なる場合、アルゴリズムは以下の手順で動作します。

• プロセスは到着時刻の順にレディキューへ追加される
• CPUは先頭の実行可能なプロセスを、クォンタム時間だけ処理する
• クォンタム内で処理が完了すれば、そのプロセスは終了する
• 完了しなかった場合は、レディキューの末尾へ移動する
• 新しく到着したプロセスはレディキューに加わり、自分の順番を待つ
• コンテキストスイッチにより、割り込まれたプロセスの状態が保存される

主な特徴

• スタベーションの防止： すべてのプロセスがいずれ必ずCPU時間を得られる
• 公平なスケジューリング: 全プロセスに同一のクォンタム時間を付与
• 優れた応答性： 対話型システムやリアルタイムシステムに適している
• コンテキストスイッチのオーバーヘッド: クォンタムが小さいほど切り替えコストが増加する

例1:クォンタム時間 = 2 の場合

異なる到着時刻とバースト時間(CPU使用時間)を持つ3つのプロセスを考えてみましょう。

ガントチャート(クォンタム = 2)

P1(0〜2)→ P2(2〜4)→ P3(4〜6)→ P1(6〜8)→ P2(8〜9)→ P3(9〜14)

ステップごとの実行内容

平均時間の計算

平均ターンアラウンドタイム =(8 + 8 + 12)÷ 3 = 9.33単位

平均待ち時間 =(4 + 5 + 5)÷ 3 = 4.67単位

例2:クォンタム時間 = 4 の場合

次に、より大きなクォンタムサイズを使用した場合を見てみましょう。

ガントチャート(クォンタム = 4)

P2(0〜4)→ P3(4〜8)→ P1(8〜12)→ P2(12〜15)→ P3(15〜20)→ P1(20〜24)

平均ターンアラウンドタイム =(22 + 15 + 19)÷ 3 = 18.67単位

平均待ち時間 =(14 + 8 + 10)÷ 3 = 10.67単位

まとめ

到着時刻が異なるプロセスを扱うラウンドロビンスケジューリングは、動的に変化するプロセスの到着に対応しながら、公平なCPU割り当てを実現します。クォンタムサイズはパフォーマンスに大きな影響を与えます。小さなクォンタムは応答時間を改善する一方でコンテキストスイッチのオーバーヘッドを増大させ、逆に大きなクォンタムは公平性が低下する可能性があるものの、スループットの向上につながります。