変動するプロセス到着時間に合わせて最適化されたラウンドロビンスケジューリング

ラウンド ロビン (RR) は、各プロセスにクォンタムと呼ばれる固定タイム スライスが割り当てられるプリエンプティブ CPU スケジューリング アルゴリズムです。到着時間がゼロの標準的なラウンド ロビンとは異なり、このバリアントは異なる時間に到着するプロセスを処理するため、レディ キューが動的に変化するため、スケジューリングがより複雑になります。

プリエンプティブ スケジューリングでは、実行中のプロセスが中断され、レディ キューに戻されることがあります。ラウンド ロビンは、各プロセスに均等な CPU 時間を与えることで公平性を確保し、対話型システムの良好な応答時間を維持しながら飢餓を防ぎます。

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

プロセスの到着時間が異なる場合、アルゴリズムは次の手順に従います。

• プロセスは到着時間に基づいて準備完了キューに入ります

• CPU は、クォンタム期間中に最初に利用可能なプロセスを実行します

• プロセスがクォンタム内で完了すると、終了します。

• 完了していない場合は、準備完了キューの最後に移動します

• 新しい到着者は準備の列に加わり、順番を待ちます

• コンテキストの切り替えにより、プリエンプトされたプロセスの状態が保存されます

主な機能

• 飢餓を防ぐ すべてのプロセスは最終的に CPU 時間を取得します

• 公平なスケジューリング すべてのプロセスの均等な時間量

• 優れた応答時間 インタラクティブなリアルタイム システムに適しています

• コンテキスト切り替えのオーバーヘッド クォンタムが小さいほど、スイッチング コストが増加します

例 1 量子時間 =2

到着時間とバースト時間が異なる 3 つのプロセスを考えてみましょう。

プロセス 到着時刻 バースト時間 P104P213P327

ガントチャート？ラウンドロビン (量子 =2) P1 P2 P3 P1 P2 P3 0 2 4 6 8 9 14

ステップバイステップの実行

時刻 プロセス 準備完了キュー アクション 0-2P1P1P1 は 2 ユニット実行、P2 は t=12 に到着-4P2P2、P1P2 は 2 ユニット実行、P3 は t=24 に到着-6P3P3、P1P3 は 2 ユニット実行6-8P1P1、P2、P3P1 は残り 2 ユニットを完了8-9P2P2、P3P2 は残り 1 ユニットを完了9-14P3P3P3残りの5ユニットを完了します

平均時間の計算

プロセス 到着 バースト 完了 ターンアラウンド 待機中 P104884P213985P32714125

平均所要時間 =(8 + 8 + 12) / 3 =9.33 単位

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

例 2 量子時間 =4

より大きな量子サイズの場合:

プロセス 到着時刻 バースト時間 P128P207P319

ガントチャート？ラウンドロビン (クォンタム =4) P2 P3 P1 P2 P3 P1 0 4 8 12 15 20 24

プロセス 到着 バースト 完了 ターンアラウンド 待機中 P128242214P20715158P319201910

平均所要時間 =(22 + 15 + 19) / 3 =18.67 ユニット

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

結論

異なる到着時間によるラウンド ロビン スケジューリングにより、動的なプロセスの到着を処理しながら、公平な CPU 割り当てが提供されます。量子サイズはパフォーマンスに大きく影響しますか?クォンタムが小さいと応答時間は向上しますが、コンテキスト切り替えのオーバーヘッドが増加します。一方、クォンタムが大きいと公平性は低下しますが、スループットは向上します。