はじめに

こんにちは、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

入力例 1 に対する出力

サンプルコード

#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;
}