ラウンドロビン・スケジューリングは、オペレーティングシステムにおけるプロセスに関する単純なスケジューリングアルゴリズムの一種である。処理待ち状態のプロセスに対し、順番に同じタイムスライスを割り当てる方式を呼ぶ。このアルゴリズムの名称の由来については、ラウンドロビンを参照されたい。原始的なラウンドロビン・スケジューリングは単純で実装が容易であり、優先度をつけたり、他のアルゴリズムと併用しなければ、リソーススタベーションも発生しない。なお、優先度のあるスケジューリング方式でも同一優先度のプロセス群についてはラウンドロビン・スケジューリングが使用されることが多い。ラウンドロビン・スケジューリングはネットワークのスケジューリングなどにも適用可能である。無線ネットワークでは、多くのステーションが1つのチャンネルを共有するので、ラウンドロビン方式を使って各ステーションが定期的に送受信する機会を与える。ラウンドロビンは公正なアルゴリズムのように思われるかもしれない。しかし、各ステーションの通信品質や転送速度の違いを考慮していないため、必ずしも最適なサービスを提供できない。また、ネットワークの回線容量も確実に減少する。その主な原因は受信機が受信可能な状態かどうかを考慮せずにスケジュールするため、約半分の時間は受信不可能な受信機に時間を割り当ててしまうことにある。これに対して は平均以上の確率で送受信可能なステーションとの通信をスケジュールすることができる。各タスク(またはジョブ)にはタイムスロットあるいは「クォンタム; "quantum"」が割り当てられる(CPU時間の割り当てであり、例えば100ミリ秒といった長さ)。"job1"が完了までに250msかかるとき、ラウンドロビンスケジューラは "job1" が 100ms 間実行された後で中断し、他のジョブにCPU時間を割り当てる。他のジョブがそれぞれ同じ時間(100ms)ずつ実行された後、"job1" にはさらに100msのCPU時間が割り当てられ、ラウンドロビンスケジューラがその実行を中断して別のジョブにCPU時間を割り当てる。再度、他のジョブがそれぞれ同じ時間(100ms)ずつ実行された後、"job1" が再度実行され、最後まで実行されることになる。加重ラウンドロビン(Weighted Round-robin、WRR)は、ベストエフォート型接続のスケジューリング方式である。方式の最も簡単なエミュレーションでもある。GPSでは空でないコネクションについて無限小(infinitesimal)のデータ量を考慮するのに対して、WRRは空でないコネクションについてパケット数を考慮する(パケット数 = 正規化(加重 / 平均パケットサイズ))。正規化された加重を得るには、平均パケットサイズを知る必要がある。そうしないとWRRはGPSのエミュレートとは言えない。事前にその値を知っているのが最善であるが、インターネット上で平均パケットサイズを事前に知ることは困難なので、概算の予測を立てるしかないがそれも難しい。WRRの別の問題点として、1回のラウンドで見たときの公平さの欠如がある。WRR機構(擬似コード)://コネクション毎に1回のラウンドで処理すべきパケット数を計算するfor (each connection)min = findSmallestNormalizedWeight();for (each connection)// メインループwhile (true) {不足ラウンドロビン(Deficit Round-robin､ DRR)は、加重ラウンドロビン方式の修正版である。DRRは 1995年に M. Shreedhar と G. Varghese が提案した。事前に平均サイズを知らなくても、任意のサイズのパケットを扱うことができる。ただし、1ラウンドでの送出可能量(F)を事前に決めておく必要がある。各フロー(コネクション)の1ラウンド当たりの通信量は「加重 × F」であり、これを不足カウンタ(Deficit Counter)に設定する。各フローについて、送出したパケットサイズを不足カウンタから減算し、不足カウンタが負にならない限り送出を続ける。ラウンドの最後には不足カウンタに再度「加重 × F」を加えて次のラウンドに備える。

出典:wikipedia