Cho tiến trình, thời gian thực thi (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 ưu tiên (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.
Thuật toán SJF có thể là preemptive cũng như non-preemptive. Lập lịch preemptive còn được gọi là shortest-remaining-time-first scheduling. Trong cách tiếp cận preemptive, tiến trình mới xuất hiện khi đã có tiến trình đang thực thi. Nếu burst time của tiến trình mới đến nhỏ hơn burst time của tiến trình đang thực thi thì bộ lập lịch sẽ ưu tiên thực thi tiến trình có burst time nhỏ hơn.
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 như bảng sau:
| Tiến trình | Burst Time | Arrival Time |
|---|---|---|
| P1 | 4 | 0 |
| P2 | 2 | 1 |
| P3 | 8 | 2 |
| P4 | 1 | 3 |
| P5 | 9 | 4 |
Vì arrival time của P1 là 0 nên nó được thực thi đầu tiên cho đến khi tiến trình khác đến. Khi tại thời điểm 1, tiến trình P2 đến và burst time của P2 nhỏ hơn P1 nên bộ lập lịch sẽ phân phối CPU cho P2, và cứ thế.
Thời gian chờ trung bình tính dựa trên biểu đồ Gantt. P1 chờ (0+4)=4, P2 chờ 1, P3 chờ 7, P4 chờ 3, P5 chờ 15. Thời gian chờ trung bình:
Thuật toán
Bắt đầu
Bước 1 -> Khai báo struct Process
Khai báo pid, bt, art
Bước 2 -> Trong hàm findTurnAroundTime(Process proc[], int n, int wt[], int tat[])
Vòng lặp Với i = 0 đến i < n và i++
Gán tat[i] = proc[i].bt + wt[i]
Bước 3 -> Trong hàm findWaitingTime(Process proc[], int n, int wt[])
Khai báo rt[n]
Vòng lặp Với i = 0 đến i < n và i++
Gán rt[i] = proc[i].bt
Gán complete = 0, t = 0, minm = INT_MAX
Gán shortest = 0, finish_time
Gán bool check = false
Vòng lặp Khi (complete != n)
Vòng lặp Với j = 0 đến j < n và j++
NẾU (proc[j].art <= t) VÀ (rt[j] < minm) VÀ rt[j] > 0 thì,
Gán minm = rt[j]
Gán shortest = j
Gán check = true
NẾU check == false thì,
Tăng t lên 1
Tiếp tục
Kết thúc
Giảm rt[shortest] đi 1
Gán minm = rt[shortest]
NẾU minm == 0 thì,
Gán minm = INT_MAX
Kết thúc
NẾU rt[shortest] == 0 thì,
Tăng complete lên 1
Gán check = false
Gán finish_time = t + 1
Gán wt[shortest] = finish_time - proc[shortest].bt - proc[shortest].art
NẾU wt[shortest] < 0
Gán wt[shortest] = 0
Kết thúc
Tăng t lên 1
Bước 4 -> Trong hàm findavgTime(Process proc[], int n)
Khai báo và gán wt[n], tat[n], total_wt = 0, total_tat = 0
Gọi findWaitingTime(proc, n, wt)
Gọi findTurnAroundTime(proc, n, wt, tat)
Vòng lặp Với i = 0 đến i < n và i++
Gán total_wt = total_wt + wt[i]
Gán total_tat = total_tat + tat[i]
In proc[i].pid, proc[i].bt, wt[i], tat[i]
In thời gian chờ trung bình: total_wt / n
In thời gian vòng tròn trung bình: total_tat / n
Bước 5 -> Trong hàm int main()
Khai báo và gán Process proc[] = {{1, 5, 1}, {2, 3, 1}, {3, 6, 2}, {4, 5, 3}}
Gán n = sizeof(proc) / sizeof(proc[0])
Gọi findavgTime(proc, n)
Kết thúc
Ví dụ mã C++
#include <bits/stdc++.h>
using namespace std;
// Cấu trúc cho mỗi tiến trình
struct Process {
int pid; // ID tiến trình
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];
}
// Thời gian chờ của tất cả tiến trình
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;
}
// giảm thời gian còn lại
rt[shortest]--;
minm = rt[shortest];
if (minm == 0)
minm = INT_MAX;
// Nếu tiến trình hoàn thành hoàn toàn
if (rt[shortest] == 0) {
complete++;
check = false;
finish_time = t + 1;
// Tính thời gian chờ
wt[shortest] = finish_time - proc[shortest].bt - proc[shortest].art;
if (wt[shortest] < 0)
wt[shortest] = 0;
}
// Tăng thời gian
t++;
}
}
// Hàm tính thời gian trung bình
void findavgTime(Process proc[], int n) {
int wt[n], tat[n], total_wt = 0, total_tat = 0;
// Tìm thời gian chờ của tất cả tiến trình
findWaitingTime(proc, n, wt);
// Tìm thời gian vòng tròn cho tất cả tiến trình
findTurnAroundTime(proc, n, wt, tat);
cout << "Tiến trình " << " 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 << "\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;
}
// Hàm main
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;
}
Đầu ra
