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

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

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

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

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

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

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

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

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

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

예시

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

프로세스 P4의 버스트 시간은 모든 프로세스 중에서 최소이므로 CPU가 먼저 할당됩니다. 그 후, P2는 P1, P3 및 P5에 차례로 대기됩니다.

평균 대기 시간은 간트 차트를 기반으로 계산됩니다. P1은 3, P2는 1, P3은 7, P4는 0, P5는 15를 기다려야 합니다. 따라서 평균 대기 시간은 -

알고리즘

Start
Step 1-> In function swap(int *a, int *b)
   Set temp = *a
   Set *a = *b
   Set *b = temp
Step 2-> In function arrangeArrival(int num, int mat[][3])
   Loop For i=0 and i<num and i++
      Loop For j=0 and j<num-i-1 and j++
         If mat[1][j] > mat[1][j+1] then,
            For k=0 and k<5 and k++
            Call function swap(mat[k][j], mat[k][j+1])
Step 3-> In function completionTime(int num, int mat[][3])
   Declare temp, val
   Set mat[3][0] = mat[1][0] + mat[2][0]
   Set mat[5][0] = mat[3][0] - mat[1][0]
   Set mat[4][0] = mat[5][0] - mat[2][0]
    Loop For i=1 and i<num and i++
      Set temp = mat[3][i-1]
      Set low = mat[2][i]
      Loop For j=i and j<num and j++
         If temp >= mat[1][j] && low >= mat[2][j] then,
            Set low = mat[2][j]
            Set val = j
            Set mat[3][val] = temp + mat[2][val]
            Set mat[5][val] = mat[3][val] - mat[1][val]
            Set mat[4][val] = mat[5][val] - mat[2][val]
            Loop For  k=0; k<6; k++
            Call function swap(mat[k][val], mat[k][i])
Step 4-> In function int main()
   Declare and set num = 3, temp
   Declare and set mat[6][3] = {1, 2, 3, 3, 6, 4, 2, 3, 4}
   Print Process ID, Arrival Time, Burst Time
   Loop For i=0 and i<num and i++
      Print the values of mat[0][i], mat[1][i], mat[2][i]
      Call function arrangeArrival(num, mat)
      Call function completionTime(num, mat)
      Print Process ID, Arrival Time, Burst Time, Waiting Time, Turnaround Time
      Loop For i=0 and i<num and i++  
      Print the values of  mat[0][i], mat[1][i], mat[2][i], mat[4][i], mat[5][i]
Stop

예시

// C++ program to implement Shortest Job first with Arrival Time
#include<iostream>
using namespace std;
void swap(int *a, int *b) {
   int temp = *a;
   *a = *b;
   *b = temp;
}
void arrangeArrival(int num, int mat[][3]) {
   for(int i=0; i<num; i++) {
      for(int j=0; j<num-i-1; j++) {
         if(mat[1][j] > mat[1][j+1]) {
            for(int k=0; k<5; k++) {
               swap(mat[k][j], mat[k][j+1]);
            }
         }
      }
   }
}
void completionTime(int num, int mat[][3]) {
   int temp, val;
   mat[3][0] = mat[1][0] + mat[2][0];
   mat[5][0] = mat[3][0] - mat[1][0];
   mat[4][0] = mat[5][0] - mat[2][0];
    for(int i=1; i<num; i++) {
      temp = mat[3][i-1];
      int low = mat[2][i];
      for(int j=i; j<num; j++) {
         if(temp >= mat[1][j] && low >= mat[2][j]) {
            low = mat[2][j];
            val = j;
         }
      }
      mat[3][val] = temp + mat[2][val];
      mat[5][val] = mat[3][val] - mat[1][val];
      mat[4][val] = mat[5][val] - mat[2][val];
      for(int k=0; k<6; k++) {
         swap(mat[k][val], mat[k][i]);
      }
   }
}
int main() {
   int num = 3, temp;
   int mat[6][3] = {1, 2, 3, 3, 6, 4, 2, 3, 4};
   cout<<"Before Arrange...\n";
   cout<<"Process ID\tArrival Time\tBurst Time\n";
   for(int i=0; i<num; i++) {
      cout<<mat[0][i]<<"\t\t"<<mat[1][i]<<"\t\t"<<mat[2][i]<<"\n";
   }
   arrangeArrival(num, mat);
   completionTime(num, mat);
   cout<<"Final Result...\n";
   cout<<"Process ID\tArrival Time\tBurst Time\tWaiting Time\tTurnaround Time\n";
   for(int i=0; i<num; i++) {
      cout<<mat[0][i]<<"\t\t"<<mat[1][i]<<"\t\t"<<mat[2][i]<<"\t\t"<<mat[4][i]<<"\t\t"<<mat[5][i]<<"\n";
   }
}

출력