Lập lịch chương trình C ++ cho công việc ngắn nhất đầu tiên (SJF) (không ưu tiên)

Đã cho quá trình, thời gian bùng nổ của một quá trình tương ứng và một giới hạn lượng tử; nhiệm vụ là tìm và in thời gian chờ, thời gian quay vòng và thời gian trung bình tương ứng của chúng bằng cách sử dụng phương pháp không ưu tiên Lập lịch trước cho công việc ngắn nhất.

Công việc ngắn nhất lên lịch đầu tiên là gì?

Lập lịch trình đầu tiên cho công việc ngắn nhất là thuật toán lập lịch công việc hoặc quy trình tuân theo kỷ luật lập lịch không miễn phí. Trong trường hợp này, bộ lập lịch chọn tiến trình từ hàng đợi có thời gian hoàn thành ít nhất và phân bổ CPU cho công việc hoặc quá trình đó. Công việc đầu tiên ngắn nhất đáng mong đợi hơn thuật toán FIFO vì SJF tối ưu hơn vì nó giảm thời gian chờ trung bình sẽ làm tăng thông lượng.

Thời gian quay vòng, thời gian chờ và thời gian hoàn thành là gì?

• Thời gian hoàn thành là thời gian cần thiết của quá trình để hoàn thành quá trình thực thi

• Thời gian quay vòng là khoảng thời gian từ khi gửi quy trình đến khi hoàn thành quy trình.

  Thời gian quay vòng =hoàn thành quy trình - gửi quy trình

• Thời gian chờ là sự khác biệt giữa thời gian quay vòng và thời gian liên tục

  Thời gian chờ =thời gian quay vòng - thời gian liên tục

Ví dụ

Chúng tôi đưa ra các quy trình P1, P2, P3, P4 và P5 có thời gian bùng nổ tương ứng của chúng được đưa ra bên dưới

Vì thời gian bùng nổ của quá trình P4 là tối thiểu trong số tất cả các quá trình nên nó sẽ được cấp phát CPU đầu tiên. Sau đó, P2 sẽ được xếp hàng đợi rồi đến P1, P3 và P5.

Thời gian chờ đợi trung bình được tính trên cơ sở biểu đồ gantt. P1 phải đợi 3, P2 phải đợi 1, P3 phải đợi 7, P4 phải đợi 0 và P5 phải chờ 15. Vì vậy, thời gian chờ trung bình của họ sẽ là -

Thuật toán

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

Ví dụ

// 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";
   }
}

Đầu ra