Chúng tôi được cung cấp n quy trình với thời gian bùng nổ và lượng tử thời gian tương ứng của chúng và nhiệm vụ là tìm thời gian chờ trung bình và thời gian quay vòng trung bình và hiển thị kết quả.
Lập lịch Round Robin là gì?
Round robin là một thuật toán lập lịch CPU được thiết kế đặc biệt cho các hệ thống chia sẻ thời gian. Nó giống như một thuật toán lập lịch FCFS với một thay đổi là trong các quy trình Round Robin được giới hạn với kích thước thời gian lượng tử. Một đơn vị thời gian nhỏ được gọi là Lượng tử thời gian hoặc Lát thời gian. Lượng tử thời gian có thể nằm trong khoảng từ 10 đến 100 mili giây. CPU coi hàng đợi sẵn sàng như một hàng đợi tròn để thực hiện các quy trình với thời gian nhất định. Nó tuân theo cách tiếp cận phủ đầu vì thời gian cố định được phân bổ cho các quy trình. Nhược điểm duy nhất của nó là chi phí chuyển đổi ngữ cảnh.
Chúng tôi cần tính toán những 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 3 quy trình P1, P2 và P3 với thời gian bùng nổ tương ứng của chúng là 24, 3 và 3
| Quy trình | Thời gian nổ |
|---|---|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
Vì lượng tử thời gian là 4 mili giây, nên quy trình P1 nhận 4 mili giây đầu tiên nhưng nó cần 20 mili giây nữa để hoàn thành quá trình thực thi nhưng CPU sẽ xử lý nó sau lần lượng tử đầu tiên và CPU sẽ được phân bổ cho quy trình tiếp theo P2. Như được hiển thị trong bảng, Quy trình P2 chỉ cần 3 mili giây để hoàn thành quá trình thực thi của nó, do đó CPU sẽ được phân bổ cho lượng tử thời gian chỉ là 3 mili giây thay vì 4 mili giây.
Sử dụng biểu đồ Gantt, thời gian chờ trung bình được tính như dưới đây -
Thời gian chờ trung bình =17/3 =5,66 mili giây
Thuật toán
Start
Step 1-> In function int turnarroundtime(int processes[], int n, int bt[], int wt[], int tat[])
Loop For i = 0 and i < n and i++
Set tat[i] = bt[i] + wt[i]
return 1
Step 2-> In function int waitingtime(int processes[], int n, int bt[], int wt[], int quantum)
Declare rem_bt[n]
Loop For i = 0 and i < n and i++
Set rem_bt[i] = bt[i]
Set t = 0
Loop While (1)
Set done = true
Loop For i = 0 and i < n and i++
If rem_bt[i] > 0 then,
Set done = false
If rem_bt[i] > quantum then,
Set t = t + quantum
Set rem_bt[i] = rem_bt[i] - quantum
Else
Set t = t + rem_bt[i]
Set wt[i] = t - bt[i]
Set rem_bt[i] = 0
If done == true then,
Break
Step 3->In function int findavgTime(int processes[], int n, int bt[], int quantum)
Declare and initialize wt[n], tat[n], total_wt = 0, total_tat = 0
Call function waitingtime(processes, n, bt, wt, quantum)
Call function turnarroundtime(processes, n, bt, wt, tat)
Print "Processes Burst Time Waiting Time turnaround time "
Loop For i=0 and i<n and i++
Set total_wt = total_wt + wt[i]
Set total_tat = total_tat + tat[i]
Print the value i+1, bt[i], wt[i], tat[i]
Print "Average waiting time = total_wt / n
Print "Average turnaround time =total_tat / n
Step 4-> In function int main()
Delcare and initialize processes[] = { 1, 2, 3}
Declare and initialize n = sizeof processes / sizeof processes[0]
Declare and initialize burst_time[] = {8, 6, 12}
Set quantum = 2
Call function findavgTime(processes, n, burst_time, quantum) Ví dụ
#include <stdio.h>
// Function to calculate turn around time
int turnarroundtime(int processes[], int n,
int bt[], int wt[], int tat[]) {
// calculating turnaround time by adding
// bt[i] + wt[i]
for (int i = 0; i < n ; i++)
tat[i] = bt[i] + wt[i];
return 1;
}
// Function to find the waiting time for all
// processes
int waitingtime(int processes[], int n,
int bt[], int wt[], int quantum) {
// Make a copy of burst times bt[] to store remaining
// burst times.
int rem_bt[n];
for (int i = 0 ; i < n ; i++)
rem_bt[i] = bt[i];
int t = 0; // Current time
// Keep traversing processes in round robin manner
// until all of them are not done.
while (1) {
bool done = true;
// Traverse all processes one by one repeatedly
for (int i = 0 ; i < n; i++) {
// If burst time of a process is greater than 0
// then only need to process further
if (rem_bt[i] > 0) {
done = false; // There is a pending process
if (rem_bt[i] > quantum) {
// Increase the value of t i.e. shows
// how much time a process has been processed
t += quantum;
// Decrease the burst_time of current process
// by quantum
rem_bt[i] -= quantum;
}
// If burst time is smaller than or equal to
// quantum. Last cycle for this process
else {
// Increase the value of t i.e. shows
// how much time a process has been processed
t = t + rem_bt[i];
// Waiting time is current time minus time
// used by this process
wt[i] = t - bt[i];
// As the process gets fully executed
// make its remaining burst time = 0
rem_bt[i] = 0;
}
}
}
// If all processes are done
if (done == true)
break;
}
return 1;
}
// Function to calculate average time
int findavgTime(int processes[], int n, int bt[],
int quantum) {
int wt[n], tat[n], total_wt = 0, total_tat = 0;
// Function to find waiting time of all processes
waitingtime(processes, n, bt, wt, quantum);
// Function to find turn around time for all processes
turnarroundtime(processes, n, bt, wt, tat);
// Display processes along with all details
printf("Processes Burst Time Waiting Time turnaround time\n");
// Calculate total waiting time and total turn
// around time
for (int i=0; i<n; i++) {
total_wt = total_wt + wt[i];
total_tat = total_tat + tat[i];
printf("\t%d\t\t\t%d\t\t\t%d\t\t\t%d\n",i+1, bt[i], wt[i], tat[i]);
}
printf("Average waiting time = %f", (float)total_wt / (float)n);
printf("\nAverage turnaround time = %f\n", (float)total_tat / (float)n);
return 1;
}
// main function
int main() {
// process id's
int processes[] = { 1, 2, 3};
int n = sizeof processes / sizeof processes[0];
// Burst time of all processes
int burst_time[] = {8, 6, 12};
// Time quantum
int quantum = 2;
findavgTime(processes, n, burst_time, quantum);
return 0;
} Đầu ra
