ラウンドロビンスケジューリングのためのCプログラム

n個のプロセスとそれに対応するバースト時間とタイムクォンタムが与えられます。タスクは、平均待機時間と平均ターンアラウンドタイムを見つけて結果を表示することです。

ラウンドロビンスケジューリングとは何ですか？

ラウンドロビンは、特にタイムシェアリングシステム用に設計されたCPUスケジューリングアルゴリズムです。これは、ラウンドロビンプロセスで量子時間サイズに制限されるという1つの変更を加えたFCFSスケジューリングアルゴリズムに似ています。時間の小さな単位は、タイムクォンタムまたはタイムスライスとして知られています。タイムクォンタムの範囲は10〜100ミリ秒です。 CPUは、レディキューを、指定されたタイムスライスでプロセスを実行するための循環キューとして扱います。固定時間がプロセスに割り当てられるため、プリエンプティブアプローチに従います。唯一の欠点は、コンテキスト切り替えのオーバーヘッドです。

何を計算する必要がありますか？

完了時間 プロセスが実行を完了するのに必要な時間です

所要時間 プロセスの送信から完了までの時間間隔です。

所要時間=プロセスの完了–プロセスの提出

待機時間は、ターンアラウンドタイムとバーストタイムの差です

待機時間=所要時間–バースト時間

例

3つのプロセスP1、P2、およびP3が与えられ、対応するバースト時間は24、3、および3です

タイムクォンタムは4ミリ秒であるため、プロセスP1は最初の4ミリ秒を取得しますが、実行を完了するにはさらに20ミリ秒が必要ですが、CPUは最初のタイムクォンタムの後にプリエンプトし、CPUは次のプロセスP2に割り当てられます。表に示されているように、プロセスP2は実行を完了するのに3ミリ秒しか必要としないため、CPUは4ミリ秒ではなく3ミリ秒のタイムクォンタムにのみ割り当てられます。

ガントチャートを使用して、平均待機時間は次のように計算されます-

平均待機時間=17/3=5.66ミリ秒

アルゴリズム

Start
Step 1-> In function int turnarroundtime(int processes[], int n, int bt[], int wt[], int tat[])
   Loop For i = 0 and i < n and i++
      Set tat[i] = bt[i] + wt[i]
   return 1
Step 2-> In function int waitingtime(int processes[], int n, int bt[], int wt[], int quantum)
Declare rem_bt[n]
   Loop For i = 0 and i < n and i++
      Set rem_bt[i] = bt[i]
      Set t = 0
   Loop While (1)
      Set done = true
   Loop For i = 0 and i < n and i++
      If rem_bt[i] > 0 then,
         Set done = false
      If rem_bt[i] > quantum then,
         Set t = t + quantum
         Set rem_bt[i] = rem_bt[i] - quantum
      Else
         Set t = t + rem_bt[i]
         Set wt[i] = t - bt[i]
         Set rem_bt[i] = 0
      If done == true then,
   Break
Step 3->In function int findavgTime(int processes[], int n, int bt[], int quantum)
   Declare and initialize wt[n], tat[n], total_wt = 0, total_tat = 0
   Call function waitingtime(processes, n, bt, wt, quantum)
   Call function turnarroundtime(processes, n, bt, wt, tat)
   Print "Processes Burst Time Waiting Time turnaround time "
   Loop For i=0 and i<n and i++
   Set total_wt = total_wt + wt[i]
   Set total_tat = total_tat + tat[i]
   Print the value i+1, bt[i], wt[i], tat[i]
   Print "Average waiting time = total_wt / n
   Print "Average turnaround time =total_tat / n
Step 4-> In function int main()
   Delcare and initialize processes[] = { 1, 2, 3}
   Declare and initialize n = sizeof processes / sizeof processes[0]
   Declare and initialize burst_time[] = {8, 6, 12}
   Set quantum = 2
   Call function findavgTime(processes, n, burst_time, quantum)

例

#include <stdio.h>
// Function to calculate turn around time
int turnarroundtime(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];
   return 1;
}
// Function to find the waiting time for all
// processes
int waitingtime(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 (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 burst time is smaller than or equal to
            // quantum. Last cycle for this process
            else {
               // Increase the value of t i.e. shows
               // how much time a process has been processed
               t = 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;
   }
   return 1;
}
// Function to calculate average time
int 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
   waitingtime(processes, n, bt, wt, quantum);
   // Function to find turn around time for all processes
   turnarroundtime(processes, n, bt, wt, tat);
   // Display processes along with all details
   printf("Processes Burst Time Waiting Time turnaround 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];
      printf("\t%d\t\t\t%d\t\t\t%d\t\t\t%d\n",i+1, bt[i], wt[i], tat[i]);
   }
   printf("Average waiting time = %f", (float)total_wt / (float)n);
   printf("\nAverage turnaround time = %f\n", (float)total_tat / (float)n);
   return 1;
}
// main function
int main() {
   // process id's
   int processes[] = { 1, 2, 3};
   int n = sizeof processes / sizeof processes[0];
   // Burst time of all processes
   int burst_time[] = {8, 6, 12};
   // Time quantum
   int quantum = 2;
   findavgTime(processes, n, burst_time, quantum);
   return 0;
}

出力