Chương trình C++ cho lập lịch Priority Scheduling

Cho n tiến trình P1, P2, P3,...,Pn với burst time tương ứng và priority liên kết với mỗi tiến trình. Nhiệm vụ là tìm thời gian chờ trung bình, thời gian vòng tròn trung bình và trình tự thực thi tiến trình sử dụng thuật toán lập lịch CPU priority scheduling.

Waiting Time và Turnaround Time là gì?

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

Priority Scheduling là gì?

Trong priority scheduling, mỗi tiến trình liên kết với độ ưu tiên từ 0-10, trong đó 0 đại diện cho ưu tiên thấp nhất và 10 đại diện cho ưu tiên cao nhất. Độ ưu tiên có thể xác định nội bộ hoặc ngoại bộ. Priority scheduling có thể preemptive hoặc non-preemptive.

Trong preemptive priority scheduling, bộ lập lịch sẽ chiếm CPU nếu độ ưu tiên của tiến trình mới đến cao hơn tiến trình đang thực thi.

Trong non-preemptive priority scheduling, bộ lập lịch sẽ xếp tiến trình mới vào đầu hàng đợi sẵn sàng.

Nhược điểm của priority scheduling là chặn vô hạn hoặc starvation. Tiến trình ưu tiên thấp có thể phải chờ vô hạn tài nguyên do tiến trình ưu tiên cao dẫn đến starvation.

Ví dụ

Giả sử có 4 tiến trình P1, P2, P3, P4 với burst time và priority như bảng (0 = thấp nhất, 10 = cao nhất):

Thứ tự thực thi nhiều tiến trình được biểu diễn bằng biểu đồ Gantt:

Thuật toán

Bắt đầu
Bước 1 -> Tạo cấu trúc Process với biến pid, bt, priority
Bước 2 -> Trong hàm bool compare(Process a, Process b)
    Trả về (a.priority > b.priority)
Bước 3 -> Trong hàm waitingtime(Process pro[], int n, int wt[])
    Gán wt[0] = 0
    Vòng lặp Với i = 1 đến i < n và i++
        Gán wt[i] = pro[i-1].bt + wt[i-1]
    Kết thúc
Bước 4 -> Trong hàm turnarround(Process pro[], int n, int wt[], int tat[])
    Vòng lặp Với i = 0 đến i < n và i++
        Gán tat[i] = pro[i].bt + wt[i]
    Kết thúc vòng lặp
Bước 5 -> Trong hàm avgtime(Process pro[], int n)
    Khai báo và khởi tạo wt[n], tat[n], total_wt = 0, total_tat = 0
    Gọi waitingtime(pro, n, wt)
    Gọi turnarround(pro, n, wt, tat)
    In "Processes, Burst time, Waiting time, Turn around time"
    Vòng lặp Với i=0 đến i Trong hàm scheduling(Process pro[], int n)
    Gọi hàm sort(pro, pro + n, compare)
    Vòng lặp Với i = 0 đến i < n và i++
        In thứ tự.
    Kết thúc vòng lặp
    Gọi hàm avgtime(pro, n)
Bước 7 -> Trong hàm int main()
    Khai báo và khởi tạo Process pro[] = {{1, 10, 2}, {2, 5, 0}, {3, 8, 1}}
    Khai báo và khởi tạo n = sizeof pro / sizeof pro[0]
    Gọi hàm scheduling(pro, n)
Kết thúc

Ví dụ mã C++

#include<bits/stdc++.h>
using namespace std;

struct Process {
    int pid; // Process ID
    int bt;  // CPU Burst time required
    int priority; // Priority of this process
};

// Sắp xếp tiến trình theo priority
bool compare(Process a, Process b) {
    return (a.priority > b.priority);
}

void waitingtime(Process pro[], int n, int wt[]) {
    // Thời gian chờ ban đầu cho tiến trình là 0
    wt[0] = 0;
    // Tính thời gian chờ
    for (int i = 1; i < n; i++)
        wt[i] = pro[i-1].bt + wt[i-1];
}

// Hàm tính turn around time
void turnarround(Process pro[], int n, int wt[], int tat[]) {
    // Tính turnaround time bằng bt[i] + wt[i]
    for (int i = 0; i < n; i++)
        tat[i] = pro[i].bt + wt[i];
}

// Hàm tính thời gian trung bình
void avgtime(Process pro[], int n) {
    int wt[n], tat[n], total_wt = 0, total_tat = 0;
    // Tìm waiting time tất cả tiến trình
    waitingtime(pro, n, wt);
    // Tìm turn around time tất cả tiến trình
    turnarround(pro, n, wt, tat);
    // Hiển thị tiến trình với tất cả chi tiết
    cout << "\nTiến trình " << " Burst time " << " Waiting time " << " Turn around time\n";
    // Tính tổng waiting time và tổng turn around time
    for (int i = 0; i < n; i++) {
        total_wt = total_wt + wt[i];
        total_tat = total_tat + tat[i];
        cout << " " << pro[i].pid << "\t\t" << pro[i].bt << "\t " << wt[i] << "\t\t " << tat[i] << endl;
    }
    cout << "\nThời gian chờ trung bình = " << (float)total_wt / (float)n;
    cout << "\nThời gian vòng tròn trung bình = " << (float)total_tat / (float)n;
}

void scheduling(Process pro[], int n) {
    // Sắp xếp tiến trình theo priority
    sort(pro, pro + n, compare);
    cout<< "Thứ tự tiến trình được thực thi \n";
    for (int i = 0; i < n; i++)
        cout << pro[i].pid << " ";
    avgtime(pro, n);
}

// Hàm main
int main() {
    Process pro[] = {{1, 10, 2}, {2, 5, 0}, {3, 8, 1}};
    int n = sizeof pro / sizeof pro[0];
    scheduling(pro, n);
    return 0;
}

Đầu ra

Thứ tự tiến trình được thực thi
1 3 2
Tiến trình  Burst time  Waiting time  Turn around time
1           10          0             10
3           8           10            18
2           5           18            23
Thời gian chờ trung bình = 9.33333
Thời gian vòng tròn trung bình = 17