優先度スケジューリングを実装するC++プログラムの完全解説

はじめに

n個のプロセス(P1、P2、P3、…、Pn)と、それぞれのプロセスに対応するバーストタイムおよび優先度が与えられます。本記事では、優先度CPUスケジューリングアルゴリズムを用いて、平均待ち時間・平均ターンアラウンド時間・プロセスの実行順序を求めるC++プログラムを解説します。

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

ターンアラウンド時間とは、プロセスの投入から完了までの時間間隔のことです。

ターンアラウンド時間 = プロセスの完了時刻 − プロセスの投入時刻

待ち時間は、ターンアラウンド時間からバーストタイムを差し引いた値として求められます。

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

優先度スケジューリングとは?

優先度スケジューリングでは、各プロセスに0〜10の範囲で優先度が割り当てられます。0が最も低い優先度、10が最も高い優先度を表します。優先度の決め方には、システム内部の情報から算出する「内部定義」と、ユーザーなど外部から指定する「外部定義」の2通りがあります。また、優先度スケジューリングにはプリエンプティブ(割り込み型)とノンプリエンプティブ(非割り込み型)の2種類があります。

プリエンプティブ優先度スケジューリングでは、新しく到着したプロセスの優先度が実行中のプロセスよりも高い場合、スケジューラはCPUを横取り(プリエンプト)します。

ノンプリエンプティブ優先度スケジューリングでは、新しいプロセスはレディキューの先頭に追加され、実行中のプロセスが終了するのを待ちます。

優先度スケジューリングの欠点は、無期限ブロッキング(スタベーション)です。高優先度のプロセスが次々と到着すると、低優先度のプロセスが資源を無期限に待たされる可能性があり、これがスタベーション問題につながります。

例

4つのプロセスP1、P2、P3、P4について、それぞれのバーストタイムと優先度が以下のように与えられているとします(0が最低優先度、10が最高優先度)。

複数プロセスの実行順序は、以下のガントチャートで表されます。

アルゴリズム

開始
ステップ1→ pid、bt、priority をメンバに持つ構造体 Process を作成する
ステップ2→ 関数 bool compare(Process a, Process b)
　　return (a.priority > b.priority)
ステップ3→ 関数 waitingtime(Process pro[], int n, int wt[])
　　wt[0] = 0 を設定
　　i = 1 から i < n の間ループ
　　　　wt[i] = pro[i-1].bt + wt[i-1] を設定
　　ループ終了
ステップ4→ 関数 turnarround(Process pro[], int n, int wt[], int tat[])
　　i = 0 から i < n の間ループ
　　　　tat[i] = pro[i].bt + wt[i] を設定
　　ループ終了
ステップ5→ 関数 avgtime(Process pro[], int n)
　　wt[n]、tat[n]、total_wt = 0、total_tat = 0 を宣言・初期化
　　関数 waitingtime(pro, n, wt) を呼び出す
　　関数 turnarround(pro, n, wt, tat) を呼び出す
　　「Processes, Burst time, Waiting time, Turn around time」を出力
　　i = 0 から i < n の間ループ
　　　　total_wt = total_wt + wt[i]
　　　　total_tat = total_tat + tat[i]
　　ループ終了
　　各プロセスの「Burst time, Waiting time, Turn around time」を出力
　　平均待ち時間と平均ターンアラウンド時間を出力
ステップ6→ 関数 scheduling(Process pro[], int n)
　　関数 sort(pro, pro + n, compare) を呼び出す
　　i = 0 から i < n の間ループ
　　　　実行順序を出力
　　ループ終了
　　関数 avgtime(pro, n) を呼び出す
ステップ7→ 関数 int main()
　　Process pro[] = {{1, 10, 2}, {2, 5, 0}, {3, 8, 1}} を宣言・初期化
　　n = sizeof pro / sizeof pro[0] を宣言・初期化
　　関数 scheduling(pro, n) を呼び出す
終了

C++プログラム例

#include<bits/stdc++.h>
using namespace std;
struct Process {
    int pid; // プロセスID
    int bt; // 必要なCPUバーストタイム
    int priority; // このプロセスの優先度
};
// 優先度に基づいてプロセスをソートする
bool compare(Process a, Process b) {
    return (a.priority > b.priority);
}
void waitingtime(Process pro[], int n, int wt[]) {
    // 最初のプロセスの待ち時間は0
    wt[0] = 0;
    // 待ち時間を計算
    for (int i = 1; i < n ; i++ )
        wt[i] = pro[i-1].bt + wt[i-1] ;
}
 // ターンアラウンド時間を計算する関数
void turnarround( Process pro[], int n, int wt[], int tat[]) {
    // bt[i] + wt[i] によりターンアラウンド時間を計算
    for (int i = 0; i < n ; i++)
        tat[i] = pro[i].bt + wt[i];
}
// 平均時間を計算する関数
void avgtime(Process pro[], int n) {
    int wt[n], tat[n], total_wt = 0, total_tat = 0;
    // 全プロセスの待ち時間を求める関数
    waitingtime(pro, n, wt);
    // 全プロセスのターンアラウンド時間を求める関数
    turnarround(pro, n, wt, tat);
    // 詳細情報とともにプロセスを表示
    cout << "\nProcesses "<< " Burst time " << " Waiting time " << " Turn around time\n";
    // 合計待ち時間と合計ターンアラウンド時間を計算
    for (int i=0; i<n; i++) {
        total_wt = total_wt + wt[i];
        total_tat = total_tat + tat[i];
        cout << " " << pro[i].pid << "\t\t" << pro[i].bt << "\t " << wt[i] << "\t\t " << tat[i] <<endl;
    }
    cout << "\nAverage waiting time = " << (float)total_wt / (float)n;
    cout << "\nAverage turn around time = " << (float)total_tat / (float)n;
}
void scheduling(Process pro[], int n) {
    // 優先度に基づいてプロセスをソート
    sort(pro, pro + n, compare);
    cout<< "Order in which processes gets executed \n";
    for (int i = 0 ; i < n; i++)
        cout << pro[i].pid <<" " ;
    avgtime(pro, n);
}
// main関数
int main() {
    Process pro[] = {{1, 10, 2}, {2, 5, 0}, {3, 8, 1}};
    int n = sizeof pro / sizeof pro[0];
    scheduling(pro, n);
    return 0;
}

実行結果

Order in which processes gets executed
1 3 2
Processes  Burst time  Waiting time  Turn around time
 1              10         0              10
 3              8          10              18
 2              5          18              23
 
Average waiting time = 9.33333
Average turn around time = 17

実行結果の解説

このプログラムでは、3つのプロセスが優先度の高い順(2 → 1 → 0)にソートされ、実行順序は「1 → 3 → 2」となります。プロセス1は最初に実行されるため待ち時間は0、プロセス3はプロセス1のバーストタイム分だけ待機し、プロセス2はその両方が完了した後に実行されます。その結果、平均待ち時間は9.33、平均ターンアラウンド時間は17となりました。