用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.