C言語で学ぶラウンドロビンスケジューリングの実装方法と計算手順

n個のプロセスとそれぞれのバーストタイム(burst time)、およびタイムクォンタム(time quantum)が与えられたとき、平均待ち時間(average waiting time)と平均ターンアラウンドタイム(average turnaround time)を求めて結果を表示することが本記事の課題です。

ラウンドロビンスケジューリングとは?

ラウンドロビン(Round Robin)は、タイムシェアリングシステム向けに特別に設計されたCPUスケジューリングアルゴリズムです。基本的な仕組みはFCFS(先着順)スケジューリングに似ていますが、決定的な違いとして、各プロセスの実行が「クォンタム」という時間枠によって制限される点が挙げられます。

この小さな時間単位は「タイムクォンタム」または「タイムスライス」と呼ばれ、一般的に10〜100ミリ秒程度の範囲で設定されます。CPUは準備完了キュー(ready queue)を循環キュー(circular queue)として扱い、指定されたタイムスライスごとに順番にプロセスを実行していきます。各プロセスに固定時間が割り当てられるため、プリエンプティブ(横取り型)方式に分類されます。ただし、唯一の欠点として、コンテキストスイッチによるオーバーヘッドが発生するという点があります。

計算が必要な指標

完了時間(Completion Time)

プロセスが実行を完了するまでに必要となる時間です。

ターンアラウンドタイム(Turnaround Time)

プロセスがシステムに投入されてから完了するまでの時間間隔を指します。

ターンアラウンドタイム = 完了時間 − 投入時間

待ち時間(Waiting Time)

ターンアラウンドタイムとバーストタイムの差として求められます。

待ち時間 = ターンアラウンドタイム − バーストタイム

具体例

P1、P2、P3という3つのプロセスがあり、それぞれのバーストタイムが24、3、3である場合を考えてみましょう。

タイムクォンタムが4ミリ秒に設定されている場合、まずP1に最初の4ミリ秒が割り当てられます。しかしP1の実行完了までにはさらに20ミリ秒が必要なため、最初のタイムクォンタム終了時点でCPUからプリエンプト(強制的に中断)され、次のプロセスP2へとCPUが引き継がれます。表を見ると、P2の実行にはわずか3ミリ秒しか必要ないため、4ミリ秒ではなく残りの3ミリ秒分だけCPUが割り当てられることになります。

上記のガントチャートを用いると、平均待ち時間は以下のように計算できます。

平均待ち時間 = 17 ÷ 3 = 5.66ミリ秒

アルゴリズム

開始
ステップ1→ 関数 int turnarroundtime(int processes[], int n, int bt[], int wt[], int tat[])
    ループ i = 0、i < n、i++ ごとに
        tat[i] = bt[i] + wt[i] を設定
    return 1
ステップ2→ 関数 int waitingtime(int processes[], int n, int bt[], int wt[], int quantum)
    rem_bt[n] を宣言
    ループ i = 0、i < n、i++ ごとに
        rem_bt[i] = bt[i] を設定
        t = 0 を設定
    While (1) のループ
        done = true を設定
    ループ i = 0、i < n、i++ ごとに
        rem_bt[i] > 0 の場合、
            done = false を設定
        rem_bt[i] > quantum の場合、
            t = t + quantum を設定
            rem_bt[i] = rem_bt[i] - quantum を設定
        それ以外の場合
            t = t + rem_bt[i] を設定
            wt[i] = t - bt[i] を設定
            rem_bt[i] = 0 を設定
        done == true の場合、
            ループを抜ける
ステップ3→ 関数 int findavgTime(int processes[], int n, int bt[], int quantum)
    wt[n]、tat[n]、total_wt = 0、total_tat = 0 を宣言・初期化
    関数 waitingtime(processes, n, bt, wt, quantum) を呼び出す
    関数 turnarroundtime(processes, n, bt, wt, tat) を呼び出す
    「Processes Burst Time Waiting Time turnaround time」を出力
    ループ i = 0、i < n、i++ ごとに
        total_wt = total_wt + wt[i] を設定
        total_tat = total_tat + tat[i] を設定
        i+1、bt[i]、wt[i]、tat[i] の値を出力
    「Average waiting time = total_wt / n」を出力
    「Average turnaround time = total_tat / n」を出力
ステップ4→ 関数 int main()
    processes[] = { 1, 2, 3} を宣言・初期化
    n = sizeof processes / sizeof processes[0] を宣言・初期化
    burst_time[] = {8, 6, 12} を宣言・初期化
    quantum = 2 を設定
    関数 findavgTime(processes, n, burst_time, quantum) を呼び出す

Cプログラムの実装例

#include <stdio.h>
// ターンアラウンドタイムを計算する関数
int turnarroundtime(int processes[], int n,
int bt[], int wt[], int tat[]) {
    // bt[i] + wt[i] を加算して
    // ターンアラウンドタイムを計算する
    for (int i = 0; i < n ; i++)
    tat[i] = bt[i] + wt[i];
    return 1;
}
// 全プロセスの待ち時間を求める関数
int waitingtime(int processes[], int n,
int bt[], int wt[], int quantum) {
    // 残りバーストタイムを格納するため、
    // bt[] のコピーを作成する
    int rem_bt[n];
    for (int i = 0 ; i < n ; i++)
    rem_bt[i] = bt[i];
    int t = 0; // 現在時刻
    // 全プロセスが完了するまで、
    // ラウンドロビン方式で巡回し続ける
    while (1) {
        bool done = true;
        // 全プロセスを繰り返し順番に走査する
        for (int i = 0 ; i < n; i++) {
            // バーストタイムが0より大きい場合のみ
            // 以降の処理を行う
            if (rem_bt[i] > 0) {
                done = false; // 未完了のプロセスが存在する
                if (rem_bt[i] > quantum) {
                    // t の値を増やし、そのプロセスが
                    // 処理された時間を表す
                    t += quantum;
                    // 現在のプロセスのバーストタイムを
                    // quantum 分だけ減らす
                    rem_bt[i] -= quantum;
                }
                // バーストタイムが quantum 以下の場合。
                // このプロセスにとって最後のサイクル
                else {
                    // t の値を増やし、そのプロセスが
                    // 処理された時間を表す
                    t = t + rem_bt[i];
                    // 待ち時間は現在時刻から
                    // このプロセスが使用した時間を引いたもの
                    wt[i] = t - bt[i];
                    // プロセスが完全に実行されたので
                    // 残りバーストタイムを0にする
                    rem_bt[i] = 0;
                }
            }
        }
        // 全プロセスが完了した場合
        if (done == true)
            break;
    }
    return 1;
}
// 平均時間を計算する関数
int findavgTime(int processes[], int n, int bt[],
int quantum) {
    int wt[n], tat[n], total_wt = 0, total_tat = 0;
    // 全プロセスの待ち時間を求める関数
    waitingtime(processes, n, bt, wt, quantum);
    // 全プロセスのターンアラウンドタイムを求める関数
    turnarroundtime(processes, n, bt, wt, tat);
    // 詳細情報とともにプロセスを表示
    printf("Processes Burst Time Waiting Time turnaround time\n");
    // 合計待ち時間と合計ターンアラウンドタイムを計算
    for (int i=0; i<n; i++) {
        total_wt = total_wt + wt[i];
        total_tat = total_tat + tat[i];
        printf("\t%d\t\t\t%d\t\t\t%d\t\t\t%d\n",i+1, bt[i], wt[i], tat[i]);
    }
    printf("Average waiting time = %f", (float)total_wt / (float)n);
    printf("\nAverage turnaround time = %f\n", (float)total_tat / (float)n);
    return 1;
}
// main関数
int main() {
    // プロセスID
    int processes[] = { 1, 2, 3};
    int n = sizeof processes / sizeof processes[0];
    // 全プロセスのバーストタイム
    int burst_time[] = {8, 6, 12};
    // タイムクォンタム
    int quantum = 2;
    findavgTime(processes, n, burst_time, quantum);
    return 0;
}

出力結果