はじめに
この実験では、C++ でラウンドロビンスケジューリングアルゴリズムを実装する方法を学びます。ラウンドロビンスケジューリングアルゴリズムは、タイムクォンタムと呼ばれる固定時間スライスでプロセスを実行する先取り型アルゴリズムです。プロセスがタイムクォンタム内に実行を完了すると、そのプロセスは終了します。そうでない場合は、レディキューの末尾に移動します。
この実験では、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++ でラウンドロビンスケジューリングアルゴリズムを実装する方法を学びました。このアルゴリズムは、オペレーティングシステムにおいて、タイムクォンタムと呼ばれる時間スライスでプロセスをスケジューリングするために使用されます。また、一連のプロセスに対する平均待ち時間と平均ターンアラウンド時間を計算する方法も学びました。