はじめに
こんにちは、kuwaです。
本記事では、C言語による キューを使ったラウンドロビンスケジューリングのシュミレーション のサンプルコードを紹介します。
⚠️ 本記事は個人的な学習メモとして作成したものであり、内容に誤りが含まれている可能性があります。参考にされる際はご注意ください。
キューとラウンドロビンスケジューリング
ラウンドロビンスケジューリング は、OSのCPUスケジューリングなどで用いられる方式で、すべてのプロセスに公平にCPU時間を割り当てる方法です。
各プロセスには最大 q ミリ秒（クオンタム）の処理時間が与えられ、処理が終わらなければ再び待ち行列の末尾に追加されます。
例：
クオンタム q = 100 のとき、以下のようなキューがあったとします：
A(150) - B(80) - C(200) - D(200)
- A を 100ms 処理 → A(残り50) を末尾に追加
- B を 80ms 処理 → 終了（時刻 180ms）
- C を 100ms 処理 → C(残り100) を末尾に追加
- D を 100ms 処理 → D(残り100) を末尾に追加
- A を 50ms 処理 → 終了（時刻 450ms）
…というように、すべてのプロセスが完了するまで繰り返します。
入出力仕様
入力
入力の形式は以下の通りです。
n q
name_1 time_1
name_2 time_2
...
name_n time_n
-
n：プロセスの数 -
q：クオンタム（1回の実行で最大何ms処理できるか） -
name_i：各プロセスの名前（英数字からなる文字列） -
time_i：各プロセスが必要とする実行時間（ms）
出力
各プロセスが 終了した順 に、
プロセス名 終了時刻
の形式で出力します。
制約
- 1 ≤ n ≤ 100,000
- 1 ≤ q ≤ 1,000
- 1 ≤ time_i ≤ 50,000
- 1 ≤ name_i の長さ ≤ 10
- ∑time_i ≤ 1,000,000
入出力例
入力例 1
5 100
p1 150
p2 80
p3 200
p4 350
p5 20
入力例 1 に対する出力
p2 180
p5 400
p1 450
p3 550
p4 800
サンプルコード
#include <stdio.h>
#include <stdlib.h>
#define LEN 100005
#define NAME_LEN 100
typedef struct pp {
char name[NAME_LEN];
int time;
} Process;
Process Q[LEN];
int head = 0;
int tail = 0;
void enqueue(Process x) {
Q[tail] = x;
tail = (tail + 1) % LEN;
}
Process dequeue() {
Process x = Q[head];
head = (head + 1) % LEN;
return x;
}
int main(void) {
int elaps = 0; // 経過時間
int n, quantum;
scanf("%d %d", &n, &quantum);
for (int i = 0; i < n; i++) {
Process p;
scanf("%s %d", p.name, &p.time);
enqueue(p);
}
while (head != tail) {
Process p = dequeue();
if (p.time > quantum) {
elaps += quantum;
p.time -= quantum;
enqueue(p);
} else {
elaps += p.time;
printf("%s %d\n", p.name, elaps);
}
}
return 0;
}