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

このオペレーティングシステムのチュートリアルでは、次のことを学びます。

• ラウンドロビン スケジューリングとは何ですか。
• ラウンドロビンスケジューリングの特徴
• ラウンドロビンスケジューリングの例
• ラウンドロビンスケジューリングの利点
• ラウンドロビンスケジューリングの欠点
• ワーストケース遅延

Round-Robin Schedulingの特性

Round-Robin Schedulingの主要特性は、以下の通りです。

• ラウンドロビンはプリエンプティブアルゴリズムである
• CPUは一定時間後に次の処理に移行する（タイムクオンティティ/タイムスライスと呼ばれる）。
• プリエンプトされたプロセスはキューの最後に追加されます。
• ラウンドロビンはクロック駆動のハイブリッドモデルです。
• タイムスライスは最小でなければならず、処理すべき特定のタスクに割り当てられます。
• ラウンドロビンは最も古く、最も公平で、最も簡単なアルゴリズムの1つで、従来のOSで広く使われているスケジューリング方法である。

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

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

プロセスキュー	バーストタイム
P1	4つのプロセス。
P2	3
P3	5

ステップ1）プロセスP1から実行されます。 バーストタイム4である。 ここで、各プロセスは2秒間実行される。 P2 と P3 はまだ待ち行列にいる。

ステップ2) time=2でP1がキューの最後に追加され、P2が実行を始める

ステップ3) time=4でP2が先取りされキューの終わりに追加される。 P3が実行を開始する。

ステップ4) time=6で、P3がpreemptedされ、キューの末尾に追加されます。 P1が実行を開始する。

ステップ5) time=8で、P1のバーストタイムが4となり、実行が完了しました。 P2は実行を開始する

ステップ6) P2はバーストタイムが3であり、すでに2区間実行されている。 time=9でP2は実行を終了する。 その後、P3が実行を開始し、完了する。

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

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

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

以下、ラウンドロビンスケジューリング方式の利点について説明します。

• スターベーションやコンボイ効果の問題に直面しない。
• すべてのジョブがCPUの公平な割り当てを受ける。
• すべてのプロセスを優先順位なしで処理できる。
• 実行キューのプロセスの総数がわかれば、同じプロセスの最悪の応答時間を想定できる。
• このスケジューリング方法はバーストタイムには依存しない。 そのため、システム上で容易に実装可能である。
• あるプロセスが特定の期間実行されると、そのプロセスは先取りされ、別のプロセスがその期間実行される。
• 先取りされたプロセスの状態を保存するためにOSがコンテキスト切り替え法を使用できるようにする。
• 平均応答時間の面で最高の性能を得ることができる。

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

ここで、ラウンドロビンスケジューリングを使用する場合の欠点/短所を挙げます。

• OSのスライス時間が短い場合、プロセッサの出力が低下します。
• この方式はコンテキストスイッチに多くの時間を費やします。
• この方式の性能は時間量子に大きく依存します。
• プロセスに優先順位を設定できません。
• Decreases comprehension
• Lower time quantum results in higher the context switching overhead in the system.
• Finding a correct time quantum is a quite difficult task in this system.

Worst Case Latency

The term is used for the maximum time taking for all the tasks execution.この用語を使用すると、全タスクを実行する際に最大時間がかかります。

• dt = タスクがリストに入ったときの検出時間
• st = あるタスクから別のタスクへの切り替え時間
• et = タスク実行時間

計算式。

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

概要：

• このアルゴリズムの名前は、ラウンドロビンの原則（各人が順番に何かを等しく取り分ける）に由来する。
• ラウンドロビンは、最も古くて公平で簡単なアルゴリズムの1つで、従来のOSで広く使われているスケジューリング方法である。
• ラウンドロビンはプリエンプティブアルゴリズムである
• ラウンドロビンスケジューリング法の最大の利点は、実行キューのプロセスの総数がわかっていれば、同じプロセスの最悪応答時間も想定できることである。
• この方法はコンテキストスイッチングに多くの時間を費やします
• ワーストケース待ち時間とは、すべてのタスクの実行にかかる最大時間を表す言葉です

。