C++ 最短作业优先（SJF）调度（抢占式）程序

给定进程、每个进程的突发时间和一个时间片限制；任务是使用最短作业优先抢占式方法找到并打印等待时间、周转时间及其各自的平均时间。

什么是最短作业优先调度？

最短作业优先调度是一种作业或进程调度算法，它遵循非抢占式调度规则。在这种调度中，调度程序从等待队列中选择完成时间最短的进程，并将 CPU 分配给该作业或进程。最短作业优先比先到先服务算法更受欢迎，因为它更优化，因为它减少了平均等待时间，从而提高了吞吐量。

SJF 算法可以是抢占式的，也可以是非抢占式的。抢占式调度也称为**最短剩余时间优先**调度。在抢占式方法中，当已经有正在执行的进程时，新的进程就会出现。如果新到达进程的突发时间小于正在执行进程的突发时间，则调度程序将抢占具有较短突发时间的进程的执行。

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

• **完成时间**是进程完成执行所需的时间。

• **周转时间**是进程提交到完成之间的时间间隔。

  周转时间 = 进程完成时间 - 进程提交时间

• **等待时间**是周转时间和突发时间之间的差值。

  等待时间 = 周转时间 - 突发时间

示例

我们给出了进程 P1、P2、P3、P4 和 P5，以及它们相应的突发时间如下所示

由于 P1 的到达时间为 0，因此它将首先执行，直到另一个进程到达。当在 1 时，进程 P2 进入，并且 P2 的突发时间小于 P1 的突发时间，因此调度程序将把 CPU 分配给进程 P2，依此类推。

平均等待时间是根据甘特图计算的。P1 必须等待 (0+4)4，P2 必须等待 1，P3 必须等待 7，P4 必须等待 3，P5 必须等待 15。因此，它们的平均等待时间将为 -

算法

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

示例

 实时演示

#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;
}

输出

Sunidhi Bansal

更新于： 2019-12-23

17K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

开始学习