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

ラウンドロビン・スケジューリングとは

ラウンドロビン・スケジューリングは、オペレーティングシステムにおけるプロセス管理の基礎となるスケジューリングアルゴリズムの一つです。その名の通り、プロセスを順番に、一定の時間単位で実行させることで、リソースを公平に分配しようとするものです。

基本的な仕組み

ラウンドロビン方式では、実行可能な状態にあるプロセスを順番に並べ、それぞれに「タイムスロット」または「クォンタム」と呼ばれる、一定のCPU時間を与えます。各プロセスは割り当てられた時間だけ実行され、時間が来ると中断され、次のプロセスにCPUが移ります。このサイクルを繰り返すことで、全てのプロセスが少しずつCPU時間を得ることができます。

例えば、job1に100[ミリ秒]のクォンタムが与えられたとします。もしjob1の処理が完了するのに250ms必要であれば、まず100ms実行された後、job1は一時中断され、他のプロセスにCPUが譲られます。そして、すべてのプロセスが順番に100msずつ実行された後、再びjob1に100msのCPU時間が与えられます。このプロセスを繰り返すことで、最終的にjob1は全ての処理を完了できます。

特徴と利点

単純さと実装の容易さ: アルゴリズムがシンプルであるため、実装が容易です。
公平性: 各プロセスに平等にCPU時間が割り当てられるため、一部のプロセスがリソースを独占することを防ぎます。
リソーススタベーションの回避: 優先度設定や他のアルゴリズムとの組み合わせがない限り、特定のプロセスがいつまでも実行されないといったリソーススタベーションの問題は発生しません。

適用範囲

ラウンドロビン・スケジューリングは、オペレーティングシステムだけでなく、ネットワークのスケジューリングにも応用できます。特に無線ネットワークでは、複数のステーションが同じチャンネルを共有するため、ラウンドロビン方式で各ステーションに送受信の機会を公平に与えることができます。

課題と限界

ラウンドロビンは一見すると公平なアルゴリズムですが、いくつかの課題も抱えています。

通信品質や転送速度の差異への非対応: 各ステーションの通信品質や転送速度の違いを考慮していないため、必ずしも最適なサービスを提供できない場合があります。例えば、通信状態の悪いステーションにも平等に時間を割り当てるため、ネットワーク全体の効率を低下させる可能性があります。
回線容量の減少: 受信機が受信可能な状態かどうかを考慮せずにスケジュールするため、約半分の時間は受信不可能な受信機に時間を割り当ててしまい、結果としてネットワークの回線容量が減少する可能性があります。

加重ラウンドロビン (WRR)

加重ラウンドロビン (WRR) は、ラウンドロビンの公平性を保ちつつ、各プロセスに異なる優先度を設定できるように拡張したアルゴリズムです。各プロセスに重み付けを行い、その重みに比例したCPU時間を割り当てることで、優先度の高いプロセスにより多くのリソースを与えることができます。

しかし、WRRでは適切な重み付けを行うために、平均パケットサイズを事前に知っておく必要があり、それが難しい場合があります。

不足ラウンドロビン (DRR)

不足ラウンドロビン (DRR) は、WRRの課題を解決するために提案されたアルゴリズムです。DRRでは、各プロセスに「不足カウンタ」を設定し、割り当てられたCPU時間の残りを管理します。これにより、平均パケットサイズを事前に知らなくても、様々なサイズのパケットを効率的に処理できるようになりました。

DRRは、各フロー（コネクション）の1ラウンド当たりの通信量を「加重 × F」として不足カウンタに設定します。各フローで送出したパケットサイズを不足カウンタから減算し、不足カウンタが負にならない限り送出を続けます。ラウンドの最後には不足カウンタに再度「加重 × F」を加えて次のラウンドに備えます。

まとめ

ラウンドロビン・スケジューリングは、シンプルで実装が容易なため、多くのシステムで利用されています。しかし、その単純さゆえに、考慮すべき課題も存在します。加重ラウンドロビンや不足ラウンドロビンなどの派生アルゴリズムは、これらの課題を解決するための改良版として提案されており、より複雑な環境でより効率的なリソース管理を実現できます。

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