round-robin scheduling

ウィキペディア

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/11/14 15:22 UTC 版)

マルチタスク > スケジューリング > ラウンドロビン・スケジューリング

ラウンドロビン・スケジューリングは、オペレーティングシステムなどにおけるプロセスなどに関するスケジューリング規則のひとつで、単純な部類に分類される一種である。実行可能状態にあるプロセスに、順番にプロセッサを割り当てる。順番に交代する、という意の「ラウンドロビン」が名前の由来である。原始的なラウンドロビン・スケジューリングは単純で実装が容易であり、優先度をつけたり、他のアルゴリズムと併用しなければ、リソーススタベーションも発生しない。

また、優先度のあるシステムにおいても、同一優先度のプロセス群への割当てに、ラウンドロビンを採用することもある。

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

実施例

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

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

以上は、タスクが待ち状態に入ったりせず（普通のシステムでは何か（ファイルなどに限らず、組込みシステムでセンサ類にコマンドを送信して、データが来るのを待つこともある）を待つことが多いし、そういった場合にCPUを手放さないのは問題である）、また同時に、タイマ割込みなどを利用してプリエンプティブするようなシステムの場合である。ノン-プリエンプティブなシステム（いわゆる協調型マルチタスク）では単に、環状リストなどを用意して、あるタスクから抜けてきたら次のタスクを呼ぶ、といったような動作として実装される（すなわち、「各タスクに同一の長さのCPU時間を割り当てる」というのは、必ずしもラウンドロビン・スケジューリングの要件ではない、ということである）。

加重ラウンドロビン

加重ラウンドロビン (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. 2010年7月18日時点のオリジナルよりアーカイブ。2006年8月18日閲覧。
• 5. プロセス - The Linux Kernel