โปรแกรม C++ สำหรับการจัดลำดับความสำคัญ

เราได้รับจำนวน n กระบวนการ เช่น P1, P2, P3,.......,Pn ที่มีเวลาระเบิดและลำดับความสำคัญที่เกี่ยวข้องกันในแต่ละกระบวนการ ภารกิจคือการค้นหาเวลารอโดยเฉลี่ย เวลาตอบสนองโดยเฉลี่ย และลำดับของการดำเนินการตามกระบวนการโดยใช้อัลกอริธึมการจัดกำหนดการ CPU ที่มีลำดับความสำคัญ

เวลารอและเวลาตอบสนองคืออะไร

เวลาตอบสนอง คือช่วงเวลาระหว่างการส่งกระบวนการและเสร็จสิ้น

เวลาดำเนินการ =เสร็จสิ้นกระบวนการ – การส่งกระบวนการ

เวลารอคอย คือความแตกต่างระหว่างเวลาตอบสนองกับเวลาที่ระเบิด

เวลารอ =เวลาตอบสนอง – เวลาที่ระเบิด

การจัดกำหนดการลำดับความสำคัญคืออะไร

ในการจัดกำหนดการลำดับความสำคัญ ทุกกระบวนการเชื่อมโยงกับลำดับความสำคัญตั้งแต่ 0-10 โดยที่จำนวนเต็ม 0 แสดงถึงลำดับความสำคัญต่ำสุด และ 10 แสดงถึงลำดับความสำคัญสูงสุด สามารถกำหนดลำดับความสำคัญได้สองวิธี ได้แก่ ภายในและภายนอก นอกจากนี้ การจัดกำหนดการลำดับความสำคัญอาจเป็นแบบชั่วคราวหรือแบบไม่ใช้ตัวเลือกก็ได้

ใน การจัดกำหนดการลำดับความสำคัญเชิงป้องกัน ตัวกำหนดตารางเวลาจะยึด CPU หากลำดับความสำคัญของกระบวนการที่มาถึงใหม่สูงกว่าลำดับความสำคัญของกระบวนการที่กำลังดำเนินการ

ในการจัดกำหนดการลำดับความสำคัญแบบไม่ยึดหน่วง ตัวกำหนดตารางเวลาจะจัดคิวกระบวนการใหม่ที่ส่วนหัวของคิวที่พร้อม

ข้อเสียของการใช้อัลกอริทึมการจัดลำดับความสำคัญ คือการปิดกั้นหรืออดอาหารอย่างไม่มีกำหนด จะมีกระบวนการที่มีลำดับความสำคัญต่ำซึ่งอาจต้องรอทรัพยากรอย่างไม่มีกำหนด เนื่องจากกระบวนการที่มีลำดับความสำคัญสูงซึ่งจะนำไปสู่ปัญหาความอดอยาก

ตัวอย่าง

สมมติว่ามี 4 กระบวนการ P1, P2, P3 และ P4 ที่มีเวลาต่อเนื่องเป็นชุดและลำดับความสำคัญที่เกี่ยวข้องกับแต่ละกระบวนการ โดยที่ 0 หมายถึงลำดับความสำคัญต่ำสุด และ 10 หมายถึงลำดับความสำคัญสูงสุด

ลำดับของการดำเนินการหลายกระบวนการจะแสดงโดยใช้แผนภูมิแกนต์ด้านล่าง

อัลกอริทึม

Start
Step 1-> Make a structure Process with variables pid, bt, priority
Step 2-> In function bool compare(Process a, Process b)
   Return (a.priority > b.priority)
Step 3-> In function waitingtime(Process pro[], int n, int wt[])
   Set wt[0] = 0
   Loop For i = 1 and i < n and i++
      Set wt[i] = pro[i-1].bt + wt[i-1]
   End
Step 4-> In function turnarround( Process pro[], int n, int wt[], int tat[])
   Loop For i = 0 and i < n and i++
      Set tat[i] = pro[i].bt + wt[i]
   End Loop
Step 5-> In function avgtime(Process pro[], int n)
   Declare and initialize wt[n], tat[n], total_wt = 0, total_tat = 0
   Call function waitingtime(pro, n, wt)
   Call function turnarround(pro, n, wt, tat)
   Print “Processes, Burst time, Waiting time, Turn around time"
   Loop For i=0 and i<n and i++
      Set total_wt = total_wt + wt[i]
      total_tat = total_tat + tat[i]
   End Loop
   Print values of “Processes, Burst time, Waiting time, Turn around time"
   Print Average waiting time, Average turn around time
Step 6-> In function scheduling(Process pro[], int n)
   Call function sort(pro, pro + n, compare)
   Loop For i = 0 and i < n and i++
      Print the order.
   End Loop
   Call function avgtime(pro, n)
Step 7-> In function int main()
   Declare and initialize Process pro[] = {{1, 10, 2}, {2, 5, 0}, {3, 8, 1}}
   Declare and initialize n = sizeof pro / sizeof pro[0]
   Call function scheduling(pro, n)
Stop

ตัวอย่าง

#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
};
// sorting the Process acc. to the priority
bool compare(Process a, Process b) {
   return (a.priority > b.priority);
}
void waitingtime(Process pro[], int n, int wt[]) {
   // Initial waiting time for a process is 0
   wt[0] = 0;
   // calculating waiting time
   for (int i = 1; i < n ; i++ )
      wt[i] = pro[i-1].bt + wt[i-1] ;
}
 // Function to calculate turn around time
void turnarround( Process pro[], int n, int wt[], int tat[]) {
   // calculating turnaround time by adding
   // bt[i] + wt[i]
   for (int i = 0; i < n ; i++)
      tat[i] = pro[i].bt + wt[i];
}
//Function to calculate average time
void avgtime(Process pro[], int n) {
   int wt[n], tat[n], total_wt = 0, total_tat = 0;
   //Function to find waiting time of all processes
   waitingtime(pro, n, wt);
   //Function to find turn around time for all processes
   turnarround(pro, n, wt, tat);
   //Display processes along with all details
   cout << "\nProcesses "<< " Burst time " << " Waiting time " << " Turn around 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];
      cout << " " << pro[i].pid << "\t\t" << pro[i].bt << "\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;
}
void scheduling(Process pro[], int n) {
   // Sort processes by priority
   sort(pro, pro + n, compare);
   cout<< "Order in which processes gets executed \n";
   for (int i = 0 ; i < n; i++)
      cout << pro[i].pid <<" " ;
   avgtime(pro, n);
}
// main function
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;
}

ผลลัพธ์

Order in which processes gets executed
1 3 2
Processes  Burst time  Waiting time  Turn around time
 1              10         0              10
 3              8          10             18
 2              5          18             23
 
Average waiting time = 9.33333
Average turn around time = 17