Chương trình C++ cho lập lịch Shortest Job First (SJF) non-preemptive

Cho tiến trình, burst time của tiến trình tương ứng và giới hạn quantum; nhiệm vụ là tìm và in thời gian chờ, thời gian vòng tròn và thời gian trung bình tương ứng của chúng sử dụng phương pháp lập lịch Shortest Job First non-preemptive.

Lập lịch Shortest Job First là gì?

Lập lịch Shortest Job First là thuật toán lập lịch công việc hoặc tiến trình tuân theo quy tắc lập lịch non-preemptive. Trong đó, bộ lập lịch chọn tiến trình từ hàng đợi chờ với thời gian hoàn thành ít nhất và cấp CPU cho công việc hoặc tiến trình đó. Shortest Job First ưu tiên hơn thuật toán FIFO vì SJF tối ưu hơn do giảm thời gian chờ trung bình, tăng thông lượng.

Turnaround time, waiting time và completion time là gì?

• Completion Time là thời gian cần thiết để tiến trình hoàn thành thực thi.

• Turnaround Time là khoảng thời gian giữa lúc nộp tiến trình và lúc hoàn thành.

  Turnaround Time = thời gian hoàn thành tiến trình – thời gian nộp tiến trình

• Waiting Time là hiệu giữa turnaround time và burst time.

  Waiting Time = turnaround time – burst time

Ví dụ

Cho các tiến trình P1, P2, P3, P4, P5 với burst time tương ứng:

Vì burst time của P4 nhỏ nhất trong tất cả tiến trình nên nó được cấp CPU đầu tiên. Sau đó là P2, P1, P3, P5.

Thời gian chờ trung bình tính dựa trên biểu đồ Gantt. P1 chờ 3, P2 chờ 1, P3 chờ 7, P4 chờ 0, P5 chờ 15. Thời gian chờ trung bình:

Thuật toán

Bắt đầu
Bước 1 -> Trong hàm swap(int *a, int *b)
    Gán temp = *a
    Gán *a = *b
    Gán *b = temp
Bước 2 -> Trong hàm arrangeArrival(int num, int mat[][3])
    Vòng lặp Với i=0 đến i mat[1][j+1] thì,
                Với k=0 đến k<5 và k++
                    Gọi hàm swap(mat[k][j], mat[k][j+1])
Bước 3 -> Trong hàm completionTime(int num, int mat[][3])
    Khai báo temp, val
    Gán mat[3][0] = mat[1][0] + mat[2][0]
    Gán mat[5][0] = mat[3][0] - mat[1][0]
    Gán mat[4][0] = mat[5][0] - mat[2][0]
    Vòng lặp Với i=1 đến i= mat[1][j] VÀ low >= mat[2][j] thì,
                Gán low = mat[2][j]
                Gán val = j
        Gán mat[3][val] = temp + mat[2][val]
        Gán mat[5][val] = mat[3][val] - mat[1][val]
        Gán mat[4][val] = mat[5][val] - mat[2][val]
        Vòng lặp Với k=0 đến k<6
            Gọi hàm swap(mat[k][val], mat[k][i])
Bước 4 -> Trong hàm int main()
    Khai báo và gán num = 3, temp
    Khai báo và gán mat[6][3] = {1, 2, 3, 3, 6, 4, 2, 3, 4}
    In Process ID, Arrival Time, Burst Time
    Vòng lặp Với i=0 đến i
Ví dụ mã C++
// Chương trình C++ triển khai Shortest Job First với 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 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= 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<<"Trước khi sắp xếp...\n";
    cout<<"Process ID\tArrival Time\tBurst Time\n";
    for(int i=0; i
Đầu ra