Edited at

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

More than 5 years have passed since last update.

今回はラウンドロビン・スケジューリングについてです。

Wikipedia様によるとプロセスに関する単純なスケジューリングアルゴリズムの一種だそうです。

正直この分野はまともに勉強したことがないので良くわかりません。。。

ラウンドロビンと聞くとLoadbalancerの分散方式しか思い出しません。

そういえばAWSのELBはラウンドロビン+コネクション数を監視しているようです。

[AWSマイスターシリーズ]Amazon Elastic Load Balancing (ELB)

※なんか順番に振られないなーと思ったら上記事情ですね。

話それましたが、


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

について書いていきます。

正直、悩むものでもなかったため、今回もコードとコメントで書いていきます。

問題見た方が早いかも


解法


package aoj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class RoundRobinScheduling {

public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] firstRow = br.readLine().split("\\s");

// 要素数
int elementNum = Integer.parseInt(firstRow[0]);
// 減算する値
int quantum = Integer.parseInt(firstRow[1]);

// 先に入れた物を先に抜き出す(いわゆるFIFO
// ※前回stack,dequeueでやったので今回はqueueで(一番適切そうってのもありますが)
Queue<Process> que = new LinkedList<Process>();
for (int i = 0; i < elementNum; i++) {
String[] stringArray = br.readLine().split("\\s");
// (p1 150)のような形式でstringArrayに渡されるため、
// p1(プロセス名),150(処理に掛かる時間)をインスタンスとして管理する
// ※もっとスマートな方法あるかも。。。
Process process = new Process(stringArray[0],
Integer.parseInt(stringArray[1]));
que.offer(process);
}

// 処理合計時間
int resultTime = 0;
while (que.size() > 0) {
Process process = que.poll();
// 合計処理時間として加算
resultTime += quantum;
// 処理時間を減算する
if ((process.processTime = process.processTime - quantum) > 0) {
// 減算した結果、処理に必要な時間に満たない場合は
// 最後尾に待ちタスクとして保管する
que.offer(process);
continue; // else嫌いなので
}
// processTimeが(-20)などになっていれば、その分の時間を
// 処理合計時間へ加算する
resultTime += process.processTime;
// 処理に必要な時間を満たした場合はプロセス名と、ここまでにかかっている
// 全体の時間を出力する
System.out.println(process.name + " " + resultTime);
}

}

/**
* Process管理クラス
*/

private final static class Process {
// めんどいからpublicに。。。
public String name = null;
public int processTime = 0;

public Process(String name, int processTime) {
this.name = name;
this.processTime = processTime;
}
}
}