ラウンドロビンスケジューリングアルゴリズムを実装する

はじめに

この実験では、C++ でラウンドロビンスケジューリングアルゴリズムを実装する方法を学びます。ラウンドロビンスケジューリングアルゴリズムは、タイムクォンタムと呼ばれる固定時間スライスでプロセスを実行する先取り型アルゴリズムです。プロセスがタイムクォンタム内に実行を完了すると、そのプロセスは終了します。そうでない場合は、レディキューの末尾に移動します。

Skills Graph

新しい C++ ファイルを作成する

まず、~/project ディレクトリに新しい C++ ファイルを作成します。ファイル名は round_robin.cpp とすることができます。

$ cd ~/project
$ touch round_robin.cpp

必要なライブラリをインクルードする

round_robin.cpp ファイルに必要なライブラリをインクルードします。

#include <iostream>
using namespace std;

main() 関数を定義する

main() 関数を定義し、プロセス ID、バースト時間、タイムクォンタム、およびプロセスの数を初期化します。

int main()
{
    // Process IDs
    int processes[] = { 1, 2, 3, 4 };

    // Burst time of all processes
    int burst_time[] = { 5, 9, 6, 8 };

    // Time quantum
    int quantum = 2;

    // Number of processes
    int n = sizeof processes / sizeof processes[0];

    return 0;
}

待ち時間を求める関数を実装する

findWaitingTime() 関数は、すべてのプロセスの待ち時間を求めるために使用されます。この関数は、ラウンドロビン方式でプロセスを反復処理するように定義されています。

void findWaitingTime(int processes[], int n, int bt[], int wt[], int quantum)
{
    // Make a copy of burst times bt[] to store remaining
    // burst times.
    int rem_bt[n];
    for (int i = 0; i < n; i++)
        rem_bt[i] = bt[i];

    int t = 0; // Current time

    // Keep traversing processes in round-robin manner
    // until all of them are not done.
    while (1) {
        bool done = true;

        // Traverse all processes one by one repeatedly
        for (int i = 0; i < n; i++) {
            // If burst time of a process is greater than 0
            // then only need to process further
            if (rem_bt[i] > 0) {
                done = false; // There is a pending process

                /* If remaining burst time is greater than
                quantum then decrease the time slice
                from remaining burst time */
                if (rem_bt[i] > quantum) {
                    // Increase the value of t i.e. shows
                    // how much time a process has been processed
                    t += quantum;

                    // Decrease the burst_time of current process
                    // by quantum
                    rem_bt[i] -= quantum;
                }
                /* If remaining burst time is smaller than
                or equal to quantum then the remaining
                burst time for this process is 0.*/
                else {
                    // Increase the value of t i.e. shows
                    // how much time a process has been processed
                    t += rem_bt[i];

                    // Waiting time is current time minus time
                    // used by this process
                    wt[i] = t - bt[i];

                    // As the process gets fully executed
                    // make its remaining burst time = 0
                    rem_bt[i] = 0;
                }
            }
        }

        // If all processes are done
        if (done == true)
            break;
    }
}

ターンアラウンド時間を求める関数を実装する

findTurnAroundTime() 関数は、すべてのプロセスのターンアラウンド時間を求めるために使用されます。

void findTurnAroundTime(int processes[], int n,
                         int bt[], int wt[], int tat[])
{
    // calculating turnaround time by adding
    // bt[i] + wt[i]
    for (int i = 0; i < n; i++)
        tat[i] = bt[i] + wt[i];
}

平均時間を計算する関数を実装する

findavgTime() 関数は、すべてのプロセスの平均待ち時間と平均ターンアラウンド時間を計算するために使用されます。

void findavgTime(int processes[], int n, int bt[],
                                                 int quantum)
{
    int wt[n], tat[n], total_wt = 0, total_tat = 0;

    // Function to find waiting time of all processes
    findWaitingTime(processes, n, bt, wt, quantum);

    // Function to find turn around time for all processes
    findTurnAroundTime(processes, n, bt, wt, tat);

    // Display processes along with all details
    cout << "Processes "
         << " Burst time "
         << " Waiting time "
         << " Turn around time\n";

    // Calculate total waiting time and total turn
    // around time
    for (int i = 0; i < n; i++) {
        total_wt = total_wt + wt[i];
        total_tat = total_tat + tat[i];
        cout << " " << i + 1 << "\t\t" << bt[i] << "\t "
             << wt[i] << "\t\t " << tat[i] << endl;
    }

    cout << "Average waiting time = "
         << (float)total_wt / (float)n;
    cout << "\nAverage turn around time = "
         << (float)total_tat / (float)n;
}

findavgTime() 関数を呼び出す

findavgTime() 関数を呼び出して、プロセスの平均待ち時間と平均ターンアラウンド時間を計算します。

int main()
{
    int processes[] = { 1, 2, 3, 4 };

    // Burst time of all processes
    int burst_time[] = { 5, 9, 6, 8 };

    // Time quantum
    int quantum = 2;

    // Number of processes
    int n = sizeof processes / sizeof processes[0];

    // Function to find average time
    findavgTime(processes, n, burst_time, quantum);

    return 0;
}

コードをターミナルで実行するには、~/project ディレクトリから次のコマンドを実行します。

$ g++ round_robin.cpp -o round_robin &&./round_robin

まとめ

この実験では、C++ でラウンドロビンスケジューリングアルゴリズムを実装する方法を学びました。このアルゴリズムは、オペレーティングシステムにおいて、タイムクォンタムと呼ばれる時間スライスでプロセスをスケジューリングするために使用されます。また、一連のプロセスに対する平均待ち時間と平均ターンアラウンド時間を計算する方法も学びました。