Đã 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 ư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 ngắn nhất Đầu tiên được 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.
Thuật toán SJF có thể ưu tiên cũng như không ưu tiên. Lập lịch trước còn được gọi là thời gian ngắn nhất còn lại trước tiên lập kế hoạch. Trong cách tiếp cận Preemptive, quy trình mới phát sinh khi đã có quy trình đang thực thi. Nếu thời gian liên tục của quá trình mới đến ít hơn thời gian liên tục của quá trình thực thi thì bộ lập lịch sẽ bắt trước việc thực hiện quá trình với thời gian liên tục nhỏ hơn.
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 xoay vòng là khoảng thời gian giữa quá trình gửi đến khi hoàn thà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
| Quy trình | Thời gian nổ | Giờ đến |
|---|---|---|
| P1 | 4 | 0 |
| P2 | 2 | 1 |
| P3 | 8 | 2 |
| P4 | 1 | 3 |
| P5 | 9 | 4 |
Vì thời gian đến của P1 là 0 nên nó sẽ là thời điểm đầu tiên được thực thi cho đến khi xuất hiện một quá trình khác. Khi ở 1, quá trình P2 đi vào và thời gian bùng nổ của P2 nhỏ hơn thời gian bùng nổ của P1, do đó bộ lập lịch sẽ điều khiển CPU theo quá trình P2, v.v.
Thời gian chờ đợi trung bình được tính trên cơ sở biểu đồ gantt. P1 phải đợi (0 + 4) 4, P2 phải đợi 1, P3 phải đợi 7, P4 phải đợi 3 và P5 phải đợi 15. Vì vậy, thời gian chờ trung bình của họ sẽ là -
Thuật toán
Start
Step 1-> Declare a struct Process
Declare pid, bt, art
Step 2-> In function findTurnAroundTime(Process proc[], int n, int wt[], int tat[])
Loop For i = 0 and i < n and i++
Set tat[i] = proc[i].bt + wt[i]
Step 3-> In function findWaitingTime(Process proc[], int n, int wt[])
Declare rt[n]
Loop For i = 0 and i < n and i++
Set rt[i] = proc[i].bt
Set complete = 0, t = 0, minm = INT_MAX
Set shortest = 0, finish_time
Set bool check = false
Loop While (complete != n)
Loop For j = 0 and j < n and j++
If (proc[j].art <= t) && (rt[j] < minm) && rt[j] > 0 then,
Set minm = rt[j]
Set shortest = j
Set check = true
If check == false then,
Increment t by 1
Continue
Decrement the value of rt[shortest] by 1
Set minm = rt[shortest]
If minm == 0 then,
Set minm = INT_MAX
If rt[shortest] == 0 then,
Increment complete by 1
Set check = false
Set finish_time = t + 1
Set wt[shortest] = finish_time - proc[shortest].bt -proc[shortest].art
If wt[shortest] < 0
Set wt[shortest] = 0
Increment t by 1
Step 4-> In function findavgTime(Process proc[], int n)
Declare and set wt[n], tat[n], total_wt = 0, total_tat = 0
Call findWaitingTime(proc, n, wt)
Call findTurnAroundTime(proc, n, wt, tat)
Loop For i = 0 and i < n and i++
Set total_wt = total_wt + wt[i]
Set total_tat = total_tat + tat[i]
Print proc[i].pid, proc[i].bt, wt[i], tat[i]
Print Average waiting time i.e., total_wt / n
Print Average turn around time i.e., total_tat / n
Step 5-> In function int main()
Declare and set Process proc[] = { { 1, 5, 1 }, { 2, 3, 1 }, { 3, 6, 2 }, { 4, 5, 3 } }
Set n = sizeof(proc) / sizeof(proc[0])
Call findavgTime(proc, n)
Stop Ví dụ
#include <bits/stdc++.h>
using namespace std;
//structure for every process
struct Process {
int pid; // Process ID
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];
}
//waiting time of all process
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;
}
// decrementing the remaining time
rt[shortest]--;
minm = rt[shortest];
if (minm == 0)
minm = INT_MAX;
// If a process gets completely
// executed
if (rt[shortest] == 0) {
complete++;
check = false;
finish_time = t + 1;
// Calculate waiting time
wt[shortest] = finish_time -
proc[shortest].bt -
proc[shortest].art;
if (wt[shortest] < 0)
wt[shortest] = 0;
}
// Increment time
t++;
}
}
// Function to calculate average time
void findavgTime(Process proc[], int n) {
int wt[n], tat[n], total_wt = 0,
total_tat = 0;
// Function to find waiting time of all
// processes
findWaitingTime(proc, n, wt);
// Function to find turn around time for
// all processes
findTurnAroundTime(proc, n, wt, tat);
cout << "Processes " << " 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 << "\nAverage waiting time = " << (float)total_wt / (float)n; cout << "\nAverage turn around time = " << (float)total_tat / (float)n;
}
// main function
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
