最短ジョブ優先（SJF）スケジューリングのためのC++プログラム（非プリエンプティブ方式）

プロセスとそのバースト時間、およびクオンタム制限が与えられたとき、最短ジョブ優先（SJF）スケジューリングの非プリエンプティブ方式を用いて、各プロセスの待ち時間・ターンアラウンド時間、およびそれぞれの平均時間を求めて出力することが本記事の課題です。

最短ジョブ優先（SJF）スケジューリングとは？

最短ジョブ優先（SJF: Shortest Job First）スケジューリングは、非プリエンプティブ（ノンプリエンプティブ）方式に従うジョブ・プロセススケジューリングアルゴリズムです。この方式では、スケジューラが待ち行列の中から完了までの時間が最も短いプロセスを選択し、そのジョブまたはプロセスにCPUを割り当てます。SJFは平均待ち時間を最小化できるため、スループットの向上が期待でき、FIFO（先入れ先出し）アルゴリズムよりも優れた方式とされています。

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

• 完了時間（Completion Time）：プロセスが実行を完了するまでに必要な時間です。

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

• 待ち時間（Waiting Time）：ターンアラウンド時間からバースト時間を差し引いた時間です。
  待ち時間 = ターンアラウンド時間 − バースト時間

実行例

プロセスP1、P2、P3、P4、P5が与えられ、それぞれのバースト時間は以下の通りです。

プロセスP4のバースト時間が全プロセスの中で最も短いため、最初にCPUが割り当てられます。その後、P2、P1、P3、P5の順にキューに入って実行されます。

ガントチャートに基づいて平均待ち時間を計算します。P1は3、P2は1、P3は7、P4は0、P5は15の待ち時間が発生します。したがって、平均待ち時間は以下のように求められます。

アルゴリズム

Start
Step 1-> In function swap(int *a, int *b)
    Set temp = *a
    Set *a = *b
    Set *b = temp
Step 2-> In function arrangeArrival(int num, int mat[][3])
    Loop For i=0 and i mat[1][j+1] then,
             For k=0 and k<5 and k++
             Call function swap(mat[k][j], mat[k][j+1])
Step 3-> In function completionTime(int num, int mat[][3])
    Declare temp, val
    Set mat[3][0] = mat[1][0] + mat[2][0]
    Set mat[5][0] = mat[3][0] - mat[1][0]
    Set mat[4][0] = mat[5][0] - mat[2][0]
    Loop For i=1 and i= mat[1][j] && low >= mat[2][j] then,
             Set low = mat[2][j]
             Set val = j
             Set mat[3][val] = temp + mat[2][val]
             Set mat[5][val] = mat[3][val] - mat[1][val]
             Set mat[4][val] = mat[5][val] - mat[2][val]
             Loop For k=0; k<6; k++
             Call function swap(mat[k][val], mat[k][i])
Step 4-> In function int main()
    Declare and set num = 3, temp
    Declare and set mat[6][3] = {1, 2, 3, 3, 6, 4, 2, 3, 4}
    Print Process ID, Arrival Time, Burst Time
    Loop For i=0 and i
サンプルコード
// C++ program to implement Shortest Job first with Arrival Time
#include<iostream>
using namespace std;
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
void arrangeArrival(int num, int mat[][3]) {
    for(int i=0; i<num; i++) {
        for(int j=0; j<num-i-1; j++) {
            if(mat[1][j] > mat[1][j+1]) {
                for(int k=0; k<5; k++) {
                    swap(mat[k][j], mat[k][j+1]);
                }
            }
        }
    }
}
void completionTime(int num, int mat[][3]) {
    int temp, val;
    mat[3][0] = mat[1][0] + mat[2][0];
    mat[5][0] = mat[3][0] - mat[1][0];
    mat[4][0] = mat[5][0] - mat[2][0];
    for(int i=1; i<num; i++) {
        temp = mat[3][i-1];
        int low = mat[2][i];
        for(int j=i; j<num; j++) {
            if(temp >= mat[1][j] && low >= mat[2][j]) {
                low = mat[2][j];
                val = j;
            }
        }
        mat[3][val] = temp + mat[2][val];
        mat[5][val] = mat[3][val] - mat[1][val];
        mat[4][val] = mat[5][val] - mat[2][val];
        for(int k=0; k<6; k++) {
            swap(mat[k][val], mat[k][i]);
        }
    }
}
int main() {
    int num = 3, temp;
    int mat[6][3] = {1, 2, 3, 3, 6, 4, 2, 3, 4};
    cout<<"Before Arrange...\n";
    cout<<"Process ID\tArrival Time\tBurst Time\n";
    for(int i=0; i<num; i++) {
        cout<<mat[0][i]<<"\t\t"<<mat[1][i]<<"\t\t"<<mat[2][i]<<"\n";
    }
    arrangeArrival(num, mat);
    completionTime(num, mat);
    cout<<"Final Result...\n";
    cout<<"Process ID\tArrival Time\tBurst Time\tWaiting Time\tTurnaround Time\n";
    for(int i=0; i<num; i++) {
        cout<<mat[0][i]<<"\t\t"<<mat[1][i]<<"\t\t"<<mat[2][i]<<"\t\t"<<mat[4][i]<<"\t\t"<<mat[5][i]<<"\n";
    }
}
出力結果
上記のプログラムを実行すると、到着時刻順に並べ替えられた後、各プロセスのプロセスID、到着時刻、バースト時間、待ち時間、ターンアラウンド時間が表形式で出力されます。これにより、SJFスケジューリングが平均待ち時間を最小化できることが確認できます。