FCFS スケジューリングアルゴリズムの C++ プログラム

はじめに

この実験では、C++ を使用して先着順 (First Come First Serve, FCFS) スケジューリングアルゴリズムを実装します。FCFS は、CPU をプロセスが要求した順序で割り当てる最も単純な CPU スケジューリングアルゴリズムです。レディキューに最初に到着したプロセスが最初に処理されます。

このアルゴリズムは理解と実装が容易ですが、平均待機時間の点で最適なパフォーマンスを提供しない場合があります。この実験の終わりまでに、FCFS アルゴリズムの動作原理を理解し、プロセスの待機時間やターンアラウンド時間などの重要な指標を計算できるようになります。

Skills Graph

FCFS の理解とプログラム構造の作成

先着順 (First Come First Serve, FCFS) は、レディキューに到着した順序でプロセスを実行する非プリエンプティブなスケジューリングアルゴリズムです。このステップでは、プログラムファイルを作成し、基本的な構造を設定します。

まず、新しい C++ ファイルを作成しましょう。

1. WebIDE インターフェイスを開き、ファイルエクスプローラーパネルに移動します。
2. エクスプローラーパネルで右クリックし、「新しいファイル」を選択します。
3. ファイル名を fcfs.cpp として、Enter キーを押します。

次に、必要なヘッダーファイルと名前空間の宣言をプログラムに追加しましょう。

#include <iostream>
#include <iomanip> // For formatted output

using namespace std;

int main() {
    cout << "FCFS Scheduling Algorithm Implementation" << endl;
    cout << "----------------------------------------" << endl;

    return 0;
}

このコードは、以下の要素でプログラムの基本構造を設定します。

• #include <iostream> - 入出力操作のため
• #include <iomanip> - 出力テーブルの書式設定のため
• using namespace std; - 標準名前空間を使用するため
• タイトルを表示する main() 関数

プログラムが正しく設定されていることを確認するために、コンパイルして実行しましょう。

g++ fcfs.cpp -o fcfs
./fcfs

以下の出力が表示されるはずです。

FCFS Scheduling Algorithm Implementation
----------------------------------------

これにより、基本的なプログラム構造が正しく動作していることが確認できます。次のステップでは、プロセスの詳細を入力する機能を実装します。

プロセス入力機能の実装

このステップでは、スケジューリング対象のプロセスに関する情報を収集する機能を実装します。FCFS スケジューリングでは、以下の情報が必要です。

1. プロセスの数
2. 各プロセスのバースト時間（各プロセスが必要とする実行時間）

fcfs.cpp ファイルを修正して、この機能を追加しましょう。

#include <iostream>
#include <iomanip> // For formatted output

using namespace std;

int main() {
    cout << "FCFS Scheduling Algorithm Implementation" << endl;
    cout << "----------------------------------------" << endl;

    // Variables declaration
    int n;                  // Number of processes
    int burst_time[20];     // Array to store burst time of each process

    // Get the number of processes from the user
    cout << "\nEnter the number of processes (maximum 20): ";
    cin >> n;

    // Input validation
    if (n <= 0 || n > 20) {
        cout << "Invalid number of processes. Please enter a value between 1 and 20." << endl;
        return 1;
    }

    // Get burst time for each process
    cout << "\nEnter the Burst Time for each process:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Process P" << i + 1 << ": ";
        cin >> burst_time[i];

        // Input validation for burst time
        if (burst_time[i] <= 0) {
            cout << "Burst time must be a positive integer. Please restart the program." << endl;
            return 1;
        }
    }

    // Display the entered data
    cout << "\nProcess\tBurst Time" << endl;
    cout << "--------------------" << endl;
    for (int i = 0; i < n; i++) {
        cout << "P" << i + 1 << "\t" << burst_time[i] << endl;
    }

    return 0;
}

追加した部分を見ていきましょう。

1. プロセスの数 (n) と各プロセスのバースト時間 (burst_time[20]) を格納する変数。
2. プロセスの数と各プロセスのバースト時間を収集するための入力プロンプト。
3. プロセスの数が合理的な範囲（1 - 20）内であり、バースト時間が正であることを確認する入力検証。
4. 入力されたデータを確認するためのテーブル表示。

更新したプログラムをコンパイルして実行しましょう。

g++ fcfs.cpp -o fcfs
./fcfs

プログラムを実行すると、プロセスの数とそれぞれのバースト時間を入力するように促されます。以下のデータを入力してみましょう。

3
5
9
4

これは、それぞれバースト時間が 5、9、4 時間単位の 3 つのプロセスを表しています。以下のような出力が表示されるはずです。

FCFS Scheduling Algorithm Implementation
----------------------------------------

Enter the number of processes (maximum 20): 3

Enter the Burst Time for each process:
Process P1: 5
Process P2: 9
Process P3: 4

Process Burst Time
--------------------
P1      5
P2      9
P3      4

これにより、入力機能が正しく動作していることが確認できます。次のステップでは、各プロセスの待機時間とターンアラウンド時間を計算します。

待機時間とターンアラウンド時間の計算

このステップでは、各プロセスに関する2つの重要な指標を計算します。

1. 待機時間 (Waiting Time, WT)：プロセスがCPU時間を取得する前にレディキューで待機する時間。
2. ターンアラウンド時間 (Turnaround Time, TAT)：プロセスの提出から完了までにかかる総時間。

FCFSにおいてこれらがどのように計算されるかを理解しましょう。

• 最初のプロセス (P1) の待機時間は常に0です（すぐに開始されるため）。
• それ以降のプロセスの待機時間は、それ以前のすべてのプロセスのバースト時間の合計です。
• 各プロセスのターンアラウンド時間は、そのバースト時間と待機時間の合計です。

では、これらの計算を追加するために fcfs.cpp ファイルを修正しましょう。

#include <iostream>
#include <iomanip> // For formatted output

using namespace std;

int main() {
    cout << "FCFS Scheduling Algorithm Implementation" << endl;
    cout << "----------------------------------------" << endl;

    // Variables declaration
    int n;                      // Number of processes
    int burst_time[20];         // Array to store burst time of each process
    int waiting_time[20];       // Array to store waiting time of each process
    int turnaround_time[20];    // Array to store turnaround time of each process
    int total_waiting_time = 0;
    int total_turnaround_time = 0;

    // Get the number of processes from the user
    cout << "\nEnter the number of processes (maximum 20): ";
    cin >> n;

    // Input validation
    if (n <= 0 || n > 20) {
        cout << "Invalid number of processes. Please enter a value between 1 and 20." << endl;
        return 1;
    }

    // Get burst time for each process
    cout << "\nEnter the Burst Time for each process:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Process P" << i + 1 << ": ";
        cin >> burst_time[i];

        // Input validation for burst time
        if (burst_time[i] <= 0) {
            cout << "Burst time must be a positive integer. Please restart the program." << endl;
            return 1;
        }
    }

    // Calculate waiting time for each process
    waiting_time[0] = 0;    // First process has 0 waiting time

    for (int i = 1; i < n; i++) {
        waiting_time[i] = 0;
        // Add burst times of all previous processes
        for (int j = 0; j < i; j++) {
            waiting_time[i] += burst_time[j];
        }
    }

    // Calculate turnaround time for each process and total times
    cout << "\nProcess\tBurst Time\tWaiting Time\tTurnaround Time" << endl;
    cout << "----------------------------------------------------" << endl;

    for (int i = 0; i < n; i++) {
        turnaround_time[i] = burst_time[i] + waiting_time[i];
        total_waiting_time += waiting_time[i];
        total_turnaround_time += turnaround_time[i];

        cout << "P" << i + 1 << "\t" << burst_time[i] << "\t\t"
             << waiting_time[i] << "\t\t" << turnaround_time[i] << endl;
    }

    return 0;
}

追加した部分を理解しましょう。

1. 2つの新しい配列：waiting_time[20] と turnaround_time[20] で、各プロセスの待機時間とターンアラウンド時間を格納します。
2. 総待機時間と総ターンアラウンド時間を追跡する変数。
3. 待機時間の計算：
   • 最初のプロセスの待機時間は0です。
   • それ以降の各プロセスの待機時間は、それ以前のすべてのプロセスのバースト時間の合計です。
4. ターンアラウンド時間の計算：
   • 各プロセスのターンアラウンド時間 = バースト時間 + 待機時間。
5. 結果を表示するための書式付きテーブル。

更新したプログラムをコンパイルして実行しましょう。

g++ fcfs.cpp -o fcfs
./fcfs

前回と同じデータを入力してみましょう。

3
5
9
4

以下のような出力が表示されるはずです。

FCFS Scheduling Algorithm Implementation
----------------------------------------

Enter the number of processes (maximum 20): 3

Enter the Burst Time for each process:
Process P1: 5
Process P2: 9
Process P3: 4

Process Burst Time      Waiting Time    Turnaround Time
----------------------------------------------------
P1      5               0               5
P2      9               5               14
P3      4               14              18

結果を分析しましょう。

• P1: 待機時間 = 0、ターンアラウンド時間 = 5（そのバースト時間）
• P2: 待機時間 = 5（P1のバースト時間）、ターンアラウンド時間 = 14（5 + 9）
• P3: 待機時間 = 14（P1 + P2のバースト時間）、ターンアラウンド時間 = 18（14 + 4）

これにより、待機時間とターンアラウンド時間の計算が正しく動作していることが確認できます。次のステップでは、平均時間を計算し、最終結果を表示します。

平均時間の計算と最終結果の表示

この最後のステップでは、すべてのプロセスの平均待機時間と平均ターンアラウンド時間を計算します。これらの平均値は、スケジューリングアルゴリズムの効率を評価するための重要な指標です。

これらの計算を追加し、プログラムを完成させるために fcfs.cpp ファイルを修正しましょう。

#include <iostream>
#include <iomanip> // For formatted output

using namespace std;

int main() {
    cout << "FCFS Scheduling Algorithm Implementation" << endl;
    cout << "----------------------------------------" << endl;

    // Variables declaration
    int n;                      // Number of processes
    int burst_time[20];         // Array to store burst time of each process
    int waiting_time[20];       // Array to store waiting time of each process
    int turnaround_time[20];    // Array to store turnaround time of each process
    int total_waiting_time = 0;
    int total_turnaround_time = 0;
    float avg_waiting_time = 0.0;
    float avg_turnaround_time = 0.0;

    // Get the number of processes from the user
    cout << "\nEnter the number of processes (maximum 20): ";
    cin >> n;

    // Input validation
    if (n <= 0 || n > 20) {
        cout << "Invalid number of processes. Please enter a value between 1 and 20." << endl;
        return 1;
    }

    // Get burst time for each process
    cout << "\nEnter the Burst Time for each process:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Process P" << i + 1 << ": ";
        cin >> burst_time[i];

        // Input validation for burst time
        if (burst_time[i] <= 0) {
            cout << "Burst time must be a positive integer. Please restart the program." << endl;
            return 1;
        }
    }

    // Calculate waiting time for each process
    waiting_time[0] = 0;    // First process has 0 waiting time

    for (int i = 1; i < n; i++) {
        waiting_time[i] = 0;
        // Add burst times of all previous processes
        for (int j = 0; j < i; j++) {
            waiting_time[i] += burst_time[j];
        }
    }

    // Calculate turnaround time for each process and total times
    cout << "\nProcess\tBurst Time\tWaiting Time\tTurnaround Time" << endl;
    cout << "----------------------------------------------------" << endl;

    for (int i = 0; i < n; i++) {
        turnaround_time[i] = burst_time[i] + waiting_time[i];
        total_waiting_time += waiting_time[i];
        total_turnaround_time += turnaround_time[i];

        cout << "P" << i + 1 << "\t" << burst_time[i] << "\t\t"
             << waiting_time[i] << "\t\t" << turnaround_time[i] << endl;
    }

    // Calculate average waiting time and average turnaround time
    avg_waiting_time = (float)total_waiting_time / n;
    avg_turnaround_time = (float)total_turnaround_time / n;

    // Display the results with two decimal places
    cout << fixed << setprecision(2);
    cout << "\nAverage Waiting Time: " << avg_waiting_time << " time units" << endl;
    cout << "Average Turnaround Time: " << avg_turnaround_time << " time units" << endl;

    // Visual representation of the FCFS schedule (Gantt chart in text)
    cout << "\nGantt Chart:" << endl;
    cout << " ";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < burst_time[i]; j++) {
            cout << "--";
        }
    }
    cout << endl << "|";

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < burst_time[i] - 1; j++) {
            cout << " ";
        }
        cout << "P" << i + 1;
        for (int j = 0; j < burst_time[i] - 1; j++) {
            cout << " ";
        }
        cout << "|";
    }

    cout << endl << " ";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < burst_time[i]; j++) {
            cout << "--";
        }
    }

    cout << endl;
    cout << "0";
    int current_time = 0;
    for (int i = 0; i < n; i++) {
        current_time += burst_time[i];
        for (int j = 0; j < burst_time[i] * 2 - 1; j++) {
            cout << " ";
        }
        if (current_time < 10) cout << " ";
        cout << current_time;
    }
    cout << endl;

    return 0;
}

追加した部分を理解しましょう。

1. 2つの新しい変数：avg_waiting_time と avg_turnaround_time で、平均時間を格納します。
2. 平均時間の計算：
   • 平均待機時間 = 総待機時間 / プロセス数
   • 平均ターンアラウンド時間 = 総ターンアラウンド時間 / プロセス数
3. 平均時間を小数点以下2桁で表示するための書式付き出力。
4. FCFSスケジュールを視覚化するための簡単なテキストベースのガントチャート：
   • 各プロセスはそのID（P1、P2など）で表されます。
   • 各プロセスブロックの幅はそのバースト時間に比例しています。
   • 時間マーカーは下部に表示されます。

最終的なプログラムをコンパイルして実行しましょう。

g++ fcfs.cpp -o fcfs
./fcfs

前回と同じデータを入力してみましょう。

3
5
9
4

以下のような出力が表示されるはずです。

FCFS Scheduling Algorithm Implementation
----------------------------------------

Enter the number of processes (maximum 20): 3

Enter the Burst Time for each process:
Process P1: 5
Process P2: 9
Process P3: 4

Process Burst Time      Waiting Time    Turnaround Time
----------------------------------------------------
P1      5               0               5
P2      9               5               14
P3      4               14              18

Average Waiting Time: 6.33 time units
Average Turnaround Time: 12.33 time units

Gantt Chart:
 --------------------
|   P1    |    P2    |  P3  |
 --------------------
0         5         14     18

結果を見てみましょう。

• 平均待機時間: (0 + 5 + 14) / 3 = 6.33 時間単位
• 平均ターンアラウンド時間: (5 + 14 + 18) / 3 = 12.33 時間単位

ガントチャートは、プロセスが時間の経過とともにどのようにスケジューリングされるかを視覚的に表しています。

• P1は時間0から5まで実行されます。
• P2は時間5から14まで実行されます。
• P3は時間14から18まで実行されます。

これで、FCFSスケジューリングアルゴリズムの実装が完了しました。異なるプロセス数とバースト時間を試して、平均待機時間とターンアラウンド時間にどのような影響があるかを確認することができます。

まとめ

この実験では、C++を使用して先着順 (First Come First Serve, FCFS) CPUスケジューリングアルゴリズムを成功裏に実装しました。ここでは、学んだ主要な概念とスキルを紹介します。

1. FCFSアルゴリズムの基本：プロセスが到着した順にスケジューリングされる仕組みを理解する。

2. パフォーマンス指標の計算：

   • 待機時間：プロセスが実行を開始する前に待機する時間
   • ターンアラウンド時間：提出から完了までの総時間
   • 平均待機時間と平均ターンアラウンド時間：スケジューリングアルゴリズムの重要なパフォーマンス指標

3. C++プログラミングの概念：

   • プロセス情報を格納するための配列
   • 反復計算を行うためのループ
   • 入力検証を伴う入出力操作
   • データをより良く提示するための書式付き出力

4. 視覚化技術：スケジューリングのタイムラインを視覚化するためのテキストベースのガントチャートの作成

FCFSアルゴリズムは理解と実装が簡単ですが、必ずしも最適なパフォーマンスを提供するとは限りません。短いプロセスが長いプロセスの後ろで待機する「コンボイ効果」が発生し、平均待機時間が増加することがあります。

この実装は、最短作業優先 (Shortest Job First, SJF)、優先度スケジューリング、ラウンドロビン (Round Robin, RR) など、プロセススケジューリングのさまざまな側面を最適化するより複雑なスケジューリングアルゴリズムを理解するための基礎となります。