C++ SJF CPU调度程序

什么是最快的作业调度

遵循非抢占式调度原则的作业或进程调度方法被称为最短作业优先调度。在这种情况下，调度程序从等待列表中选择完成时间最短的作业或进程，并将CPU分配给它。因为SJF比FIFO更优化，可以减少平均等待时间，从而提高吞吐量，所以它优于FIFO。

抢占式和非抢占式SJF算法都是可行的。最短剩余时间优先调度是抢占式调度的另一个名称。在抢占式方法中，新进程出现时，现有进程仍在运行。如果新进程的执行时间比当前进程的执行时间短，则调度程序将阻止较短的进程执行。

周转时间、等待时间和完成时间是什么

完成时间是进程完成运行所需的时间。
周转时间是从开始一个过程到完成它的时间段。
周转时间等于完成一个过程并提交它的时间。
周转时间与执行时间之间的延迟称为等待时间。
周转时间减去执行时间等于等待时间。

算法

Start
Step 1-> Declare a struct Process
   Declare pid , bt , art
Step 2-> In function findTurnAroundTime ( Process proc [ ] , int n , int wt [ ] , int tat [ ] )
   Loop For i = 0 and i < n and i++
      Set tat [ i ] = proc [ i ].bt + wt [ i ]
Step 3-> In function findWaitingTime ( Process proc [ ] , int n , int wt [ ] )
   Declare rt [ n ]
   Loop For i = 0 and i < n and i++
      Set rt [ i ] = proc [ i ].bt
      Set complete = 0 , t = 0 , minm = INT_MAX
      Set shortest = 0 , finish_time
      Set bool check = false
      Loop While ( complete != n )
         Loop For j = 0 and j < n and j++
            If (proc [ j ].art <= t ) && ( rt [ j ] < minm ) && rt [ j ] > 0 then ,
               Set minm = rt [ j ]
               Set shortest = j
               Set check = true
            If check == false then ,
               Increment t by 1
               Continue
               Decrement the value of rt [ shortest ] by 1
               Set minm = rt [ shortest ]
            If minm == 0 then ,
               Set minm = INT_MAX
               If rt [ shortest ] == 0 then ,
               Increment complete by 1
               Set check = false
               Set finish_time = t + 1
               Set wt [ shortest ] = finish_time - proc [ shortest ].bt - proc [ shortest ].art
            If wt [ shortest ] < 0
               Set wt [ shortest ] = 0
               Increment t by 1
Step 4-> In function findavgTime ( Process proc [ ] , int n )
   Declare and set wt [ n ] , tat [ n ] , total_wt = 0 , total_tat = 0
   Call findWaitingTime ( proc , n , wt )
   Call findTurnAroundTime ( proc , n , wt , tat )
   Loop For i = 0 and i < n and i++
      Set total_wt = total_wt + wt [ i ]
      Set total_tat = total_tat + tat [ i ]
      Print proc [ i ].pid , proc [ i ].bt , wt [ i ] , tat [ i ]
      Print Average waiting time i.e. , total_wt / n
      Print Average turn around time i.e. , total_tat / n
Step 5-> In function int main ( )
   Declare and set Process proc [ ] = { { 1 , 5 , 1 } , { 2 , 3 , 1 } , { 3 , 6 , 2 } , { 4 , 5 , 3 } }
   Set n = sizeof ( proc ) / sizeof ( proc [ 0 ] )
   Call findavgTime ( proc , n )
Stop

C++中的SJF调度程序

#include <bits/stdc++.h>
using namespace std;
//structure for every process
struct Process {
   int pid; // Process ID
   int bt; // Burst Time
   int art; // Arrival Time
};
void findTurnAroundTime(Process proc[], int n, int wt[], int tat[]) {
   for (int i = 0; i < n; i++)
   tat[i] = proc[i].bt + wt[i];
}
//waiting time of all process
void findWaitingTime(Process proc[], int n, int wt[]) {
   int rt[n];
   for (int i = 0; i < n; i++)
   rt[i] = proc[i].bt;
   int complete = 0, t = 0, minm = INT_MAX;
   int shortest = 0, finish_time;
   bool check = false;
   while (complete != n) {
      for (int j = 0; j < n; j++) {
         if ((proc[j].art <= t) && (rt[j] < minm) && rt[j] > 0) {
            minm = rt[j];
            shortest = j;
            check = true;
         }
      }
      if (check == false) {
         t++;
         continue;
      }
      // decrementing the remaining time
      rt[shortest]--;
      minm = rt[shortest];
      if (minm == 0)
         minm = INT_MAX;
         // If a process gets completely
         // executed
         if (rt[shortest] == 0) {
            complete++;
            check = false;
            finish_time = t + 1;
            // Calculate waiting time
            wt[shortest] = finish_time -
            proc[shortest].bt -
            proc[shortest].art;
            if (wt[shortest] < 0)
               wt[shortest] = 0;
         }
         // Increment time
         t++;
   }
}
// Function to calculate average time
void findavgTime(Process proc[], int n) {
   int wt[n], tat[n], total_wt = 0,
   total_tat = 0;
   // Function to find waiting time of all
   // processes
   findWaitingTime(proc, n, wt);
   // Function to find turn around time for
   // all processes
   findTurnAroundTime(proc, n, wt, tat);
   cout << "Processes " << " 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 << " " << proc[i].pid << "\t\t" << proc[i].bt << "\t\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;
}
// main function
int main() {
   Process proc[] = { { 1, 5, 1 }, { 2, 3, 1 }, { 3, 6, 2 }, { 4, 5, 3 } };
   int n = sizeof(proc) / sizeof(proc[0]);
   findavgTime(proc, n);
   return 0;
}

输出：

Processes  Burst Time   Waiting Time  Turn Around Time
   1            5           3               8
   2            3           0               3
   3            6           12              18
   4            5           6               11

Average waiting time = 5.25
Average turn around time = 10
........................................................
Process executed in 1.33 seconds
Press any key to continue.