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

出典: フリー百科事典『ウィキペディア（Wikipedia）』

ラウンドロビン・スケジューリングは、オペレーティングシステムにおけるプロセスに関する単純なスケジューリングアルゴリズムの一種である。処理待ち状態のプロセスに対し、優先度を設定せずに順番に同じタイムスライスを割り当てる方式を呼ぶ。

ラウンドロビン・スケジューリングは単純で実装が容易であり、リソーススタベーションも発生しない。ラウンドロビン・スケジューリングはネットワークのスケジューリングなどにも適用可能である。

無線ネットワークでは、多くのステーションが1つのチャンネルを共有するので、ラウンドロビン方式を使って各ステーションが定期的に送受信する機会を与える。ラウンドロビンは公正なアルゴリズムのように思われるかもしれない。しかし、各ステーションの通信品質や転送速度の違いを考慮していないため、必ずしも最適なサービスを提供できない。また、ネットワークの容量(バンド幅)も確実に減少する。その主な原因は受信機が受信可能な状態かどうかを考慮せずにスケジュールするため、約半分の時間は受信不可能な受信機に時間を割り当ててしまうことにある。これに対して Proportionally-Fairスケジューリングは平均以上の確率で送受信可能なステーションとの通信をスケジュールすることができる。

このアルゴリズムの名称の由来については、ラウンドロビンを参照されたい。

なお、優先度のあるスケジューリング方式でも同一優先度のプロセス群についてはラウンドロビン・スケジューリングが使用されることが多い。

[編集] 実施例

各タスク(またはジョブ)にはタイムスロットあるいは「クォンタム; quantum」が割り当てられる(CPU時間の割り当てであり、例えば100ミリ秒といった長さ)。job1が完了までに250msかかるとき、ラウンドロビンスケジューラは job1 が 100ms 間実行された後で中断し、他のジョブにCPU時間を割り当てる。他のジョブがそれぞれ同じ時間(100ms)ずつ実行された後、job1 にはさらに100msのCPU時間が割り当てられ、ラウンドロビンスケジューラがその実行を中断して別のジョブにCPU時間を割り当てる。再度、他のジョブがそれぞれ同じ時間(100ms)ずつ実行された後、job1 が再度実行され、最後まで実行されることになる。

Job1 = 完了までにかかる時間は 250ms (クォンタムは 100ms)
1. 1回目の割り当て = 100ms
2. 2回目の割り当て = 100ms
3. 3回目の割り当て = 100ms ただし job1 は 50ms 実行した時点で終了
4. job1 の全CPU時間 = 250ms

[編集] 加重ラウンドロビン

加重ラウンドロビン(Weighted Round-robin、WRR)は、ベストエフォート型接続のスケジューリング方式である。Generalized Processor Sharing (GPS)方式の最も簡単なエミュレーションでもある。GPSでは空でないコネクションについて無限小(infinitesimal)のデータ量を考慮するのに対して、WRRは空でないコネクションについてパケット数を考慮する(パケット数 = 正規化(加重 / 平均パケットサイズ))。

正規化された加重を得るには、平均パケットサイズを知る必要がある。そうしないとWRRはGPSのエミュレートとは言えない。事前にその値を知っているのが最善であるが、インターネット上で平均パケットサイズを事前に知ることは困難なので、概算の予測を立てるしかないがそれも難しい。WRRの別の問題点として、1回のラウンドで見たときの公平さの欠如がある。

WRR機構(擬似コード):

//コネクション毎に1回のラウンドで処理すべきパケット数を計算する

for (each connection)
   connection[i].normalized_weight = connection[i].weight / connection[i].mean_packet_size;

min = findSmallestNormalizedWeight();

for (each connection)
   connection[i].packets_to_be_served = connection[i].normalized_weight / min;

// メインループ

while (true)
{
   for (each non-empty connection)
      for (j=0; j< min(connection[i].packets_to_be_served, connection[i].packets_waiting); j++)
         servePacket (connection[i].getPacket());
}

[編集] 不足ラウンドロビン

不足ラウンドロビン(Deficit Round-robin､ DRR)は、加重ラウンドロビン方式の修正版である。DRRは 1995年に M. Shreedhar と G. Varghese が提案した。事前に平均サイズを知らなくても、任意のサイズのパケットを扱うことができる。

ただし、1ラウンドでの送出可能量(F)を事前に決めておく必要がある。各フロー(コネクション)の1ラウンド当たりの通信量は「F×加重」であり、これを不足カウンタ(Deficit Counter)に設定する。各フローについて、送出したパケットサイズを不足カウンタから減算し、不足カウンタが負にならない限り送出を続ける。ラウンドの最後には不足カウンタに再度「F×加重」を加えて次のラウンドに備える。

[編集] 関連項目

[編集] 外部リンク

1.1 プロセス / タスク管理 - BTRON3仕様書 Ver 3.20.00より
5. プロセス - The Linux Kernel

カテゴリ: OSのプロセス管理 | コンピュータネットワーク | 並行計算

See also ebooksgratis.com: no banners, no cookies, totally FREE.