SJF(Shortest Job First) 스케줄링을 위한 C++ 프로그램(선점형)

주어진 프로세스, 각각 프로세스의 버스트 시간 및 양자 제한; 작업은 Shortest Job First Scheduling 선점 방식을 사용하여 대기 시간, 처리 시간 및 각각의 평균 시간을 찾아 인쇄하는 것입니다.

가장 짧은 작업 우선 일정은 무엇입니까?

최단 작업 우선 스케줄링은 비선점 스케줄링 원칙을 따르는 작업 또는 프로세스 스케줄링 알고리즘입니다. 여기서 스케줄러는 대기 큐에서 완료 시간이 가장 짧은 프로세스를 선택하고 해당 작업이나 프로세스에 CPU를 할당합니다. SJF가 평균 대기 시간을 줄여 처리량을 증가시키므로 최적이기 때문에 FIFO 알고리즘보다 Shortest Job First가 더 바람직합니다.

SJF 알고리즘은 선점형일 수도 있고 비선점형일 수도 있습니다. 선점형 스케줄링은 최단 잔여 시간 우선이라고도 합니다. 일정. 선점 방식에서는 이미 실행 중인 프로세스가 있을 때 새로운 프로세스가 발생합니다. 새로 도착한 프로세스의 버스트가 실행 중인 프로세스의 버스트 시간보다 짧으면 스케줄러가 더 짧은 버스트 시간으로 프로세스의 실행을 선점합니다.

처리 시간, 대기 시간 및 완료 시간은 어떻게 됩니까?

• 완료 시간 프로세스가 실행을 완료하는 데 필요한 시간입니다.

• 처리 시간 프로세스 제출과 완료 사이의 시간 간격입니다.

  처리 시간 =프로세스 완료 – 프로세스 제출

• 대기 시간 처리 시간과 버스트 시간의 차이입니다.

  대기 시간 =처리 시간 – 버스트 시간

예시

아래에 주어진 해당 버스트 시간을 갖는 프로세스 P1, P2, P3, P4 및 P5가 제공됩니다.

P1의 도착 시간이 0이므로 다른 프로세스가 도착할 때까지 가장 먼저 실행됩니다. 1에서 프로세스 P2가 시작되고 P2의 버스트 시간이 P1의 버스트 시간보다 작으면 스케줄러는 프로세스 P2와 함께 CPU를 디스패치하는 식으로 진행됩니다.

평균 대기 시간은 간트 차트를 기반으로 계산됩니다. 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;
}

출력