|
ラウンドロビン・スケジューリングは、オペレーティングシステムにおけるプロセスに関する単純なスケジューリングアルゴリズムの一種である。処理待ち状態のプロセスに対し、順番に同じタイムスライスを割り当てる方式を呼ぶ。このアルゴリズムの名称の由来については、ラウンドロビンを参照されたい。 原始的なラウンドロビン・スケジューリングは単純で実装が容易であり、優先度をつけたり、他のアルゴリズムと併用しなければ、リソーススタベーションも発生しない。なお、優先度のあるスケジューリング方式でも同一優先度のプロセス群についてはラウンドロビン・スケジューリングが使用されることが多い。 ラウンドロビン・スケジューリングはネットワークのスケジューリングなどにも適用可能である。無線ネットワークでは、多くのステーションが1つのチャンネルを共有するので、ラウンドロビン方式を使って各ステーションが定期的に送受信する機会を与える。ラウンドロビンは公正なアルゴリズムのように思われるかもしれない。しかし、各ステーションの通信品質や転送速度の違いを考慮していないため、必ずしも最適なサービスを提供できない。また、ネットワークの回線容量も確実に減少する。その主な原因は受信機が受信可能な状態かどうかを考慮せずにスケジュールするため、約半分の時間は受信不可能な受信機に時間を割り当ててしまうことにある。これに対して Proportionally-Fairスケジューリングは平均以上の確率で送受信可能なステーションとの通信をスケジュールすることができる。 ==実施例== 各タスク(またはジョブ)にはタイムスロットあるいは「クォンタム; ''quantum''」が割り当てられる(CPU時間の割り当てであり、例えば100ミリ秒といった長さ)。''job1''が完了までに250msかかるとき、ラウンドロビンスケジューラは ''job1'' が 100ms 間実行された後で中断し、他のジョブにCPU時間を割り当てる。他のジョブがそれぞれ同じ時間(100ms)ずつ実行された後、''job1'' にはさらに100msのCPU時間が割り当てられ、ラウンドロビンスケジューラがその実行を中断して別のジョブにCPU時間を割り当てる。再度、他のジョブがそれぞれ同じ時間(100ms)ずつ実行された後、''job1'' が再度実行され、最後まで実行されることになる。 job1 = 完了までにかかる時間は 250ms (クォンタムは 100ms) 1回目の割り当て = 100ms 2回目の割り当て = 100ms 3回目の割り当て = 100ms ただし job1 は 50ms 実行した時点で終了 job1 の全CPU時間 = 250ms 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ラウンドロビン・スケジューリングは、オペレーティングシステムにおけるプロセスに関する単純なスケジューリングアルゴリズムの一種である。処理待ち状態のプロセスに対し、順番に同じタイムスライスを割り当てる方式を呼ぶ。このアルゴリズムの名称の由来については、ラウンドロビンを参照されたい。原始的なラウンドロビン・スケジューリングは単純で実装が容易であり、優先度をつけたり、他のアルゴリズムと併用しなければ、リソーススタベーションも発生しない。なお、優先度のあるスケジューリング方式でも同一優先度のプロセス群についてはラウンドロビン・スケジューリングが使用されることが多い。ラウンドロビン・スケジューリングはネットワークのスケジューリングなどにも適用可能である。無線ネットワークでは、多くのステーションが1つのチャンネルを共有するので、ラウンドロビン方式を使って各ステーションが定期的に送受信する機会を与える。ラウンドロビンは公正なアルゴリズムのように思われるかもしれない。しかし、各ステーションの通信品質や転送速度の違いを考慮していないため、必ずしも最適なサービスを提供できない。また、ネットワークの回線容量も確実に減少する。その主な原因は受信機が受信可能な状態かどうかを考慮せずにスケジュールするため、約半分の時間は受信不可能な受信機に時間を割り当ててしまうことにある。これに対して Proportionally-Fairスケジューリングは平均以上の確率で送受信可能なステーションとの通信をスケジュールすることができる。==実施例==各タスク(またはジョブ)にはタイムスロットあるいは「クォンタム; ''quantum''」が割り当てられる(CPU時間の割り当てであり、例えば100ミリ秒といった長さ)。''job1''が完了までに250msかかるとき、ラウンドロビンスケジューラは ''job1'' が 100ms 間実行された後で中断し、他のジョブにCPU時間を割り当てる。他のジョブがそれぞれ同じ時間(100ms)ずつ実行された後、''job1'' にはさらに100msのCPU時間が割り当てられ、ラウンドロビンスケジューラがその実行を中断して別のジョブにCPU時間を割り当てる。再度、他のジョブがそれぞれ同じ時間(100ms)ずつ実行された後、''job1'' が再度実行され、最後まで実行されることになる。 job1 = 完了までにかかる時間は 250ms (クォンタムは 100ms) 1回目の割り当て = 100ms 2回目の割り当て = 100ms 3回目の割り当て = 100ms ただし job1 は 50ms 実行した時点で終了 job1 の全CPU時間 = 250ms」の詳細全文を読む スポンサード リンク
|