เราได้รับกับกระบวนการ n ที่มีเวลาระเบิดและควอนตัมเวลาที่สอดคล้องกัน และภารกิจคือการค้นหาเวลารอโดยเฉลี่ยและเวลาตอบสนองโดยเฉลี่ยและแสดงผล
การจัดกำหนดการ Round Robin คืออะไร
Round robin เป็นอัลกอริธึมการตั้งเวลา CPU ที่ออกแบบมาโดยเฉพาะสำหรับระบบการแบ่งปันเวลา มันเหมือนกับอัลกอริธึมการตั้งเวลา FCFS ที่มีการเปลี่ยนแปลงหนึ่งครั้งซึ่งในกระบวนการ Round Robin นั้นถูกจำกัดด้วยขนาดเวลาควอนตัม หน่วยเวลาเล็ก ๆ เรียกว่า Time Quantum หรือ Time Slice ควอนตัมเวลาสามารถอยู่ในช่วงตั้งแต่ 10 ถึง 100 มิลลิวินาที CPU ปฏิบัติต่อคิวที่พร้อมเป็นคิวแบบวงกลมสำหรับดำเนินการกระบวนการด้วยการแบ่งเวลาที่กำหนด เป็นไปตามแนวทางยึดเอาเสียก่อนเนื่องจากมีการจัดสรรเวลาคงที่ให้กับกระบวนการ ข้อเสียเพียงอย่างเดียวของมันคือค่าใช้จ่ายในการเปลี่ยนบริบท
เราต้องคำนวณอะไร
เวลาเสร็จสิ้น เป็นเวลาที่กระบวนการต้องใช้เพื่อให้การดำเนินการเสร็จสิ้น
เวลาตอบสนอง คือช่วงเวลาระหว่างการส่งกระบวนการและเสร็จสิ้น
เวลาดำเนินการ =เสร็จสิ้นกระบวนการ – การส่งกระบวนการ
เวลารอคือความแตกต่างระหว่างเวลาตอบสนองกับเวลาที่ระเบิด
เวลารอ =เวลาตอบสนอง – เวลาที่ระเบิด
ตัวอย่าง
เราได้รับ 3 กระบวนการ P1, P2 และ P3 โดยมีเวลาระเบิดที่สอดคล้องกันเป็น 24, 3 และ 3
| กระบวนการ | เวลาระเบิด |
|---|---|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
เนื่องจากเวลาควอนตัมคือ 4 มิลลิวินาที กระบวนการ P1 จะได้รับ 4 มิลลิวินาทีแรก แต่ต้องใช้เวลาอีก 20 มิลลิวินาทีในการดำเนินการให้เสร็จสิ้น แต่ CPU จะยึดไว้ก่อนหลังจากควอนตัมครั้งแรก และ CPU จะถูกจัดสรรให้กับกระบวนการ P2 ถัดไป ตามที่แสดงในตาราง กระบวนการ P2 ใช้เวลาเพียง 3 มิลลิวินาทีในการดำเนินการให้เสร็จสิ้น ดังนั้น CPU จะถูกจัดสรรสำหรับควอนตัมเวลา 3 มิลลิวินาทีเท่านั้นแทนที่จะเป็น 4 มิลลิวินาที
ใช้แผนภูมิแกนต์ เวลารอเฉลี่ยคำนวณตามที่ระบุด้านล่าง -
เวลารอเฉลี่ย =17/3 =5.66 มิลลิวินาที
อัลกอริทึม
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) ตัวอย่าง
#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;
} ผลลัพธ์
