C言語で実装するFCFSスケジューリング：平均待ち時間とターンアラウンド時間の計算方法

n個のプロセスP1、P2、P3、…、Pnとそれぞれのバーストタイム（CPU実行時間）が与えられたとき、FCFS（First Come, First Served）CPUスケジューリングアルゴリズムを用いて平均待ち時間と平均ターンアラウンド時間を求めるのが本記事のテーマです。

待ち時間とターンアラウンド時間とは？

• ターンアラウンド時間：プロセスの投入から完了までの時間間隔です。
  ターンアラウンド時間 ＝ プロセスの完了時刻 − プロセスの投入時刻

• 待ち時間：ターンアラウンド時間からバーストタイムを差し引いた時間です。
  待ち時間 ＝ ターンアラウンド時間 − バーストタイム

FCFSスケジューリングとは？

First Come, First Served（FCFS）は「First In, First Out（FIFO）」とも呼ばれ、レディキュー（準備キュー）に並んだ順番どおりにCPUを各プロセスへ割り当てていくCPUスケジューリングアルゴリズムです。

FCFSはノンプリエンプティブ（非奪取）方式のスケジューリングです。つまり、一度CPUがあるプロセスに割り当てられると、そのプロセスが終了するか、何らかのI/O割り込みによって中断されるまで、CPUを手放すことはありません。

例題

3つのプロセスがP2、P3、P1の順に到着し、それぞれの実行時間が下の表のとおりであるとします。なお、到着時刻はすべて0とします。

システム内のプロセスP1、P2、P3の待ち時間を示すガントチャートは以下のとおりです。

上図より、

• プロセスP2の待ち時間は0ミリ秒
• プロセスP3の待ち時間は3ミリ秒
• プロセスP1の待ち時間は6ミリ秒

したがって、平均待ち時間 ＝ (0 ＋ 3 ＋ 6) ÷ 3 ＝ 3ミリ秒となります。

今回は到着時刻を0としているため、ターンアラウンド時間と完了時刻は同じ値になります。

実行例

入力：  processes = P1, P2, P3
        バーストタイム = 5, 8, 12
出力：
Processes   Burst     Waiting     Turn around
1           5         0           5
2           8         5           13
3           12        13          25
Average Waiting time = 6.000000
Average turn around time = 14.333333

アルゴリズム

開始
Step 1-> 関数 int waitingtime(int proc[], int n, int burst_time[], int wait_time[])
    wait_time[0] = 0 を設定
    i = 1、i < n、i++ でループ
        wait_time[i] = burst_time[i-1] + wait_time[i-1] を設定
    ループ終了
Step 2-> 関数 int turnaroundtime(int proc[], int n, int burst_time[], int wait_time[], int tat[])
    i = 0、i < n、i++ でループ
        tat[i] = burst_time[i] + wait_time[i] を設定
    ループ終了
Step 3-> 関数 int avgtime(int proc[], int n, int burst_time[])
    wait_time[n]、tat[n]、total_wt = 0、total_tat = 0 を宣言・初期化
    waitingtime(proc, n, burst_time, wait_time) を呼び出す
    turnaroundtime(proc, n, burst_time, wait_time, tat) を呼び出す
    i = 0、i < n、i++ でループ
        total_wt に wait_time[i] を加算
        total_tat に tat[i] を加算
        プロセス番号・バーストタイム・待ち時間・ターンアラウンド時間を出力
    ループ終了
    「Average waiting time = total_wt / n」を出力
    「Average turn around time = total_tat / n」を出力
Step 4-> int main()
    入力 int proc[] = { 1, 2, 3 } を宣言
    n = sizeof proc / sizeof proc[0] を宣言・初期化
    バーストタイム burst_time[] = {5, 8, 12} を宣言・初期化
    avgtime(proc, n, burst_time) を呼び出す
終了

C言語プログラム例

#include <stdio.h>
// 全プロセスの待ち時間を求める関数
int waitingtime(int proc[], int n,
int burst_time[], int wait_time[]) {
    // 最初のプロセスの待ち時間は0
    wait_time[0] = 0;
    // 待ち時間を計算
    for (int i = 1; i < n ; i++ )
    wait_time[i] = burst_time[i-1] + wait_time[i-1] ;
    return 0;
}
// ターンアラウンド時間を計算する関数
int turnaroundtime( int proc[], int n,
int burst_time[], int wait_time[], int tat[]) {
    // burst_time[i] + wait_time[i] の加算によりターンアラウンド時間を計算
    int i;
    for ( i = 0; i < n ; i++)
    tat[i] = burst_time[i] + wait_time[i];
    return 0;
}
// 平均時間を計算する関数
int avgtime( int proc[], int n, int burst_time[]) {
    int wait_time[n], tat[n], total_wt = 0, total_tat = 0;
    int i;
    // 全プロセスの待ち時間を求める関数を呼び出し
    waitingtime(proc, n, burst_time, wait_time);
    // 全プロセスのターンアラウンド時間を求める関数を呼び出し
    turnaroundtime(proc, n, burst_time, wait_time, tat);
    // 各プロセスの詳細を表示
    printf("Processes   Burst    Waiting Turn around \n");
    // 合計待ち時間と合計ターンアラウンド時間を計算
    for ( i=0; i<n; i++) {
        total_wt = total_wt + wait_time[i];
        total_tat = total_tat + tat[i];
        printf(" %d\t   %d\t\t %d \t%d\n", i+1, burst_time[i], wait_time[i], tat[i]);
    }
    printf("Average waiting time = %f\n", (float)total_wt / (float)n);
    printf("Average turn around time = %f\n", (float)total_tat / (float)n);
    return 0;
}
// main関数
int main() {
    // プロセスID
    int proc[] = { 1, 2, 3};
    int n = sizeof proc / sizeof proc[0];
    // 全プロセスのバーストタイム
    int burst_time[] = {5, 8, 12};
    avgtime(proc, n, burst_time);
    return 0;
}

出力結果

Processes   Burst     Waiting     Turn around
1           5         0           5
2           8         5           13
3           12        13          25
Average Waiting time = 6.000000
Average turn around time = 14.333333

まとめ

FCFSは実装が非常にシンプルで公平性の高いアルゴリズムですが、先頭で実行された長時間のプロセスが後続の短いプロセスを長く待たせる「コンボイ効果」が発生しやすく、平均待ち時間が長くなるという欠点があります。そのため、実際のOSではラウンドロビンやSRTFなど、他のスケジューリング手法と組み合わせて採用されることが多くなっています。